【操作系统】：一文带你了解磁盘调度算法

IsLand1314

发布于 2025-07-18 14:42:13

40700

代码可运行

文章被收录于专栏：学习之路学习之路

运行总次数：0

代码可运行

一、前言 – 关于磁盘

磁盘（硬盘，HDD）是一种机械式存储设备，其 结构图如下：

1. 磁盘的基本组成

① 盘片（Platter）

功能：盘片的表面涂有磁性物质，这些磁性物质用来记录二进制数据。因为正反两面都可涂上磁性物质，故一个盘片可能会有两个盘面
特点：
- 一个磁盘（如一个 1T 的机械硬盘）由多个盘片（如上图中的 0 号盘片）叠加而成（多盘片设计可增加容量）
- 数据以同心圆（磁道）形式存储在盘片表面

② 磁头（Read/Write Head）

功能：读取或写入数据的机械臂末端装置，悬浮在盘片表面（通过空气动力学原理，与盘片保持极小间隙）。
特点：
- 每个盘片表面有一个磁头，多个磁头固定在同一磁头臂（Actuator Arm）上，同步移动。
- 磁头通过改变磁性材料的极性（写入）或检测极性（读取）来操作数据。

③ 主轴（Spindle）

功能：驱动盘片高速旋转的电机轴，决定盘片的转速（如 5400 RPM、7200 RPM、10000 RPM）。
转速影响 ：转速越高，**旋转延迟（Rotational Latency）**越低。

④ 磁道（Track）

定义：盘片上的一圈同心圆，每个磁道存储一定量的数据。
特点：磁道编号从外向内递增（最外层为 0 号磁道），靠近主轴的同心园用于停靠磁头，不存储数据

⑤ 扇区（Sector）

定义：磁道被划分为多个扇区，每个扇区存储固定大小的数据（通常为 512 字节或 4KB）。
特点：
- 扇区是磁盘数据读写的最小单位。
- 每个扇区包含数据、地址信息（如磁道号、扇区号）和校验码（CRC）

如下图：

⑥ 柱面（Cylinder）

定义：所有盘片上相同半径的磁道组成一个柱面（Cylinder）。例如，如果硬盘有 4 个盘片，则每个柱面包含 8 个磁道（每个盘片的上下表面各一个）。
作用：柱面是磁盘寻道操作的基本单位，减少磁头臂移动次数

磁盘容量 = 磁头数 x 磁道(柱面)数 x 毎道扇区数 x 毎扇区字节数

2. 磁盘的工作原理

磁盘通过机械运动和磁性技术实现数据的读写

（1）数据存储方式

磁性记录 ：数据以二进制形式存储为磁性变化。磁头通过改变磁性材料的极性（写入）或检测极性（读取）来操作数据。
编码方式 ：现代硬盘使用PRML（部分响应最大似然）*或* EPRML 技术提高存储密度。

（2）数据访问过程

由上，可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。

在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块（逻辑地址），这个块号就可以转换成（柱面号，盘面号，扇区号）的地址形式。

可根据该地址读取一个“块”，操作如下：

寻道（Seek）：根据“柱面号”移动磁臂，让磁头指向目标磁道所在柱面
旋转延迟（Rotational Latency）：等待目标扇区旋转到磁头下方
数据传输（Transfer）：磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写

磁盘访问时间由以下三部分组成：

寻道时间（Seek Time） ：磁头移动到目标磁道所需时间，约 3-15 毫秒（取决于硬盘型号和磁头移动距离）
旋转延迟（Rotational Latency） ：磁盘旋转到目标扇区所需时间（取决转速，如7200 RPM硬盘平均延迟约

\frac{60}{7200*2}=4.17ms

）

传输时间（Transfer Time） ：读取或写入数据的时间（取决于数据块大小和磁盘带宽），如，传输 1MB 数据（带宽 100MB/s）需要 10 毫秒

优化重点 ：寻道时间通常占主导，因此磁盘调度主要针对减少磁头移动距离。

3. 磁盘的性能指标

(1) 容量（Capacity）

定义：磁盘可存储的总数据量，单位为 GB 或 TB。
影响因素 ：盘片数量、单盘片存储密度、扇区大小。

(2) 转速（RPM, Revolutions Per Minute）

定义：盘片每分钟旋转的次数，如 5400 RPM、7200 RPM、10000 RPM。
影响：转速越高，旋转延迟越低，但噪音和功耗增加。

(3) 缓存（Cache）

定义：硬盘内置的高速内存（通常为几 MB 到几百 MB），用于临时存储频繁访问的数据。
作用：减少磁头频繁移动，提升读写效率。

(4) 平均寻道时间（Average Seek Time）

定义：磁头从一个磁道移动到另一个随机磁道所需的平均时间。
典型值 ：3-15 毫秒。

(5) 数据传输率（Data Transfer Rate）

定义：单位时间内传输的数据量，分为内部传输率 （磁盘内部读写）和外部传输率 （接口到主机）。
影响因素 ：磁盘接口（如 SATA、SCSI）、盘片转速、存储密度。

4. HDD vs SSD

