考研笔记

调度的概念

多道程序环境下，就绪队列里通常不止一个进程，而 CPU 只有一个。调度要回答的就是”下一个给谁”。

但”给谁”这个问题在系统的不同位置上被问了三次，粒度和频率完全不同。把这三层分清楚，是本节的全部内容。

机制

为什么调度分成三层

一个任务从被提交到最终完成，要跨越两道门槛：

第一道是从外存进内存。批处理系统里，用户提交的一批任务先躺在外存的后备队列上，此时它们还只是作业，没有 PCB、不占内存、操作系统也不调度它们。内存装不下所有作业，必须挑一批进来。

第二道是从内存上 CPU。已经进了内存、变成进程的那些，仍然要排队等 CPU。

如果内存吃紧，还需要一个中间手段：把某些暂时不急的进程整个换到外存去，腾出内存给别人，过一阵再换回来。这就是第三层。

三层因此得名：

层次别名做什么频率
高级调度作业调度外存后备队列 → 内存，并创建进程最低（分钟级）
中级调度内存调度外存挂起区 ↔ 内存中等
低级调度进程调度就绪队列 → CPU最高（毫秒级）
flowchart LR
    J["外存·后备作业队列<br/>（还只是作业）"]:::ext
    R["内存·就绪队列"]:::mem
    C(["CPU"]):::cpu
    S["外存·挂起区"]:::ext

    J -->|"<b>高级调度</b><br/>创建进程<br/>频率最低"| R
    R -->|"<b>低级调度</b><br/>频率最高<br/><b>不可或缺</b>"| C
    R -.->|"<b>中级调度</b>换出"| S
    S -.->|"换入"| R

    classDef ext fill:#f1f5f9,stroke:#94a3b8,color:#334155
    classDef mem fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef cpu fill:#fef3c7,stroke:#d97706,color:#78350f

三层各自的要点

高级调度（作业调度）：从外存后备队列中挑选作业，为其分配内存、建立 PCB，使之成为进程并进入就绪队列。

这一层有两个必须记住的性质：

其一，每个作业只会被调入一次、调出一次。调入是作业调度的动作，调出发生在作业运行结束时。这与低级调度形成鲜明对比——一个进程在其生命周期内会被低级调度选中无数次。

其二，它是唯一会”创建进程”的调度层。这正好解释了 2.1.4 里那个看似矛盾的说法：作业调度程序本身是常驻的，它创建的是被它选中的作业。

中级调度（内存调度）：把暂时不能运行的进程换出到外存，使其进入挂起态；条件合适时再换回内存。

它的目的是提高内存利用率和系统吞吐量。被换出的进程 PCB 仍留在内存中，只是程序和数据被换到了外存——因为操作系统还需要通过 PCB 知道它的存在和状态，才能在合适的时机把它换回来。

低级调度（进程调度）：从就绪队列中选一个进程，把 CPU 分配给它。这是最基本、频率最高、也是唯一不可或缺的一层。

三级调度与七状态模型的对应

三层调度恰好对应状态图上的三组转换，这个对应关系一记就不会乱：

  • 高级调度：无 → 创建态 → 就绪态
  • 中级调度：就绪 ↔ 静止就绪、阻塞 ↔ 静止阻塞
  • 低级调度：就绪 → 运行

不同系统类型的调度侧重

疑问点：分时系统是什么，通常采用什么调度算法

分时操作系统的确切定义是什么？它通常采用哪种调度算法为用户服务？ 实时系统的进程调度又有何不同？

分时系统把 CPU 时间划分成很短的时间片，轮流分配给各个联机用户作业。每个用户通过自己的终端交互式地使用计算机，由于时间片很短、轮转很快，每个用户都感觉自己在独占整台机器。

它的四个特征是多路性、独立性、及时性、交互性。核心追求是响应时间短——用户敲下回车后不能等太久。

因此分时系统通常采用**时间片轮转（RR）**算法。原因很直接：RR 保证每个进程在一轮之内必定能获得一次执行机会，响应时间有上界，这正是交互性的硬需求。而 FCFS 或 SJF 都可能让一个进程等待任意长的时间。

实时系统要求在规定的时限（deadline）内完成对外部事件的响应。它追求的不是平均性能好，而是最坏情况可控。

实时系统的调度因此有两个显著不同：

其一，广泛采用抢占式的优先级调度。紧急任务一到，必须能立刻把当前任务踢下 CPU，否则可能错过时限。

其二，评价标准从”平均周转时间”换成了”能否满足截止时间”。一个平均性能很好但偶尔超时的算法，在实时系统里是不合格的。

实时系统按对时限的严格程度又分两类：硬实时要求绝对不能超时（导弹控制、工业控制），软实时允许偶尔超时（视频播放、在线订票）。

边界

”调度”与”分派”不是一回事

调度（scheduling）是决策——按算法选出下一个该运行的进程；分派（dispatch）是执行——真正把 CPU 交给它，包括切换上下文、切换到用户态、跳到断点。

考题会问”调度程序做了什么”，要看它问的是决策还是执行。详见 2.2.2 的调度程序三部分。

只有低级调度是每个系统都必须有的

  • 高级调度主要存在于批处理系统。交互式系统（分时、实时）中，用户提交的任务通常直接建立进程，没有”后备作业队列”这一环。
  • 中级调度只在引入了虚拟存储/对换技术的系统中才有。
  • 低级调度是任何多道程序系统都必不可少的。

所以选择题问”下列哪种调度是必不可少的”，答案永远是进程调度。

作业调度调入的是作业，进程调度调度的是进程

这两层最容易混，判据是操作对象跨没跨内存边界：

  • 高级调度让一个东西从没有 PCB 变成有 PCB，是”无中生有”。
  • 低级调度只是在已有的 PCB 之间做选择，不改变任何进程的存在性。

对照速查

高级调度中级调度低级调度
别名作业调度内存调度进程调度
操作对象作业（外存）挂起的进程进程（内存）
是否创建 PCB是否否
频率最低中最高
是否必不可少否（主要见于批处理）否（需对换技术）是
每个对象经历次数调入 1 次、调出 1 次可多次多次
状态转换无→创建→就绪就绪↔静止就绪
阻塞↔静止阻塞		就绪→运行
系统类型核心追求典型算法
批处理吞吐量、平均周转时间FCFS、SJF、HRRN
分时响应时间时间片轮转 RR
实时满足截止时间抢占式优先级调度

考点

  • 三级调度的对象、频率、是否创建 PCB
  • 低级调度是唯一必不可少的
  • 作业只被调入一次、调出一次
  • 中级调度换出后 PCB 仍留在内存
  • 分时系统 → RR；实时系统 → 抢占式优先级

链接

反向链接