4. 磁盘调度算法（二）：SCAN（电梯算法）、C-SCAN、LOOK与C-LOOK的调度策略与性能分析

在上一节中，我们讨论了FCFS（先来先服务）和SSTF（最短寻道时间优先）两种基础调度算法。FCFS公平但效率低下，SSTF虽然减少了平均寻道时间，却容易导致“饥饿”现象（即远离磁头的请求长时间得不到服务）。为了解决这些问题，计算机科学家从日常生活中的电梯运行机制中获得了灵感，设计出了SCAN算法及其一系列变种。

本节将深入剖析SCAN（电梯算法）、C-SCAN（循环扫描）、LOOK与C-LOOK四种算法的核心调度策略、工作流程、性能指标以及适用场景。通过对比分析，你将理解这些算法如何在“公平性”与“吞吐量”之间取得平衡。

4.1 SCAN（电梯算法）

SCAN算法，因其工作方式与电梯运行高度相似，也被称为“电梯算法”（Elevator Algorithm）。其核心思想是：磁头从磁盘的一端开始，向另一端移动，在移动过程中处理沿途经过的所有I/O请求；当到达磁盘的另一端（边界）时，立即改变移动方向，继续处理新方向上的请求。

4.1.1 工作流程

1. 初始化方向：磁头选择一个初始移动方向（通常向外或向内）。
2. 单向扫描：磁头沿当前方向移动，每经过一个柱面，检查该柱面是否有等待的I/O请求。若有，则处理该请求。
3. 到达边界：当磁头移动到磁盘的物理边界（柱面0或最大柱面号）时，立即反转移动方向。
4. 反向扫描：磁头沿相反方向移动，继续处理沿途的请求。
5. 重复：重复步骤2-4，直到所有请求被处理完毕。

4.1.2 性能分析

4.2 C-SCAN（循环扫描算法）

C-SCAN（Circular SCAN）是SCAN算法的一个改进版本，旨在解决SCAN算法中“边界区域请求等待时间过长”的问题。其核心思想是：磁头始终沿一个方向移动（例如从外向内），处理沿途请求；到达磁盘末端后，不反向，而是立即快速返回到磁盘的起始端，然后再次开始单向扫描。

4.2.1 工作流程

1. 单向扫描：磁头从磁盘一端（如柱面0）开始，向另一端（如最大柱面）移动，处理沿途所有请求。
2. 快速回扫：到达磁盘末端后，磁头立即以最高速度返回起始端，此过程中不处理任何I/O请求。
3. 重复扫描：回到起始端后，再次开始新一轮的单向扫描。

4.2.2 性能分析

4.3 LOOK 与 C-LOOK

SCAN和C-SCAN算法的一个明显缺点是：它们总是将磁头移动到磁盘的物理边界，即使边界附近没有任何待处理的I/O请求。这导致了不必要的寻道时间浪费。LOOK和C-LOOK算法正是为了解决这个问题而设计的，它们通过“前瞻”（Look Ahead）机制，只移动到当前方向上最远的请求柱面，而不是物理边界。

4.3.1 LOOK 算法

LOOK算法是SCAN算法的优化版本。它不再机械地移动到磁盘边界，而是“看一眼”当前方向上还有没有请求。如果没有，则立即反转方向。

• 调度策略：磁头沿当前方向移动，处理沿途请求。当该方向上没有更多请求时，立即反转方向，而不是继续移动到磁盘边界。
• 优势：避免了SCAN算法中不必要的边界行程，显著减少了平均寻道时间。
• 劣势：与SCAN类似，刚经过的区域的新请求仍需等待磁头到达最远请求并返回后才能被服务。

4.3.2 C-LOOK 算法

C-LOOK算法是C-SCAN算法的优化版本，也是LOOK算法的循环版本。它结合了C-SCAN的“单向服务+快速回扫”策略和LOOK的“智能边界”策略。

• 调度策略：磁头沿一个方向移动，处理沿途请求。当该方向上没有更多请求时，立即快速返回到当前方向上最远的请求柱面（而不是磁盘起始端），然后再次开始单向扫描。
• 优势：在C-SCAN的基础上，进一步减少了快速回扫的距离，是四种算法中平均寻道时间最短、公平性最好的算法之一。
• 适用场景：现代操作系统和数据库系统中广泛使用，特别是在高并发、大负载的磁盘I/O场景下。