特性	HDD（机械硬盘）	SSD（固态硬盘）
存储原理	磁性存储，机械读写	电子存储（NAND 闪存），无机械部件
访问速度	慢（寻道时间和旋转延迟）	快（直接电子访问，无延迟）
耐用性	易磨损（机械部件）	寿命有限（写入次数限制）
功耗	高（电机和磁头运动）	低
价格	低（按容量计算）	高
适用场景	大容量存储（如备份、冷数据）	高速读写（如系统盘、数据库）

二、磁盘调度算法简介

(1) 先来先服务（FCFS, First-Come-First-Served）

原理：FIFO 算法按照请求到达的顺序进行服务。无论磁头当前位置和请求磁道位置如何，总是先处理最早到达的请求。

优点: 实现逻辑简单，易于理解和实现。
缺点: 不考虑磁盘物理特性（磁头位置），可能导致磁头频繁来回移动，寻道效率低下，平均寻道时间较长。
适用场景 ：请求较少或无法预测请求模式时。

示例：

磁头初始位置：50
请求队列：[95, 180, 34, 119, 11, 123, 62, 64]
处理顺序：50 → 95 → 180 → 34 → 119 → 11 → 123 → 62 → 64
总寻道距离： (45)+(85)+(146)+(85)+(108)+(112)+(61)+(2) = 644

(2) 最短寻道时间优先（SSTF, Shortest Seek Time First）

原理：SSTF 算法的核心思想是 “就近服务”。它总是选择离当前磁头位置最近的那个磁道请求进行服务。这样做可以最大程度地减少单次寻道时间，从而通常能获得较短的平均寻道时间

优点：寻道时间短，吞吐量高。
缺点：可能导致“饥饿”现象（starvation）。如果磁头附近不断有新的请求到来，远离磁头的请求可能长时间得不到服务。此外，每次都需要遍历所有未处理请求以找到最近的，开销相对较大。
适用场景 ：追求平均响应时间最短。

示例：磁头初始位置：50

请求队列：[95, 180, 34, 119, 11, 123, 62, 64]

处理顺序：

50 → 62（+12）
62 → 64（+2）
64 → 34（-30）
34 → 11（-23）
11 → 95（+84）
95 → 119（+24）
119 → 123（+4）
123 → 180（+57）

总寻道距离：12+2+30+23+84+24+4+57 = 236

(3) 扫描算法（SCAN, 电梯算法）

原理：SCAN 算法（也称电梯算法）模拟电梯的运行方式。磁头从当前位置开始，沿一个方向（例如，磁道号增大的方向）移动并服务该方向上的所有请求，直到到达磁盘的最远端（或该方向上最后一个请求）。然后，它会反向移动，并服务另一个方向上的所有请求，直到到达另一端（或该方向上最后一个请求）

优点：解决了 SSTF 的饥饿问题，因为磁头会扫描整个磁盘范围，所有请求最终都会被服务。相对 SSTF 提供了更公平的等待时间
缺点：磁头会强制移动到磁盘的边缘，即使在边缘方向没有请求，也需要额外的寻道时间
适用场景 ：平衡公平性和效率。

示例：磁头初始位置：50，方向：向右

请求队列：[95, 180, 34, 119, 11, 123, 62, 64]

处理顺序：

50 → 62 → 64 → 95 → 119 → 123 → 180（到右端）
反向：180 → 34（经过中间未处理的请求）
34->11

总寻道距离：(12)+(2)+(31)+(24)+(4)+(57)+(180-34=146) + (34-11=23) = 299

(4) 循环扫描（C-SCAN, Circular SCAN）

原理： C-SCAN 算法是 SCAN 算法的改进版，旨在提供更均匀的等待时间。磁头从当前位置开始向一个方向（例如，磁道号增大的方向）扫描并服务请求，直到到达磁盘的一段（如： 最大磁道），或者说这个方法上已经没有其他请求为止。然后，它会 立即跳回 到磁盘的另一端（如：最小磁道），并从那里重新开始向同一方向（磁道号增大的方向）扫描和服务的循环。这个从最大磁道跳回最小磁道的寻道距离会计入总寻道长度，但回程路上不处理任何请求

优点：提供了比 SCAN 更均匀的等待时间，因为它总是向一个方向服务，避免了磁头在回程途中服务请求导致某些请求等待时间过长
缺点：磁头在回程时不服务请求，这部分寻道开销是“浪费”的，但在某些场景下（如实时系统）均匀性可能比总寻道时间更重要
适用场景 ：适合均匀分布的请求

示例：

磁头初始位置：50，方向：向右

请求队列：[95, 180, 34, 119, 11, 123, 62, 64]

处理顺序：

50 → 62 → 64 → 95 → 119 → 123 → 180（到右端）
快速返回：180 → 11（忽略中间请求）
11 → 34 总寻道距离：(12)+(2)+(31)+(24)+(4)+(57) + (169) + (23) = 322

SCAN 和 CSCAN区别：

