是什么
-
定义:操作系统中用于决定磁盘 I/O 请求队列中哪个请求首先得到服务的算法。主要目的是减少寻道时间(磁头移动距离),从而提高磁盘访问效率。
-
大白话:货拉拉司机(磁头)手上有好几个送货单(磁道请求),他需要规划一条路线,尽量少跑冤枉路,把货送完。
核心内容
1. 概念与分类
磁盘调度主要针对寻道时间进行优化。
| 算法名称 | 英文全称 | 核心思想 | 优缺点 |
|---|---|---|---|
| 先来先服务 | FCFS (First-Come, First-Served) | 按请求到达的顺序服务。 | 最公平,实现简单;但寻道时间可能很长,产生”磁臂粘着”现象,性能最差。 |
| 最短寻道时间优先 | SSTF (Shortest Seek Time First) | 优先服务离磁头当前位置最近的磁道请求。 | 局部最优,能显著减少寻道时间;但由于局部优先,可能导致远处磁道的请求"饥饿"。 |
| 扫描算法 (电梯算法) | SCAN | 磁头在盘面上双向移动(如 0 399 0),移动过程中服务请求。遇到该方向请求则服务,直到移动到该方向的尽头,然后反向。 | 避免饥饿,性能较好,移动轨迹像电梯。对两端磁道的请求不公平(等待时间短)。 |
| 循环扫描算法 | C-SCAN (Circular SCAN) | 磁头单向移动服务请求(如 0 399),服务完请求且移动到尽头后,磁头快速返回另一端尽头,中途不服务,再开始新一轮单向服务。 | 性能较好,对所有磁道的请求提供更均匀的等待时间。返回过程不服务,这部分寻道时间是纯开销。 |
| LOOK 算法 | LOOK | SCAN 算法的改进版。磁头在移动时,如果该方向上已无请求,则立即反向,无需移动到磁盘尽头。 | 进一步减少不必要的寻道开销。 |
| C-LOOK 算法 | C-LOOK | C-SCAN 算法的改进版。磁头在单向移动服务时,如果该方向上已无请求,则直接返回到反方向上离尽头最近的一个请求处,无需移动到尽头。 | 最灵活,能显著提高效率。 |
2. 寻道距离计算公式
例题
题目
(出自 2013 年 408 考研真题,第 32 题) 磁盘磁道数为 400(号为 0~399),用循环扫描算法(C-SCAN)进行调度。完成对 200 号磁道的请求后,磁头向磁道号减小的方向移动,若还有 7 个请求,磁道号分别为 300, 120, 110, 0, 160, 210, 399,则完成上述请求后磁头移动的距离是( )。 A. 599 B. 619 C. 788 D. 799
分析
1. 初始状态与条件提取:
-
总磁道数:400 号(0~399)。
-
当前磁头位置:200 号(刚完成)。
-
磁头移动方向:磁道号减小的方向。
-
请求队列:。
-
目标算法:C-SCAN (循环扫描算法)。
2. 磁头移动策略拆解(C-SCAN): C-SCAN 核心特点:
-
单向服务:磁头只在一个方向移动时服务请求。
-
返回不服务:到达一端服务完,直接空服务快速返回另一端。
-
题目特有策略:题目指明初始方向为”磁道号减小”(200 0),这成了 C-SCAN 的”服务方向”。
3. 执行路径规划:
-
服务路径:磁头从 200 号开始,向 0 号方向移动。在此过程中,服务遇到的请求。
-
纯移动路径:服务完全部”磁道号减小”方向的请求后,磁头必须继续移动到该方向的尽头(0号)。然后,空服务直接返回到反方向(磁道号增大方向)的尽头(399号)。
-
再次服务路径:从 399 号尽头开始,向 0 号服务方向移动,服务剩余请求。
答案
完整的计算过程如下:
第一阶段:磁头向减小方向移动服务 磁头从 200 出发,服务遇到的请求:。
-
服务结束位置:0 号。
-
第一阶段纯移动距离:从 200 移动到 0,距离为 。
易错点警示:C-SCAN 必须到达尽头!虽然 0 号本身也是请求,但即便 0 号不是请求,磁头也必须到达尽头。
第二阶段:磁头从尽头纯返回服务 服务完全部请求且移动到尽头(0 号)后,磁头快速返回反方向尽头。
-
返回路径:从 0 快速移动到反方向尽头 399。
-
此过程不服务中途请求(如:399 号)。
-
第二阶段纯移动距离:从 0 返回 399,距离为 。
第三阶段:从反方向尽头开始服务方向移动服务 磁头从 399 号出发,服务剩余请求:。
-
由于 C-SCAN 总是向特定服务方向移动,此时的 399 请求是在磁头到达 399 尽头后才被服务的。
-
服务位置路径:磁头从 399 号开始向减小方向服务,依此遇到并服务请求:
-
服务 399 号:距离为
-
服务 300 号:距离为
-
服务 210 号:距离为
-
-
第三阶段移动距离(服务过程):。
注意LOOK改进版(C-LOOK)的区别:第三阶段在 C-LOOK 中直接返回到 399 后立即服务,中途不再移动。第三阶段距离计算为 (结果碰巧一样,但过程有区别,LOOK不回尽头)。
总移动距离汇总
最终选择:C. 788
特别追加:其他算法在该题中的应用演示
为了深入理解,我们将题目改为其他扫描算法,计算结果: 请求队列已排序(方便计算):
1. 扫描算法 (SCAN)
-
策略:200 减小尽头(0) 增大尽头(399)。移动过程中服务请求。
-
计算过程:
-
减小阶段:200 0 号服务完毕且到达尽头(服务:)。距离 。
-
反向阶段:0 号反向服务增大方向(服务:)。距离 。
-
总距离:。
-
2. LOOK 算法
-
策略:200 减小方向最后一个请求(0) 增大方向最后一个请求(399)。已无请求方向则提前反向。
-
计算过程:
-
减小阶段:200 0 号服务完毕(服务方向上无请求,反向)。距离 。
-
反向阶段:0 号反向服务增大方向最后一个请求 399。距离 。
-
总距离:。(结果碰巧一样,因请求队列两端刚好是磁盘两端尽头)。
-
3. C-LOOK (循环 LOOK) 算法
-
策略:200 减小方向最后一个请求(0) 空服务直接返回增大方向最后一个请求(399) 减小方向服务剩余。
-
计算过程:
-
服务方向:200 0 号服务完毕(服务方向无请求)。距离 。
-
纯返回阶段:0 号空服务快速返回增大方向最后一个请求 399。距离 。
-
再次服务阶段:从 399 号尽头请求处,继续向减小服务方向移动(LOOK中则不再移动,直接反向)。距离 。
-
总距离:。(结果由于队列首尾请求刚好是磁盘首尾号,C-LOOK 和 C-SCAN 结果往往一样,过程有区别)。
-
4. 最短寻道时间优先 (SSTF)
-
策略:每次选离磁头最近的服务。
-
计算过程:
-
磁头 200 号,最近:210 号(距离 10)
-
磁头 210 号,最近:160 号(距离 50)
-
磁头 160 号,最近:120 号(距离 40)
-
磁头 120 号,最近:110 号(距离 10)
-
磁头 110 号,最近:0 号(距离 110)
-
磁头 0 号,最近:300 号(距离 300)
-
磁头 300 号,最近:399 号(距离 99)
-
总距离:。
-
-
SSTF 结果:B. 619。
⚠️ 易错点
Warning
C-SCAN vs SCAN:SCAN 是双向服务(遇到请求即服务),C-SCAN 是单向服务(到达一端尽头返回后,只在服务方向上移动并服务请求)。正确的是:SCAN 就像电梯,C-SCAN 是去一趟送完,直接快速回起点再来一趟。
尽头服务 vs 提前结束:SCAN/C-SCAN 算法磁头必须移动到该方向的尽头号(0 或 399),即使尽头没有请求;LOOK/C-LOOK 算法磁头在发现该方向已无请求时,立即反向/返回,无需到达尽头号。
C-SCAN 返回开销:C-SCAN 到达一个尽头服务完后,空服务返回反方向尽头的移动距离,是总寻道距离的一部分纯开销(距离计算为磁盘总磁道数,比如 399-0=399),不被服务请求抵消。