02-进程调度

6.1　进程调度

进程调度器是个内核子系统，其功能是把有限的处理器资源分配给系统中的各个进程。换句话说，进程调度器（简称调度器）是个内核组件，决定选择哪个进程来运行。在决定哪个进程运行以及何时运行的过程中，调度器既要最大化处理器资源利用率，同时要支持从用户角度看多个进程是并发、无缝运行的。

在本章，我们将重点讨论“就绪进程（runnable process）”。就绪进程是非阻塞进程；“阻塞进程（blocked process）”是正在睡眠的进程，等待I/O，需要内核唤醒。

进行用户交互、执行大量的文件读写操作以及响应网络事件的进程往往会花费大量时间来等待资源可用，长时间被阻塞，在这期间无法转为就绪状态。如果只有一个就绪进程，进程调度器的任务就非常简单：运行这个进程！但是，当就绪进程数大于处理器数时，调度器就非常必要了。在这些情况下，有些进程会运行，而其他进程必须等待。决定哪个进程可以运行、何时运行、运行多久是进程调度器的基本功能。

在单处理机上，如果操作系统能交错地运行多个进程，从用户角度似乎是同时运行多个进程，就称该操作系统是“多任务（multitasking）”的。在多处理机上，多任务操作系统支持进程真正在不同处理器上并行执行。对于非多任务操作系统，比如DOS，每次只能运行一个任务。

多任务操作系统可以分为两大类：协同式（cooperative）和抢占式（preemptive）。Linux实现了后一种形式的多任务，调度器决定某个进程何时停止运行，而由另一个进程运行。这种中止正在运行的进程而由另一个进程运行的行为称作“抢占”。进程在被抢占前所能够运行的时间称为该进程的“时间片（timeslice）”（该名称归因于调度器给每个就绪进程分配一个处理器“时间片”）。

相反地，在协同式多任务系统中，进程会一直运行直到它自己结束。这种自发结束的行为称为“让出（yielding）”。理想情况下，会经常有进程让出，但操作系统绝不可强制要求其让出。因此，一个拙劣或破坏性的程序可能会运行很长时间，破坏了多任务机制，甚至导致整个系统崩溃。由于这个原因，现代操作系统几乎都采用抢占式多任务机制，Linux也不例外。

这些年，Linux进程调度器不断发生变化。当前进程调度器是在Linux内核版本2.6.23发布的，称为“完全公平调度器（Completely Fair Scheduler,CFS）”。这个名称源于该调度器采用了“公平入队（fair queuing）”策略，公平入队是个调度算法，对竞争进程采取公平访问资源的策略。CFS和其他UNIX进程调度器存在天壤之别，包括其前身O(1)进程调度器。在6.2节中，我们将深入探讨它。