企业官网建设流程全解析

• 文档
• 教程
• 知识库

导读

操作系统是计算机系统的"大管家"，而调度算法就是这位管家分配 CPU、内存和磁盘资源的核心策略。本文基于 CS-Base（小林图解计算机基础）仓库中 《进程调度/页面置换/磁盘调度算法》 一文，系统梳理操作系统的三大调度机制——进程调度、页面置换与磁盘调度，并结合仓库内进程与线程基础、虚拟内存、内存回收、磁盘存储等配套章节深入剖析其底层原理。读完本文，你将掌握六大进程调度算法、五种页面置换算法和五种磁盘调度算法的核心思想、适用场景与相互优劣，足以应对校招/社招中关于操作系统调度的高频面试题。

一、总览：操作系统的三大调度机制

操作系统的"调度"贯穿于 CPU、内存、磁盘三大资源的管理之中，对应三大类算法：

这三者有一个共同点：都是在资源有限、请求众多的情况下，决定"下一个该服务谁"。理解了这一点，再看具体算法时就会事半功倍。

二、进程调度算法：把 CPU 时间公平地分出去

2.1 什么是进程调度？何时触发调度？

进程调度算法也称CPU 调度算法。当 CPU 空闲时，操作系统会从内存中选择某个「就绪状态」的进程，为其分配 CPU。在进程、线程基础知识中我们知道，进程在运行态、就绪态、阻塞态之间不断变迁，每一次状态变迁都可能触发一次调度。

通常，CPU 调度发生在以下四种情况：

1. 进程从运行状态转到等待状态；
2. 进程从运行状态转到就绪状态；
3. 进程从等待状态转到就绪状态；
4. 进程从运行状态转到终止状态。

其中，情况 1 和 4 属于非抢占式调度（进程运行直到完成或被阻塞才让出 CPU），情况 2 和 3 属于抢占式调度（进程运行过程中可以被打断，把 CPU 让给其他进程）。抢占的原则一般有三种：时间片原则、优先权原则、短作业优先原则。

为什么等待状态转到就绪状态也会触发调度？假设一个高优先级进程等待的事件发生了，它转入就绪状态，如果调度算法按优先级调度，它就会立即抢占正在运行的进程。而运行态转到就绪态，典型就是时间片到——时间片耗尽触发中断，抢占当前进程。这就是 CPU 调度的本质：在进程状态变迁的瞬间，决定 CPU 的归属。

调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真正使用 CPU 的时间和 I/O 时间——这是理解各类调度算法效果的前提。

2.2 调度原则：好调度算法的评判标准

在进程与线程基础的"调度原则"一节中，给出了五种核心评判维度：

• CPU 利用率：调度程序应确保 CPU 始终忙碌，提高利用率；
• 系统吞吐量：单位时间内 CPU 完成的进程数量，短作业能提升吞吐量，长作业会拉低它；
• 周转时间：进程运行时间 + 阻塞时间 + 等待时间的总和，越小越好；
• 等待时间：进程处于就绪队列的时间（注意不是阻塞时间），等待越久用户体验越差；
• 响应时间：用户提交请求到系统第一次产生响应所花费的时间，交互式系统中尤为重要。

一句话总结：这么多原则，目的就是让进程执行得更快。不同的调度算法正是对这些原则的权衡取舍。

2.3 六大经典进程调度算法

① 先来先服务调度算法（FCFS）

先来先服务（First Come First Served, FCFS）是最简单的非抢占式调度算法：每次从就绪队列选择最先进入队列的进程，一直运行，直到进程退出或被阻塞，才继续选择队列中下一个进程。

• 优点：实现简单、公平；
• 缺点：当一个长作业先运行时，后面所有短作业都要长时间等待；
• 适用性：对长作业有利，适用于CPU 繁忙型作业的系统，不适用于I/O 繁忙型作业的系统。

② 最短作业优先调度算法（SJF）

最短作业优先（Shortest Job First, SJF）：优先选择运行时间最短的进程运行，有助于提高系统吞吐量。

• 优点：吞吐量高；
• 缺点：对长作业极不友好——如果一个长作业在就绪队列中等待，而队列里不断涌入短作业，长作业会被不断往后推，周转时间越来越长，甚至长期得不到运行，造成饥饿。

③ 高响应比优先调度算法（HRRN）

FCFS 和 SJF 都没有很好权衡长短作业，高响应比优先（Highest Response Ratio Next, HRRN）对此做了折中。每次调度时，先计算每个进程的「响应比优先级」，把响应比最高的进程投入运行：

响应比 = (等待时间 + 要求的服务时间) / 要求的服务时间

从公式可以推导出两个性质：

