Linux 进程调度原理

minsky

unread,

Oct 13, 2008, 10:19:23 PM10/13/08

to 操作系统课程论坛

　　进程调度依据

　　调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_strUCt结构中有
以下四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，
用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间
片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度 goodness时起重要作用，因
此，counter也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。
　　Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了以上提到的四项，还结合了一些其他的因素，给每
个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。关于goodness()的情况在后面将会详细分
析。

　　进程调度策略

　　调度程序运行时,要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢?在每个进程的task_struct
结构中有这么四项：

　　policy, priority , counter, rt_priority

　　这四项就是调度程序选择进程的依据.其中,policy是进程的调度策略,用来区分两种进程-实时和普通；priority是进程(实时和普通)的
优先级；counter 是进程剩余的时间片,它的大小完全由priority决定;rt_priority是实时优先级,这是实时进程所特有的，用于
实时进程间的选择。

　　首先，Linux 根据policy从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通
进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程：

　　对于普通进程，Linux采用动态优先调度，选择进程的依据就是进程counter的大小。进程创建时，优先级priority被赋一个初值，一般
为 0～70之间的数字，这个数字同时也是计数器counter的初值，就是说进程创建时两者是相等的。字面上看，priority是\"优先级
\"、 counter是\"计数器\"的意思，然而实际上，它们表达的是同一个意思-进程的\"时间片\"。Priority代表分配给该进程的时间
片，counter表示该进程剩余的时间片。在进程运行过程中，counter不断减少，而priority保持不变，以便在counter变为0的时
候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用priority对counter进行赋值，
只有所有处于可运行状态的普通进程的时间片(p->counter==0)都用完了以后，才用priority对counter重新赋值，这个普通进程
才有了再次被调度的机会。这说明，普通进程运行过程中，counter的减小给了其它进程得以运行的机会，直至counter减为0时才完全放弃对
CPU 的使用，这就相对于优先级在动态变化，所以称之为动态优先调度。至于时间片这个概念，和其他不同操作系统一样的，Linux的时间单位也是
\"时钟滴答 \"，只是不同操作系统对一个时钟滴答的定义不同而已（Linux为10ms）。进程的时间片就是指多少个时钟滴答，比如，若
priority为20，则分配给该进程的时间片就为20个时钟滴答，也就是20*10ms=200ms。Linux中某个进程的调度策略
(policy)、优先级 (priority)等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为
200ms(更准确的，应为 210ms)，用户可以通过系统调用改变它。

　　对于实时进程，Linux采用了两种调度策略，即FIFO(先来先服务调度)和 RR（时间片轮转调度）。因为实时进程具有一定程度的紧迫性，所以
衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的 counter只是用来表示该进程的剩余时间片，并不作为衡量它是否
值得运行的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。上面已经看
到，每个进程有两个优先级，实时优先级就是用来衡量实时进程是否值得运行的。

　　这一切看来比较麻烦，但实际上Linux中的实现相当简单。Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。
该函数综合了上面提到的各个方面，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。

　　Linux根据policy的值将进程总体上分为实时进程和普通进程，提供了三种调度算法：一种传统的Unix调度程序和两个由POSIX.
1b(原名为POSIX.4)操作系统标准所规定的\"实时\"调度程序。但这种实时只是软实时，不满足诸如中断等待时间等硬实时要求，只是保证了当实
时进程需要时一定只把CPU分配给实时进程。

　　非实时进程有两种优先级，一种是静态优先级，另一种是动态优先级。实时进程又增加了第三种优先级，实时优先级。优先级是一些简单的整数，为了决定应
该允许哪一个进程使用CPU的资源，用优先级代表相对权值-优先级越高，它得到CPU时间的机会也就越大。

　　? 静态优先级(priority)-不随时间而改变，只能由用户进行修改。
它指明了在被迫和其他进程竞争CPU之前，该进程所应该被允许的时间片的最大值（但很可能的，在该时间片耗尽之前，进程就被迫交出了CPU）。

　　? 动态优先级(counter)-只要进程拥有CPU，它就随着时间不断减小；当它小于0时，标记进程重新调度。它指明了在这个时间片中所剩余的
时间量。

