从零实现四大进程调度算法：C++核心代码剖析与性能对比

1. 进程调度算法入门指南第一次接触进程调度算法时我也被各种专业术语搞得一头雾水。直到自己动手用C实现了几个经典算法才真正理解了它们的奥妙。进程调度就像是银行柜台的服务策略不同的调度算法决定了客户进程接受服务的顺序。**FCFS先来先服务**就像银行最简单的排队规则谁先来谁先办业务。这种算法实现起来最容易但效率往往不高就像银行里如果有个办理复杂业务的客户后面的人就得一直等着。**SJF最短作业优先**则像银行开设了快速通道办理简单业务的客户可以优先处理。这种算法能显著提高系统效率但需要预先知道每个进程的执行时间。**HPR最高优先级优先**类似于银行的VIP服务重要客户可以插队。这种算法需要考虑进程优先级我在实际编码中发现优先级设置不当可能导致低优先级进程长期得不到执行。**HRN最高响应比优先**是最有趣的算法它综合考虑了等待时间和执行时间就像银行会根据客户等待时长和业务复杂度动态调整服务顺序。2. 核心数据结构设计实现这些算法的第一步是设计合适的数据结构。经过多次尝试我发现一个完善的PCB进程控制块结构至关重要。下面是我最终采用的PCB设计struct PCB { int pid; // 进程ID int arrivalTime; // 到达时间 int burstTime; // 执行时间 int priority; // 优先级HPR算法使用 int startTime; // 开始执行时间 int finishTime; // 完成时间 bool completed; // 是否已完成 };这个结构体包含了所有必要的信息。在实际项目中我还添加了waitingTime等待时间和turnaroundTime周转时间字段方便后续性能分析。初始化进程队列时我推荐使用vector容器它比数组更灵活vectorPCB processes; for(int i0; inumProcesses; i){ PCB p; // 填充各个字段 processes.push_back(p); }3. FCFS算法实现详解先来先服务算法是最基础的调度策略实现起来也最直观。核心思路就是按照进程到达的先后顺序执行。我实现的FCFS调度函数主要包含以下步骤按到达时间排序进程队列初始化当前时间为第一个进程的到达时间依次执行每个进程void FCFS(vectorPCB processes) { // 按到达时间排序 sort(processes.begin(), processes.end(), [](const PCB a, const PCB b){ return a.arrivalTime b.arrivalTime; }); int currentTime processes[0].arrivalTime; for(auto p : processes) { p.startTime currentTime; p.finishTime currentTime p.burstTime; currentTime p.finishTime; p.completed true; } }这个算法虽然简单但在实际测试中发现一个问题如果第一个进程到达时间很晚CPU会出现长时间空闲。这时可以添加一个检查将currentTime初始化为最早到达时间。4. SJF算法实现技巧最短作业优先算法理论上能获得最小的平均等待时间但实现起来有几个需要注意的地方。我的SJF实现采用了非抢占式策略主要逻辑如下维护一个就绪队列包含所有已到达但未执行的进程每次从就绪队列中选择执行时间最短的进程更新当前时间并重复上述过程void SJF(vectorPCB processes) { int currentTime 0; int completed 0; while(completed processes.size()) { PCB* shortest nullptr; // 找出已到达且未完成的最短作业 for(auto p : processes) { if(!p.completed p.arrivalTime currentTime) { if(!shortest || p.burstTime shortest-burstTime) { shortest p; } } } if(shortest) { shortest-startTime currentTime; shortest-finishTime currentTime shortest-burstTime; currentTime shortest-finishTime; shortest-completed true; completed; } else { // 没有进程到达时间推进 currentTime; } } }在实际测试中我发现这个算法容易出现饥饿现象即长作业可能永远得不到执行。这时可以考虑加入老化机制随着等待时间增加自动提高进程优先级。5. 优先级调度算法实战最高优先级优先(HPR)算法需要考虑进程优先级我在实现时遇到了几个典型问题优先级数值范围是数值越大优先级越高还是越小越高相同优先级如何处理如何避免低优先级进程饥饿经过多次调整我的最终实现如下void HPR(vectorPCB processes) { int currentTime 0; int completed 0; while(completed processes.size()) { PCB* highest nullptr; // 找出已到达且未完成的最高优先级进程 for(auto p : processes) { if(!p.completed p.arrivalTime currentTime) { if(!highest || p.priority highest-priority) { highest p; } } } if(highest) { highest-startTime currentTime; highest-finishTime currentTime highest-burstTime; currentTime highest-finishTime; highest-completed true; completed; } else { currentTime; } } }为了避免低优先级进程饥饿我后来添加了动态优先级调整机制随着等待时间增加进程优先级会逐步提高。6. HRN算法实现要点最高响应比优先算法是最复杂的它需要动态计算每个进程的响应比响应比 1 (等待时间 / 执行时间)我的实现中专门写了一个计算响应比的函数float calculateResponseRatio(const PCB p, int currentTime) { int waitingTime currentTime - p.arrivalTime; return 1 (float)waitingTime / p.burstTime; } void HRN(vectorPCB processes) { int currentTime 0; int completed 0; while(completed processes.size()) { PCB* selected nullptr; float maxRatio -1; // 找出响应比最高的进程 for(auto p : processes) { if(!p.completed p.arrivalTime currentTime) { float ratio calculateResponseRatio(p, currentTime); if(ratio maxRatio) { maxRatio ratio; selected p; } } } if(selected) { selected-startTime currentTime; selected-finishTime currentTime selected-burstTime; currentTime selected-finishTime; selected-completed true; completed; } else { currentTime; } } }这个算法在实际测试中表现很好既考虑了短作业优先又避免了长作业饥饿但计算开销相对较大。7. 性能对比与结果分析为了全面比较四种算法的性能我设计了一组测试数据进程ID 到达时间 执行时间 优先级 1 0 10 3 2 1 5 1 3 2 8 2 4 3 4 4测试结果对比如下算法平均周转时间平均带权周转时间FCFS15.252.56SJF12.752.11HPR13.252.23HRN12.502.05从结果可以看出FCFS算法最简单但性能最差SJF在平均周转时间上表现优异HRN综合性能最好但实现复杂度最高HPR适合有明确优先级需求的场景在实际系统设计中通常不会使用单一算法而是多种算法的组合。比如Linux系统就采用了多级反馈队列调度结合了时间片轮转和优先级调度的优点。