• 两个进程等待时间相同时，要求的服务时间越短，响应比越高 → 短作业容易被选中（吸收 SJF 优点）；
• 两个进程要求的服务时间相同时，等待时间越长，响应比越高 → 长作业随着等待时间增加，响应比不断升高，最终获得运行机会（避免饥饿）。

注意：该算法需要预知进程要求的服务时间，而现实中这一信息不可预估，因此 HRRN 属于"理想型"算法，现实中难以实现。

④ 时间片轮转调度算法（RR）

时间片轮转（Round Robin, RR）是最古老、最简单、最公平且使用最广的算法。每个进程被分配一个时间段（时间片 Quantum），在该时间段内运行：

• 时间片用完进程还在运行 → 从 CPU 释放，分配给下一个进程；
• 进程在时间片结束前阻塞或结束 → CPU 立即切换。

时间片长度是关键参数：

• 太短：进程上下文切换过于频繁，降低 CPU 效率；
• 太长：短作业的响应时间变长，退化为 FCFS；
• 折中值：通常设为20ms ~ 50ms。

⑤ 最高优先级调度算法（HPF）

时间片轮转假设所有进程同等重要，但多用户系统希望调度有优先级。最高优先级（Highest Priority First, HPF）从就绪队列中选择最高优先级的进程运行。

进程优先级分为两类：

• 静态优先级：创建进程时就确定，运行期间不变；
• 动态优先级：随进程状态动态调整，如运行时间增加则降低优先级，等待时间（就绪队列等待）增加则升高优先级——随着时间的推移提高等待进程的优先级。

HPF 有两种实现方式：

• 非抢占式：当前进程运行完后，再选择高优先级进程；
• 抢占式：高优先级进程一出现，立即挂起当前进程去运行它。

致命缺点：可能导致低优先级进程永远得不到运行（饥饿）。动态优先级可以部分缓解该问题。

⑥ 多级反馈队列调度算法（MFQ）

多级反馈队列（Multilevel Feedback Queue）是时间片轮转与最高优先级算法的综合与发展：

• "多级"：设置多个队列，队列优先级从高到低，同时优先级越高时间片越短；
• "反馈"：新进程进入高优先级队列时，立刻停止当前运行进程，转去运行高优先级队列中的进程。

具体工作流程：

1. 新进程放入第一级队列末尾，按 FCFS 原则排队等待调度；
2. 若在第一级队列规定的时间片内未运行完成，转入第二级队列末尾，以此类推直至完成；
3. 只有较高优先级队列为空时，才调度较低优先级队列中的进程；若进程运行时有新进程进入高优先级队列，则停止当前进程并将其移入原队列末尾，让出 CPU。

效果：短作业在第一级队列即可快速完成；长作业逐级下沉，虽然等待时间变长，但每级运行的时间片也变长了。因此 MFQ兼顾长短作业，且有较好的响应时间，是综合最均衡的进程调度算法。

三、内存页面置换算法：缺页时的"换人"决策

3.1 前置知识：缺页异常（缺页中断）

当 CPU 访问的页面不在物理内存时，会产生缺页中断，请求操作系统把所缺页面调入物理内存。它与一般中断有两个关键区别：

1. 缺页中断在指令执行期间产生和处理中断信号；一般中断在指令执行完成后才检查和处理；
2. 缺页中断返回后重新执行该指令；一般中断返回后执行下一条指令。

缺页中断的处理流程（6 步）：

1. CPU 执行 Load M 指令，查找 M 对应的页表项；
2. 若页表项状态位"有效"，直接访问物理内存；若"无效"，CPU 发送缺页中断请求；
3. 操作系统执行缺页中断处理函数，先在磁盘上查找该页面的位置；
4. 在物理内存中找空闲页：找到则把页面换入物理内存；
5. 换入完成后，把页表项状态位修改为"有效"；
6. CPU 重新执行导致缺页异常的指令。

如果第 4 步找不到空闲页（内存已满），就需要页面置换算法来选择一个物理页换出：若该页被修改过（脏页），先换出到磁盘，并把被置换页的页表项状态位改为"无效"，再把正在访问的页面装入该物理页。

3.2 页表项的关键字段

理解页面置换算法前，先弄清页表项通常包含的字段（详见虚拟内存中对页表与多级页表的讲解）：

页面置换算法的功能是：当出现缺页异常、需调入新页面而内存已满时，选择被置换的物理页面。其算法目标是尽可能减少页面的换入换出次数。

3.3 五种经典页面置换算法

以下算法讲解沿用原文档的经典示例：3 个空闲物理页，请求页面序列为7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1（该序列常用于教材对比各类算法表现）。

① 最佳页面置换算法（OPT）

基本思路：置换在"未来"最长时间不访问的页面。实现需要计算内存中每个逻辑页面的"下一次"访问时间，选择未来最长时间不被访问的页面。

