Linux调度器之主调度器框架

进程是操作系统提供的最古老，最重要的抽象之一，它对开发人员和操作人员隐藏了两个基本的硬件资源：处理器和存储器。进程的重要性在于它营造出个数不受物理处理器限制的虚拟处理器并为每个虚拟处理器配备了独立的，容量不受物理内存大小限制的内存空间。这些虚拟处理器为应用程序模拟出一个和物理处理器几乎相同的环境：每个虚拟处理器都拥有独立的，与物理处理器一样的寄存器集合；每个虚拟处理器可以使用同样的地址访问到的却是各自的存储单元；更重要的是，这么多虚拟处理器可以同时并发运行各自的程序，哪怕实际上只存在一个物理处理器。这就是本章讨论的重点：进程调度。

1.1,进程状态

虽然在很多操作系统里进程的状态多达五六，甚至八九种，但是从调度器的角度，进程的状态只有三种：阻塞态，就绪态和运行态。

处于阻塞态的进程不参与进程调度，事实上调度器在分配处理器时间时根本不知道阻塞态进程的存在。阻塞态进程要想参与调度，必须有一个‘第三方’将其提交给调度器，不然这个进程就是一个虽然存在但再也无法运行的‘植物人’。比如一个进程调用sleep()函数休眠一段时间，该进程就从当前运行进入阻塞态，从此不再受调度器的调遣，不再有机会占据处理器。等到指定的休眠时间到达，操作系统的定时器模块作为‘第三方’，将该进程提交给调度器，使其再度参与调度，又有机会成为当前运行进程。

与阻塞态不受调度器控制不同，就绪态和运行态进程都处于调度器的管辖之下。处于就绪态的进程本该运行于处理器上，可是调度器为了平衡众多进程对处理器时间的需求，让该进程暂时停下来听候调遣而安排其它进程在处理器上运行。就绪进程和阻塞进程共同点是都没有占用处理器，区别是阻塞态进程即使在处理器空闲时也不能运行，而就绪进程处于‘预备役’状态，只要处理器空闲或‘时机成熟’马上能运行于处理器上。就绪进程在调度器的队列里排队等候调遣，不同调度算法有各自的排队方式，如linux的完全公平(CFS)算法使用基于虚拟运行时间的红黑树，实时(RT)算法为每个调度优先级设置一条先入先出的队列。

运行态进程又叫当前进程，就是当前正在处理器上运行的进程。由于它占用了宝贵的处理器时间，在很多调度算法里当前进程都是重点监控对象，它的运行时间受到严密监视。一旦发现运行时间超标就会将其从‘现役’转为‘预备役’，进入就绪态，把处理器让给其它就绪进程（当然必须有其它就绪进程存在）。linux对当前进程运行时间的监控是在操作系统的tick中断里完成的，间隔从10毫秒到1毫秒不等。即使是这样的周期CFS算法的设计者还觉得不够精确，又设置了精度为纳秒级的高精度定时器(hrtimer)来监控当前进程，保证其占用的处理器时间严格符合预先给予的配额。

进程的三种基本状态在linux里并不直观。阻塞态有很多表达方式用以表示更精细的状态，比如常用的TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。当前进程的状态表示为TASK_RUNNING，可是就绪进程的状态也是用TASK_RUNNING表示。这不会造成混淆，因为当前运行进程是有专门变量记录的，而就绪进程则统一排列在运行队列中。在linux里TASK_RUNNING的值是0，其它状态值都非0。为运行态和就绪态设置相同值的一个好处是调度器可以很简单地判断一个进程是否能还能继续参与调度：只要状态非0的进程就是应该进入阻塞态的进程，调度器发现这样的进程就将其从调度器脱离开，不再竞争处理器。

1.2,Linux调度器相关文件

调度器是Linux内核中变化较多的模块，功能和性能随着应用的拓展不断增强，代码结构也随着需求的变化持续重构和优化。下表列出了本章将要涉及的，与调度器相关的源代码所在的文件。由于变化较大，可能随着内核版本的持续升级很快表中内容就与最新版本不符合了。
 

文件名	作用
linux_2.6.34-rc6/kernel/sched.c	该文件是调度器主体，包含调度器初始化，主调度器框架，调度器相关的API，各个具体调度算法也就是调度类的公共函数，用以支持分组调度的处理器子系统。
linux_2.6.34-rc6/kernel/sched_fair.c	该文件实现完全公平调度(CFS)算法和多处理器的负载平衡，与CFS调度类对应
linux_2.6.34-rc6/kernel/sched_rt.c	该文件实现实时调度(RT)算法，与RT调度类对应
linux_2.6.34-rc6/kernel/sched_idletask.c	该文件实现空闲(idle)任务调度，与idle调度类对应
linux_2.6.34-rc6/kernel/sched_cpupri.c	该文件跟踪系统中所有处理器上当前运行进程的优先级，用于实时调度算法的处理器选择
linux_2.6.34-rc6/kernel/sched.h	该文件是调度器最主要的头文件，比较重要的数据结构包括进程控制块(PCB)task_struct，调度项sched_entity的定义
linux_2.6.34-rc6/kernel/sched_feature.h	该文件包含存放调度器性能的参数和默认值

