考研笔记

调度的实现

上一节定了用什么标准衡量，下一节讲按什么规则挑人。这一节夹在中间，回答的是工程问题：谁来执行调度、什么时候执行、执行时具体发生了什么。

考点集中在两处：调度程序由哪三部分组成，以及哪些时刻不允许调度。后者几乎年年考。

机制

调度程序的三个部分

疑问点：调度程序由哪三部分组成

调度器（scheduler）的三个组成部分分别承担什么职责？

调度程序把”换人”这件事拆成了三个职责清晰的部件：

排队器——把就绪进程按某种策略排成一个或多个队列，以便调度时能快速取出下一个。队列的组织方式直接决定了算法的实现效率，比如多级反馈队列就需要多条队列配合。

分派器——把调度器选中的进程真正投入运行：取出该进程的 PCB，完成上下文切换，把 CPU 交给它。

上下文切换器——执行两次上下文切换：第一次保存当前进程的上下文并装入分派程序的上下文；第二次移出分派程序的上下文，把新选中进程的 CPU 现场装入处理机的各个寄存器。

这个三分法的意义在于把”决策”和”执行”分开了：排队器和调度算法负责决策（选谁），分派器和上下文切换器负责执行（怎么换过去）。考题问”调度”还是”分派”，指的往往是这两个不同环节。

什么时候该调度

需要调度的时机分成两类，判据是当前进程是主动让出还是被动剥夺。

主动放弃：

  • 进程正常终止
  • 进程异常终止（越界、非法指令等）
  • 进程主动请求阻塞（等待 I/O、申请不到资源、执行 P 操作被阻塞）

被动放弃：

  • 分给该进程的时间片用完
  • 有更紧迫的事情需要处理（如 I/O 中断）
  • 有更高优先级的进程进入就绪队列

疑问点：系统调用完成并返回用户态时，能否进行处理机调度

可以，而且这是一个非常典型的调度时机。

原因是：进程执行系统调用期间处于内核态，此时可能已经发生了改变调度局面的事情——比如它请求的 I/O 已经完成、唤醒了某个高优先级进程；或者它自己的时间片在内核中用完了。

内核在准备返回用户态之前，本来就要做一系列收尾检查（前面 2.1.5 讲过，检查信号位图也在这个位置）。顺带检查一下”是否需要重新调度”几乎不增加成本。这与信号检测选在同一时机，是完全相同的工程考量。

什么时候不能调度

疑问点：不能进行进程调度的时机有哪些

有三种情况禁止调度与切换，必须记牢：

① 在处理中断的过程中

中断处理程序执行时，系统正处在一个不完整的状态：现场刚保存了一部分，某些内核数据结构可能改到一半。此时若切换进程，这个残缺状态就会被固定下来，之后再也无法正确恢复。而且中断处理本身要求尽快完成，切换进去做别的事会大幅延长中断响应时间。

② 进程在操作系统内核程序临界区中

这一条最需要仔细区分（见下方边界段）。内核临界区保护的是内核数据结构（就绪队列、PCB 链表、内存分配表等）。进程进入这类临界区时会给该结构上锁。

如果此刻切换到另一个进程，而它恰好也要访问同一个内核数据结构，就会因为拿不到锁而阻塞。更糟的是，原来那个进程还持有着锁，却被换下了 CPU——内核的核心数据结构被长时间锁住，整个系统的调度、内存分配全部卡死。

③ 在原子操作过程中

原语的定义就是不可中断。原语执行期间处于关中断状态，时钟中断都进不来，自然也无从触发调度。

进程调度的两种方式

非剥夺方式（非抢占）：一旦把 CPU 分配给某进程，就让它一直运行下去，只有它自己主动让出（终止或阻塞），才会重新调度。

实现简单、系统开销小，但无法及时处理紧急任务，也不适合分时和实时系统。

剥夺方式（抢占）：当有更重要或更紧迫的进程需要 CPU 时，立即暂停当前进程，把 CPU 分配给它。

抢占必须遵循一定的原则，主要有优先权原则（高优先级可抢占低优先级）、短作业优先原则（短作业可抢占长作业）、时间片原则（时间片用完即抢占）。