SCAN 更注重减少磁头移动距离，但可能导致边缘请求等待时间较长。
CSCAN 通过循环移动保证所有请求的响应时间更均匀，但回程的空转会增加总寻道距离。
选择依据 ：根据请求分布模式选择算法——SCAN 适合局部密集型请求，CSCAN 适合全局均匀型请求 。

3. 算法对比

算法	平均寻道时间	公平性	饥饿问题	适用场景
FCFS	高	高	无	简单环境
SSTF	最低	低	有	高吞吐量
SCAN	中等	中等	无	普遍适用
C-SCAN	中等	高	无	均匀请求

三、磁盘调度算法的模拟实现

1. 类基本框架和辅助函数实现

// 磁道范围  -- 用于SCAN/C-SCAN的边界处理
const int MIN_TRACK = 0;
const int MAX_TRACK = 999;

class DiskScheduler {
private:
	std::vector<int> _requests;	// 存储磁道请求序列
	int _currentHeadPos;			// 当前磁头存储位置

	// 统一输出调度结果
	void PrintSchedulingResults(const std::string& algorithmName,
        const std::vector<int>& path,
        double totalSeekLength,
        int numRequests)
    {
        std::cout << "\n--- " << algorithmName << " 调度结果 ---" << std::endl;
        std::cout << "寻道路径: ";
        for (int i = 0; i < path.size(); ++i) {
            std::cout << path[i];
            if (i < path.size() - 1) std::cout << "-> ";
        }
        std::cout << std::endl;

        std::cout << "总寻道长度: " << std::fixed << std::setprecision(2) << totalSeekLength << std::endl;
        if (numRequests > 0) {
            // 打印两位小数
            std::cout << "平均寻道长度: " << std::fixed << std::setprecision(2)
                << totalSeekLength / numRequests << std::endl;
        }
        else {
            std::cout << "没有磁道请求，无法计算平均寻道长度。" << std::endl;
        }
        std::cout << "--------------------------" << std::endl;
    }

	bool Empty() {
		if (_requests.empty()) {
			std::cout << "没有磁道请求需要处理！" << std::endl;
			return true;
		}
		return false;
	}

public:
	DiskScheduler(const std::vector<int>& requests)
		:_requests(requests), _currentHeadPos(0) {}

	~DiskScheduler() {
		_requests.clear();
		_currentHeadPos = 0;
	}
		
	// 获取用户输入磁道号, 并进行简单校验 prompt 是输入提醒字符串
	static int getValidatedTrackInput(const std::string& prompt) {
		int value;
		while (true) {
			if(!prompt.empty())std::cout << prompt;
			std::cin >> value;
			if (std::cin.fail() || value < MIN_TRACK || value > MAX_TRACK) {
				std::cout << "输入无效！磁道号应在 " << MIN_TRACK << " 到 " << MAX_TRACK
					<< " 之间。请重新输入。" << std::endl;
				std::cin.clear(); // 清除错误标志
				std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略错误输入
			}
			else {
				return value;
			}
		}
	}

	// 设置当前磁头位置
	void SetCurrentHead() {
		_currentHeadPos = getValidatedTrackInput("请输入当前所在的磁道号: ");
	}

	// 显示当前初识磁道请求序列
	void DisplayInitialRequests() const {
		int max_label_length = 0;
		for (size_t i = 1; i <= _requests.size(); ++i) {
			int len = std::to_string(i).length() + 1; // "R" + 数字的长度
			max_label_length = std::max(max_label_length, len);
		}

		// 设置固定字段宽度（标签+数值）
		int field_width = max_label_length + 3; // 标签+数值总宽度（如 "R1" + 3位数字）

		// 打印标签行
		for (size_t i = 1; i <= _requests.size(); ++i) {
			std::cout << std::setw(field_width) << "R" + std::to_string(i);
		}
		std::cout << std::endl;

		// 打印数值行
		for (int request : _requests) {
			std::cout << std::setw(field_width) << request;
		}

		std::cout << "\n----------------------" << std::endl;
	}

	// 顺序处理
	void RunFCFS(bool true){
		if (Empty()) return;
		
        // ...
       	PrintSchedulingResults("FIFO", path, totalSeekLength, _requests.size());
    }

	void RunSSTF(bool flag = true){
        if (Empty()) return;
        if (flag == true) SetCurrentHead();
		// ...
        PrintSchedulingResults("SSTF", path, totalSeekLength, _requests.size());
	}

	void RunSCAN(bool flag = true) {
		if (Empty()) return;
        if (flag == true) SetCurrentHead();
        // ...
        PrintSchedulingResults("SCAN", path, totalSeekLength, _requests.size());
	}

	void RunCSCAN(bool flag = true) {
        if (Empty()) return;
        if (flag == true) SetCurrentHead();
		// ...
        PrintSchedulingResults("C-SCAN", path, totalSeekLength, _requests.size());
	}

    void RunAll() {
		SetCurrentHead();
		RunFCFS(false); RunSSTF(false);
		RunSCAN(false); RunCSCAN(false);
	}
    