4.4 四种算法性能对比与选择

为了帮助你更直观地理解这四种算法的性能差异，下表从多个维度进行了对比。在实际系统设计中，选择哪种算法取决于具体的负载特征和性能目标。

4.5 代码示例：LOOK 算法核心逻辑

以下是一个简化的C语言伪代码，展示了LOOK算法的核心调度逻辑。它维护了一个请求队列，并根据当前磁头位置和移动方向来决定下一个要服务的请求。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_REQUESTS 100
#define DISK_SIZE 200  // 假设磁盘有200个柱面

// 请求结构体
typedef struct {
    int track;      // 目标柱面号
    bool serviced;  // 是否已被服务
} Request;

// 判断当前方向上是否还有未服务的请求
bool has_request_in_direction(Request requests[], int n, int current_track, int direction) {
    for (int i = 0; i < n; i++) {
        if (!requests[i].serviced) {
            if (direction == 1 && requests[i].track > current_track) return true;  // 向外
            if (direction == -1 && requests[i].track < current_track) return true; // 向内
        }
    }
    return false;
}

// 在当前方向上找到最近的请求（LOOK算法的核心）
int find_next_request(Request requests[], int n, int current_track, int direction) {
    int next_track = -1;
    int min_distance = DISK_SIZE;

    for (int i = 0; i < n; i++) {
        if (!requests[i].serviced) {
            int distance = requests[i].track - current_track;
            // 检查是否在当前方向上
            if ((direction == 1 && distance > 0) || (direction == -1 && distance < 0)) {
                int abs_distance = abs(distance);
                if (abs_distance < min_distance) {
                    min_distance = abs_distance;
                    next_track = requests[i].track;
                }
            }
        }
    }
    return next_track;
}

// LOOK 调度主函数
void look_schedule(Request requests[], int n, int start_track) {
    int current_track = start_track;
    int direction = 1; // 1: 向外（柱面号增大）, -1: 向内（柱面号减小）
    int total_seek_distance = 0;
    int serviced_count = 0;

    printf("LOOK 调度开始，起始柱面: %d\n", start_track);

    while (serviced_count < n) {
        // 检查当前方向是否还有请求
        if (has_request_in_direction(requests, n, current_track, direction)) {
            // 找到当前方向上最近的请求
            int next_track = find_next_request(requests, n, current_track, direction);
            if (next_track != -1) {
                int seek_distance = abs(next_track - current_track);
                total_seek_distance += seek_distance;
                current_track = next_track;

                // 标记该请求为已服务
                for (int i = 0; i < n; i++) {
                    if (!requests[i].serviced && requests[i].track == next_track) {
                        requests[i].serviced = true;
                        serviced_count++;
                        printf("  服务请求: 柱面 %d, 寻道距离: %d, 当前位置: %d\n",
                               next_track, seek_distance, current_track);
                        break;
                    }
                }
            }
        } else {
            // 当前方向没有请求，反转方向（LOOK算法的关键）
            direction = -direction;
            printf("  当前方向无请求，反转方向为: %s\n", direction == 1 ? "向外" : "向内");
        }
    }

    printf("LOOK 调度结束，总寻道距离: %d\n", total_seek_distance);
}

int main() {
    // 示例请求序列
    Request requests[] = {
        {98, false}, {183, false}, {37, false}, {122, false},
        {14, false}, {124, false}, {65, false}, {67, false}
    };
    int n = sizeof(requests) / sizeof(requests[0]);
    int start_track = 53;

    look_schedule(requests, n, start_track);
    return 0;
}

4.6 本章小结

本章深入剖析了SCAN、C-SCAN、LOOK和C-LOOK四种磁盘调度算法。我们从“电梯算法”的灵感出发，逐步分析了每种算法如何通过不同的策略来平衡吞吐量、公平性和响应时间。从SCAN的“边界反转”到C-SCAN的“快速回扫”，再到LOOK和C-LOOK的“智能前瞻”，每一次改进都旨在减少不必要的磁头移动，并降低请求的最大等待时间。理解这些算法的设计哲学和性能特征，对于构建高性能的存储系统至关重要。