C++磁盘调度算法详解（从零开始掌握FCFS、SSTF与SCAN算法）

1. 先来先服务算法（FCFS）

先来先服务算法是最简单的调度策略：按照请求到达的顺序依次处理。虽然公平，但效率通常不高。

C++实现示例：

#include <iostream>#include <vector>#include <cmath>using namespace std;int fcfs(const vector<int>& requests, int head) {    int totalSeek = 0;    int current = head;        cout << "FCFS 调度顺序: " << head;    for (int req : requests) {        totalSeek += abs(req - current);        current = req;        cout << " -> " << req;    }    cout << endl;        return totalSeek;}int main() {    vector<int> requests = {98, 183, 37, 122, 14, 124, 65, 67};    int head = 53;        int seekTime = fcfs(requests, head);    cout << "总寻道时间: " << seekTime << endl;        return 0;}  

2. 最短寻道时间优先（SSTF）

最短寻道时间优先每次选择离当前磁头位置最近的请求进行处理。这能有效减少总移动距离，但可能导致某些请求“饥饿”（长时间得不到响应）。

C++实现思路：

• 维护一个未处理请求列表
• 每次遍历找出距离当前磁头最近的请求
• 将其加入调度序列并从列表中移除

int sstf(vector<int> requests, int head) {    int totalSeek = 0;    int current = head;    vector<bool> visited(requests.size(), false);        cout << "SSTF 调度顺序: " << head;        for (int i = 0; i < requests.size(); ++i) {        int closestIndex = -1;        int minDistance = INT_MAX;                for (int j = 0; j < requests.size(); ++j) {            if (!visited[j]) {                int dist = abs(requests[j] - current);                if (dist < minDistance) {                    minDistance = dist;                    closestIndex = j;                }            }        }                visited[closestIndex] = true;        totalSeek += minDistance;        current = requests[closestIndex];        cout << " -> " << current;    }    cout << endl;        return totalSeek;}  

3. 扫描算法（SCAN）

扫描算法C++实现模拟电梯运行：磁头沿一个方向移动，处理路径上的所有请求，直到到达磁盘一端，再反向扫描。因此也叫“电梯算法”。

关键步骤：

1. 将请求分为小于和大于当前磁头位置的两组
2. 对两组分别排序
3. 按当前移动方向依次处理

int scan(vector<int> requests, int head, bool towardsEnd = true) {    vector<int> left, right;        for (int r : requests) {        if (r < head)            left.push_back(r);        else            right.push_back(r);    }        sort(left.begin(), left.end(), greater<int>());   // 降序    sort(right.begin(), right.end());               // 升序        int totalSeek = 0;    int current = head;        cout << "SCAN 调度顺序: " << head;        if (towardsEnd) {        for (int r : right) {            totalSeek += abs(r - current);            current = r;            cout << " -> " << r;        }        // 到达末端后反向        for (int r : left) {            totalSeek += abs(r - current);            current = r;            cout << " -> " << r;        }    } else {        for (int r : left) {            totalSeek += abs(r - current);            current = r;            cout << " -> " << r;        }        for (int r : right) {            totalSeek += abs(r - current);            current = r;            cout << " -> " << r;        }    }    cout << endl;        return totalSeek;}  

总结

通过本教程，我们学习了三种核心的C++磁盘调度算法：

• 先来先服务算法：简单但效率低
• 最短寻道时间优先：高效但可能造成饥饿
• 扫描算法C++实现：兼顾公平与效率，实际系统常用

建议读者动手编写完整程序，修改请求序列和初始磁头位置，观察不同算法的表现差异。掌握这些基础算法，是深入理解操作系统I/O管理的重要一步！