操作系统基础19-CPU调度

2020-11-20 13:11·重学IT的老猫

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 执行的交替序列

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

CPU执行时间的直方图

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

抢占调度

需要进行 CPU 调度的情况可分为以下四种：

当一个进程从运行状态切换到等待状态时（例如，I/O 请求，或 wait() 调用以便等待一个子进程的终止)。
当一个进程从运行状态切换到就绪状态时（例如，当出现中断时）。
当一个进程从等待状态切换到就绪状态时（例如，I/O 完成）。
当一个进程终止时。

对于第 1 种和第 4 种情况，除了调度没有选择。一个新进程（如果就绪队列有一个进程存在）必须被选择执行。不过，对于第 2 种和第 3 种情况，还是有选择的。如果调度只能发生在第 1 种和第 4 种情况下，则调度方案称为非抢占的或协作的；否则，调度方案称为抢占的。在非抢占调度下，一旦某个进程分配到CPU，该进程就会一直使用CPU，直到它终止或切换到等待状态。 Windows 3.x 就使用这种调度方法。Windows 95引入抢占调度，所有之后的 Windows 操作系统都使用了抢占调度。Mac OS X操作系统采用抢占调度，而之前的 Macintosh操作系统采用协作调度。协作调度在有些硬件平台上是唯一的方法，因为它不需要特殊硬件（如定时器）来支持抢占调度。不过，当多个进程共享数据时，抢占调度可能导致竞争情况。假设两个进程共享数据。当第一个进程正在更新数据时，它被抢占以便第二个进程能够运行。然后，第二个进程可能试图读数据，但是这时该数据处于不一致的状态（可以使用互斥锁、信号量等方法解决）。抢占也影响操作系统的内核设计。在处理系统调用时，内核可能为进程而忙于某个活动。这些活动可能涉及改变重要的内核数据（如 I/O 队列）。如果一个进程在进行这些修改时被抢占，并且内核（或设备驱动）需要读取或修改同样的结构，那么会有什么结果呢？肯定导致混乱。有的操作系统（包括大多数 UNIX 系统）这样处理问题：在上下文切换前，等待系统调用的完成，或者等待 I/O 阻塞的发生。这种方案确保内核结构的简单，这是因为在内核数据结构处于不一致状态时，内核不会抢占进程。遗憾的是，这种内核执行模式对于实时计算的支持较差（实时系统的任务应在给定时间内执行完成）。因为根据定义中断可能随时发生，而且不能总是被内核所忽视，所以受中断影响的代码段应加以保护，从而避免同时使用。操作系统需要几乎任何时候都能接受中断，否则输入会被丢失或者输出会被改写。为了这些代码段不被多个进程同时访问，在进入时禁用中断而在退出时启用中断。重要的是，要注意禁用中断的代码段并不经常发生，而且常常只有少量指令。

CPU调度程序

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

切换上下文。
切换到用户模式。
跳转到用户程序的合适位置，以便重新启动程序。

调度程序应尽可能快，因为在每次进程切换时都要使用。调度程序停止一个进程而启动另一个所需的时间称为调度延迟。每当CPU空闲时，操作系统就应从就绪队列中选择一个进程来执行。进程选择采用短期调度程序或 CPU调度程序。调度程序从内存中选择一个能够执行的进程，并为其分配 CPU。注意，就绪队列不必是先进先出（FIFO）队列。其实现可以是 FIFO 队列、优先队列、树或简单的无序链表等。然而，在概念上，就绪队列内的所有进程都要排队以便等待在 CPU 上运行。队列内的记录通常为进程控制块（PCB）。

参考资料：《操作系统概念 operating system concepts》