面试题：设备管理之中等难度：磁盘调度算法的应用

Question

假设系统中有一个磁盘，当前磁头位于第50号磁道，有以下几个磁道访问请求序列：30, 85, 100, 20, 120。请分别使用先来先服务（FCFS）、最短寻道时间优先（SSTF）和扫描（SCAN）算法计算磁头移动的总距离，并说明每种算法的优缺点。

Answer 1

先来先服务（FCFS）算法

1. 计算磁头移动总距离： 磁头从50号磁道开始，依次访问30, 85, 100, 20, 120。

• 从50到30，移动距离为|50 - 30| = 20。
• 从30到85，移动距离为|30 - 85| = 55。
• 从85到100，移动距离为|85 - 100| = 15。
• 从100到20，移动距离为|100 - 20| = 80。
• 从20到120，移动距离为|20 - 120| = 100。 总移动距离 = 20 + 55 + 15 + 80 + 100 = 270。

2. 优缺点：

• 优点：实现简单，公平对待每个请求，按照请求到达的顺序处理。
• 缺点：可能导致平均寻道时间较长，尤其是当请求序列随机分布时，磁头会在磁盘上频繁移动，效率较低。

最短寻道时间优先（SSTF）算法

1. 计算磁头移动总距离： 磁头从50号磁道开始，距离50最近的是30，然后是20，接着是85，100，120。

• 从50到30，移动距离为|50 - 30| = 20。
• 从30到20，移动距离为|30 - 20| = 10。
• 从20到85，移动距离为|20 - 85| = 65。
• 从85到100，移动距离为|85 - 100| = 15。
• 从100到120，移动距离为|100 - 120| = 20。 总移动距离 = 20 + 10 + 65 + 15 + 20 = 130。

2. 优缺点：

• 优点：平均寻道时间比FCFS短，优先处理距离当前磁头近的请求，减少了磁头移动的距离，提高了效率。
• 缺点：可能会出现“饥饿”现象，即一些距离当前磁头远的请求长时间得不到处理。而且需要预先知道所有请求的磁道位置信息。

扫描（SCAN）算法

1. 计算磁头移动总距离： 假设磁头向磁道号增加的方向移动（从50开始），先访问85，100，120，然后反向访问30，20。

• 从50到85，移动距离为|50 - 85| = 35。
• 从85到100，移动距离为|85 - 100| = 15。
• 从100到120，移动距离为|100 - 120| = 20。
• 从120到30，移动距离为|120 - 30| = 90。
• 从30到20，移动距离为|30 - 20| = 10。 总移动距离 = 35 + 15 + 20 + 90 + 10 = 170。

2. 优缺点：

• 优点：避免了“饥饿”现象，因为磁头会扫描整个磁盘，每个请求最终都会被处理。而且平均寻道时间相对较短，效率较高。
• 缺点：实现相对复杂，需要维护磁头的移动方向等信息。并且在某些情况下，可能会出现磁头移动距离较长的情况，例如请求集中在磁盘的一端时。