	// 显示主菜单
	void displayMenu() const {
		std::cout << "\n============== 磁盘调度算法模拟 ==============" << std::endl;
		std::cout << "1. 先进先出算法（FIFO）" << std::endl;
		std::cout << "2. 最短服务时间优先算法（SSTF）" << std::endl;
		std::cout << "3. 扫描算法（SCAN）" << std::endl;
		std::cout << "4. 循环扫描算法（C-SCAN）" << std::endl;
		std::cout << "5. 退出" << std::endl;
		std::cout << "==============================================" << std::endl;
		std::cout << "请选择： ";
	}
	
};

2. 算法函数模拟实现

2.1 FCFS

void RunFCFS(bool flag = true){
	if (Empty()) return;
	if(flag == true) SetCurrentHead();

	std::vector<int> remainingRequests = _requests; //备份
	std::vector<int> path; // 路径
	path.push_back(_currentHeadPos);
	double totalSeekLength = 0;  // 总长
	int currentTrack = _currentHeadPos; // 当前轨道位置

	for(int request: _requests) {
		path.emplace_back(request);
		totalSeekLength += std::abs(request - currentTrack);
		currentTrack = request;
	}
	PrintSchedulingResults("FIFO", path, totalSeekLength, _requests.size());
}

代码实现分析:

if (Empty()) return;: 首先检查请求序列是否为空，如果为空则直接返回。
if(flag == true) SetCurrentHead();: 如果 flag 为真（默认情况），则提示用户输入当前磁头位置。这使得在单独运行 FIFO 时可以设置磁头位置，而在 RunAll 中统一设置一次即可。
std::vector<int> path; path.push_back(_currentHeadPos);: path 向量用于记录磁头移动的完整路径，从当前磁头位置开始。
double totalSeekLength = 0; int currentTrack = _currentHeadPos;: 初始化总寻道长度和当前磁头位置。
for(int request: _requests) { ... }: 遍历原始的 _requests 向量，因为 FIFO 不改变请求顺序。
- path.emplace_back(request);: 将当前服务的请求磁道添加到寻道路径中。
- totalSeekLength += std::abs(request - currentTrack);: 计算从 currentTrack 到 request 的绝对距离，并累加到 totalSeekLength。
- currentTrack = request;: 更新 currentTrack 为刚刚服务的请求磁道，作为下一次寻道计算的起点。
PrintSchedulingResults("FIFO", path, totalSeekLength, _requests.size());: 调用辅助函数打印 FIFO 调度结果。

2.2 SSTF

void RunSSTF(bool flag = true){
	if (Empty()) return;
	if (flag == true) SetCurrentHead();

	std::vector<int> remainingRequests = _requests; //备份
	std::vector<int> path; // 路径
	path.push_back(_currentHeadPos);
	double totalSeekLength = 0;  // 总长
	int currentTrack = _currentHeadPos; // 当前轨道位置

	while (!remainingRequests.empty()) {
		// 最小距离  下个轨道位置
		int shortestDistance = -1, nextTrackIndex = -1;

		// 找每次剩余磁头中距离当前最近的轨道（绝对距离）
		for (size_t i = 0; i < remainingRequests.size(); ++i) {
			int dis = std::abs(remainingRequests[i] - currentTrack);
			if (nextTrackIndex == -1 || dis < shortestDistance) {
				shortestDistance = dis;
				nextTrackIndex = i;
			}
		}

		// 此时就是最近, 然后处理走到下一个轨道
		totalSeekLength += shortestDistance;
		currentTrack = remainingRequests[nextTrackIndex];
		path.emplace_back(currentTrack);
		remainingRequests.erase(remainingRequests.begin() + nextTrackIndex);
	}
	PrintSchedulingResults("SSTF", path, totalSeekLength, _requests.size());
}

代码实现分析:

if (Empty()) return; / SetCurrentHead();: 与 FIFO 类似，进行空检查并设置磁头位置。
std::vector<int> remainingRequests = _requests;: 关键一步。创建原始请求的副本 remainingRequests。这是因为 SSTF 会修改（删除）已被服务的请求，我们不能直接修改原始 _requests 向量，以确保其他算法能够使用原始数据。
path, totalSeekLength, currentTrack: 初始化与 FIFO 类似。
while (!remainingRequests.empty()) { ... }: 循环直到所有请求都被服务。
- 寻找最近请求:
  - int shortestDistance = -1, nextTrackIndex = -1; 初始化最短距离和对应请求的索引。
  - for (size_t i = 0; i < remainingRequests.size(); ++i) { ... }：遍历 remainingRequests 中的每一个请求。
  - int dis = std::abs(remainingRequests[i] - currentTrack);: 计算当前请求到磁头的距离。
  - if (nextTrackIndex == -1 || dis < shortestDistance) { ... }: 如果这是第一个请求，或者当前请求的距离比已知的 shortestDistance 更短，则更新 shortestDistance 和 nextTrackIndex。
- 服务最近请求:
  - totalSeekLength += shortestDistance;: 累加找到的最短距离。
  - currentTrack = remainingRequests[nextTrackIndex];: 更新磁头位置到刚刚服务的请求磁道。
  - path.emplace_back(currentTrack);: 将服务过的磁道添加到路径。
  - remainingRequests.erase(remainingRequests.begin() + nextTrackIndex);: 从 remainingRequests 中移除已被服务的请求。这是 SSTF 区别于 FIFO 的重要操作。
