Linux中的进程管理

摘自：Linux内核设计与实现

进程是运行中的程序以及与该运行程序相关的资源的总合

Linux对线程和进程并不特别区分，对于Linux而言，线程只是一种特殊的进程罢了

进程描述符及其任务结构

任务队列与task_struct: Linux中的进程又叫做任务，内核把进程列表放在叫做**任务队列(task list)的双向循环链表中，链表中的每一项都是task_struct，称为进程描述符(process descriptor)**，其包含的数据能够完整地描述一个正在执行的程序：打开的文件，进程的地址空间，挂起的信号，进程的状态等等

1
2
3
4
5
6
7
8
9
10
11
struct task_struct {
    unsigned long state;
    int prio;
    unsigned long policy;
    struct task struct *parent; // 当前进程的父进程
    struct list_head tasks; // 当前进程的子进程链表
    pid_t pid;
    // 链表中的下一节点
    // 链表中的前一节点
    ...
}

thread_info: Linux通过slab分配器分配task_struct结构，这样能达到对象复用和缓存着色（cache coloring）的目的。由于现在用slab分配器动态生成task_struct，所以只需在栈底（对于向下增长的栈来说）或栈顶（对于向上增长的栈来说）创建一个新的结构 struct thread_info。thread_info中有一个指向tast_struct（进程描述符）的指针。

1
2
3
4
5
6
7
8
9
10
11
12
struct thread_info {
    struct task_struct *task;
    struct exec domain *exec domain;
    _u32 flags;
    _u32 status;
    _u32 cpu;
    int preempt_count;
    mm_segment_t addr_limit;
    struct restart block restart block;
    void *sysenter_return;
    int uaccess_err;
};

PID: 内核通过一个唯一的进程标识值PID来标识每个进程。PID是一个数，实际上就是一个int类型。为了与老版本的Unix和Linux兼容，PID的最大值默认设置为32768（short int短整型的最大值），尽管这个值也可以增加到高达400万（这受<linux/threads.h>中所定义PID最大值的限制）。内核把每个进程的PID存放在它们各自的进程描述符中。

进程状态：

  • TASK_RUNNING（运行）——进程是可执行的；它或者正在执行，或者在运行队列中等待执行。这是进程在用户空间中执行的唯一可能的状态；这种状态也可以应用到内核空间中正在执行的进程。
  • TASK_INTERRUPTIBLE（可中断）——进程正在睡眠（也就是说它被阻塞），等待某些条件的达成。一旦这些条件达成，内核就会把进程状态设置为运行。处于此状态的进程也会因为接收到信号而提前被唤醒并随时准备投入运行。
  • TASK_UNINTERRUPTIBLE（不可中断）——除了就算是接收到信号也不会被唤醒或准备投入运行外，这个状态与可打断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于处于此状态的任务对信号不做响应，所以较之可中断状态，使用得较少。
  • _TASK_TRACED——被其他进程跟踪的进程，例如通过ptrace对调试程序进行跟踪。
  • _TASK_STOPPED（停止）——进程停止执行；进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP、SIGTSTP、SIGTTIN、SIGTTOU等信号的时候。此外，在调试期间接收到任何信号，都会使进程进入这种状态。

进程创建

  • 写时拷贝
  • fork
  • vfork

进程终结

在调用了do_exit()之后，尽管线程已经僵死不能再运行了，但是系统还保留了它的进程描述符

wait()这一族函数都是通过唯一的一个系统调用wait4()来实现的。它的标准动作是挂起调用它的进程，直到其中的一个子进程退出，此时函数会返回该子进程的PID。此外，调用该函数时提供的指针会包含子函数退出时的退出代码。

当最终需要释放进程描述符时，release_task()会被调用，release_task()调用put_task_struct()释放进程内核栈和thread_info结构所占的页，并释放tast_struct所占的slab高速缓存。

Linux中的进程调度

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序（常常简称调度程序）可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。绝大多数操作系统都是采取抢占式的多任务模式。

O1已经是上一代调度器了，由于其对多核、多CPU系统的支持性能并不好，并且内核功能上要加入cgroup等因素，Linux在2.6.23之后开始启用CFS作为对一般优先级(SCHED_OTHER)进程调度方法。

Linux实现了CFS(完全公平调度)，CPU提供的时钟tick，为每一个进程安排一个vruntime，运行得越久，vruntime越大，没有得到执行的进程vruntime很小，所以让CPU去执行vuntime很小的进程。时间片，动态、静态优先级以及IO消耗，CPU消耗的概念都不再重要。优先级是以时间消耗(vruntime增长)的快慢来决定的。vruntime用红黑树存储，平衡了查询与更新的时间。Linux独一无二的公平调度程序并没有采取时间片来达到公平调度。

进程优先级NI和PR

NICE值反应一个进程优先级状态的值，其取值范围是-20至19，一共40个级别。这个值越小，表示进程”优先级”越高，而值越大“优先级”越低。nice值虽然不是priority，但是它确实可以影响进程的优先级。它是静态优先级。形象解释：越nice的人抢占资源的能力就越差，而越不nice的人抢占能力就越强。这就是nice值大小的含义，nice值越低，说明进程越不nice，抢占cpu的能力就越强，优先级就越高。nice值在SCHED_NORMAL（普通的、非实时的）有意义