1.3,Linux主调度器

尽管代码已经‘几易其稿’，调度器几个主要API依旧保持着‘原生态’的形式在内核各处广泛调用，其中就包括主调度器schedule()。这个函数既没有参数也没有返回值，简单到了极致，却是整个调度器的奠基石，最基本的进程上下文切换就发生在这个函数中。该函数主要用在三个地方：

自主调度

这是内核进程主动发起的调度，表明当前进程由于种种原因需要撤离调度器，不再参与处理器的竞争而转入阻塞态。一个直观的例子就是调用sleep(timeout)函数使当前进程休眠指定时间后再次唤醒，类似于以下程序：

set_current_state(TASK_UNINTERRUPTIBLE);

设置唤醒定时器;

schedule();

第一行将当前进程设置为不响应信号的阻塞态，前面说过，在linux里只要状态不为TASK_RUNNING的进程都是阻塞态进程。第二行设置睡眠多长时间后将本进程唤醒。接下来调用schedule()函数发现当前进程状态已经设置为阻塞态就将当前进程切换出处理器并脱离调度器，然后从运行队列中取出下一个适合运行的进程继续运行。处于阻塞态的进程不会‘自然醒’，要想再次运行起来必须由‘第三方’将其唤醒，这个‘第三方’包括中断处理程序或其‘下半部’处理或其它进程。

用户态抢占

这是运行于用户态的进程被动剥夺处理器的一种方式。当前运行于用户态的进程P由于系统调用或中断发生进入了内核态。待到从内核态返回用户态时，如果它设置了标志TIF_NEED_RESCHED，说明在运行队列里有更适合运行的进程在排队等待，需要重新评估并切换当前进程，可是由于条件限制这个评估和切换没有立刻执行，只好推迟到从内核态返回到用户态时再执行，这时需要调用一次schedule()函数挑选一个合适的进程来替换当前进程P。与自主调度不同，通常在调用schedule()时候P的状态依旧为TASK_RUNNING，所以P让出处理器后不会进入阻塞态，而是在运行队列中等待下一次被调度。经过一番任务切换，P总是有机会占据处理器，回到用户态继续运行。这个过程从宏观上看就是运行于用户态的进程被另外一个进程剥夺了处理器。

为什么不在需要的时候直接调用schedule()切换进程，而要先设这么个标志等到以后再做进程切换？原因有二：一是在有些情况下不允许进程调度，比如在中断上下文中。在linux里中断象寄生虫一样附着于被它打断的进程（宿主进程）之上：它没有自己独立的类似于进程控制块的实体，直接使用宿主进程的栈和内存空间，所以中断是不可调度的，即使要强行调度也是宿主进程的调度，而不是中断本身的调度。换一个角度说，在中断里无论怎样做进程切换也无法切换到宿主进程上，因为中断本质上就是宿主进程的延伸，只不过是运行于内核态罢了。而假如中断是个和宿主进程一样可调度的实体，那么只要宿主进程处于就绪状态，从中断里总是有机会切换到宿主进程上。总而言之，在中断里调用schedule()，不但中断处理程序被阻塞了，还造成了一个副作用就是同时也阻塞了宿主进程，这样对宿主进程来说是不公平的。另一个不能调用schedule()的地方是与中断紧密联系的中断‘下半部’处理，原因和中断处理程序是一样的。可是中断处理程序或‘下半部’往往又是整个系统特别是事件驱动系统的‘动力源’，需要唤醒休眠等待的进程对中断事件做进一步处理。所以中断处理程序中只好将需要唤醒的进程添加到运行队列里，然后设置当前进程的TIF_NEED_RESCHED标志好在中断推出时执行调度。这样既防止了在中断中切换进程上下文，又实现了进程抢占式调度。二是在多处理器时，如果唤醒的进程在另一个处理器上，那在本处理器上调用schedule()是没有用的，因为它不能操作其它处理器上的运行队列。通常采用迂回的做法：先设置被唤醒进程的TIF_NEED_RESCHED标志，然后向该进程所在的处理器发送中断。处理器在中断返回处就会调用schedule()（或preempt_schedule_irq()如果中断发生在内核态）运行被唤醒的进程。

内核态抢占

这是运行于内核态的进程被动剥夺处理器的方式。早期的linux版本不支持内核态下的抢占式调度，进程在内核态下的切换完全依赖于上面提到的进程自主调度完成。这样可以简化内核设计，不需要保护许多全局变量和资源，但缺点是调度延时大，无法做到实时调度。经过一番‘实时化’改造，目前的内核已经是真正的抢占式内核，进程在内核态下运行时随时会被其它进程打断。实现抢占式内核最根本的修改是中断结束时，如果返回的是内核空间也执行一次schedule()（同样也要检查TIF_NEED_RESCHED标志）。而以前的非抢占式内核只有在用户态发生的中断在返回用户空间时才执行一次schedule()函数。中断随时可能发生，所以运行在内核态下的进程也随时会在中断返回时切换到其它进程，从而实现真正的内核抢占。