操作系统磁道调度算法 王道

### 操作系统磁道调度算法原理及实现

#### FCFS (First-Come, First-Served) 算法
FCFS 是最简单的磁盘调度算法之一。该算法按照请求到达的顺序处理磁盘 I/O 请求，不考虑其他因素。对于给定的例子，初始磁头位置为53号磁道，磁头向内移动。

- **磁头移动路径**: 53 → 98 → 138 → 37 → 122 → 14 → 124 → 65 → 67
- **总寻道长度**: |53−98|+|98−138|+|138−37|+|37−122|+|122−14|+|14−124|+|124−65|+|65−67|=301[^1]
- **平均寻道长度**: 总寻道长度 / 请求次数 = 301 / 8 ≈ 37.625

def fcfs(initial_position, requests):
    current_position = initial_position
    total_distance = 0
    
    for request in requests:
        distance = abs(current_position - request)
        total_distance += distance
        current_position = request
        
    average_distance = total_distance / len(requests)
    
    return total_distance, average_distance

#### SSTF (Shortest Seek Time First) 算法
SSTF 算法总是选择距离当前磁头最近的那个未完成的服务请求作为下一个要服务的对象。这可以减少不必要的等待时间并提高效率。

- 对于相同的例子，在每次选择最小绝对差值的情况下：
- 初始状态：53 -> 最近的是65(12), 更新后的序列变为[65]+其余项...

最终得到更短且合理的访问路径

#### SCAN (Elevator) 算法
SCAN 算法类似于电梯的工作方式。当磁臂从一端移向另一端时，会依次响应沿途遇到的所有读写请求；一旦达到边界，则改变方向继续扫描直到再次触及相反边界的极限为止。

- 假设磁头朝内侧运动（即从小到大），则先按升序排列所有小于等于当前位置的数列部分{14,37}加上大于它的剩余元素组成的有序列表{65,67,98,122,124,138}
- 结果形成了一条平滑过渡而不会频繁折返的路线图

#### C-SCAN (Circular SCAN) 算法
C-SCAN 可视为改进版SCAN方法，区别在于后者返回起点时不直接跳跃而是绕过整个圆周回到起始处重新开始新一轮循环。因此即使某些区域暂时无待处理任务也能保持均匀分布特性而不至于造成局部热点现象。

- 同样条件下构建环形队列结构来模拟此过程即可获得相应解集