头歌实验5：从FCFS到HRRN，三大调度算法实战解析

1. 处理机调度算法入门指南第一次接触处理机调度算法时我也被各种专业术语搞得晕头转向。直到在实验室里用实际代码跑了一遍FCFS、SJF和HRRN三种算法才真正理解它们的区别。这就像在食堂打饭FCFS就是老老实实排队SJF是让饭量小的同学先打HRRN则是既考虑排队时间又考虑饭量的综合方案。进程调度的本质是决定哪个进程能获得CPU资源。想象你是一个操作系统内核面前有五个同学进程等着你批改作业CPU时间你会按照什么顺序处理这就是调度算法要解决的问题。实验用的数据结构很简单每个进程包含进程名如A、B、C到达时间同学来到办公室的时间服务时间需要批改的作业量完成时间实际结束时刻周转时间从来到走的总耗时带权周转时间周转时间与服务时间的比值通过这个实验你会直观看到不同算法如何影响进程的等待体验周转时间系统资源利用率CPU是否总在干活公平性与效率的权衡是否让短作业占便宜2. FCFS算法先到先得的朴素哲学2.1 算法原理与生活实例FCFS(First Come First Serve)就像老式理发店不管你要剪光头还是做造型都得按进门顺序排队。我们实验用的进程数据如下进程到达时间服务时间A03B26C44D65E82用C语言实现时关键点在于维护一个完成时间变量记录当前时刻新进程的完成时间 max(到达时间, 前一个进程的完成时间) 服务时间周转时间 完成时间 - 到达时间void FCFS(PCB pcb[N]) { pcb[0].finishTime pcb[0].arriveTime pcb[0].serveTime; for(int i1; iN; i) { if(pcb[i].arriveTime pcb[i-1].finishTime) { pcb[i].finishTime pcb[i-1].finishTime pcb[i].serveTime; } else { pcb[i].finishTime pcb[i].arriveTime pcb[i].serveTime; } pcb[i].aroundTime pcb[i].finishTime - pcb[i].arriveTime; pcb[i].waroundTime (float)pcb[i].aroundTime / pcb[i].serveTime; } }2.2 性能分析与缺陷跑完程序你会发现进程B的带权周转时间高达1.83——因为它虽然只需求6个时间单位却因为前面有个A挡着实际等了7个单位周转时间13。这就暴露了FCFS的致命伤** convoy效应**。就像高速公路上慢车挡道一个长进程会拖累后面所有进程。实测数据对比平均周转时间(3119116)/5 8.0平均带权周转时间(11.832.252.23)/5 2.06这个算法实现简单但性能波动大。我在实际项目中遇到过类似情况当系统突然来个耗时任务整个交互体验就会明显卡顿。3. SJF算法短作业优先的效率革命3.1 算法思想与实现技巧SJF(Shortest Job First)像智能取号机银行柜员会优先处理存款业务耗时短而非开户业务耗时长。实现时需要维护一个状态数组记录已调度进程每次选择已到达且服务时间最短的进程int findShortestJob(PCB pcb[N], int currentTime, int status[N]) { int minIndex -1; int minTime INT_MAX; for(int i0; iN; i) { if(!status[i] pcb[i].arriveTime currentTime pcb[i].serveTime minTime) { minTime pcb[i].serveTime; minIndex i; } } return minIndex; // 返回最短作业索引 } void SJF(PCB pcb[N]) { int status[N] {0}; int currentTime 0; for(int count0; countN; count) { int next findShortestJob(pcb, currentTime, status); if(next -1) { // 没有进程到达时时间推进 currentTime; continue; } pcb[next].finishTime currentTime pcb[next].serveTime; pcb[next].aroundTime pcb[next].finishTime - pcb[next].arriveTime; pcb[next].waroundTime (float)pcb[next].aroundTime / pcb[next].serveTime; currentTime pcb[next].finishTime; status[next] 1; } }3.2 优势与潜在问题同样的进程组SJF的调度顺序变为A(0)→E(8)→C(4)→D(6)→B(2)。性能指标显著提升平均周转时间降为7.2平均带权周转时间降为1.57但我在实验室踩过坑如果不断有短作业到达长作业可能饿死。就像快餐店总是优先做外卖订单堂食顾客可能永远等不到餐。这引出了我们需要更智能的算法——HRRN。4. HRRN算法响应比衡量的平衡之道4.1 动态优先级的艺术HRRN(Highest Response Ratio Next)的响应比公式响应比 (等待时间 服务时间) / 服务时间这相当于在SJF基础上给等待久的进程加分。实现时需要实时计算每个就绪进程的响应比选择响应比最高者调度float calculateResponseRatio(PCB p, int currentTime) { return (float)(currentTime - p.arriveTime p.serveTime) / p.serveTime; } void HRRN(PCB pcb[N]) { int status[N] {0}; int currentTime 0; for(int count0; countN; count) { int selected -1; float maxRatio -1; for(int i0; iN; i) { if(!status[i] pcb[i].arriveTime currentTime) { float ratio calculateResponseRatio(pcb[i], currentTime); if(ratio maxRatio) { maxRatio ratio; selected i; } } } if(selected -1) { currentTime; continue; } pcb[selected].finishTime currentTime pcb[selected].serveTime; pcb[selected].aroundTime pcb[selected].finishTime - pcb[selected].arriveTime; pcb[selected].waroundTime (float)pcb[selected].aroundTime / pcb[selected].serveTime; currentTime pcb[selected].finishTime; status[selected] 1; } }4.2 平衡性的体现运行结果显示出良好的折中特性进程B不再像SJF那样最后处理平均周转时间7.6介于FCFS和SJF之间平均带权周转时间1.68避免了极端情况这让我想起实际项目中的经验纯粹的公平FCFS或效率SJF都可能引发问题而动态权重往往是更优解。HRRN虽然计算开销略大但在交互式系统中表现优异。