　　? 实时优先级(rt_priority)-指明这个进程自动把CPU交给哪一个其他进程；较高权值的进程总是优先于较低权值的进程。如果一个进程
不是实时进程，其优先级就是0，所以实时进程总是优先于非实时进程的（但实际上，实时进程也会主动放弃CPU）。

　　当policy分别为以下值时：

　　1) SCHED_OTHER：这是普通的用户进程，进程的缺省类型，采用动态优先调度策略，选择进程的依据主要是根据进程goodness值的大
小。这种进程在运行时，可以被高goodness值的进程抢先。

　　2) SCHED_FIFO：这是一种实时进程，遵守POSIX1.b标准的FIFO(先入先出)调度规则。它会一直运行，直到有一个进程因I/O
阻塞，或者主动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。在Linux实现中，SCHED_FIFO进程仍然拥
有时间片-只有当时间片用完时它们才被迫释放CPU。因此，如同POSIX1.b一样，这样的进程就象没有时间片(不是采用分时)一样运行。Linux
中进程仍然保持对其时间片的记录（不修改counter）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句 if (!
(current->policy&SCHED_FIFO)){...}-要知道，其他大量非FIFO进程都需要记录时间片，这种多余的检测只会浪费
CPU资源。（一种优化措施，不该将执行时间占10%的代码的运行时间减少到50%；而是将执行时间占90%的代码的运行时间减少到
95%。0.9+0.1*0.5=0.95>0.1+0.9*0.9=0.91）

　　3) SCHED_RR：这也是一种实时进程，遵守POSIX1.b标准的RR(循环round-robin)调度规则。除了时间片有些不同外，这
种策略与 SCHED_FIFO类似。当SCHED_RR进程的时间片用完后，就被放到SCHED_FIFO和SCHED_RR队列的末尾。

　　只要系统中有一个实时进程在运行，则任何SCHED_OTHER进程都不能在任何CPU运行。每个实时进程有一个rt_priority，因此，可
以按照rt_priority在所有SCHED_RR进程之间分配CPU。其作用与SCHED_OTHER进程的priority作用一样。只有
root用户能够用系统调用sched_setscheduler，来改变当前进程的类型(sys_nice,sys_setpriority)。
　　此外，内核还定义了SCHED_YIELD，这并不是一种调度策略，而是截取调度策略的一个附加位。如同前面说明的一样，如果有其他进程需要
CPU，它就提示调度程序释放CPU。特别要注意的就是这甚至会引起实时进程把CPU释放给非实时进程。

　　主要的进程调度的函数分析

　　真正执行调度的函数是schedule(void),它选择一个最合适的进程执行，并且真正进行上下文切换，使得选中的进程得以执行。而
reschedule_idle(struct task_struct *p)的作用是为进程选择一个合适的CPU来执行，如果它选中了某个CPU，
则将该CPU上当前运行进程的need_resched标志置为1,然后向它发出一个重新调度的处理机间中断，使得选中的CPU能够在中断处理返回时执
行schedule函数，真正调度进程p在CPU上执行。在 schedule()和reschedule_idle()中调用了goodness()
函数。goodness()函数用来衡量一个处于可运行状态的进程值得运行的程度。此外，在schedule()函数中还调用了
schedule_tail()函数;在reschedule_idle()函数中还调用了reschedule_idle_slow()。这些函数的
实现对理解SMP的调度非常重要，下面一一分析这些函数。先给出每个函数的主要流程图，然后给出源代码，并加注释。

　　goodness()函数分析

　　goodness()函数计算一个处于可运行状态的进程值得运行的程度。一个任务的goodness是以下因素的函数：正在运行的任务、想要运行的
任务、当前的CPU。goodness返回下面两类值中的一个：1000以下或者1000以上。1000或者1000以上的值只能赋给\"实时\"进
程，从0到999的值只能赋给普通进程。实际上，在单处理器情况下，普通进程的goodness值只使用这个范围底部的一部分，从0到41。在SMP情
况下，SMP模式会优先照顾等待同一个处理器的进程。不过，不管是UP还是SMP，实时进程的goodness值的范围是从1001到1099。

　　goodness()函数其实是不会返回-1000的，也不会返回其他负值。由于idle进程的counter值为负，所以如果使用idle进程作
为参数调用goodness，就会返回负值，但这是不会发生的。

　　goodness()是个简单的函数，