PrintSchedulingResults("SSTF", path, totalSeekLength, _requests.size());: 打印结果。

2.3 SCAN

void RunSCAN(bool flag = true) {
	if (Empty()) return;
	if (flag == true) SetCurrentHead();

	std::vector<int> sortedRequests = _requests; // 升序轨道
	std::sort(sortedRequests.begin(), sortedRequests.end());

	std::vector<int> path;
	path.push_back(_currentHeadPos);
	double totalSeekLength = 0; // 总数
	int currentTrack = _currentHeadPos; // 当前轨道

	// 使用二分查找当前轨道的大于等于轨道
	// 方式一：适用于随机访问容器 (vector)
	// int startIndex = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos) - sortedRequests.begin(); 
	// 方式二：适用于所有容器
	auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);
	int startIndex = std::distance(sortedRequests.begin(), it);

	// 升序往右走
	for (int i = startIndex; i < sortedRequests.size(); ++i) {
		// 当前轨道和下一个轨道距离
		totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
		currentTrack = sortedRequests[i];
		path.emplace_back(currentTrack);
	}
	for (int i = startIndex - 1; i >= 0; --i) {
		totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
		currentTrack = sortedRequests[i];
		path.push_back(currentTrack);
	}
	PrintSchedulingResults("SCAN", path, totalSeekLength, _requests.size());
}

代码实现分析:

if (Empty()) return; / SetCurrentHead();: 检查和设置磁头位置。
std::vector<int> sortedRequests = _requests; std::sort(sortedRequests.begin(), sortedRequests.end());: 关键一步。对请求序列进行升序排序，方便后续按顺序扫描。同样，使用副本避免修改原始数据。
path, totalSeekLength, currentTrack: 初始化。
auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);: 使用 std::lower_bound 找到在排序后的 sortedRequests 中，第一个大于或等于 _currentHeadPos 的请求的位置。这确定了磁头开始向右扫描的起始点。
int startIndex = std::distance(sortedRequests.begin(), it);: 获取起始点的索引。
向右（高磁道号）扫描:
- for (int i = startIndex; i < sortedRequests.size(); ++i) { ... }: 从 startIndex 开始，遍历到 sortedRequests 的末尾，服务所有大于等于当前磁头位置的请求。
- totalSeekLength += std::abs(sortedRequests[i] - currentTrack);：累加寻道距离。
- currentTrack = sortedRequests[i]; path.emplace_back(currentTrack);：更新磁头位置和路径。
向左（低磁道号）扫描:
- for (int i = startIndex - 1; i >= 0; --i) { ... }: 从 startIndex - 1 （即当前磁头左侧的第一个请求）开始，反向遍历到 sortedRequests 的开头，服务所有小于当前磁头位置的请求。
- totalSeekLength += std::abs(sortedRequests[i] - currentTrack);：累加寻道距离。
- currentTrack = sortedRequests[i]; path.push_back(currentTrack);：更新磁头位置和路径。

2.4 C-SCAN

void RunCSCAN(bool flag = true) {
	if (Empty()) return;
	if (flag == true) SetCurrentHead();

	std::vector<int> sortedRequests = _requests; // 升序轨道
	std::sort(sortedRequests.begin(), sortedRequests.end());

	std::vector<int> path;
	path.push_back(_currentHeadPos);
	double totalSeekLength = 0; // 总数
	int currentTrack = _currentHeadPos; // 当前轨道

	// 二分
	auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);
	int startIndex = std::distance(sortedRequests.begin(), it);

	// 升序往右走
	for (int i = startIndex; i < sortedRequests.size(); ++i) {
		// 当前轨道和下一个轨道距离
		totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
		currentTrack = sortedRequests[i];
		path.emplace_back(currentTrack);
	}
	
	// 从最左端开始
	for (int i = 0; i < startIndex; ++i) {
		totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
		currentTrack = sortedRequests[i];
		path.push_back(currentTrack);
	}
	PrintSchedulingResults("C-SCAN", path, totalSeekLength, _requests.size());
}

代码实现分析:

if (Empty()) return; / SetCurrentHead();: 检查和设置磁头位置。
std::vector<int> sortedRequests = _requests; std::sort(sortedRequests.begin(), sortedRequests.end());: 排序请求。
path, totalSeekLength, currentTrack: 初始化。
auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);: 找到起始扫描点。
向右（高磁道号）扫描:
- for (int i = startIndex; i < sortedRequests.size(); ++i) { ... }: 从 startIndex 开始，向右服务所有请求。寻道距离累加方式与 SCAN 相同。
磁头回绕, 从最小磁道继续向右扫描:
- for (int i = 0; i < startIndex; ++i) { ... }: 从 sortedRequests 的开头（即最小磁道附近的请求）开始，服务所有在 startIndex 之前的请求。这些请求是在第一次向右扫描时被跳过的。
- totalSeekLength += std::abs(sortedRequests[i] - currentTrack);：累加寻道距离。
- currentTrack = sortedRequests[i]; path.push_back(currentTrack);：更新磁头位置和路径。
PrintSchedulingResults("C-SCAN", path, totalSeekLength, _requests.size());: 打印结果。

