linux调度器之主调度器框架

进程是操作系统提供的最古老，最重要的抽象之一，它对开发人员和操作人员隐藏了两个基本的硬件资源：处理器和存储器。进程的重要性在于它营造出个数不受物理处理器限制的虚拟处理器并为每个虚拟处理器配备了独立的，容量不受物理内存大小限制的内存空间。这些虚拟处理器为应用程序模拟出一个和物理处理器几乎相同的环境：每个虚拟处理器都拥有独立的，与物理处理器一样的寄存器集合；每个虚拟处理器可以使用同样的地址访问到的却是各自的存储单元；更重要的是，这么多虚拟处理器可以同时并发运行各自的程序，哪怕实际上只存在一个物理处理器。这就是本章讨论的重点：进程调度。
1.1         进程状态
虽然在很多操作系统里进程的状态多达五六，甚至八九种，但是从调度器的角度，进程的状态只有三种：阻塞态，就绪态和运行态。
处于阻塞态的进程不参与进程调度，事实上调度器在分配处理器时间时根本不知道阻塞态进程的存在。阻塞态进程要想参与调度，必须有一个‘第三方’将其提交给调度器，不然这个进程就是一个虽然存在但再也无法运行的‘植物人’。比如一个进程调用sleep()函数休眠一段时间，该进程就从当前运行进入阻塞态，从此不再受调度器的调遣，不再有机会占据处理器。等到指定的休眠时间到达，操作系统的定时器模块作为‘第三方’，将该进程提交给调度器，使其再度参与调度，又有机会成为当前运行进程。
与阻塞态不受调度器控制不同，就绪态和运行态进程都处于调度器的管辖之下。处于就绪态的进程本该运行于处理器上，可是调度器为了平衡众多进程对处理器时间的需求，让该进程暂时停下来听候调遣而安排其它进程在处理器上运行。就绪进程和阻塞进程共同点是都没有占用处理器，区别是阻塞态进程即使在处理器空闲时也不能运行，而就绪进程处于‘预备役’状态，只要处理器空闲或‘时机成熟’马上能运行于处理器上。就绪进程在调度器的队列里排队等候调遣，不同调度算法有各自的排队方式，如linux的完全公平(CFS)算法使用基于虚拟运行时间的红黑树，实时(RT)算法为每个调度优先级设置一条先入先出的队列。
运行态进程又叫当前进程，就是当前正在处理器上运行的进程。由于它占用了宝贵的处理器时间，在很多调度算法里当前进程都是重点监控对象，它的运行时间受到严密监视。一旦发现运行时间超标就会将其从‘现役’转为‘预备役&rsq