priority的值在之前内核的O1调度器（Linux2.6之后内核调度算法替换为了CFS）上表现是会变化的，所以也叫做动态优先级，priority范围从0到MAX_RT_PRIO减1。默认情况下，MAX_RT_PRIO为100——所以默认的实时优先级范围是从0到99。SCHED_NORMAL级进程的nice值共享了这个取值空间；它的取值范围是从MAX_RT_PRIO到（MAX_RT_PRIO+40）。也就是说，在默认情况下，nice值从-20到+19直接对应的是从100到139的实时优先级范围。priority在两种实时调度策略：SCHED_FIFO和SCHED_RR中有意义

时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片，但这并不是件简单的事。时间片过长会导致系统对交互的响应表现欠佳；时间片太短会明显增大进程切换带来的处理器耗时

此外，I/O消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来：I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如这样可以让它们的高速缓存命中率更高）。

任何长时间片都将导致系统交互表现欠佳，所以默认的时间片很短，如10ms。但是Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的。这个比例进一步还会受进程nice值的影响，nice值作为权重将调整进程所使用的处理器时间使用比。具有更高nice值（更低优先权）的进程将被赋予低权重，从而丧失一小部分的处理器使用比；而具有更小nice值（更高优先级）的进程则会被赋予高权重，从而抢得更多的处理器使用比。

像前面所说的，Linux系统是抢占式的。当一个进程进入可运行态，它就被准许投入运行。在多数操作系统中，是否要将一个进程立刻投入运行（也就是抢占当前进程），是完全由进程优先级和是否有时间片决定的。而在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则，将推迟其运行。

Unix的进程调度

在Unix系统上，优先级以nice值形式输出给用户空间。这点听起来简单，但是在现实中，却会导致许多反常的问题，我们下面具体讨论。

  • nice单位值要对应到处理器的绝对时间，这会导致进程切换无法最优化进行，比如nice=0分配100ms，nice=20分配5ms，假设只有两个nice=20的进程，他们各自运行5ms就要换位
  • 相对nice值的问题，假设nice=0分配100ms，nice=1分配95ms，它们的差距只差5%，但如果nice=18分配10ms，nice=19分配5ms，它们差距100%
  • 时间片得是定时器节拍的整数倍，而且时间片还会随着定时器节拍改变
  • 为了优化交互任务而唤醒相关进程，得提升待唤醒进程的优先级，即便它们的时间片已用尽，但这会打破公平原则

上述问题中的绝大多数都可以通过对传统Unix调度器进行改造解决，虽然这种改造修改不小，但也并非是结构性调整。比如，将nice值呈几何增加而非算数增加的方式解决第二个问题；采用一个新的度量机制将从nice值到时间片的映射与定时器节拍分离开来，以此解决第三个问题。但是这些解决方案都回避了实质问题——即分配绝对的时间片引发的固定的切换频率，给公平性造成了很大变数。CFS采用的方法是对时间片分配方式进行根本性的重新设计（就进程调度器而言）：完全摒弃时间片而是分配给进程一个处理器使用比重。通过这种方式，CFS确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。

CFS

完全公平调度（CFS）是一个针对普通进程的调度类，在Linux中称为SCHED_NORMAL

CFS的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程将能获得1/n的处理器时间——n是指可运行进程的数量。

CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值（越低的优先级）进程获得更低的处理器使用权重，更低的nice值（越高的优先级）的讲程获得更高的处理器使用权重。

每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行，为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标称作“目标延迟”，越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统总吞吐能力。

总结一下，任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS称为公平调度器是因为它确保给每个进程公平的处理器使用比。正如我们知道的，CFS不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下，降低了调度延迟带来的不公平性。

CFS不再有时间片的概念，但是它也必须维护每个进程运行的时间记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。CFS使用调度器实体结构（定义在文件<linux/sched.h>的struct_sched_entity中）来追踪进程运行记账，sched_entity作为一个名为se的成员变量，嵌入在进程描述符struct task_struct中

vruntime变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算是经过了所有可运行进程总数的标准化（或者说是被加权的）。虚拟时间是以ns为单位的，所以vruntime和定时器节拍不再相关。虚拟运行时间可以帮助我们逼近CFS模型所追求的“理想多任务处理器”。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

vruntime的更新：系统定时器周期性调用update_curr()函数来更新sched_enetity的vruntime，update_curr()计算了当前进程的执行时间，并且将其存放在变量delta_exec中。然后它又将运行时间传递给了__update_curr()，由后者再根据当前可运行进程总数对运行时间进行加权计算。最终将上述的权重值加在当前运行进程的vruntime上。

CFS调度算法的核心：选择具有最小vruntime的任务。而为了加速这个寻找最小vruntime的过程，CFS使用红黑树来组织所有可运行进程，在Linux中，红黑树简称rbtree，它是自平衡二叉搜索树，rbtree最左边叶子节点就是最小vruntime。在进程变为可运行状态（被唤醒）或者是通过fork()调用第一次创建进程时，CFS将进程加入rbtree；进程堵塞（变为不可运行态）或者终止时（结束运行）时，CFS将进程从rbtree中删除

实时调度策略

Linux 提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL（CFS使用）。

SCHED_FIFO实现了一种简单的、先入先出的调度算法：它不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止；它不基于时间片，可以一直执行下去。只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的同优先级的SCHED_FIFO级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器时才会退出。只要有SCHED_FIFO级进程在执行，其他级别较低的进程就只能等待它变为不可运行态后才有机会执行。

SCHED_RR是带有时间片的 SCHED_FIFO——这是一种实时轮流调度算法。当SCHED_RR任务耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度。对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程决不能抢占SCHED_RR任务，即使它的时间片耗尽。

这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。

调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，只要有可以执行的进程，那么就总会有进程正在执行。