用C++模拟操作系统：手把手教你实现四种进程调度算法（附完整可运行代码）

用C++模拟操作系统：手把手教你实现四种进程调度算法（附完整可运行代码）

在计算机科学领域，操作系统作为硬件与应用程序之间的桥梁，其核心功能之一就是进程调度。想象一下，当多个程序同时请求CPU资源时，操作系统如何决定谁先谁后？这就是进程调度算法要解决的问题。对于计算机专业的学生和初级开发者来说，理解这些抽象概念最好的方式莫过于亲手实现它们。本文将带你用C++从零构建一个完整的进程调度模拟器，涵盖FCFS、SJF、HPR和HRN四种经典算法。

1. 环境准备与基础设计

1.1 项目结构与开发环境

我们推荐使用以下工具链进行开发：

• 编译器：GCC 9.0+ 或 Clang 10+
• 构建工具：CMake 3.15+
• 编辑器：VS Code 或 CLion

项目目录结构建议如下：

scheduler_simulator/ ├── include/ │ └── pcb.h # 进程控制块定义 ├── src/ │ ├── fcfs.cpp # FCFS算法实现 │ ├── sjf.cpp # SJF算法实现 │ ├── hpr.cpp # HPR算法实现 │ └── hrn.cpp # HRN算法实现 └── main.cpp # 主程序入口

1.2 进程控制块(PCB)设计

PCB是操作系统中表示进程的核心数据结构，我们的实现需要考虑以下字段：

struct PCB { int pid; // 进程ID int arrival_time; // 到达时间 int burst_time; // 需要执行时间 int priority; // 优先级（仅HPR需要） int start_time = -1;// 开始执行时间 int finish_time; // 完成时间 // 计算周转时间 int turnaround_time() const { return finish_time - arrival_time; } // 计算带权周转时间 double weighted_turnaround() const { return static_cast<double>(turnaround_time()) / burst_time; } };

注意：实际项目中应考虑使用智能指针管理PCB内存，避免手动内存管理错误。

2. 先来先服务(FCFS)算法实现

2.1 算法原理与特点

FCFS(First Come First Serve)是最简单的调度算法，其核心规则就一条：先到先得。就像超市排队结账，谁先来谁就先被服务。

算法特性：

• 非抢占式：一旦开始执行，直到进程完成
• 公平性：严格按照到达顺序处理
• 缺点：可能导致短作业长时间等待（"护航效应"）

2.2 完整实现代码

void schedule_fcfs(std::vector<PCB>& processes) { std::sort(processes.begin(), processes.end(), [](const PCB& a, const PCB& b) { return a.arrival_time < b.arrival_time; }); int current_time = 0; for (auto& p : processes) { if (current_time < p.arrival_time) { current_time = p.arrival_time; } p.start_time = current_time; p.finish_time = current_time + p.burst_time; current_time = p.finish_time; } }

2.3 性能分析示例

假设有如下进程序列：

调度结果将呈现以下特点：

• 平均周转时间： (10 + 14 + 21)/3 = 15
• 平均带权周转时间： (1 + 2.8 + 2.625)/3 ≈ 2.14

3. 短作业优先(SJF)算法实现

3.1 算法优化思路

SJF(Shortest Job First)试图解决FCFS的护航效应，其核心思想是：优先执行耗时最短的作业。这就像聪明的银行柜员会先处理快速的简单业务。

关键实现难点在于：

1. 如何动态选择当前可运行的最短作业
2. 处理新作业到达时的调度决策

3.2 非抢占式SJF实现

void schedule_sjf(std::vector<PCB>& processes) { std::sort(processes.begin(), processes.end(), [](const PCB& a, const PCB& b) { return a.arrival_time < b.arrival_time; }); int current_time = 0; std::vector<PCB*> ready_queue; auto next_shortest = [&]() -> PCB* { PCB* shortest = nullptr; for (auto& p : processes) { if (!p.start_time && p.arrival_time <= current_time) { if (!shortest || p.burst_time < shortest->burst_time) { shortest = &p; } } } return shortest; }; while (std::any_of(processes.begin(), processes.end(), [](const PCB& p) { return p.start_time == -1; })) { if (auto p = next_shortest()) { p->start_time = current_time; p->finish_time = current_time + p->burst_time; current_time = p->finish_time; } else { current_time++; } } }

3.3 算法对比实验

使用相同进程集测试SJF：

可见SJF在平均性能上优于FCFS，但存在饥饿问题——长作业可能永远得不到执行。

4. 最高优先级(HPR)与最高响应比(HRN)算法

4.1 HPR算法实现

HPR(Highest Priority First)引入优先级概念，适合有不同重要程度的任务场景：

void schedule_hpr(std::vector<PCB>& processes) { // 按优先级排序，数字越大优先级越高 std::sort(processes.begin(), processes.end(), [](const PCB& a, const PCB& b) { return a.priority > b.priority; }); int current_time = 0; for (auto& p : processes) { p.start_time = current_time; p.finish_time = current_time + p.burst_time; current_time = p.finish_time; } }

4.2 HRN算法创新

HRN(Highest Response Ratio Next)是SJF的改进版，通过动态计算响应比来平衡等待时间和执行时间：

响应比 = 1 + (等待时间 / 执行时间)

实现关键点：

double calculate_response_ratio(const PCB& p, int current_time) { int wait_time = current_time - p.arrival_time; return 1 + static_cast<double>(wait_time) / p.burst_time; } void schedule_hrn(std::vector<PCB>& processes) { int current_time = 0; while (!processes.empty()) { // 找出当前响应比最高的进程 auto it = std::max_element(processes.begin(), processes.end(), [current_time](const PCB& a, const PCB& b) { return calculate_response_ratio(a, current_time) < calculate_response_ratio(b, current_time); }); it->start_time = current_time; it->finish_time = current_time + it->burst_time; current_time = it->finish_time; processes.erase(it); } }

5. 可视化与性能对比

5.1 甘特图生成

我们可以用ASCII艺术展示调度顺序：

void print_gantt(const std::vector<PCB>& processes) { std::cout << "Gantt Chart:\n"; for (const auto& p : processes) { std::cout << "|P" << p.pid << " "; for (int i = 0; i < p.burst_time; ++i) { std::cout << "#"; } std::cout << "|"; } std::cout << "\n"; }

5.2 综合性能对比表

在实际系统设计中，通常会采用多级反馈队列等混合策略，结合不同算法的优势。这个模拟器项目可以进一步扩展支持更多算法和抢占式调度，建议尝试添加时间片轮转(RR)算法作为练习。