在示例序列中，缺页共发生7次（空闲页换入 3 次 + 最优页面置换 4 次），页面置换发生4次——这是所有算法中的理论下限。

局限：实际系统中程序访问页面是动态的，无法预知每个页面下一次访问前的等待时间，因此 OPT无法实现。它的价值在于作为衡量其他算法效率的基准——你的算法缺页次数越接近 OPT，说明越高效。

② 先进先出置换算法（FIFO）

既然无法预知未来，就选择在内存中驻留时间最长的页面进行置换——这就是先进先出（First In First Out）思想。

示例序列下，FIFO 缺页发生10次，页面置换7次，明显劣于 OPT。

补充知识点：FIFO 还存在著名的Belady 异常——在某些访问序列下，增大物理页框数反而导致缺页次数增加，这在 LRU 等栈式算法中不会出现。

③ 最近最久未使用置换算法（LRU）

基本思路：发生缺页时，选择最长时间没有被访问的页面置换，即假设"很久没用的页面，未来很长一段时间内仍不会被使用"。

LRU 与 OPT 的对比很有意思：OPT 用"未来"推测，LRU 用"历史"推测，因此 LRU 是 OPT 的近似。示例序列下，LRU 缺页发生9次，页面置换6次，优于 FIFO。

代价：完全实现 LRU 需要在内存中维护所有页面的链表（最近最多使用的在表头，最少使用的在表尾），每次访问内存都要更新整个链表——查找、删除、移动到表头，都是非常费时的操作。因此 LRU 虽然理论上可行、效果不错，但实际应用中较少直接使用。

值得一提：在 Linux 内核的内存回收中（见内存满了，会发生什么？），LRU 思想被工程化为active / inactive 两个双向链表的近似实现，越靠近链表尾部表示越不常访问，回收时优先回收不活跃页面——这正是 LRU 在真实系统中的落地形态。

④ 时钟页面置换算法（Clock）

能否找到一种"既能优化置换次数，又方便实现"的算法？时钟页面置换算法（Clock）就是这样的两全之选：它近似 LRU，又是对 FIFO 的改进。

算法思路：把所有页面保存在一个类似钟面的环形链表中，表针指向最老的页面。发生缺页中断时，检查表针指向的页面：

• 若其访问位为 0：淘汰该页面，把新页面插入这个位置，表针前移一个位置；
• 若其访问位为 1：清除访问位，表针前移，重复此过程直到找到访问位为 0 的页面。

因为表针像时钟指针一样在环形链表上转动，该算法因此得名"时钟算法"。它通过访问位来"记住"页面最近是否被访问过，既避免了 FIFO 的机械，又不像 LRU 那样维护全量链表，实现成本低、效果好，是实际操作系统中最常使用的页面置换算法。

⑤ 最不常用置换算法（LFU）

最不常用（Least Frequently Used, LFU）：发生缺页中断时，选择"访问次数"最少的页面淘汰。实现方式是为每个页面设置一个"访问计数器"，每访问一次累加 1，缺页时淘汰计数器值最小的页面。

LFU 看似简单，但落地面临两个问题：

1. 硬件成本高：每个页面都要增加计数器；查找访问次数最小的页面需要遍历链表，链表很长时非常耗时；
2. 只考虑频率、不考虑时间：某些页面过去访问频率很高但现在已不活跃，而当前正在频繁访问但累计次数还不高的页面，反而可能被"误伤"淘汰。

解决方案：定期衰减访问次数——例如在时间中断发生时，把过去时间访问页面的计数除以 2。这样随着时间流逝，以前的高频页面计数慢慢降低，被置换的概率相应增大，让 LFU 能"记住最近"而非只"记住曾经"。

四、磁盘调度算法：让磁头少跑冤枉路

4.1 磁盘结构与寻道成本

在磁盘比内存慢几万倍？一文中我们了解到：机械硬盘的随机访问延迟高达 10 毫秒，比 CPU L1 Cache 慢千万倍，是存储层次中最慢的一层。这种慢主要源于寻道——磁头移动到目标磁道的时间。

机械磁盘结构要点：中间为盘片（一般有多个），每个盘面有独立磁头；盘片每层分为多个磁道，每个磁道分为多个扇区，每个扇区512字节；多个相同编号的磁道形成一个柱面。

磁盘调度算法的目的：通过优化磁盘访问请求的顺序，减少不必要的寻道时间，提高磁盘访问性能。

下文所有算法基于同一个示例：请求序列98, 183, 37, 122, 14, 124, 65, 67（数字代表磁道位置），磁头初始位置在第53磁道。

4.2 五种经典磁盘调度算法

① 先来先服务（FCFS）

先到来的请求先被服务，按98 → 183 → 37 → 122 → 14 → 124 → 65 → 67顺序移动。

