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