Linux进程调度方法与实例

由前面的描述可知，Linux进程是抢占式的。被抢占的进程仍然处于TASK_RUNNING状态，只是暂时没有被CPU运行。进程的抢占发生在进程处于用户态执行阶段，在内核态执行时是不能被抢占的。为了能让进程有效地使用系统资源，又能使进程有较快的响应时间，就需要对进程的切换调度采用一定的调度策略。

1.调度方式

Linux中的每个进程都分配有一个相对独立的虚拟地址空间。该虚存空间分为两部分：用户空间包含了进程本身的代码和数据；内核空间包含了操作系统的代码和数据。

Linux采用“有条件的可剥夺”调度方式。对于普通进程，当其时间片结束时，调度程序挑选出下一个处于TASK_RUNNING状态的进程作为当前进程（自愿调度）。对于实时进程，若其优先级足够高，则会从当前的运行进程中抢占CPU成为新的当前进程（强制调度）。发生强制调度时，若进程在用户空间中运行，就会直接被剥夺CPU；若进程在内核空间中运行，即使迫切需要其放弃CPU，也仍要等到从系统空间返回的前夕才被剥夺CPU。

2.3种调度策略

1）SCHED_OTHER：这是普通的用户进程，是进程的默认类型。采用该策略时，系统为处于TASK_RUNNING状态的每个进程分配一个时间片。当时间片用完时，进程调度程序再选择下一个优先级相对较高的进程，并授予CPU使用权。

2）SCHED_FIFO：这是一种实时进程。采用该策略时，各实时进程按其进入可运行队列的顺序依次获得CPU。除了因等待某个事件主动放弃CPU，或者出现优先级更高的进程而剥夺其CPU之外，该进程将一直占用CPU运行。

3）SCHED_RR：这也是一种实时进程。采用该策略时，各实时进程按时间片轮流使用CPU。当一个运行进程的时间片用完后，进程调度程序停止其运行，并将其置于可运行队列的末尾。

3.进程调度信息

调度程序利用这部分信息决定系统中的哪个进程最应该运行，并结合进程的状态信息保证系统运转的公平和高效。这一部分信息通常包括进程的类别（是普通进程，还是实时进程）和进程的优先级等。进程调度信息见表9-2。

表9-2 进程调度信息

4.Linux进程描述符—task_struct结构

为了管理进程，操作系统必须对每个进程所做的事情进行清楚地描述。为此，操作系统使用数据结构来代表处理不同的实体，这个数据结构就是通常所说的进程描述符或进程控制块。在Linux系统中，这就是task_struct结构，在include\linux\sched.h文件中定义。每个进程都会被分配一个task_struct结构，它包含了这个进程的所有信息，在任何时候操作系统都能跟踪这个结构的信息，这个结构是Linux内核汇总最重要的数据结构。这个结构的部分源代码及其注释如下。

task_struct数据结构内部成员的关系如图9-5所示。

图9-5 task_struct数据结构内部成员的关系

内核函数goodness（）用来衡量一个处于可运行状态的进程值得运行的程度，该函数给每个处于可运行状态的进程赋予一个权值（Weight）。函数主体如下。(https://www.xing528.com)

从goodness（）函数可以看出，对于普通进程，其权值主要取决于剩余的时间配额和nice两个因素。nice的规定取值范围为19～-20，只有特权用户才能把nice值设为负数，而表达式（20-p->nice）的值为1～40。所以，综合的权值在时间片尚未用完时基本上是两者之和。如果是内核进程，或者其用户空间与当前进程相同，则权值将额外加1作为奖励。对于实时进程，其权值为1000+p->rt_priority。当p->counter达到0时，该进程将移到队列的尾部，但其优先级仍不少于1000。可见，当有实时进程就绪时，普通进程是没机会运行的。

由此可以看出，通过goodness（）函数，Linux从优先考虑实时进程出发，实现了多种调度策略的统一处理。

5.进程调度程序

Linux的进程调度由调度函数schedule（）完成。schedule（）函数首先扫描任务数组。通过比较每个就绪态（TASK_RUNNING）任务的运行时间递减计数counter的值来确定当前哪个进程运行的时间最少。哪一个的值大，就表示运行时间还不长，于是就选中该进程，并使用任务切换宏函数切换到该进程运行。

如果此时所有处于TASK_RUNNING状态进程的时间片都已经用完，系统就会根据每个进程的优先权值priority对系统中的所有进程（包括正在睡眠的进程）重新计算每个任务需要运行的时间片值counter。

然后，schedule（）函数重新扫描任务数组中所有处于TASK_RUNNING状态的进程。重复上述过程，直到选择出一个进程为止。最后调用switch_to（）执行实际的进程切换操作。如果此时没有其他进程可运行，系统就会选择进程0运行。

通过对schedule（）的分析能更好地理解调度的过程。schedule（）首先判断当前运行的进程是否具有SCHED_RR标志，本文取一部分加以分析：

prev->counter代表当前进程的运行时间配额，其值逐渐减小。一旦减至0，就要从可执行队列runqueue中当前的位置移到末尾。宏操作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额，即恢复其初始的时间配额。把该进程移到末尾意味着：如果没有权值更高的进程，但是有一个权值与这个权值相同的进程存在，那么那个权值相同而排列在前的进程就会被选中，从而顾全了大局。

接下来调度函数，查询当前运行进程的状态是否已改变。

如果发现进程处于TASK_INTERRUPTIBLE状态且有信号等待处理，则内核将其状态设为TASK_RUNNING，让其处理完信号。接下来仍有机会获得CPU；如果没有信号等待，则将其从可运行队列中撤下来；如果处于TASK_RUNNING状态，则继续进行。然后，将prev->need_resched的值恢复成0，因为所需的调度已经在运行。

调度之前，将待调度的进程默认为0号进程，权值设置为-1000。0号进程比较特别，既不会睡眠，又不能被杀死。接下来，内核遍历可执行队列runqueue中的每个进程，为每个进程通过goodness（）函数计算出它当前所具有的权值，然后与当前的最高值c比较。如果两个进程具有相同权值的话，那么排在前面的进程胜出。

上面的代码表明，如果当前进程想要继续运行，那么在挑选进程时以当前进程此刻的权值开始。这意味着，相对于权值相同的其他进程来说，当前进程优先。若发现当前已选进程的权值为0，则需要重新计算各个进程的时间配额，schedule（）将转入recalculate部分。