一文读懂 Linux 内核进程调度原理

2022 年 4 月 09 日
本文字数：4195 字
阅读完需：约 14 分钟

前言;长期以来，Linux 一直把具有较好的平均系统响应时间和较高的吞吐量作为调度算法的主要目标。但近年来，鉴于嵌入式系统的要求，Linux2.6 在支持系统的实时性方面也做出了重大的改进。

【纯干货】耗时数月吐血大整理十万字《深入理解Linux内核》要点笔记总结(高级程序员必备)

【纯干货】耗时数月吐血大整理五十万字《Linux内核网络内幕》要点笔记总结(高级程序员必备)

【纯干货】耗时数月吐血大整理二十万字《Linux内核设备驱动开发》要点笔记总结(高级程序员必备)

一，Linux 进程时间片与权重参数

在处理器资源有限的系统中，所有进程都以轮流占用处理器的方式交叉运行。为使每个进程都有运行的机会，调度器为每个进程分配了一个占用处理器的时间额度，这个额度叫做进程的“时间片”，其初值就存放在进程控制块的 counter 域中。进程每占用处理器一次，系统就将这次所占用时间从 counter 中扣除，因为 counter 反映了进程时间片的剩余情况，所以叫做剩余时间片。

Linux 调度的主要思想为：调度器大致以所有进程时间片的总和为一个调度周期；在每个调度周期内可以发生若干次调度，每次调度时，所有进程都以 counter 为资本竞争处理器控制权，counter 值大者胜出，优先运行；凡是已耗尽时间片（即 counter=0）的，则立即退出本周期的竞争；当所有未被阻塞进程的时间片都耗尽，那就不等了。然后，由调度器重新为进程分配时间片，开始下一个调度周期。

Linux 基于时间片调度的基本思想如下图所示：

上面的调度方式主要体现的是一种公平性：如果一个进程的剩余时间片多，那么它在前期获得运行的时间片就少，为了公平性，就应该适当的赋予它更高的优先级。但是这仅仅是一个总体的原则，为了应付实际问题中的特殊状况，在上述平等原则的基础上，为了给特殊进程一些特殊照顾，在为进程分配时间片时，Linux 允许用户通过一个系统调用 nice()来设置参数 nice 影响进程的优先权。所以，系统真正用来确定进程的优先权时，使用的依据为权重参数 weight，weight 大的进程优先运行。

weight 与 nice、counter 之间的关系大体如下：

weight 正比于 [counter+(20-nice)]

关于三者之间的这个关系将会在后面的内容中详细的讲到。

因为 nice 是用户在创建进程时确定的，在进程的运行过程中一般不会改变，所以叫做静态优先级；counter 则随着进程时间片的小号在不断减小，是变化的，所以叫做动态优先级。

调度策略

目前，标准 Linux 系统支持非实时（普通）和实时两种进程。与此相对应的，Linux 有两种进程调度策略：普通进程调度和实时进程调度。因此，在每个进程的进程控制块中都有一个域 policy，用来指明该进程为何种进程，应该使用何种调度策略。

Linux 调度的总体思想是：实时进程优先于普通进程，实时进程以进程的紧急程度为优先顺序，并为实时进程赋予固定的优先级；普通进程则以保证所有进程能平均占用处理器时间为原则。所以其具体做法就是：对于实时进程来说，总的思想是为实时进程赋予远大于普通进程的固定权重参数 weight，以确保实时进程的优先级。在此基础上，还分为两种做法：一种与时间片无关，另一种与时间片有关；对于普通进程来说，原则上以相等的 weight 作为所有进程的初始权重值，即 nice=0，然后在每次进行进程调度时，根据剩余时间片对 weight 动态调整。

普通进程调度策略

如果进程控制块的 policy 的值为 SCHED_OTHER，则该进程为普通进程，适用于普通进程调度策略。

时间片的分配

当一个普通进程被创建时，系统会先为它分配一个默认的时间片（nice=0）。在 Linux2.4 内核中，进程的默认时间片时按照下面的算法来计算的：

#if HZ < 200#define TICK_SCALE(x)        ((x)>>2)#elif HZ < 400#define TICK_SCALE(x)        ((x)>>1)#elif HZ < 800#define TICK_SCALE(x)        (x)#elif HZ < 1600#define TICK_SCALE(x)        ((x)<<1)#dele#define TICK_SCALE(x)        ((x)<<2)#endif#define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1)......

复制代码

在每个调度周期之前，调度器为每个普通进程进程分配时间片的算法为：

p->counter = (p->counter>>1) + NICE_TO_TICKS(p->nice);

复制代码

其中，p 为进程控制块指针。这里为什么需要加上 p->counter>>1 呢？这会在本文后面的内容中讲到。例如，用户定义 HZ 为 100，而 counter 初值和 nice 的默认值为 0，于是可以计算出 counter 的值为 6 ticks（((20-0)>>2)+1），也就是说，进程时间片的默认值大概为 60ms（100Hz，10ms）。

weight 的微调函数 goodness()

