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。协议的具体内容请参见http://www.gnu.org/copyleft/fdl.html。在遵循GNU Free Document License的基础上，可以自由地传播或发行本文，但请保留本文的完整性。
欢迎大家对这篇文章提出意见和指正，我的email是：shisheng_liu@yahoo.com.cn。

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标志。当中断处理程序一结束，系统会重新调度，在这种情况下，新转入执行态的进程很可能 会获得执行机会，从而使系统保持对IO事件的快速响应。
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所示。
 

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。

SMP系统中的调度

7 参考文献：
1． linux内核源代码版本2.4.14
在任何时候真实的代码总是提供给我们最准确和详细的资料。感谢Linus Torvalds，Alan Cox和其它linux开发者的辛勤劳动。
2．DANIEL P.BOVET & MARCO CESATI
<<UNDERSTANDING THE LINUX KERNEL>> 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开发人员，无论水平高低，都有参考价值。翻译的水准也难得一见的高明。

from:
http://www.linuxforum.net/forum/gshowflat.php?Cat=&Board=linuxK&Number=294463&page=16&view=collapsed&sb=5&o=all&fpart=