linux内核设计与实现笔记<三>---进程调度

   调度程序是内核的组成部分，它负责选择下一个要运行的进程。进程调度程序（有时也简称调度程序）可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。调度程序是诸如Linux这样的多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度地发挥作用，多进程才会有并发执行的效果。

调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，只要有可以执行的进程，那么就总会有进程正在执行。但是只要系统中进程的数目比处理器的个数多，就注定某一给定时刻会有一些进程不能执行。这些进程在等待运行。在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。

1.I/O消耗型和处理器消耗型的进程

进程可以被分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或是等待I/O请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为它在等待更多的I/O请求时最后总会阻塞（这里指的是所有的I/O操作，像键盘活动等都包括，并不仅仅局限于磁盘I/O）。

相反，处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的I/O需求。但是，因为它们不属于I/O驱动类型，所以从系统响应速度考虑，调度器不应该经常让它们运行。对于这类处理器消耗型的进程，调度策略是尽量降低它们的运行频率，对它们而言，延长其运行时间会更合适些。处理器消耗型进程的极端例子就是无限循环地执行。

2. 进程优先级

调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。在包括Linux在内的某些系统中，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。

Linux内核提供了两组独立的优先级范围。第一种是nice值，范围从-20到＋19，默认值是0。nice的值越大优先级越低—你正在为系统中其他进程做好事（being nice）。nice值小的进程（优先级高）在nice值大的进程（优先级低）之前执行。另外nice值也用来决定分配给进程的时间片的长短。nice值为-20的进程可能获得的时间片最长，nice值为19的进程获得的时间片可能最短。nice是所有Unix系统都用到的标准优先级范围。第二个范围是实时优先级，其值是可配置的，默认情况下它的变化范围是从0到99。任何实时进程的优先级都高于普通的进程。

3. 时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片，但这并不是件简单的事。时间片过长会导致系统对交互的响应表现欠佳；让人觉得系统无法并发执行应用程序。时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。此外，I/O消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来：I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如说这样可以让它们的高速缓存命中率更高）。

Linux调度程序提高交互式程序的优先级，让它们运行得更频繁。于是，调度程序提供较长的默认时间片（参看图4-1）给交互式程序。此外，Linux调度程序还能根据进程的优先级动态调整分配给它的时间片。从而保证了优先级高的进程，假定也是重要性高的进程，执行的频率高，执行时间长。通过实现这样一种动态调整优先级和时间片长度的机制，Linux调度性能不但非常稳定而且也很强健。

注意，进程并不是一定非要一次就用完它所有的时间片。举例来说，一个拥有100毫秒时间片的进程并不一定在一次运行中就要用完所有这些时间。相反，进程可以通过重复调度，分五次每次20毫秒用完这些时间片。这样，即使是交互式程序也能从中获益—当它们没必要一次用这么多时间的时候，它们可以分几次使用，这样能保证它们尽可能长时间的处于可运行状态。

当一个进程的时间片耗尽时，就认为进程到期了。没有时间片的进程不会再投入运行，除非等到其他所有的进程都耗尽了它们的时间片（也就是说它们的剩余时间片为0）。在那个时候，所有进程的时间片会被重新计算。

4. 进程抢占

像前面所说的，Linux系统是抢占式的。当一个进程进入TASK_RUNNING状态，内核会检查它的优先级是否高于当前正在执行的进程。如果是这样，调度程序会被唤醒，抢占当前正在运行的进程并运行新的可运行进程。此外，当一个进程的时间片变为0时，它会被抢占，调度程序被唤醒以选择一个新的进程。

5. Linux调度算法

Linux的调度程序定义于kernel/sched.c中。调度程序的算法和相关支持代码大部分都在2.5版内核的开发版中被重写了。因此，现在的程序与以前版本内核中的调度程序区别很大，几乎是全新的。设计新的调度程序是为了实现下列目标：

充分实现O(1)调度。不管有多少进程，新调度程序采用的每个算法都能在恒定时间内完成。

