磁盘调度算法：SCAN 算法和 C-SCAN 算法的平均寻道长度计算

假设磁盘共有 200 个磁道，当前磁头位于 100 号磁道，有以下磁盘访问请求序列：40、56、39、28、90、163、155、48、190。现在使用 SCAN 算法和 C-SCAN 算法计算平均寻道长度。

SCAN 算法

将请求序列按照磁道号从小到大排序：28、39、40、48、56、90、155、163、190。
从当前磁道号 100 开始，向外扫描，直到最外侧的磁道号 199，然后返回最里侧的磁道号 0，再向外扫描，直到请求序列中最后一个磁道号 190。
在扫描过程中，如果发现有请求序列中的磁道号与当前磁道号相同，就将其删除，并计算当前磁道号移动的距离。
最后将移动距离求和并除以请求序列的长度，即为平均寻道长度。

具体的计算过程如下：

从 100 开始，向外扫描：100->155->163->190->199->48->40->39->28->56->90->0->155->163->190

移动距离 = 55 + 8 + 27 + 9 + 151 + 151 + 10 + 11 + 11 + 28 + 34 + 90 + 155 + 27 + 27 = 636

平均寻道长度 = 636 / 9 ≈ 70.67

C-SCAN 算法

将请求序列按照磁道号从小到大排序：28、39、40、48、56、90、155、163、190。
从当前磁道号 100 开始，向外扫描，直到最外侧的磁道号 199，然后直接返回最里侧的磁道号 0，再向外扫描，直到请求序列中最后一个磁道号 190。
在扫描过程中，如果发现有请求序列中的磁道号与当前磁道号相同，就将其删除，并计算当前磁道号移动的距离。
最后将移动距离求和并除以请求序列的长度，即为平均寻道长度。

具体的计算过程如下：

从 100 开始，向外扫描：100->155->163->190->199->0->28->39->40->48->56->90->155->163->190

移动距离 = 55 + 8 + 27 + 9 + 199 + 28 + 11 + 1 + 8 + 8 + 8 + 65 + 65 + 27 = 501

平均寻道长度 = 501 / 9 ≈ 55.67

算法原理

SCAN 算法 (电梯调度算法)

SCAN 算法将磁盘请求按照磁道号从小到大排序，并从当前磁道号开始，向一个方向扫描，直到扫描到最外侧的磁道号，然后返回最里侧的磁道号，再继续向相反的方向扫描，直到请求序列的最后一个磁道号。在扫描过程中，如果发现有请求序列中的磁道号与当前磁道号相同，就将其删除，并计算当前磁道号移动的距离。

C-SCAN 算法 (循环扫描算法)

C-SCAN 算法与 SCAN 算法类似，将磁盘请求按照磁道号从小到大排序，并从当前磁道号开始，向一个方向扫描，直到扫描到最外侧的磁道号，然后直接返回最里侧的磁道号，再继续向相同的方向扫描，直到请求序列的最后一个磁道号。在扫描过程中，如果发现有请求序列中的磁道号与当前磁道号相同，就将其删除，并计算当前磁道号移动的距离。与 SCAN 算法不同的是，C-SCAN 算法不需要在请求序列的最后一个磁道号停下来，而是直接返回最里侧的磁道号。

总结

SCAN 算法和 C-SCAN 算法都是常用的磁盘调度算法，它们都能够有效地减少磁盘寻道时间，提高磁盘访问效率。C-SCAN 算法比 SCAN 算法更加公平，因为它不会偏向于某个方向的请求。在实际应用中，应该根据具体情况选择合适的磁盘调度算法。