Linux 内核笔记 – 进程调度

原文链接:

刘世胜

Linux 内核笔记 – 进程调度

1      前言
2      调度算法
2.1.1        常用概念
2.1.2        进程数据结构中相关内容
2.1.3        调度算法说明
2.1.4        相关函数
3      调度程序的执行
3.1.1        直接调用
3.1.2        延迟调用
3.1.3        相关函数
4      进程调度示意图
5      SMP系统的调度
6      问题与答案
7      参考文献

1        前言
本文的许可协议遵循GNU Free Document License。协议的具体内容请参见。在遵循GNU Free Document License的基础上，可以自由地传播或发行本文，但请保留本文的完整性。
欢迎大家对这篇文章提出意见和指正，我的email是：。

2        调度算法
2.1.1        常用概念
2.1.1.1            定时中断
    通过硬件的可编程中断控制器8254来实现，定时中断发生的频率由HZ定义，发生的时间间隔被称为tick。
2.1.1.2            CPU节拍（tick）
计算机内部时间的一个计数单位，表示发生一次时钟中断的时间间隔。
2.1.1.3            HZ
 时钟中断发生的频率。在i386机器上，HZ被定义为100，因此时钟中断每10ms一次。
2.1.1.4            CPU时期 
      调度是以CPU时期为周期的，在一个CPU时期/调度周期内，系统中所有程序都被执行直到用完当前的时间片，然后所有进程的counter值被重新计算，并开始另一个CPU时期。
2.1.1.5            进程的分类
在调度程序看来，系统中的进程分为两大类，分别是实时进程和普通进程。在任何时候实时进程的执行都高于普通进程。进程数据结构中的policy成员变量表示了进程是哪一类，而sched_set(/get)scheduler提供了控制进程调度policy的用户级编程接口。
2.1.2        进程数据结构中相关内容
2.1.2.1               1．nice 
    进程的优先级，影响进程获得CPU事件的多少，20为最低，-19为最高。
2.1.2.2            2．counter
 进程时间片所剩余的CPU节拍数。初始值根据进程的nice值决定，在每次时钟中断发生时，也就是一个CPU节拍（tick）的时候，当前进程的counter值减1，如果counter值变为0则表示当前进程的时间片已经用完，系统会重新调度，决定下一个执行的进程。
2.1.2.3            3．need_resched
  标志位。该位在从中断和系统调用中返回的时候被检查，need_resched为1的时候表示要求启动调度程序，这通常发生在进程的时间片已经用完，或者因为IO事件发生而强行抢占当前进程的时候。
2.1.2.4            4．policy
  进程的调度策略。如果调度策略为SCHED_RR或者SCHED_FIFO则表示当前进程为实时进程，否则(SCHED_OTHER)为普通进程。
2.1.3        调度算法说明 
Linux采用相当简单但实际证明效果不错的调度算法。在调度的时候，所有正在运行进程的执行权值(goodness)都被计算，最终权值最高的进程获得执行的机会。假设得到的最大权值为0，就认为本次CPU时期已经执行完毕，会重新计算所有进程的counter值，开始新的CPU时期。调度算法的核心就是goodness的计算，计算的基本思路如下：
如果等待调度的进程是实时进程，它的goodness为1000 + 本身的优先级,而普通进程的goodness远小于1000，这就保证了实时进程总是优先于普通进程执行。
  如果进程剩余的counter为0,就认为它已经用光了自己在该时期的CPU时间片，goodness返回0。
  对于其他的情况，用下面的公式来计算goodness:
goodness = counter + 20 – nice；
2.1.4        相关函数
1．schedule()  in kernel/sched.c
主调度函数，选择要运行的进程
2．goodness() in kernel/sched.c
由schedule()调用，计算进程的执行权值
3        调度程序的执行
可以通过两种方式来激活调度程序，分别是直接调用和延迟调用。
3.1.1        直接调用
   当current进程准备主动放弃CPU的时候，它会直接调用调度程序schedule()，将CPU让给另一个进程。
促使current进程主动放弃CPU的原因有两种，一种情况是current需要睡眠（阻塞）来等待所需的资源准备好，此时current的状态被设置为TASK_INTERRUPTABLE或TASK_UNINTERRUPTABLE，在调用schedule()后进程进入睡眠状态；另一种情况下进程设置SCHED_YIELD的调度策略，然后用schedule()，此时进程只是短暂的放弃CPU，在下一次schedule()被调用的时候进程会继续参与CPU的竞争。
3.1.2        延迟调用
通过设置当前进程的need_resched标志来在其后的某个时刻激活调度程序。前面说过，在从中断/异常/系统调用中返回时，need_resched标志被检查，在标志不为0的时候会激活调度程序。例如：当时钟中断发生时，中断处理程序检查到当前进程的时间片已经执行完毕，它就会设置当前进程的need_resched标志；另一个例子是当某个IO中断发生时，中断处理程序发现有进程在等待该IO事件，它会将正在等待的进程的状态变为执行态，并设置当前进程的need_resched标志。当中断处理程序结束[注1]，系统会重新调度，在这种情况下，新转入执行态的进程很可能会获得执行机会，从而使系统保持对IO事件的快速响应。
[注1]：如果当前进程运行在内核态，即正在执行系统调用过程中，重新调度会延迟到当前进程的系统调用执行完毕才进行。
3.1.3        相关函数
  1．wake_up_common() in kernel/sched.c
   激活IO等待队列中的进程，它会顺序调用try_to_wake_up()，reschedule_idle()等函数来要求对进程进程重新调度。
  2．do_timer() in kernel/timer.c
   定时时钟中断程序，减少当前进程的counter值，如果counter已经用完，则设置进程的need_resched域要求重新调度。
  3．ret_from_intr/sys_call/exception   in arch/i386/entry.S
  汇编语言中的程序点，在从中断/异常/系统调用中返回时都会执行这一段程序，检查当前进程的need_resched域，如果不为0就会激活schedule()重新调度。