3. 实验测试

int main() {
	std::cout << "欢迎来到磁盘调度算法模拟器！\n";
	int numRequests;
	while (true) {
		std::cout << "请先输入磁道请求数量 (1-" << MAX_TRACK << ")： ";
		std::cin >> numRequests;
		if (std::cin.fail() || numRequests <= 0 || numRequests > MAX_TRACK) {
			std::cout << "输入无效！请求数量应为正整数且不超过 " << MAX_TRACK << "。请重新输入。\n";
			std::cin.clear();
            // 忽略缓冲区中当前行的所有字符（直到遇到换行符），防止无效输入残留在缓冲区中影响后续输入
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
		}
		else break;
	}
	std::vector<int> initialRequests(numRequests);
	std::cout << "请输入 " << numRequests << " 个磁道序列 (范围 " << MIN_TRACK << "-" << MAX_TRACK << ")：\n";
	for (int i = 0; i < numRequests; ++i) {
		initialRequests[i] = DiskScheduler::getValidatedTrackInput("请输入第 " + std::to_string(i + 1) + " 个磁道号: ");
		// initialRequests[i] = DiskScheduler::getValidatedTrackInput("");
	}

	DiskScheduler scheduler(initialRequests); // 创建调度器对象
	scheduler.DisplayInitialRequests(); // 显示初识请求
	while (true) {
		scheduler.displayMenu();
		int choice;
		std::cin >> choice;

		if (std::cin.fail()) {
			std::cout << "输入无效！请选择一个数字选项。" << std::endl;
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			continue;
		}

		switch (choice) {
		case 1:
			scheduler.RunFCFS();
			break;
		case 2:
			scheduler.RunSSTF();
			break;
		case 3:
			scheduler.RunSCAN();
			break;
		case 4:
			scheduler.RunCSCAN();
			break;
		case 5:
			scheduler.RunAll();
			break;
		case 6:
			std::cout << "\n感谢使用，再见！" << std::endl;
			return 0;
		default:
			std::cout << "选择错误，请重新选择 (1-5)！" << std::endl;
			break;
		}
		std::cout << std::endl; // 每次操作后换行，美观
	}
	return 0;
}

结果如下：

欢迎来到磁盘调度算法模拟器！
请先输入磁道请求数量 (1-999)： 8
请输入 8 个磁道序列 (范围 0-999)：
请输入第 1 个磁道号: 95
请输入第 2 个磁道号: 180
请输入第 3 个磁道号: 34
请输入第 4 个磁道号: 119
请输入第 5 个磁道号: 11
请输入第 6 个磁道号: 123
请输入第 7 个磁道号: 62
请输入第 8 个磁道号: 64
   R1   R2   R3   R4   R5   R6   R7   R8
   95  180   34  119   11  123   62   64
----------------------

============== 磁盘调度算法模拟 ==============
1. 先进先出算法（FCFS）
2. 最短服务时间优先算法（SSTF）
3. 扫描算法（SCAN）
4. 循环扫描算法（C-SCAN）
5. 对比所有算法（all）
6. 退出
==============================================
请选择： 5
请输入当前所在的磁道号: 50

--- FIFO 调度结果 ---
寻道路径: 50-> 95-> 180-> 34-> 119-> 11-> 123-> 62-> 64
总寻道长度: 644.00
平均寻道长度: 80.50
--------------------------

--- SSTF 调度结果 ---
寻道路径: 50-> 62-> 64-> 34-> 11-> 95-> 119-> 123-> 180
总寻道长度: 236.00
平均寻道长度: 29.50
--------------------------

--- SCAN 调度结果 ---
寻道路径: 50-> 62-> 64-> 95-> 119-> 123-> 180-> 34-> 11
总寻道长度: 299.00
平均寻道长度: 37.38
--------------------------

--- C-SCAN 调度结果 ---
寻道路径: 50-> 62-> 64-> 95-> 119-> 123-> 180-> 11-> 34
总寻道长度: 322.00
平均寻道长度: 40.25
--------------------------

四、完整代码及小结

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <string>
#include <iomanip>
#include <iterator>

// 数据
// 磁道请求队列:[95, 180, 34, 119, 11, 123, 62, 64]
// 当前磁道: 50

// 磁道范围  -- 用于SCAN/C-SCAN的边界处理
const int MIN_TRACK = 0;
const int MAX_TRACK = 999;

class DiskScheduler {
private:
	std::vector<int> _requests;	// 存储磁道请求序列
	int _currentHeadPos;	   // 当前磁头存储位置

