调度

当系统中有多个任务都想使用有限资源时，操作系统必须决定谁先使用资源。这个选择过程就是调度。

一个程序要真正运行，通常要先从外存进入内存，再进入就绪队列，最后才可能被分配 CPU。因此，处理机调度要分成三个层次理解。

900

高级调度

高级调度也称作业调度。

用户提交的作业最初通常位于外存的后备队列。由于内存空间有限，系统不能把所有作业一次性装入内存。高级调度按照一定规则，从外存后备队列中选择作业调入内存，并为它创建进程。

高级调度的关键动作是：

  1. 从外存后备队列选择作业。
  2. 将作业调入内存。
  3. 为该作业创建进程和 PCB。
  4. 让新建进程进入创建态，再进入就绪态。

高级调度面向的是作业。一个作业通常只被高级调度调入一次，作业结束后再调出一次。因此，高级调度发生频率最低。

低级调度

低级调度也称进程调度或处理机调度。

低级调度从内存中的就绪队列选择一个进程，把 CPU 分配给它。它直接决定哪个进程从就绪态变为运行态。

低级调度的关键动作是：

  1. 查看就绪队列。
  2. 按调度策略选择一个就绪进程。
  3. 分配处理机。
  4. 让该进程从就绪态进入运行态。

低级调度是最基本的调度。一般操作系统都必须配置进程调度。它发生频率最高，常以几十毫秒为尺度发生。

低级调度不是上下文切换本身

低级调度负责“选谁运行”。真正把 CPU 现场保存、恢复，并让 CPU 开始执行另一个进程，是后续分派和进程切换过程。

# 中级调度

中级调度也称内存调度。

当内存紧张时，操作系统可以把某些暂时不能运行或暂时不急于运行的进程映像调到外存。进程被调到外存后，就进入挂起状态。等内存空闲，或者该进程又需要运行时，中级调度再决定把哪个挂起进程重新调入内存。

中级调度的关键动作是：

  1. 在内存紧张或系统需要调整并发度时，将部分进程挂起到外存。
  2. 把被挂起进程的 PCB 组织到挂起队列中。
  3. 在合适时机，从挂起队列选择进程重新调入内存。
  4. 根据该进程原本是否在等待事件，恢复到就绪态或阻塞态。

中级调度面向的是进程，不是作业。一个进程可能被多次调出、调入内存，所以中级调度发生频率高于高级调度，但低于低级调度。

挂起态

挂起态表示进程映像暂时被调到外存。挂起并不等于阻塞。

状态 进程映像位置 是否等待事件 不能运行的直接原因
阻塞态 内存 是 等待 I/O、资源或事件
挂起态 外存 不一定 进程映像不在内存

阻塞态强调等事件；挂起态强调不在内存。一个进程可以既等待事件，又被调到外存，所以挂起态还可以细分为就绪挂起和阻塞挂起。

挂起状态 含义 调入内存后的状态
就绪挂起 进程不在内存，但除 CPU 外已经具备运行条件 就绪态
阻塞挂起 进程不在内存，并且仍在等待事件 阻塞态；若等待事件已发生，可转为就绪挂起或调入后进入就绪态

有的操作系统会把就绪挂起、阻塞挂起放入不同挂起队列；也可以按阻塞原因继续细分挂起队列。

七状态模型

原来的五状态模型包括创建态、就绪态、运行态、阻塞态、终止态。加入挂起机制后，可以扩展为七状态模型：创建态、就绪态、运行态、阻塞态、终止态、就绪挂起、阻塞挂起。

900

涉及挂起态的状态转换：

  • 就绪态 $\to$ 就绪挂起：进程本来可以运行，但内存压力较大，被调到外存。
  • 阻塞态 $\to$ 阻塞挂起：进程本来就在等待事件，同时又被调到外存。
  • 阻塞挂起 $\to$ 就绪挂起：等待事件发生，但进程映像仍在外存。
  • 就绪挂起 $\to$ 就绪态：中级调度把该进程重新调入内存。
  • 阻塞挂起 $\to$ 阻塞态：进程重新调入内存，但等待事件尚未发生。
Warning

阻塞挂起不能直接变为就绪态。 等待事件发生后，进程仍在外存，所以应先变为就绪挂起；只有被中级调度调回内存后，才进入就绪态。

就绪挂起也不能直接变为运行态。 它虽然已经具备运行条件，但进程映像不在内存，CPU 无法直接执行。它必须先由中级调度调回内存，进入就绪态，再由低级调度选中后进入运行态。

# 三层调度对比
调度层次 别名 管理对象 发生位置 主要动作 发生频率 对状态的影响
高级调度 作业调度 作业 外存 $\to$ 内存 从后备队列选作业调入内存，并创建进程 最低 无 $\to$ 创建态 $\to$ 就绪态
中级调度 内存调度 挂起进程 外存 $\leftrightarrow$ 内存 挂起进程，或把挂起进程重新调入内存 中等 就绪态/阻塞态 $\leftrightarrow$ 就绪挂起/阻塞挂起
低级调度 进程调度、处理机调度 就绪进程 内存 $\to$ CPU 从就绪队列选进程并分配处理机 最高 就绪态 $\to$ 运行态
  • 高级调度决定作业能不能进入内存。
  • 中级调度决定挂起进程能不能回到内存。
  • 低级调度决定就绪进程能不能获得 CPU。