磁头总共移动640个磁道。算法简单粗暴，但当大量进程竞争使用磁盘、请求磁道分布很分散时，寻道时间过长，性能很差。

② 最短寻道时间优先（SSF）

优先选择从当前磁头位置所需寻道时间最短的请求。从 53 磁道出发，服务顺序为：65 → 67 → 37 → 14 → 98 → 122 → 124 → 183。

磁头移动总距离236磁道，相比 FCFS 性能大幅提升。

致命缺陷——饥饿：若后续动态请求都集中在磁头当前所在的小区域（如都在 183 以下），则 183 磁道的请求可能永远不被响应。饥饿的根源是磁头在一小块区域来回移动，而"眼下的最优"未必是"全局的最优"。

③ 扫描算法（Scan，电梯算法）

为解决 SSF 的饥饿问题，规定：磁头沿一个方向移动，访问该方向上所有未完成请求，直到到达该方向最后的磁道，才调换方向——这就是扫描算法，也叫电梯算法（电梯保持一个方向移动，直到该方向没有请求才改变方向）。

假设先朝磁道号减小的方向移动，服务顺序为：37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183（先响应左侧请求直到最左端 0 磁道，再反向响应右侧请求）。

• 优点：性能较好，不会产生饥饿；
• 缺点：中间部分磁道比较占便宜——磁头每次往返都经过中间区域，导致每个磁道的响应频率存在差异。

④ 循环扫描算法（C-SCAN）

为消除 Scan 的"中间占便宜"问题，规定总是按相同方向扫描，使每个磁道响应频率基本一致：

• 只有磁头朝某个特定方向移动时才处理请求；
• 返回时直接快速移动至最靠边缘的磁道（复位磁头），返回途中不处理任何请求。

假设先朝磁道增加的方向移动，服务顺序为：65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37（磁头碰到最右端 199 磁道后立即回到磁道 0，返回途中不响应任何请求）。

相比扫描算法，C-SCAN 对各个位置磁道的响应频率相对平均。

⑤ LOOK 与 C-LOOK 算法

Scan 和 C-SCAN 的共同点是：磁头都要移动到磁盘的最始端或最末端才调换方向。这其实可以优化——磁头只移动到"最远的请求"位置就立即反向。

• LOOK 算法（对 Scan 的优化）：每个方向上只移动到最远请求位置就反向，反向途中会响应请求；
• C-LOOK 算法（对 C-SCAN 的优化）：每个方向上只移动到最远请求位置就反向，反向途中不会响应请求。

两者省去了往返磁盘边界的无效行程，在请求未覆盖全盘的情况下能显著减少磁头移动距离。

五、三大调度机制横向对比与面试要点

5.1 算法速查表

5.2 面试高频追问

1. 抢占式与非抢占式调度怎么区分？关键看进程运行中能否被打断：FCFS 是非抢占，RR 靠时钟中断实现抢占，HPF 可按抢占/非抢占实现。
2. LRU 与 OPT 的区别？OPT 看"未来"（理论最优、不可实现），LRU 看"历史"（近似实现）。
3. Clock 算法为何叫 Clock？页面组织成环形链表，表针像时钟指针一样转动，靠访问位的 0/1 决定淘汰与放行。
4. SSF 为什么会饥饿？磁头总在小区域来回移动，远离该区域（如大磁道号）的请求永远轮不到。
5. Scan 与 C-SCAN 的差异？Scan 往返都响应请求，中间磁道受益多；C-SCAN 只单方向响应、返回时快速复位，各磁道响应频率更均匀。
6. MFQ 为什么综合最优？短作业在高优先级队列快速完成，长作业逐级下沉获得更大时间片，兼顾吞吐量与响应时间。

六、结语：调度算法的学习路径

调度算法是操作系统"资源分配"思想的集中体现，三类算法表面不同，内核相通——都是在约束条件下做取舍：进程调度在公平与效率间取舍，页面置换在命中率与实现开销间取舍，磁盘调度在寻道距离与公平性间取舍。

想进一步巩固这部分知识，建议在 CS-Base 仓库中按以下顺序阅读配套章节：

• 进程状态、PCB、上下文切换与调度时机：进程、线程基础知识；
• 虚拟内存、分页与页表结构：为什么要有虚拟内存？；
• LRU 在真实内核中的落地（active/inactive 链表）与内存回收流程：内存满了，会发生什么？；
• 机械磁盘的物理结构与性能差距：磁盘比内存慢几万倍？。

操作系统是计算机系统的"大管家"，而调度算法就是这位管家分配 CPU、内存和磁盘资源的三大核心策略。把这三大调度机制吃透，你对操作系统资源管理的理解将上升一个台阶。

• 文档
• 教程
• 知识库