	// 统一输出调度结果
	void PrintSchedulingResults(const std::string& algorithmName,
		const std::vector<int>& path,
		double totalSeekLength,
		int numRequests)
	{
		std::cout << "\n--- " << algorithmName << " 调度结果 ---" << std::endl;
		std::cout << "寻道路径: ";
		for (int i = 0; i < path.size(); ++i) {
			std::cout << path[i];
			if (i < path.size() - 1) std::cout << "-> ";
		}
		std::cout << std::endl;

		std::cout << "总寻道长度: " << std::fixed << std::setprecision(2) << totalSeekLength << std::endl;
		if (numRequests > 0) {
			// 打印两位小数
			std::cout << "平均寻道长度: " << std::fixed << std::setprecision(2)
				<< totalSeekLength / numRequests << std::endl;
		}
		else {
			std::cout << "没有磁道请求，无法计算平均寻道长度。" << std::endl;
		}
		std::cout << "--------------------------" << std::endl;
	}

	bool Empty() {
		if (_requests.empty()) {
			std::cout << "没有磁道请求需要处理！" << std::endl;
			return true;
		}
		return false;
	}

public:
	DiskScheduler(const std::vector<int>& requests)
		:_requests(requests), _currentHeadPos(0) {}

	~DiskScheduler() {
		_requests.clear();
		_currentHeadPos = 0;
	}
		
	// 获取用户输入磁道号, 并进行简单校验 prompt 是输入提醒字符串
	static int getValidatedTrackInput(const std::string& prompt) {
		int value;
		while (true) {
			if(!prompt.empty())std::cout << prompt;
			std::cin >> value;
			if (std::cin.fail() || value < MIN_TRACK || value > MAX_TRACK) {
				std::cout << "输入无效！磁道号应在 " << MIN_TRACK << " 到 " << MAX_TRACK
					<< " 之间。请重新输入。" << std::endl;
				std::cin.clear(); // 清除错误标志
				std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); // 忽略错误输入
			}
			else {
				return value;
			}
		}
	}

	// 设置当前磁头位置
	void SetCurrentHead() {
		_currentHeadPos = getValidatedTrackInput("请输入当前所在的磁道号: ");
	}

	// 显示当前初识磁道请求序列
	void DisplayInitialRequests() const {
		int max_label_length = 0;
		for (size_t i = 1; i <= _requests.size(); ++i) {
			int len = std::to_string(i).length() + 1; // "R" + 数字的长度
			max_label_length = std::max(max_label_length, len);
		}

		// 设置固定字段宽度（标签+数值）
		int field_width = max_label_length + 3; // 标签+数值总宽度（如 "R1" + 3位数字）

		// 打印标签行
		for (size_t i = 1; i <= _requests.size(); ++i) {
			std::cout << std::setw(field_width) << "R" + std::to_string(i);
		}
		std::cout << std::endl;

		// 打印数值行
		for (int request : _requests) {
			std::cout << std::setw(field_width) << request;
		}

		std::cout << "\n----------------------" << std::endl;
	}

	// 顺序处理原则
	void RunFCFS(bool flag = true){
		if (Empty()) return;
		if(flag == true) SetCurrentHead();

		std::vector<int> remainingRequests = _requests; //备份
		std::vector<int> path; // 路径
		path.push_back(_currentHeadPos);
		double totalSeekLength = 0;  // 总长
		int currentTrack = _currentHeadPos; // 当前轨道位置

		for(int request: _requests) {
			path.emplace_back(request);
			totalSeekLength += std::abs(request - currentTrack);
			currentTrack = request;
		}
		PrintSchedulingResults("FIFO", path, totalSeekLength, _requests.size());
	}

	// 最近处理原则
	void RunSSTF(bool flag = true){
		if (Empty()) return;
		if (flag == true) SetCurrentHead();

		std::vector<int> remainingRequests = _requests; //备份
		std::vector<int> path; // 路径
		path.push_back(_currentHeadPos);
		double totalSeekLength = 0;  // 总长
		int currentTrack = _currentHeadPos; // 当前轨道位置

		while (!remainingRequests.empty()) {
			// 最小距离  下个轨道位置
			int shortestDistance = -1, nextTrackIndex = -1;

			// 找每次剩余磁头中距离当前最近的轨道（绝对距离）
			for (size_t i = 0; i < remainingRequests.size(); ++i) {
				int dis = std::abs(remainingRequests[i] - currentTrack);
				if (nextTrackIndex == -1 || dis < shortestDistance) {
					shortestDistance = dis;
					nextTrackIndex = i;
				}
			}

			// 此时就是最近, 然后处理走到下一个轨道
			totalSeekLength += shortestDistance;
			currentTrack = remainingRequests[nextTrackIndex];
			path.emplace_back(currentTrack);
			remainingRequests.erase(remainingRequests.begin() + nextTrackIndex);
		}
		PrintSchedulingResults("SSTF", path, totalSeekLength, _requests.size());
	}

	// 基于当前轨道升序走, 走到尽头再回到起始轨道位置降序走
	void RunSCAN(bool flag = true) {
		if (Empty()) return;
		if (flag == true) SetCurrentHead();

		std::vector<int> sortedRequests = _requests; // 升序轨道
		std::sort(sortedRequests.begin(), sortedRequests.end());

		std::vector<int> path;
		path.push_back(_currentHeadPos);
		double totalSeekLength = 0; // 总数
		int currentTrack = _currentHeadPos; // 当前轨道

		// 使用二分查找当前轨道的大于等于轨道
		// 方式一：适用于随机访问容器 (vector)
		// int startIndex = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos) - sortedRequests.begin(); 
		// 方式二：适用于所有容器
		auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);
		int startIndex = std::distance(sortedRequests.begin(), it);

		// 升序往右走
		for (int i = startIndex; i < sortedRequests.size(); ++i) {
			// 当前轨道和下一个轨道距离
			totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
			currentTrack = sortedRequests[i];
			path.emplace_back(currentTrack);
		}
		for (int i = startIndex - 1; i >= 0; --i) {
			totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
			currentTrack = sortedRequests[i];
			path.push_back(currentTrack);
		}
		PrintSchedulingResults("SCAN", path, totalSeekLength, _requests.size());
	}
	
	// 和 SCAN 类似, 但是其回头的时候直接从最左端开始
	void RunCSCAN(bool flag = true) {
		if (Empty()) return;
		if (flag == true) SetCurrentHead();

		std::vector<int> sortedRequests = _requests; // 升序轨道
		std::sort(sortedRequests.begin(), sortedRequests.end());

		std::vector<int> path;
		path.push_back(_currentHeadPos);
		double totalSeekLength = 0; // 总数
		int currentTrack = _currentHeadPos; // 当前轨道

		// 二分
		auto it = std::lower_bound(sortedRequests.begin(), sortedRequests.end(), _currentHeadPos);
		int startIndex = std::distance(sortedRequests.begin(), it);

		// 升序往右走
		for (int i = startIndex; i < sortedRequests.size(); ++i) {
			// 当前轨道和下一个轨道距离
			totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
			currentTrack = sortedRequests[i];
			path.emplace_back(currentTrack);
		}
	

		// 从最左端开始
		for (int i = 0; i < startIndex; ++i) {
			totalSeekLength += std::abs(sortedRequests[i] - currentTrack);
			currentTrack = sortedRequests[i];
			path.push_back(currentTrack);
		}
		PrintSchedulingResults("C-SCAN", path, totalSeekLength, _requests.size());
	}

	void RunAll() {
		SetCurrentHead();
		RunFCFS(false); RunSSTF(false);
		RunSCAN(false); RunCSCAN(false);
	}

	// 显示主菜单
	void displayMenu() const {
		std::cout << "\n============== 磁盘调度算法模拟 ==============" << std::endl;
		std::cout << "1. 先进先出算法（FCFS）" << std::endl;
		std::cout << "2. 最短服务时间优先算法（SSTF）" << std::endl;
		std::cout << "3. 扫描算法（SCAN）" << std::endl;
		std::cout << "4. 循环扫描算法（C-SCAN）" << std::endl;
		std::cout << "5. 对比所有算法（all）" << std::endl;
		std::cout << "6. 退出" << std::endl;
		std::cout << "==============================================" << std::endl;
		std::cout << "请选择： ";
	}
	
};


