6.1 进程调度/⻚⾯置换/磁盘调度算法
6.1 进程调度/⻚⾯置换/磁盘调度算法
最近，我偷偷 潜伏在各⼤技术群，因为秋招在即，看到不少⼩伙伴 分享的⼤⼚⾯经。
然后发现，操作系统的知识点考察还是⽐较多的，⼤⼚就是⼤⼚就爱问基础知识。其中，关于操
作系统的「调度算法」考察也算⽐较频繁。
所以，我这边 总结了操作系统的三⼤调度机制，分别 是「进程调度/⻚⾯置换/磁盘调度算法」，供
⼤家复习，希望⼤家在秋招能斩获⾃⼰⼼意的 offer 。
进程调度算法
进程调度算法也称 CPU 调度算法，毕竟进程是由 CPU 调度的。
当 CPU 空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU 。
什么 时候会发⽣ CPU 调度呢？通常有以下情况：
当进程从运⾏状态转到等待状态；
当进程从运⾏状态转到就绪状态；
当进程从等待状态转到就绪状态；
当进程从运⾏状态转到终⽌状态；
其中发⽣在 1 和 4 两种情况下的调度称为「⾮抢占式调度」，2 和 3 两种情况下发⽣的调度称为
「抢占式调度」。
⾮抢占式的意思就是，当进程正在运⾏时，它就会⼀直运⾏，直到该进程完成或 发⽣某个事 件⽽
被阻塞时，才会把 CPU 让给其他进程。
⽽抢占式调度，顾名思义就是进程正在运⾏的时，可以被打断，使其把 CPU 让给其他进程。那抢
占的原则⼀般有三种，分别 是时 间⽚原则、优先权原则、短作业优先原则。
你可能会好奇 为什么 第 3 种情况也会发⽣ CPU 调度呢？假设有⼀个进程是处于等待状态的，但是
它的优先级⽐较⾼，如果该进程等待的事件发⽣了，它就会转到就绪状态，⼀旦它转到就绪状
态，如果我们的调度算法是以优 先级来进⾏调度的，那么它就会⽴⻢抢占正在运⾏的进程，所以
这个时候就会发⽣ CPU 调度。
那第 2 种状态通常是时 间⽚到的情况，因为时间⽚到了就会发⽣中断，于是就会抢占正在运⾏的
进程，从⽽占⽤ CPU 。
调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），⽽不能影响进程真在使⽤
CPU 的时间和 I/O 时间。
接下来，说说 常⻅的调度算法：
先来先服务调度算法
最短作业优先调度算法
⾼响应⽐优先调度算法
时间⽚轮转 调度算法
最⾼优先级调度算法
多级反馈队列调度算法
先来先服务调度算法
最简单的⼀个调度算法，就是⾮抢占式的先来先服务（First Come First Severd, FCFS ）算法了。
顾名思义，先来后到，每次 从就绪队列选择最先进⼊队列的进程，然后⼀直运⾏，直到进程退出
或被阻塞，才会继续从队列中选择第⼀个进程接着运⾏。
这似乎很公平，但是当⼀个⻓作业先运⾏了，那么后⾯的短作业等待的时间就会很⻓，不利于短
作业。
FCFS 对⻓作业有利，适⽤于 CPU 繁忙型作业的系统，⽽不适⽤于 I/O 繁忙型作业的系统。
最短作业优先调度算法
最短作业优先（Shortest Job First, SJF ）调度算法同样也是顾名思义，它会优先选择运⾏时间最短
的进程来运⾏，这有助于提⾼系统的吞吐 量。
这显然对⻓作业不 利，很容易造成⼀种极端现象。
⽐如，⼀个⻓作业在就绪队列等待运⾏，⽽这个就绪队列有⾮常多的短作业，那么就会使 得⻓作
业不 断的往后推，周转时间变⻓，致使⻓作业⻓期不会被运⾏。
⾼响应⽐优先调度算法
前⾯的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和⻓作
业。
那么，⾼响应⽐优先 （Highest Response Ratio Next, HRRN ）调度算法主要是权衡了短作业和⻓
作业。
每次 进⾏进程调度时，先计算「响应⽐优先级」，然后把「响应⽐优先级」最⾼的进程投⼊运⾏，
「响应⽐优先级」的计算公式：
从上 ⾯的公式，可以发现：
如果两个 进程的「等待时间」相同时，「要求的服务时间」越短，「响应⽐」就越⾼，这样短作
业的进程容易被选中运⾏；
如果两个 进程「要求的服务时间」相同时，「等待时间」越⻓，「响应⽐」就越⾼，这就兼顾到
了⻓作业进程，因为进程的响应⽐可以随时间等待的增加⽽提⾼，当其等待时间⾜够⻓时，其
响应⽐便可以升到很⾼，从⽽获得运⾏的机会；
时间⽚轮转 调度算法
最古⽼、最简单、最公平且使⽤最⼴的算法就是时间⽚轮转 （Round Robin, RR ）调度算法。
每个进程被分配⼀个时间段，称为时间⽚（Quantum ），即允许该 进程在该时间段中运⾏。
如果时间⽚⽤完，进程还在运⾏，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外⼀
个进程；
如果该进程在时间⽚结束前阻塞或结束，则 CPU ⽴即进⾏切换；
另外，时间⽚的⻓度就是⼀个很关键的点：
如果时间⽚设得太短会导致过多的进程上下 ⽂切换，降低了 CPU 效率；
如果设得太⻓⼜可能引起对短作业进程的响应时间变⻓。将
通常时间⽚设为 20ms~50ms 通常是⼀个⽐较合理的折中值。
最⾼优先级调度算法
前⾯的「时间⽚轮转 算法」做了个 假设，即让所有的进程同等重要，也不 偏袒谁，⼤家的运⾏时
间都⼀样。
但是，对于多⽤⼾计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序
能从就绪队列中选择最⾼优先级的进程进⾏运⾏，这称为最⾼优先级（Highest Priority First
，
HPF ）调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
静态优先级：创建进程时候，就已经确定了优先级了，然后整个运⾏时间优先级都不会变化 ；
动态优先级：根据进程的动态变化 调整优先级，⽐如如 果进程运⾏时间增加，则降低其优先
级，如果进程等待时间（就绪队列的等待时间）增加，则升⾼其优先级，也就是随着时间的推
移增加等待进程的优先级。
该算法也有两种处理优先级⾼的⽅法，⾮抢占式和抢占式：
⾮抢占式：当就绪队列中出现优先级⾼的进程，运⾏完当前进程，再选择优先级⾼的进程。
抢占式：当就绪队列中出现优先级⾼的进程，当前进程挂起，调度优先级⾼的进程运⾏。
但是依然有缺点，可能会导致低优 先级的进程永远不会运⾏。
多级反馈队列调度算法
多级反馈队列（Multilevel Feedback Queue ）调度算法是「时间⽚轮转 算法」和「最⾼优先级算
法」的综合和 发展。
顾名思义：
「多级」表⽰有多个队列，每个队列优先级从⾼到低，同时优先级越⾼时间⽚越短。
「反馈」表⽰如果有 新的进程加⼊优先级⾼的队列时，⽴刻停⽌当前正在运⾏的进程，转⽽去
运⾏优先级⾼的队列；
来看看 ，它是如何⼯作的：
设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从⾼到低，同时优先级越⾼时
间⽚越短；
新的进程会被放⼊到第⼀级队列的末尾，按先来先服务的原则排队等待被调度，如果在第⼀级
队列规定的时间⽚没运⾏完成，则将其转⼊到第⼆级队列的末尾，以此类推，直⾄完成；
当较⾼优先级的队列为空，才调度较低优 先级的队列中的进程运⾏。如果进程运⾏时，有新进
程进⼊较⾼优先级的队列，则停⽌当前运⾏的进程并将其移⼊到原队列末尾，接着让较⾼优先
级的进程运⾏；
可以发现，对于短作业可能可以在第⼀级队列很快 被处理完。对于⻓作业，如果在第⼀级队列处
理不完，可以移⼊下次队列等待被执⾏，虽然等待的时间变⻓了，但是运⾏时间也会更⻓了，所
以该算法很好的兼顾了⻓短作业，同时有较好的响应时间。
内存⻚⾯置换算法
在了解内存⻚⾯置换算法前，我们得先谈⼀下缺⻚异常（缺⻚中断）。
当 CPU 访问的⻚⾯不在物理内存时，便会 产⽣⼀个缺⻚中断，请求操作系统将所缺⻚调⼊到物理
内存。那它与⼀般中断的主要区别在于：
缺⻚中断在指令执⾏「期间」产⽣和处理中断信号，⽽⼀般中断在⼀条指令执⾏「完成」后检
查和处理中断信号。
缺⻚中断返回到该指令的开始重新执⾏「该指令」，⽽⼀般中断返回回 到该指令的「下⼀个指
令」执⾏。
我们来看⼀下缺⻚中断的处理流程，如下图：
在 CPU ⾥访问⼀条 Load M 指令，然后 CPU 会去找 M 所对应的⻚表项。
如果该⻚表项的状态位是「有效的」，那 CPU 就可以直接去访问物理内存了，如果状态位是
「⽆效的」，则 CPU 则会发送缺⻚中断请求。
- 操作系统收到了缺⻚中断，则会执⾏缺⻚中断处理函数，先会查找该⻚⾯在磁盘中的⻚⾯的位
置。
- 找到磁盘中对应的⻚⾯后，需要把该⻚⾯换⼊到物理内存中，但是在换⼊前，需要在物理内存
中找空闲⻚，如果找到空闲⻚，就把⻚⾯换⼊到物理内存中。
⻚⾯从磁盘换⼊到物理内存完 成后，则把⻚表项中的状态位修改为「有效的」。
最后，CPU 重新执⾏导致缺⻚异常的指令。
上⾯所说的过程，第 4 步是能在物理内存找到空闲⻚的情况，那如果找不到呢？
找不到空闲⻚的话，就说明此时内存已满了，这时候，就需要「⻚⾯置换算法」选择⼀个物理
⻚，如果该物理⻚有被修改过（脏⻚），则把它换出到 磁盘，然后把该被置换出去的⻚表项的状态
改成「⽆效的」，最后把正在访问的⻚⾯装⼊到这个物理⻚中。
这⾥提⼀下，⻚表项通常有如下图的字段：
那其中：
状态位：⽤于表⽰该⻚是否有效，也就是说是否在物理内存中，供程序访问时参考。
访问字段：⽤于记录该⻚在⼀段时间被访问的次数，供⻚⾯置换算法选择出⻚⾯时参考。
修改位：表⽰该⻚在调⼊内存后是否有被修改过，由于内存中的每⼀⻚都在磁盘上保留⼀份副
本，因此，如果没有修改，在置换该⻚时就不需要将该⻚写回到磁盘上，以减少系统的开销；
如果已经被修改，则将该⻚重写到磁盘上，以保 证磁盘中所保留的始终是最新的副本。
硬盘地址 ：⽤于指出该⻚在硬盘上的地址 ，通常是物理块号，供调⼊该⻚时使⽤。
这⾥我整理了虚拟内存的管理整个流程，你可以从下 ⾯这张图看到：
所以，⻚⾯置换算法的功能是，当出现缺⻚异常，需调⼊新⻚⾯⽽内存已满时，选择被置换的物
理⻚⾯，也就是说选择⼀个物理⻚⾯换出到 磁盘，然后把需要访问的⻚⾯换⼊到物理⻚。
那其算法⽬标则是，尽可能减少⻚⾯的换⼊换出的次数，常⻅的⻚⾯置换算法有如下⼏种：
最佳⻚⾯置换算法（OPT ）
先进先出置换算法（FIFO ）
最近最久未使⽤的置换算法（LRU ）
时钟⻚⾯置换算法（Lock ）
最不常⽤置换算法（LFU ）
最佳⻚⾯置换算法
最佳⻚⾯置换算法基本思路是，置换在「未来 」最⻓时间不访问的⻚⾯。
所以，该算法实现需要计算内存中每个逻辑⻚⾯的「下⼀次」访问时间，然后⽐较，选择未来最
⻓时间不访问的⻚⾯。
我们举个 例⼦，假设⼀开始有 3 个空闲的物理⻚，然后有请求的⻚⾯序列，那它的置换过程如下
图：
在这个请求的⻚⾯序列中，缺⻚共发⽣了 7 次（空闲⻚换⼊ 3 次 + 最优⻚⾯置换 4 次），⻚⾯置
换共发⽣了 4 次。
这很理想，但是实际系统中⽆法实现，因为程序访问⻚⾯时是 动态的，我们是⽆法预知每个⻚⾯
在「下⼀次」访问前的等待时间。
所以，最佳⻚⾯置换算法作⽤是为了 衡量你的算法的效率，你的算法效率越接近该算法的效率，
那么说明你的算法是⾼效的。
先进先出置换算法
既然我们⽆法预知⻚⾯在下⼀次访问前所需的等待时间，那我们可以选择在内存驻留时间很⻓的
⻚⾯进⾏中置换，这个就是「先进先出置换」算法的思想。
还是以前⾯的请求的⻚⾯序列作为例⼦，假设使⽤先进先出置换算法，则过程如下图：
在这个请求的⻚⾯序列中，缺⻚共发⽣了 10 次，⻚⾯置换共发⽣了 7 次，跟最佳⻚⾯置换算
法⽐较起来，性能明显 差了很多。
最近最久未使⽤的置换算法
最近最久未使⽤（LRU ）的置换算法的基本思路是，发⽣缺⻚时，选择最⻓时间没有被访问的⻚⾯
进⾏置换，也就是说，该算法假设已经很久没有使⽤的⻚⾯很有可能在未来 较⻓的⼀段时间内仍
然不会被使⽤。
这种算法近似最优置换算法，最优置换算法是通过「未来 」的使⽤情况来推测要淘汰的⻚⾯，⽽
LRU 则是通过「历史」的使⽤情况来推测要淘汰的⻚⾯。
还是以前⾯的请求的⻚⾯序列作为例⼦，假设使⽤最近最久未使⽤的置换算法，则过程如下图：
在这个请求的⻚⾯序列中，缺⻚共发⽣了 9 次，⻚⾯置换共发⽣了 6 次，跟先进先出置换算
法⽐较起来，性能提⾼了⼀些。
虽然 LRU 在理论上是可以实现的，但代价 很⾼。为了 完全实现 LRU ，需要在内存中维护⼀个所有
⻚⾯的链表，最近最多使⽤的⻚⾯在表头，最近最少使⽤的⻚⾯在表尾。
困难的是，在每次 访问内存时都必须要更新「整个链表」。在链表中找到⼀个⻚⾯，删除它，然后
把它移动到 表头是⼀个⾮常费时的操作。
所以，LRU 虽然看上去不错，但是由于开销⽐较⼤，实际应⽤中⽐较少使⽤。
时钟⻚⾯置换算法
那有没有⼀种即能优化置换的次数，也能⽅便实现的算法呢？
时钟⻚⾯置换算法就可以两者兼得，它跟 LRU 近似，⼜是对 FIFO 的⼀种改进。
该算法的思路是，把所 有的⻚⾯都保存在⼀个类似钟⾯的「环形链表」中，⼀个表针指向最⽼的
⻚⾯。
当发⽣缺⻚中断时，算法⾸先检查表针指向的⻚⾯：
如果它的访问位位 是 0 就淘汰该⻚⾯，并把新的⻚⾯插⼊这个位置，然后把表针前移⼀个位
置；
如果访问位是 1 就清除访问位，并把表针前移⼀个位置，重复这个过程直到找到了⼀个访问位
为 0 的⻚⾯为⽌；
我画了⼀副时钟⻚⾯置换算法的⼯作流程图，你可以在下⽅看到：
了解了这个算法的⼯作⽅式，就明⽩为什么 它被称为时钟（Clock ）算法了。
最不常⽤算法
最不常⽤（LFU ）算法，这名字听起来很调⽪，但是它的意思不是指这个算法不常⽤，⽽是当发⽣
缺⻚中断时，选择「访问次数」最少的那个⻚⾯，并将其淘汰。
它的实现⽅式是，对每个⻚⾯设置⼀个「访问计数器」，每当⼀个⻚⾯被访问时，该⻚⾯的访问计
数器就累加 1。在发⽣缺⻚中断时，淘汰计数器值最⼩的那个⻚⾯。
看起来很简单，每个⻚⾯加⼀个计数器就可以实现了，但是在操作系统中实现的时候，我们需要
考虑效率和硬件成本的。
要增加⼀个计数器来实现，这个硬件成本是⽐较⾼的，另外如 果要对这个计数器查找哪个⻚⾯访
问次数最⼩，查找链表本⾝，如果链表⻓度很⼤，是⾮常耗时的，效率不⾼。
但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，⽐如有些⻚⾯在过去时间⾥访问
的频率很⾼，但是现在已经没有访问了，⽽当前频繁访问的⻚⾯由于没有这些⻚⾯访问的次数
⾼，在发⽣缺⻚中断时，就会可能会误伤当前刚 开始频繁访问，但访问次数还不⾼的⻚⾯。
那这个问题的解决的办法还是有的，可以定期减少访问的次数，⽐如当发⽣时间中断时，把过去
时间访问的⻚⾯的访问次数除以 2，也就说，随着时间的流失，以前的⾼访问次数的⻚⾯会慢慢 减
少，相当于加⼤了被置换的概率。
磁盘调度算法
我们来看看 磁盘的 结构，如下图：
常⻅的机械磁盘是上图左边的样⼦，中间圆的部分是磁盘的盘 ⽚，⼀般会有多个盘⽚，每个盘⾯
都有⾃⼰的磁头。右边的图就是⼀个盘⽚的结构，盘⽚中的每⼀层分为多个磁道，每个磁道分多
个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成⼀个圆柱，称之为 磁盘的
柱⾯，如上图⾥中间的样⼦。
磁盘调度算法的⽬的很简单，就是为了 提⾼磁盘的 访问性能，⼀般是通过优化磁盘的 访问请求顺
序来做到的。
寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当 ，必然可以节省⼀些不 必要的寻
道时间，从⽽提⾼磁盘的 访问性能。
假设有下⾯⼀个请求序列，每个数字代表磁道的位置：
98 ，183 ，37 ，122 ，14 ，124 ，65 ，67
初始磁头当前的位置是在第 53 磁道。
接下来，分别 对以上的序列，作为每个调度算法的例⼦，那常⻅的磁盘调度算法有：
先来先服务算法
最短寻道时间优先算法
扫描算法
循环扫描算法
LOOK 与 C-LOOK 算法
先来先服务
先来先服务（First-Come
，First-Served
，FCFS ），顾名思义，先到来的请求，先被服务。
那按照这个序列的话：
98 ，183 ，37 ，122 ，14 ，124 ，65 ，67
那么，磁盘的 写⼊顺序是从左到右，如下图：
先来先服务算法总共移动了 640 个磁道的距离，这么⼀看这种算法，⽐较简单粗暴，但是如果
⼤量进程竞 争使⽤磁盘，请求访问的磁道可能会很分散，那先来先服务算法在性能上就会显得很
差，因为寻道时间过⻓。
最短寻道时间优先
最短寻道时间优先（Shortest Seek First
，SSF ）算法的⼯作⽅式是，优先选择从当前磁头位置所需
寻道时间最短的请求，还是以这个序列为例⼦：
98 ，183 ，37 ，122 ，14 ，124 ，65 ，67
那么，那么根据距离磁头（ 53 位置）最近的请求的算法，具体的请求则会是下列从左到右的顺
序：
65 ，67 ，37 ，14 ，98 ，122 ，124 ，183
磁头移动的总距离是 236 磁道，相⽐先来先服务性能提⾼了不 少。
但这个算法可能存在某些请求的饥饿 ，因为本次例⼦我们是静态的序列，看不出问题，假设是⼀
个动态的请求，如果后续来的请求都是⼩于 183 磁道的，那么 183 磁道可能永远不会被响应，于
是就产⽣了饥饿 现象，这⾥产⽣饥饿 的原因是磁头在⼀⼩块区域来回移动。
扫描算法
最短寻道时间优先算法会产⽣饥饿 的原因在于：磁头有可能再⼀个⼩区域内来回得移动。
为了 防⽌这个问题，可以规定：磁头在⼀个⽅向上移动，访问所有未 完成的请求，直到磁头到达
该⽅向上的最后的磁道，才调换⽅向，这就是扫描（Scan ）算法。
这种算法也叫做电梯算法，⽐如电梯保持按 ⼀个⽅向移动，直到在那个⽅向上没有请求为⽌，然
后改变⽅向。
还是以这个序列为例⼦，磁头的初始位置是 53 ：
98 ，183 ，37 ，122 ，14 ，124 ，65 ，67
那么，假设扫描调度算先朝磁道号减少的⽅向移动，具体请求则会是下列从左到右的顺序：
37 ，14 ， 0 ，65 ，67 ，98 ，122 ，124 ，183
磁头先响应左边的请求，直到到 达最左端（ 0 磁道）后，才开始反向移动，响应右边的请求。
扫描调度算法性能较好，不会产⽣饥饿 现象，但是存在这样的问题，中间部分的磁道会⽐较占便
宜，中间部分相⽐其他部分响应的频率会⽐较多，也就是说每个磁道的响应频率存在差异。
循环扫描算法
扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的⽅向
进⾏扫描，使得每个磁道的响应频率基本⼀致。
循环扫描（Circular Scan, CSCAN ）规定：只有磁头朝某 个特定⽅向移动时，才处理磁道访问请
求，⽽返回时直接快速移动⾄最靠边缘的磁道，也就是复位磁头，这个过程是很快 的，并且返回
中途不处理任何 请求，该算法的特点，就是磁道只响 应⼀个⽅向上的请求。
还是以这个序列为例⼦，磁头的初始位置是 53 ：
98 ，183 ，37 ，122 ，14 ，124 ，65 ，67
那么，假设循环扫描调度算先朝磁道增加的⽅向移动，具体请求会是下列从左到右的顺序：
65 ，67 ，98 ，122 ，124 ，183 ， 199 ， 0 ，14 ，37
磁头先响应了右边的请求，直到碰到了最右端的磁道 199 ，就⽴即回到磁盘的 开始处 （磁道 0），
但这个返回的途中是不响应任何 请求的，直到到 达最开始的磁道后，才继续顺序响应右边的请
求。
循环扫描算法相⽐于扫描算法，对于各个位置磁道响应频率相对⽐较平均。
LOOK 与 C-LOOK 算法
我们前⾯说到的扫描算法和循环扫描算法，都是磁头移动到 磁盘「最始端或最末 端」才开始调换
⽅向。
那这其实是可以优 化的，优化的思路就是磁头在移动到 「最远的请求」位置，然后⽴即反 向移
动。
那针对 SCAN 算法的优化则叫 LOOK 算法，它的⼯作⽅式，磁头在每个⽅向上仅仅 移动到 最远的
请求位置，然后⽴即反 向移动，⽽不需要移动到 磁盘的 最始端或最末 端，反向移动的途中会响应
请求。
⽽针 C-SCAN 算法的优化则叫 C-LOOK ，它的⼯作⽅式，磁头在每个⽅向上仅仅 移动到 最远的请求
位置，然后⽴即反 向移动，⽽不需要移动到 磁盘的 最始端或最末 端，反向移动的途中不 会响应请
求。
