CPU调度是多道程序操作系统的基础。通过在进程间切换 CPU,操作系统可以使得计算机更加高效。

对于单处理器系统,同一时间只有一个进程可以运行;其他进程都应等待,直到 CPU 空闲并可调度为止。多道程序的目标是,始终允许某个进程运行以最大化 CPU 利用率。

这种想法比较简单。一个进程执行直到它应等待为止,通常等待某个 I/O 请求的完成。对于简单的计算机系统,CPU 就处于闲置状态。所有这些等待时间就会浪费,没有完成任何有用工作。采用多道程序,我们试图有效利用这个时间。多个进程同时处于内存。当一个进程等待时,操作系统就从该进程接管 CPU 控制,并将 CPU 交给另一进程。这种方式不断重复。当一个进程必须等待时,另一进程接管 CPU 使用权。

这种调度是操作系统的基本功能。几乎所有计算机资源在使用前都要调度。当然,CPU 是最重要的计算机资源之一。因此,CPU 调度是操作系统设计的重要部分。

CPU-I/O执行周期

CPU 的调度成功取决于如下观察到的进程属性,进程执行包括周期进行 CPU 执行 I/O 等待。进程在这两个状态之间不断交替。

进程执行从 CPU 执行开始,之后 I/O 执行;接着另一个 CPU 执行,接着另一个 I/O 执行;等等。最终,最后的 CPU 执行通过系统请求结束,以便终止执行(图 1)。


CPU执行和I/O执行的交替序列
图 1 CPU 执行和 I/O 执行的交替序列


这些 CPU 执行时间已大量测试过。虽然它们随进程和计算机的不同而变化很大,但是 它们的频率曲线类似于图 2 所示。


CPU执行时间的直方图
图 2 CPU执行时间的直方图


该曲线通常为指数或超指数的形式,具有大量短 CPU 执行和少量长 CPU 执行。I/O 密集型程序通常具有大量短 CPU 执行。CPU 密集型程序可能只有少量长 CPU 执行。对于选择合适的 CPU 调度算法,这种分布是很重要的。

抢占调度

需要进行 CPU 调度的情况可分为以下四种:
  1. 当一个进程从运行状态切换到等待状态时(例如,I/O 请求,或 wait() 调用以便等待一个子进程的终止)。
  2. 当一个进程从运行状态切换到就绪状态时(例如,当出现中断时)。
  3. 当一个进程从等待状态切换到就绪状态时(例如,I/O 完成)。
  4. 当一个进程终止时。

对于第 1 种和第 4 种情况,除了调度没有选择。一个新进程(如果就绪队列有一个进程存在)必须被选择执行。不过,对于第 2 种和第 3 种情况,还是有选择的。

如果调度只能发生在第 1 种和第 4 种情况下,则调度方案称为非抢占的协作的;否则,调度方案称为抢占的。在非抢占调度下,一旦某个进程分配到 CPU,该进程就会一直使用 CPU,直到它终止或切换到等待状态。

Windows 3.x 就使用这种调度方法。Windows 95 引入抢占调度,所有之后的 Windows 操作系统都使用了抢占调度。Macintosh 操作系统 Mac OS X 采用抢占调度,而之前的 Macintosh 操作系统采用协作调度。协作调度在有些硬件平台上是唯一的方法,因为它不需要特殊硬件(如定时器)来支持抢占调度。

不过,当多个进程共享数据时,抢占调度可能导致竞争情况。假设两个进程共享数据。当第一个进程正在更新数据时,它被抢占以便第二个进程能够运行。然后,第二个进程可能试图读数据,但是这时该数据处于不一致的状态(可以使用互斥锁、信号量等方法解决)。

抢占也影响操作系统的内核设计。在处理系统调用时,内核可能为进程而忙于某个活动。这些活动可能涉及改变重要的内核数据(如 I/O 队列)。如果一个进程在进行这些修改时被抢占,并且内核(或设备驱动)需要读取或修改同样的结构,那么会有什么结果呢?

肯定导致混乱。有的操作系统(包括大多数 UNIX 系统)这样处理问题:在上下文切换前,等待系统调用的完成,或者等待 I/O 阻塞的发生。这种方案确保内核结构的简单,这是因为在内核数据结构处于不一致状态时,内核不会抢占进程。遗憾的是,这种内核执行模式对于实时计算的支持较差(实时系统的任务应在给定时间内执行完成)。

因为根据定义中断可能随时发生,而且不能总是被内核所忽视,所以受中断影响的代码段应加以保护,从而避免同时使用。操作系统需要几乎任何时候都能接受中断,否则输入会被丢失或者输出会被改写。为了这些代码段不被多个进程同时访问,在进入时禁用中断而在退出时启用中断。重要的是,要注意禁用中断的代码段并不经常发生,而且常常只有少量指令。

CPU调度程序

与 CPU 调度功能有关的另一个组件是调度程序。调度程序是一个模块,用来将 CPU 控制交给由短期调度程序选择的进程。

调度程序的功能包括:
  • 切换上下文。
  • 切换到用户模式。
  • 跳转到用户程序的合适位置,以便重新启动程序。

调度程序应尽可能快,因为在每次进程切换时都要使用。调度程序停止一个进程而启动另一个所需的时间称为调度延迟

每当 CPU 空闲时,操作系统就应从就绪队列中选择一个进程来执行。进程选择采用短期调度程序或 CPU 调度程序。调度程序从内存中选择一个能够执行的进程,并为其分配 CPU。

注意,就绪队列不必是先进先出(FIFO)队列。其实现可以是 FIFO 队列、优先队列、树或简单的无序链表等。然而,在概念上,就绪队列内的所有进程都要排队以便等待在 CPU 上运行。队列内的记录通常为进程控制块(PCB)。