考点频率★★★★☆选择题常考有时结合计算题考查寻道距离难度⭐⭐⭐建议重点掌握每种算法的磁头移动顺序和总寻道距离的计算方法理解SCAN与C-SCAN的核心区别1️⃣ 为什么需要磁盘调度磁盘机械硬盘的访问时间由三部分组成组成部分说明占比寻道时间磁头移动到目标磁道的时间最大占主导旋转延迟目标扇区旋转到磁头下方的时间中等传输时间实际读写数据的时间最小其中寻道时间占比最大因此减少平均寻道距离是磁盘调度算法的主要目标。注SSD固态硬盘没有机械结构不存在寻道时间因此磁盘调度算法主要针对传统机械硬盘HDD。2️⃣ 先来先服务FCFSFirst Come First Served2.1 核心思想按请求到达的先后顺序依次服务公平、无饥饿但效率通常最低。2.2 计算示例磁头初始位置100请求序列55, 58, 39, 18, 90, 160, 150, 38, 184按顺序服务计算磁头移动距离步骤当前磁道 → 目标磁道移动距离1100 → 5545255 → 583358 → 3919439 → 1821518 → 9072690 → 160707160 → 150108150 → 38112938 → 184146总寻道距离4531921727010112146 498平均寻道距离498/9 ≈ 55.33️⃣ 最短寻道时间优先SSTFShortest Seek Time First3.1 核心思想每次选择距离当前磁头最近的请求服务。平均寻道距离优于FCFS但可能导致饥饿远处的请求长期得不到服务也可能导致磁头在局部区域来回震荡。3.2 计算示例同上条件初始100请求序列同上步骤当前磁道最近请求移动距离11009010290583235855345539165393816381820718150132815016010916018424总寻道距离10323161201321024 248平均寻道距离248/9 ≈ 27.6明显优于FCFS4️⃣ 扫描算法SCAN电梯算法4.1 核心思想磁头沿一个方向移动服务沿途所有请求直到该方向最末端最大磁道号然后反向移动继续服务另一方向的请求。类比电梯电梯向上运行中途有人按楼层就停一直跑到顶楼然后向下运行再服务下行的请求。4.2 计算示例同上条件假设磁头初始向磁道号增大的方向移动最大磁道号为199。服务顺序向大号方向先遇到的请求有哪些从100向大号依次遇到160, 150, 184按磁道号排序150, 160, 184。但注意从100向大号移动最先遇到的是150是的因为90、58等都在小号方向当前方向不会服务它们。到达184或到达199后反向服务小号方向的请求90, 58, 55, 39, 38, 18按递减顺序90, 58, 55, 39, 38, 18总寻道距离假设从100移动到最大磁道199再反向到最小请求18100 → 19999199 → 18181总距离 99 181 280如果只移动到最大请求184距离为 84 166 2504.3 SCAN的特点优点缺点吞吐量较高平均寻道时间较短两端请求响应慢边缘地区等待时间长无饥饿所有请求最终都会服务磁头移动方向变化频繁5️⃣ 循环扫描算法C-SCANCircular SCAN5.1 核心思想磁头单向移动如只向磁道号增大的方向服务沿途所有请求到达最远端后快速返回到起点返回过程中不服务任何请求然后重新开始向大号方向移动。类比把磁道想象成一个环形磁头永远沿着一个方向转圈。5.2 计算示例同上条件初始100向大号方向。服务顺序向大号方向服务150, 160, 184按顺序到达184或199后快速返回0返回过程不服务从0重新向大号方向移动服务剩余的小号请求18, 38, 39, 55, 58, 90按递增顺序总寻道距离假设从184快速返回0再从0到90100 → 18484184 → 0184返回不服务0 → 9090总距离 84 184 90 358如果最大磁道号为199则距离为 99 199 90 3885.3 C-SCAN的特点优点缺点对各磁道位置的请求响应时间更均匀返回过程浪费寻道时间无饥饿总寻道距离通常略大于SCAN6️⃣ 四种算法对比表算法选择依据是否有饥饿平均寻道实现复杂度FCFS请求到达顺序无高最低SSTF离当前磁头最近有远处可能被饿死较低中等SCAN电梯当前方向上的下一个无低中等C-SCAN单向循环无较低较高补充算法了解LOOK算法SCAN的改进版磁头只需移动到当前方向上的最远请求不需要到达物理最末端如199。上面的SCAN示例中如果采用LOOK磁头只到184就反向距离会从280降到250。C-LOOKC-SCAN的改进版磁头只移动到当前方向上的最远请求然后直接返回到当前方向上的最近请求。在示例中C-LOOK的距离为 (184-100) (184-18) (90-18) 84 166 72 322比C-SCAN的358更优。7️⃣ 经典例题例题1某磁盘请求序列磁道号98, 183, 37, 122, 14, 124, 65, 67磁头初始在53向磁道号增大的方向。分别用SCAN和C-SCAN调度求服务顺序。解析SCAN向大号到199后反向向大号98, 122, 124, 183按递增反向向小号67, 65, 37, 14按递减服务顺序98 → 122 → 124 → 183 → 67 → 65 → 37 → 14C-SCAN向大号到199后返回0再向大号向大号98, 122, 124, 183返回0不服务从0向大号14, 37, 65, 67服务顺序98 → 122 → 124 → 183 → 14 → 37 → 65 → 67答案SCAN: 98→122→124→183→67→65→37→14C-SCAN: 98→122→124→183→14→37→65→67例题2以下关于磁盘调度算法的叙述中正确的是 。A. SSTF算法不会导致饥饿B. SCAN算法在服务过程中不会改变方向C. C-SCAN算法在返回过程中也服务请求D. FCFS算法公平性最好解析A错误SSTF可能导致饥饿B错误SCAN到达最远端后会改变方向C错误C-SCAN返回时不服务D正确。选D。8️⃣ 记忆口诀FCFS按序来SSTF找最近。SCAN像电梯到顶再回移。C-SCAN单向走返回不服务。9️⃣ 小测验评论区对答案磁头初始在50向磁道号增大的方向请求序列为10, 80, 30, 90, 60。采用SCAN算法服务顺序为 。A. 60→80→90→30→10B. 60→80→90→10→30C. 60→90→80→30→10D. 80→90→60→30→10本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #磁盘调度 #FCFS #SSTF #SCAN #C-SCAN #操作系统