试题1
试题正文
请按以下要求回答问题。
答案：(惩罚系数: 0 %)
若干个等待访问磁盘者依次要访问的柱面如下所示，假设每移动一个柱面需要3毫秒时间，移动臂当前位于106号柱面，请按下列算法分别计算移动臂移动的过程，以及为完成各次访问总共花费的寻道时间。
访问柱面序列: 74, 153, 76, 179, 97, 100, 20, 150, 148
访问柱面序列: 74, 153, 76, 179, 97, 100, 20, 150, 148
注：
FCFS: 先来先服务算法
SSTF: 最短寻道时间优先算法(如果有两个柱面号与当前柱面号距离相同，则选择序列中靠前的柱面号，因此答案唯一)
SCANO: 电梯算法(向小柱面号移动)
SCANI: 电梯算法(向大柱面号移动)
CSCAN: 单向扫描算法
FCFS: 先来先服务算法
SSTF: 最短寻道时间优先算法(如果有两个柱面号与当前柱面号距离相同，则选择序列中靠前的柱面号，因此答案唯一)
SCANO: 电梯算法(向小柱面号移动)
SCANI: 电梯算法(向大柱面号移动)
CSCAN: 单向扫描算法
✅1. FCFS（First Come First Served）先来先服务
核心思想
按照请求到达磁盘调度队列的先后顺序服务。
访问顺序 = 到达顺序，不改变请求排列。
算法特性
实现简单。
不考虑磁头当前位置，可能造成频繁来回移动。
寻道时间可能较差。
优点
公平，不会饿死任何请求。
缺点
寻道距离可能非常大，整体性能较差。
✅2. SSTF（Shortest Seek Time First）最短寻道时间优先
核心思想
每次选择与“当前磁头位置”距离最近的柱面。
最小化“下一次的移动距离”。
处理方式
计算所有尚未完成请求与磁头的距离。
选距离最小的一个执行。
若有距离相同的，采用请求队列中的先后顺序。
算法特性
相比 FCFS，能显著减少寻道时间。
属于“局部优化”。
缺点
会造成饥饿：远离磁头的请求可能长期得不到处理。
✅3. SCAN（电梯算法）
SCAN 是磁头按一个方向连续移动到尽头，再反向移动的方式。
类似电梯在一端停下后，再按相反方向运行。
SCAN 有两个方向：
3.1 SCAN-O（向外，向小柱面方向）
规定磁头当前开始向柱面号减小的方向移动。
途中服务所有在该方向上的请求。
到达最小柱面后再反转方向，服务反方向的请求。
3.2 SCAN-I（向内，向大柱面方向）
规定磁头当前开始向柱面号增大的方向移动。
途中服务所有在该方向的请求。
到达最大柱面后再反转并服务反方向的请求。
电梯算法特点
避免来回跳动，改进整体性能。
相比 SSTF，更公平，不太会产生饥饿。
✅4. CSCAN（循环扫描算法）
核心思想
磁头只在一个方向移动（通常向大柱面号方向）。
到达磁盘一端后，磁头快速返回到起点，不处理任何请求。
形成 “环形扫描”。
算法步骤
按规定方向（例如向大号方向）移动磁头。
遇到请求就处理。
到达磁盘末端后，迅速跳回到起点（“回程”不处理请求）。
再次向同方向扫描。
特点
请求的平均等待时间更均衡。
消除 SCAN 算法在边界柱面的偏置问题。
🔍五种算法对比总结
| 算法 | 访问顺序依据 | 寻道性能 | 是否可能饥饿 | 方向控制 |
|---|---|---|---|---|
| FCFS | 到达顺序 | 差 | 否 | 无 |
| SSTF | 离磁头最近 | 好 | 是 | 无 |
| SCAN | 电梯式往返 | 好 | 否 | 双向（到端点再反向） |
| SCANO | SCAN 向小号方向开始 | 好 | 否 | 先向小号再向大号 |
| SCANI | SCAN 向大号方向开始 | 好 | 否 | 先向大号再向小号 |
| CSCAN | 单方向循环 | 较好且均衡 | 否 | 单方向，不反向 |
⭐ 一句话快速记忆
FCFS：来了就按顺序做。
SSTF：谁最近先做。
SCAN：像电梯一样来回扫。
SCANO：先向小号扫。
SCANI：先向大号扫。
CSCAN：单方向循环，另一方向不服务。
