Linux内核的进程和进程调度解析

1、进程相关概念

①进程基本概念

进程就是出于执行期的程序。但进程并不仅仅局限于一段可执行程序代码,通常进程还要包含其他资源,比如:打开的文件,挂起的信号,内核内部数据,处理器状态以及内存映射的地址空间、数据段等等。

②进程描述符

实际上Linux内核习惯把进程叫做任务。

内核把进程的列表存放在叫做任务队列(task list)的双向循环链表中。

链表的每一项就是类型为task_struct,也就是进程描述符的结构,就是操作系统原理中的PCB进程控制块。这个结构体定义在<linux/sched.h>文件中。进程描述符中包含一个具体进程的所有信息。这个结构体在32位机器上大约有1.7KB大小。考虑到能包含进程的所有数据也还算相当小了。它描述的有:它打开的文件,进程 的地址空间,挂起的信号,进程的状态等等。

进程描述符中的state域描述了进程的当前状态。系统的每个进程都必然出于五种进程状态的一种。

TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、_TASK_TRACED、_TASK_STOPPED

③进程描述符的分配

2.6以前的内核,各个进程的task_struct存放在他们内核栈的尾端,是为了让像x86那样寄存器较少的硬件体系结构只需要通过栈指针就能计算出他的位置,从而避免使用额外的寄存器专门记录。

2.6以后的内核通过使用slab分配器动态生成task_struct,(slab分配task_struct,能达到对象复用和缓存着色的目的,通过预先分配和重复使用task_struct,可以避免动态分配和释放所带来的资源消耗,这也是Linux进程创建迅速的一个特点的原因),所以只需要在栈底(对于向下增长的栈来说),或栈顶(对于向上增长的栈来说)创建一个新的结构体struct thread_info。

x86结构中的thread_info结构体如下:

struct thread_info {
    struct task_struct    *task;           /* main task structure */
    struct exec_domain    *exec_domain;    /* execution domain */
    __u32                 flags;                /* low level flags */
    __u32                 status;               /* thread synchronous flags */
    __u32                 cpu;                  /* current CPU */
    int                   preempt_count;          /* 0 => preemptable, <0 => BUG */
    mm_segment_t          addr_limit;
    struct restart_block  restart_block;
    void __user           *sysenter_return;
#ifdef CONFIG_X86_32
    unsigned long          previous_esp; /* ESP of the previous stack in
                                   case of nested (IRQ) stacks
                                   */
    __u8                   supervisor_stack[0];
#endif
    unsigned int           sig_on_uaccess_error:1;
    unsigned int           uaccess_err:1;    /* uaccess failed */
};

内核通过一个唯一的进程标识符PID来标识每个进程。

在内核中,访问任务通常需要过得指向其task_struct的指针。在内核中我们通过current宏老查找当前正在运行进程的进程描述符。硬件体系不同,实现也不一样。在x86系统上,current把栈指针的后13个有效位屏蔽掉,用来计算出thread_info的偏移。该操作是通过current_thread_info()函数实现的。汇编代码如下

movl $-8192, %eax
andl %esp  , %eax

该部分在PowerPC中实现就是保存在一个寄存器中,可以看出不同硬件体系实现不同

④进程创建

Unix的进程创建很特别。许多其他的操作系统都提供了产生( spawn)进程的机制,首先在新的地址空间里创建进程,读入可执行文件,最后开始执行。Unix采用了与众不同的实现方式,它把上述步骤分解到两个单独的函数中去执行: fork0和 exec()首先,fork通过拷贝当前进程创建一个子进程。子进程与父进程的区别仅仅在于PID(每个进程唯一)、PPID(父进程的进程号,子进程将其设置为被拷贝进程的PID)和某些资源和统计量(例如,挂起的信号,它没有必要被继承)。 exec函数负责读取可执行文件并将其载入地址空间开始运行。把这两个函数组合起来使用的效果跟其他系统使用的单一函数的效果相似。

写时拷贝

传统的fork系统调用直接把所有的资源复制给新创建的进程。这种实现过于简单并且效率低下,因为它拷贝的数据也许并不共享,更糟的情况是,如果新进程打算立即执行一个新的映像,那么所有的拷贝都将前功尽弃。Linux的 fork使用写时拷贝(copy-on--write)页实现。写时拷贝是一种可以推迟甚至免除拷贝数据的技术。内核此时并不复制整个进程地址空间,而是让父进程和子进程共享同一个拷贝。

只有在需要写入的时候,数据才会被复制,从而使各个进程拥有各自的拷贝。也就是说,资源的复制只有在需要写入的时候才进行,在此之前,只是以只读方式共享。这种技术使地址空间上的页的拷贝被推迟到实际发生写入的时候才进行。在页根本不会被写入的情况下(举例来说, fork()后立即调用exec())它们就无须复制了。
fork的实际开销就是复制父进程的页表以及给子进程创建唯一的进程描述符。在一般情况下,进程创建后都会马上运行一个可执行的文件,这种优化可以避免拷贝大量根本就不会被使用的数据(地址空间里常常包含数十兆的数据)。由于Unix强调进程快速执行的能力,所以这个优化是很重要的。

2、Linux系统中的线程

内核线程:

它的创建和撤消是由内核的内部需求来决定的,用来负责执行一个指定的函数,一个内核线程不需要

和一个用户进程联系起来。它共享内核的正文段核全局数据,具有自己的内核堆栈。它能够单独的被调度