int main() {
	std::cout << "欢迎来到磁盘调度算法模拟器！\n";
	int numRequests;
	while (true) {
		std::cout << "请先输入磁道请求数量 (1-" << MAX_TRACK << ")： ";
		std::cin >> numRequests;
		if (std::cin.fail() || numRequests <= 0 || numRequests > MAX_TRACK) {
			std::cout << "输入无效！请求数量应为正整数且不超过 " << MAX_TRACK << "。请重新输入。\n";
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
		}
		else break;
	}
	std::vector<int> initialRequests(numRequests);
	std::cout << "请输入 " << numRequests << " 个磁道序列 (范围 " << MIN_TRACK << "-" << MAX_TRACK << ")：\n";
	for (int i = 0; i < numRequests; ++i) {
		initialRequests[i] = DiskScheduler::getValidatedTrackInput("请输入第 " + std::to_string(i + 1) + " 个磁道号: ");
		// initialRequests[i] = DiskScheduler::getValidatedTrackInput("");
	}

	DiskScheduler scheduler(initialRequests); // 创建调度器对象
	scheduler.DisplayInitialRequests(); // 显示初识请求
	while (true) {
		scheduler.displayMenu();
		int choice;
		std::cin >> choice;

		if (std::cin.fail()) {
			std::cout << "输入无效！请选择一个数字选项。" << std::endl;
			std::cin.clear();
			std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
			continue;
		}

		switch (choice) {
		case 1:
			scheduler.RunFCFS();
			break;
		case 2:
			scheduler.RunSSTF();
			break;
		case 3:
			scheduler.RunSCAN();
			break;
		case 4:
			scheduler.RunCSCAN();
			break;
		case 5:
			scheduler.RunAll();
			break;
		case 6:
			std::cout << "\n感谢使用，再见！" << std::endl;
			return 0;
		default:
			std::cout << "选择错误，请重新选择 (1-5)！" << std::endl;
			break;
		}
		std::cout << std::endl; // 每次操作后换行，美观
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-06-22，如有侵权请联系 cloudcommunity@tencent.com 删除

操作系统