全面实现SMP的可扩展性。每个处理器拥有自己的锁和自己的可执行队列。

强化SMP的亲和力。尽量将相关一组任务分配给一个CPU进行连续的执行。只有在需要平衡任务队列 的大小时才在CPU之间移动进程。

加强交互性能。即使在系统处于相当负载的情况下，也能保证系统的响应，并立即调度交互式进 程。

保证公平。在合理设定的时间范围内，没有进程会处于饥饿状态。同样的，也没有进程能够显失公 平地得到大量时间片。

虽然最常见的优化情况是系统中只有1～2个可运行进程，但是优化也完全有能力扩展到具有多处理器且每个处理器上运行多个进程的系统中。

新的调度程序实现了上述目标。

6. 可执行队列

调度程序中最基本的数据结构是运行队列（runqueue）。可执行队列定义于kernel/sched.c中，由结构runqueue表示。可执行队列是给定处理器上的可执行进程的链表，每个处理器一个。每个可投入运行的进程都惟一的归属于一个可执行队列。此外，可执行队列中还包含每个处理器的调度信息。所以，可执行队列也是每个处理器最重要的数据结构。

在对可执行队列进行操作以前，应该先锁住它（锁机制在第8章中讨论）。因为每个可执行队列惟一地对应一个处理器，所以很少出现一个处理器需要锁其他处理器的可执行队列的情况（我们将会看到，这种情况还确实可能会出现）。在其拥有者读取或改写队列成员的时候，可执行队列包含的锁用来防止队列被其他代码改动。锁住运行队列的最常见情况发生在你想锁住的运行队列上恰巧有一个特定的任务在运行。为了避免死锁，要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁：按照可执行队列地址从低向高的顺序.

7. 优先级数组

每个运行队列都有两个优先级数组，一个活跃的和一个过期的。优先级数组在kernel/ sched.c中被定义，它是prio_array类型的结构体。优先级数组是一种能够提供O(1)级算法复杂度的数据结构。优先级数组使可运行处理器的每一种优先级都包含一个相应的队列，而这些队列包含对应优先级上的可执行进程链表。优先级数组还拥有一个优先级位图，当需要查找当前系统内拥有最高优先级的可执行进程时，它可以帮助提高效率。

struct prio_array {
int nr_active; /* 任务数目*/
unsigned long bitmap[BITMAP_SIZE]; /* 优先级位图*/
struct list_head queue[MAX_PRIO]; /* 优先级队列*/
};

MAX_PRIO定义了系统拥有的优先级个数。默认值是140。这样，每个优先级都有一个struct list_head结构体。BITMAP_SIZE是优先级位图数组的大小， 类型为unsigned long长整型，长32位，如果每一位代表一个优先级的话，140个优先级需要5个长整型数才能表示。所以，bitmap就正好含有5个数组项，总共160位。

每个优先级数组都要包含一个这样的位图成员，至少为每个优先级准备一位。一开始，所有的位都被置为0。当某个拥有一定优先级的进程开始准备执行时（也就是状态变为TASK_RUNNING），位图中相应的位就会被置为1。比如，如果一个优先级为7的进程变为可执行状态，第7位就被置为1。这样，查找系统中最高的优先级就变成了查找位图中被设置的第一个位。因为优先级个数是个定值，所以查找时间恒定，并不受系统到底有多少可执行进程的影响。此外，Linux对它支持的每一种体系结构都提供了对应的快速查找算法，以保证对位图的快速查找。提供该功能的函数叫sched_find_first_bit()。很多体系结构提供了find-first-set指令，这条指令对指定的字操作。在这些系统上，找到第一个要设置的位所花的时间至多是执行这条指令的两倍，可以说微不足道。

