操作系统中的磁盘调度算法 一、问题描述 磁盘调度算法是操作系统I/O子系统的核心组件之一，用于优化磁头移动顺序，减少寻道时间（即磁头移动到目标磁道的时间）。当多个进程请求访问磁盘的不同位置时，操作系统需决定处理I/O请求的顺序，以提升磁盘吞吐量和系统效率。 二、磁盘访问的物理背景 磁盘结构 ：磁盘由多个盘片组成，每个盘片被划分为同心圆磁道，磁道进一步划分为扇区。 磁头臂 ：通过移动磁头臂定位磁道，旋转磁盘使目标扇区移到磁头下方。 寻道时间 ：磁头移动至目标磁道的时间，是影响性能的主要因素（通常占磁盘访问延迟的绝大部分）。 三、常见磁盘调度算法及步骤 1. 先来先服务（FCFS） 描述 ：按请求到达的顺序处理。 示例 ：假设磁头初始位置在50号磁道，请求队列为 [100, 30, 85, 10] 。 移动顺序：50 → 100 → 30 → 85 → 10 总寻道距离 = |50-100| + |100-30| + |30-85| + |85-10| = 50 + 70 + 55 + 75 = 250 优缺点 ：公平但效率低，可能导致磁头频繁反向移动。 2. 最短寻道时间优先（SSTF） 描述 ：优先处理距当前磁头位置最近的请求。 示例 ：初始位置50，请求队列 [100, 30, 85, 10] 。 第一步：距50最近的请求是30（距离20），移动至30。 第二步：距30最近的请求是10（距离20），移动至10。 第三步：距10最近的请求是85（距离75），移动至85。 第四步：移动至100。 总寻道距离 = |50-30| + |30-10| + |10-85| + |85-100| = 20 + 20 + 75 + 15 = 130 优缺点 ：比FCFS高效，但可能导致饥饿（远离磁头的请求长期得不到处理）。 3. 扫描算法（SCAN，电梯算法） 描述 ：磁头沿一个方向移动，处理该方向上的所有请求，到达磁盘末端后反向。 示例 ：假设磁道范围0-199，初始位置50，方向为向磁道号增大方向移动，请求队列 [100, 30, 85, 10] 。 移动顺序：50 → 85 → 100 → 199（末端）→ 30 → 10 总寻道距离 = |50-85| + |85-100| + |100-199| + |199-30| + |30-10| = 35 + 15 + 99 + 169 + 20 = 338 优缺点 ：无饥饿问题，但末端请求的响应时间较长。 4. 循环扫描算法（C-SCAN） 描述 ：类似SCAN，但仅单向处理请求（如只向大磁道号方向移动），到达末端后立即返回起点重新开始。 示例 ：初始位置50，方向增大，请求队列同上。 移动顺序：50 → 85 → 100 → 199 → 0 → 10 → 30 总寻道距离 = |50-85| + |85-100| + |100-199| + |199-0| + |0-10| + |10-30| = 35+15+99+199+10+20=378 优缺点 ：响应时间更均匀，但返回起点可能增加空移动。 5. 查看算法（LOOK与C-LOOK） LOOK ：SCAN的改进，磁头移动到最远请求即反向，无需到磁盘末端。 示例：50 → 85 → 100 → 30 → 10，距离=35+15+70+20=140 C-LOOK ：C-SCAN的改进，返回时直接跳到最小请求位置。 示例：50 → 85 → 100 → 10 → 30，距离=35+15+90+20=160 四、算法选择因素 请求负载特征 ：随机访问或顺序访问。 公平性要求 ：SSTF可能饥饿，SCAN/C-SCAN更公平。 实际实现 ：现代磁盘控制器通常内置调度优化，操作系统可能结合I/O优先级策略。 五、总结 磁盘调度算法的核心目标是通过减少磁头移动距离来降低寻道时间。需权衡效率、公平性和响应时间，根据实际场景选择合适策略（如数据库服务器常用C-LOOK，通用系统可能用SSTF或SCAN变体）。