对分时系统和实时系统而言，抢占式是必需的——否则响应时间和截止时间都无法保证。

闲逛进程

疑问点：闲逛进程执行什么指令，CPU 是否因此一直满负荷工作

就绪队列为空时 CPU 运行的闲逛进程（idle）究竟执行什么指令？ 若 CPU 始终在执行指令，为何还会有功耗高低之分、为何会发热？

当就绪队列为空、没有任何用户进程可运行时，CPU 不能真的”停下来”——它是一台取指执行的机器，必须始终有指令可取。此时运行的就是闲逛进程（idle）。

它有四个特征：

  • 优先级最低，任何进程就绪它都立刻让出 CPU
  • 不需要 CPU 之外的任何资源，因此永远不会被阻塞
  • 可以在没有其他就绪进程时随时被换下
  • 执行的是能耗低的特殊指令

最后一条正是疑问的关键。闲逛进程执行的不是一个空转的死循环，而是类似 HLT（halt）这样的停机指令——它让 CPU 进入低功耗状态，停止取指，直到下一个中断到来才被唤醒。

跨科对照：为什么指令有功耗差异（计算机组成原理）

“微程序控制不都是一个个电信号，为什么指令的功耗还不同”——这个追问的答案在数字电路层面。

CMOS 电路的动态功耗近似正比于 ，其中 是翻转率，即每个时钟周期内真正发生 0↔1 跳变的晶体管比例。

关键在于：电路只在状态翻转的瞬间才消耗显著能量，保持不变时几乎不耗电。 因此不同指令功耗不同，是因为它们激活的部件和造成的翻转量不同——一条乘法指令要驱动整个乘法器阵列翻转，一条 NOP 几乎不驱动任何数据通路。

HLT 指令更进一步：它直接门控住时钟信号（clock gating），让大片电路的 降为 0，动态功耗随之趋近于零，只剩下漏电流带来的静态功耗。

所以”CPU 一直在工作”这个前提本身就不准确——闲逛时它是在停机等待中断，而非满负荷取指执行。至于发热，来源正是上述动态功耗与静态漏电，最终全部转化为热能。

本节不含的两部分

调度决定了”换谁”，但换的过程本身和多处理机下的特殊问题，教材分别放在后面两节：

边界

内核程序临界区 ≠ 普通临界区

这是本节最容易混、也最能拉开区分度的一条。

内核程序临界区访问的是内核数据结构（就绪队列、PCB 链表、内存分配表）。这类临界区必须禁止调度，理由如上：锁住内核核心结构的进程一旦被换下，整个系统会卡死。

普通临界区访问的是普通的临界资源（打印机、共享文件）。这类临界区可以调度，甚至应该允许调度。

原因在于两者的持有时长完全不同：内核临界区通常只有几十条指令，很快就出来；而一个进程可能占用打印机长达数分钟。如果规定”占着打印机就不许被切走”，CPU 就会陪着它一起空等打印完成，利用率极低。

一句话判据：看被锁住的是内核自己的数据结构，还是外部资源。

对照速查

调度程序三部分职责属于
排队器把就绪进程排成队列决策准备
分派器取出 PCB，把 CPU 交给选中进程执行
上下文切换器保存旧现场、装入新现场（两次切换）执行
需要调度类型
正常/异常终止主动放弃
主动请求阻塞（等 I/O、P 操作）主动放弃
时间片用完被动
更高优先级进程就绪被动
系统调用返回用户态之前被动（典型时机）
不能调度原因
① 处理中断过程中系统处于不完整状态，且会延长中断响应
② 内核程序临界区中内核数据结构被锁住，切换会导致系统卡死
③ 原子操作（原语）过程中关中断状态，本就不可中断
内核程序临界区普通临界区
保护对象内核数据结构打印机、共享文件等
持有时长很短可能很长
能否调度不能可以

考点

  • 调度程序三部分：排队器、分派器、上下文切换器
  • 三种不能调度的情况（几乎年年考）
  • 内核程序临界区不能调度，普通临界区可以调度
  • 闲逛进程优先级最低、不会阻塞、执行低能耗指令

链接

反向链接