每个优先级数组还包含一个叫做struct list_head的队列，其中每个元素都是一个struct list_head类型的队列。每个链表与一个给定的优先级相对应，事实上，每个链表都包含该处理器队列上相应优先级的全部可运行进程。所以要找到下一个要运行的任务非常简单，就像在链表中选择下一个元素一样。对于给定的优先级，按轮转方式调度任务。

优先级数组还包含一个计数器nr_active。它保存了该优先级数组内可执行进程的数目。

8.  重新计算时间片

新的Linux调度程序减少了对循环的依赖。取而代之的是它为每个处理器维护两个优先级数组：既有活动数组也有过期数组。活动数组内的可执行队列上的进程都还有时间片剩余；而过期数组内的可执行队列上的进程都耗尽了时间片。当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已经给它重新计算好了。重新计算时间片现在变得非常简单，只要在活动和过期数组之间来回切换就行了。因为数组是通过指针进行访问的，所以交换它们用的时间就是交换指针需要的时间。这个动作由schedule()完成：

struct prio_array * array = rq->active;
if (!array->nr_active) {
rq->active = rq->expired;
rq->expired = array;
}

这种交换是O(1)级调度程序的核心。O(1)级的调度程序根本不需要从头到尾都忙着重新计算时间片，它只要完成一个两个步骤就能实现数组的切换。这种实现完美地解决了前面列举的所有弊端。

9. schedule()

选定下一个进程并切换到它去执行是通过schedule()函数实现的。当内核代码想要休眠时，会直接调用该函数，另外，如果有哪个进程将被抢占，那么该函数也会被唤起执行。schedule()函数独立于每个处理器运行。因此，每个CPU都要对下一次该运行哪个进程做出自己的判断。

首先，要在活动优先级数组中找到第一个被设置的位。该位对应着优先级最高的可执行进程。然后，调度程序选择这个级别链表里的头一个进程。这就是系统中优先级最高的可执行程序，也是马上会被调度执行的进程，参见图4-2

10. 睡眠和唤醒

11. 抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/ sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成了两项基本的工作：

调用定义在中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。

调用定义在中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息。

内核必须知道在什么时候调用schedule()。如果仅靠用户程序代码显式地调用schedule()，它们可能就会永远地执行下去。相反，内核提供了一个need_resched标志来表明是否需要重新执行一次调度（见表4-2）。当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。

1)

用户抢占在以下情况时产生：

从系统调返回用户空间。

从中断处理程序返回用户空间。

2)

内核抢占会发生在：

当从中断处理程序正在执行，且返回内核空间之前。

当内核代码再一次具有可抢占性的时候。

如果内核中的任务显式的调用schedule()。

如果内核中的任务阻塞（这同样也会导致调用schedule()）。

12. 实时

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。SCHED_FIFO实现了一种简单的、先入先出的调度算法，它不使用时间片。SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止；它不基于时间片，可以一直执行下去。只有较高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的SCHED_FIFO级进程，它们会轮流执行, 但是在它们愿意让出处理机时会再次让出。只要有SCHED_FIFO级进程在执行，其他级别较低的进程就只能等待它结束后才有机会执行。

SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再接着执行了。也就是说，SCHED_RR是带有时间片的SCHED_FIFO—这是一种实时轮流调度算法。当SCHED_RR任务耗尽它的时间片，在同一优先级的其他实时进程被轮流调度。时间片只用来重新调度同一优先级的进程。对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程决不能抢占SCHED_RR任务，即使它的时间片耗尽。

这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定优先级别的实时进程总能抢占优先级比它低的进程。

13. 调度程序小结

   进程调度程序是内核重要的组成部分，因为运行着的进程首先在使用计算机（至少在我们大多数人看来）。然而，满足进程调度的各种需要决不是轻而易举的：很难找到“一刀切”的算法，既适合众多的可运行进程，又具有可伸缩性，还能在调度周期和吞吐量之间求得平衡，同时还满足各种负载的需求。不过，Linux内核的新调度程序尽量满足各个方面，并以较完善的可伸缩性和外在的魅力为所有的情况提供了最佳的解决方案。