4        进程调度示意图
linux的进程调度如图1所示。

 
5        SMP系统的调度
SMP系统中的调度算法的不同主要表现在调度算法的最后，对于被切换出当前CPU运行权的进程调用了schedule_tail函数，目的是看能够将它转移到另一个CPU中运行。

6        问题与答案
Q．在当前系统下，调度时间片的长度是多少？
A. 与2.2.x版的内核相比，kernel2.4.x的时间片长度缩短了，对于最高优先级的进程来说，时间片的长度为100ms，默认优先级进程的时间片长度为60ms，而最低优先级进程的时间片长度为10ms。
Q. Linux如何保证对I/O事件相对比较快的响应速度，这个响应速度是否与调度时间片的长短有关？
A．当I/O事件发生的是时候，对应的中断处理程序被激活，当它发现有进程在等待这个I/O事件的时候，它会激活等待进程，并且设置当前正在执行进程的need_resched标志，这样在中断处理程序返回的时候，调度程序被激活，原来在等待I/O事件的进程（很可能）获得执行权，从而保证了对I/O事件的相对快速响应（毫秒级）。
    从上面的说明可以看出，在I/O事件发生的时候，I/O事件的处理进程会抢占当前进程，系统的响应速度与调度时间片的长度无关。
Q．高优先级(nice)进程和低优先级进程在执行上有何区别？例如一个优先级为-19（最高优先级）的进程和优先级为20（最低）的进程有何区别
A. 进程获得的CPU时间的绝对数目取决于它的初始counter值，初始的counter的计算公式(sched.c in kernel 2.4.14)如下：
p->counter = (p->counter >> 1) + ((20 - p->nice) >> 2) +1)
由公式可以计算出，对于标准进程（p->nice 为0）， 得到的初始counter为6，即进程获得的时间片为60ms。
最高优先级进程（nice为-19）的初始counter值为10，进程的时间片为100ms。
最低优先级进程（nice为20）的初始counter值为1,进程时间片为10ms。
 结论是最高优先级进程会获得最低优先级进程10倍的执行时间，普通优先级进程接近两倍的执行时间。当然，这是在进程不进行任何IO操作的时候的数据，在有IO操作的时候，进程会经常被迫睡眠来等待IO操作的完成,真正所占用的CPU时间是很难比较的。
我们可以看到每次重新计算counter的时候，新的counter值都要加上它本身剩余值的一半，这种奖励只适用于通过SCHED_YIELD主动放弃CPU的进程，只有它在重新计算的时候counter值没有用完，所以在计算后counter值会增大，但永远不可能超过20。
Q．进程是否可能在执行系统调用的过程中被抢占？
A．进程在执行系统调用的过程中不会被抢占。让我们设想进程a正在执行的过程中发生中断，而中断处理程序判断出系统需要被重新调度，它会设置进程a的need_resched标志（need_resched标志的作用参见前面说明），在中断处理程序结束之后（ret_from_intr），系统会检查被中断处理程序中断执行的进程的优先级，如果此时进程a处在用户态，系统会直接激活调度程序完成进程切换；而如果此时进程a处在内核态，系统会不作调度而恢复进程a的执行，只有进程a完成系统调用之后（ret_from_sys_call），它的need_resched标志才会被检查，从而完成进程切换。
进程在内核态不会被抢占的特点减少了单CPU系统中内核设计的复杂性，因为不需要考虑不同进程对内核代码和数据结构的竞争。

7        参考文献 
1．  Linux内核源代码版本2.4.14
在任何时候真实的代码总是提供给我们最准确和详细的资料。感谢Linus Torvalds，Alan Cox和其它linux开发者的辛勤劳动。
2．DANIEL P.BOVET & MARCO CESATI 
  <> ISBN: 0-596-00002-2  O’REILLY 2001
  中译版 《深入理解Linux内核》 陈莉君等译 ISBN: 7-5083-0719-4 中国电力出版社 2001。
本书是专门介绍linux内核结构的书中最详尽的一本，对代码分析讲解的也比较深入，基于2.2的内核版本
3．W.Richard Stevens 
 《UNIX环境高级编程》 尤晋元译 ISBN: 7-111-07579-X   机械工业出版社 2000
  UNIX编程圣经，程序员手头必备的书籍之一,对所有UNIX开发人员，无论水平高低，都有参考价值。翻译的水准也难得一见的高明。

====