尽管在默认情况下，系统为所有的进程都分配了相等的时间片，但在实际运行时，常常因各种原因使得进程的运行总是有先有后，于是经过一段时间运行后，在各进程之间就会产生事实上的不公平的现象，也就是各个进程在实际使用其时间片的方面形成了差异。剩余时间计数器 counter 的值就反映了这个差异的程度：该值大的，意味着这个进程占用处理器的时间少（吃亏了）；该值小的，意味着这个进程占用处理器的时间多（占便宜了）。

为了尽可能地缩小上述的这个差异，Linux 的调度器在调度周期中每次调度时，都遍历就绪列表中的所有进程，并按照各个进程的 counter 当前值调用函数 goodness()对所有进程的 weight 进行调整，想办法让 counter 值大的进程的 weight 大一些，而 counter 值小的进程的 weight 小一些。

函数 goodness()的主要代码如下：

/*返回值：        -1000：从不选择这个        0：过期进程，重新计算计数值（但它仍旧可能被选中）        正值：goodness值（越大越好）        +1000：实时进程，选择这个*/ static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm){     int weight;     weight = -1;      if (p->policy & SCHED_YIELD) //p->policy表示进程的调度策略，SCHED_YIELD是一种策略，不参与处理器的竞争！#define SCHED_YIELD          0x10          goto out;      //非实时进程     if (p->policy == SCHED_OTHER) {          weight = p->counter;                //weight的主要成分是counter          if (!weight)                        //如果时间片用尽               goto out;              #ifdef CONFIG_SMP          if (p->processor == this_cpu)               weight += PROC_CHANGE_PENALTY;#endif           if (p->mm == this_mm || !p->mm)               weight += 1;          weight += 20 - p->nice;            //nice越小，权值越大          goto out;     }      //实时进程     weight = 1000 + p->rt_priority;out:     return weight;}

复制代码

这个函数中就能看出：weight 正比于 [counter+(20-nice)]。

普通进程调度算法中的一些细节

当普通就绪队列中所有非等待进程 counter 值都减为 0 时，就在 schedule()中对每个进程利用下面的代码：

p->counter = (p->counter>>1) + NICE_TO_TICKS(p->nice);

复制代码

对所有的进程时间片 counter 重新赋值。在重新赋值时，对于耗尽时间片的进程，由于参与计算的 counter 等于 0，因此这个算法就是恢复 counter 的初值；而对于处于等待状态的进程，由于参与计算的 counter 大于 0，因此这个算法实际上就是把 counter 的剩余值折半再加上初值。也就是说，因等待而损失了时间片的进程在 counter 重新被赋值时，系统会适当地给它一些“照顾”，以使其在下一个调度周期中获得更多的时间片，并拥有更高的权重 weight。

一个进程的等待次数比较多，通常意味着它的 I/O 操作比较密集。通过对时间片进行叠加的做法给等待进程赋予更高的优先级，体现了 Linux 对 I/O 操作密集型进程的一种体贴。

可见，SCHED_OTHER 策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性：一个低优先级的进程在每一个周期中也会得到自己应得的那些运行时间；同时，它提供了 nice 使用户可以对进程优先级进行干预。

实时进程调度策略

凡是进程控制块的 policy 的值为 SCHED_FIFO 或 SCHED_RR 的进程，调度器都将其视为实时进程。

进程控制块中的域 rt_pripority 就是实时进程的优先级，其范围时 1~99。这一属性将在调度时用于对进程权重参数 weight 的计算。

从上面介绍的函数 goodness()代码中可以看到，计算实时进程 weight 的代码相当简单，即：

weight = 1000 + p->rt_priority;

复制代码

也就是说，Linux 是按照严格的优先级别来选择待运行进程的，并且实时进程的权重 weight 远高于普通进程。

普通进程参数 counter、nice，实时进程参数 rt_pripority，调度器调度依据的参数 weight 之间的关系如下图所示：

Linux 允许多个实时进程具有相同的一个优先级别，Linux 把所有的实时进程按照其优先级组织成若干个队列，对于同一队列的实时进程可以采用先来先服务和时间片轮转调度两种调度策略。

先来先服务调度（SCHED_FIFO）

该策略是符合 POSIX 标准的 FIFO（先入先出）调度规则。即在同一级别的队列中，先就绪的进程先入队，后就绪的进程后入队。调度器在选择运行进程时，就以优先级 rt_pripority 为序查询各个队列，当发现队列中有就绪进程时，就运行处于队列头位置的进程。其后，它就会一直运行，除非出现下述情况之一：

进程被具有更高优先级别进程剥夺了处理器；
进程自己因为请求资源而堵塞；
进程自己主动放弃处理器。

时间片轮转调度（SCHED_RR）

该策略时符合 POSIX 标准的 RR（循环 Round-Robin）调度规则。

这种策略与 SCHED_FIFI 类似，也根据优先级别把就绪进程分成若干个队列，但每个队列被组织成一个循环队列，并且每个进程都拥有一个时间片。调度时，调度器仍然以优先级别为序查询就绪进程对列。当发现就绪进程队列后，也是运行处在队列头部的进程，但是当这个进程将自己的时间片耗完之后，调度器把这个进程放到其队列的队尾，并且再选择处在队头的进程来运行，当然前提条件是这时没有更高优先级别的实时进程就绪。