并且使用标准的内核同步机制,可以被单独的分配到一个处理器上运行。内核线程的调度由于不需要经过

态的转换并进行地址空间的重新映射,因此在内核线程间做上下文切换比在进程间做上下文切换快得多。

轻量级进程:

clone()

轻量级进程是核心支持的用户线程,它在一个单独的进程中提供多线程控制。这些轻量级进程被单独

的调度,可以在多个处理器上运行,每一个轻量级进程都被绑定在一个内核线程上,而且在它的生命周期

这种绑定都是有效的。轻量级进程被独立调度并且共享地址空间和进程中的其它资源,但是每个LWP都应

该有自己的程序计数器、寄存器集合、核心栈和用户栈。

用户线程:

pthread_create

用户线程是通过线程库实现的。它们可以在没有内核参与下创建、释放和管理。线程库提供了同步和

调度的方法。这样进程可以使用大量的线程而不消耗内核资源,而且省去大量的系统开销。用户线程的实

现是可能的,因为用户线程的上下文可以在没有内核干预的情况下保存和恢复。每个用户线程都可以有自

己的用户堆栈,一块用来保存用户级寄存器上下文以及如信号屏蔽等状态信息的内存区。库通过保存当前

线程的堆栈和寄存器内容载入新调度线程的那些内容来实现用户线程之间的调度和上下文切换。

内核仍然负责进程的切换,因为只有内核具有修改内存管理寄存器的权力。用户线程不是真正的调度

实体,内核对它们一无所知,而只是调度用户线程下的进程或者轻量级进程,这些进程再通过线程库函数

来调度它们的线程。当一个进程被抢占时,它的所有用户线程都被抢占,当一个用户线程被阻塞时,它会

阻塞下面的轻量级进程,如果进程只有一个轻量级进程,则它的所有用户线程都会被阻塞。

3、进程调度(CFS)

在CFS调度器出现前,早期 Linux内核中曾经出现过两个调度器,分别是O(N)和O(1)调度器,O(N)调度器布于1992年,该调度器算法比较简洁,从就绪队列中比较所有进程的优先级,然后选择个最高优先级的进程作为下一个调度进程。每个进程有一个定时间片,当进程时间片目完之后,调度器会选择下一个调度进程,当所有进程都运行一遍后再重新分配时时间片这个调度器选择下一个调度进程前需要遍历整个就绪队列,花费O(N)时间

在 Linux2.6.23内核之前有一名为O(1)的调度器,优化了选择下一个进程的时间。它个CPU维护一组进程优先级队列,每个优先级一个队列。这样在选择下一个进程时,只需要查询优先级队列相应的位图即可知道哪个队列中有就绪队列,所以查询时间为常数O(1)。

目前Linux系统内部默认实现了4种调度策略,分别是deadline、realtime、CFS、idle。

内核使用0~139的数值表示进程的优先级,数值越低优先级越高。优先级0~99给实时进程使用,100~139给普通进程使用。在用户空间有一个传统的变量nice值映射到票融通进程的优先级,即100~139.

nice值的大小是从[-20,19),nice值越大表明,优先级越低,这是一个相反的,同理:nice值越小表明优先级越高

①vruntime(虚拟运行时间)

cfs定义了一种新的模型,它给cfs_rq(cfs的run queue)中的每一个进程安排一个虚拟时钟,vruntime。如果一个进程得以执行,随着时间的增长(也就是一个个tick的到来),其vruntime将不断增大。没有得到执行的进程vruntime不变。而调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同优先级的进程,优先级高的进程vruntime增长得慢,以至于它可能得到更多的运行机会。

vruntime的计算公式:vruntime= delta_exec * nice_0_weight / weihght

其中delta_exec 是实际运行时间,nice_0_weight 为1024,也就是nice值为0的权重值。weight是进程的权重值。

那么就可以用这个vruntime来选择运行的进程,谁的vruntime值较小就说明它以前占用cpu的时间较短,受到了“不公平”对待,因此下一个运行进程就是它。这样既能公平选择进程,又能保证高优先级进程获得较多的运行时间。这就是CFS的主要思想了。

Linux内核中有一个目标延迟的东西,就是类似于设置的所有进程轮番执行一遍所需要的时间,一般默认为20ms(可以更改)。同时Linux设置了每个进程获得的时间片底线,这个底线为最小粒度。默认情况下是1ms.

②进程调度(进程选择)

CFS使用红黑树来组织可运行进程队列,并利用其迅速找到最小vruntime值的进程。在Linux中,红黑树称为rbtree,它是-一个自平衡二叉搜索树。

我们先假设,有那么-一个红黑树存储了系统中所有的可运行进程,其中节点的键值便是可运行进程的虛拟运行时间。CFS调度器选取待运行的下-一个进程,是所有进程中vruntime最小的那个,它对应的便是在树中最左侧的叶子节点。也就是说,你从树的根节点沿着左边的子节点向下找,- - 直找到叶子节点,你便找到了其vruntime值最小的那个进程。如果不熟悉二叉搜索树,不用担心,只要知道它用来加速寻找过程即可。 CFS的进程选择算法可简单总结为“运行tbtree树中最左边叶子节点所代表的那个进程”。实现这一过程的函数是_ pick_ next entityO,它定义在文件kermnelsched fairc 中:

Last modification:May 18th, 2020 at 03:32 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

One comment

  1. hefh Google Chrome 78.0.3904.108 Windows 7 中国 广西 桂林

    免费试用单号网 免费快递单号网www.kuaidzj.com