闪电系列操作系统期末闪学 | 处理机调度算法导读期末考试临近还在为操作系统的处理机调度算法头秃本文是「闪电系列」期末速成指南涵盖三级调度层次、8大核心算法对比、必考计算公式及经典例题详解。内容精炼、表格清晰、计算过程完整助你高效复习稳拿高分建议收藏背诵考前必看一、处理机三级调度层次1. 高级调度作业调度调度频率最低适用仅多道批处理系统分时、实时系统无功能从外存后备队列中选择作业调入内存创建进程、分配资源放入就绪队列核心问题接纳多少作业接纳哪些作业2. 低级调度进程调度调度频率最高适用多道批处理、分时、实时系统功能从就绪队列中选择进程将CPU分配给该进程3. 中级调度中程调度功能将暂时无法运行的进程调至外存挂起状态进程具备运行条件且内存空闲时重新调入内存转为就绪状态挂入就绪队列理解提示高级调度决定“谁进内存”中级调度决定“谁暂离内存”低级调度决定“谁用CPU”。三者协同实现系统资源的高效利用。二、调度算法分类与适用场景算法名称核心特点适用范围先来先服务FCFS利于长进程不利于短进程作业调度、进程调度短作业优先SJF优先调度运行时间短的进程作业调度、进程调度高优先权优先调度支持动态优先权作业调度、进程调度高响应比优先HRRN兼顾短作业与等待时间作业调度、进程调度轮转调度算法RR按时间片轮流执行分时系统多级反馈队列算法多队列分级调度分时系统最早截止时间优先EDF按截止时间先后调度实时系统最低松弛度优先LLF按松弛度大小调度实时系统背诵速记三级调度高级作业、中级、低级进程分时系统时间片轮转、多级反馈队列实时系统最早截止时间优先、最低松弛度优先通用类作业/进程均可用先来先服务、短作业优先、高优先权优先、高响应比优先✍️记忆口诀“高作低进中挂起分时轮转反馈队实时截止松弛度通用四法要牢记。”三、核心计算公式周转时间完成时间−到达时间周转时间 完成时间 - 到达时间周转时间完成时间−到达时间进程从到达系统到完成的总时长带权周转时间周转时间服务时间带权周转时间 \frac{周转时间}{服务时间}带权周转时间服务时间周转时间平均周转时间∑所有进程周转时间进程总数平均周转时间 \frac{\sum 所有进程周转时间}{进程总数}平均周转时间进程总数∑所有进程周转时间平均带权周转时间∑所有进程带权周转时间进程总数平均带权周转时间 \frac{\sum 所有进程带权周转时间}{进程总数}平均带权周转时间进程总数∑所有进程带权周转时间高响应比等待时间服务时间服务时间1等待时间服务时间高响应比 \frac{等待时间 服务时间}{服务时间} 1 \frac{等待时间}{服务时间}高响应比服务时间等待时间服务时间1服务时间等待时间⚠️注意带权周转时间反映调度公平性值越接近1越理想平均带权周转时间是评价算法性能的关键指标。四、经典调度算法计算例题已知条件5个进程的到达时间与服务时间如下忽略I/O与其他调度开销。进程到达时间服务时间A03B26C44D65E821. 先来先服务FCFS规则最早进入就绪队列的进程优先执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C4491392.25D651318122.4E821820126平均周转时间379121258.6平均周转时间 \frac{3791212}{5} 8.6平均周转时间537912128.6平均带权周转时间11.172.252.4652.56平均带权周转时间 \frac{11.172.252.46}{5} 2.56平均带权周转时间511.172.252.462.562. 短作业优先SJF- 非抢占式规则每次选择当前就绪队列中运行时间最短的进程执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C441115112.75D651520142.8E8291131.5平均周转时间371114357.6平均周转时间 \frac{3711143}{5} 7.6平均周转时间537111437.6平均带权周转时间11.172.752.81.551.84平均带权周转时间 \frac{11.172.752.81.5}{5} 1.84平均带权周转时间511.172.752.81.51.843. 短作业优先SJF- 抢占式最短剩余时间优先规则新就绪进程的剩余运行时间若短于当前运行进程的剩余时间则抢占CPU进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B26315132.17C444841D651520142.8E8281021平均周转时间313414257.2平均周转时间 \frac{3134142}{5} 7.2平均周转时间531341427.2平均带权周转时间12.1712.8151.59平均带权周转时间 \frac{12.1712.81}{5} 1.59平均带权周转时间512.1712.811.594. 高响应比优先HRRN规则每次选择当前就绪队列中响应比最高的进程执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C4491392.25D651520142.8E82131573.5平均周转时间37914758平均周转时间 \frac{379147}{5} 8平均周转时间53791478平均带权周转时间11.172.252.83.552.14平均带权周转时间 \frac{11.172.252.83.5}{5} 2.14平均带权周转时间511.172.252.83.52.14 总结与备考建议算法平均周转时间平均带权周转时间优势劣势FCFS8.62.56简单公平对短作业极不友好SJF非抢占7.61.84平均性能较好可能饥饿长作业SJF抢占7.21.59最优平均性能实现复杂频繁切换HRRN8.02.14兼顾长短作业需动态计算响应比✅考试重点提醒务必掌握四种算法的手动推演过程尤其是抢占式SJF的时间线划分高响应比的计算是高频考点注意等待时间当前时刻−到达时间等待时间 当前时刻 - 到达时间等待时间当前时刻−到达时间区分“非抢占”与“抢占”SJF的执行顺序差异背诵速记部分可直接用于简答题或选择题。闪电系列·期末闪学| 用最少的字拿最多的分如果这篇对你有帮助欢迎点赞、收藏⭐、关注三连支持更多操作系统速成内容敬请期待《内存管理》《文件管理》《死锁》等后续篇章评论区互动你在做调度算法题时最容易错在哪一步欢迎留言交流一起避坑 （闪电系列）操作系统期末闪学 | 处理机调度算法
闪电系列操作系统期末闪学 | 处理机调度算法导读期末考试临近还在为操作系统的处理机调度算法头秃本文是「闪电系列」期末速成指南涵盖三级调度层次、8大核心算法对比、必考计算公式及经典例题详解。内容精炼、表格清晰、计算过程完整助你高效复习稳拿高分建议收藏背诵考前必看一、处理机三级调度层次1. 高级调度作业调度调度频率最低适用仅多道批处理系统分时、实时系统无功能从外存后备队列中选择作业调入内存创建进程、分配资源放入就绪队列核心问题接纳多少作业接纳哪些作业2. 低级调度进程调度调度频率最高适用多道批处理、分时、实时系统功能从就绪队列中选择进程将CPU分配给该进程3. 中级调度中程调度功能将暂时无法运行的进程调至外存挂起状态进程具备运行条件且内存空闲时重新调入内存转为就绪状态挂入就绪队列理解提示高级调度决定“谁进内存”中级调度决定“谁暂离内存”低级调度决定“谁用CPU”。三者协同实现系统资源的高效利用。二、调度算法分类与适用场景算法名称核心特点适用范围先来先服务FCFS利于长进程不利于短进程作业调度、进程调度短作业优先SJF优先调度运行时间短的进程作业调度、进程调度高优先权优先调度支持动态优先权作业调度、进程调度高响应比优先HRRN兼顾短作业与等待时间作业调度、进程调度轮转调度算法RR按时间片轮流执行分时系统多级反馈队列算法多队列分级调度分时系统最早截止时间优先EDF按截止时间先后调度实时系统最低松弛度优先LLF按松弛度大小调度实时系统背诵速记三级调度高级作业、中级、低级进程分时系统时间片轮转、多级反馈队列实时系统最早截止时间优先、最低松弛度优先通用类作业/进程均可用先来先服务、短作业优先、高优先权优先、高响应比优先✍️记忆口诀“高作低进中挂起分时轮转反馈队实时截止松弛度通用四法要牢记。”三、核心计算公式周转时间完成时间−到达时间周转时间 完成时间 - 到达时间周转时间完成时间−到达时间进程从到达系统到完成的总时长带权周转时间周转时间服务时间带权周转时间 \frac{周转时间}{服务时间}带权周转时间服务时间周转时间平均周转时间∑所有进程周转时间进程总数平均周转时间 \frac{\sum 所有进程周转时间}{进程总数}平均周转时间进程总数∑所有进程周转时间平均带权周转时间∑所有进程带权周转时间进程总数平均带权周转时间 \frac{\sum 所有进程带权周转时间}{进程总数}平均带权周转时间进程总数∑所有进程带权周转时间高响应比等待时间服务时间服务时间1等待时间服务时间高响应比 \frac{等待时间 服务时间}{服务时间} 1 \frac{等待时间}{服务时间}高响应比服务时间等待时间服务时间1服务时间等待时间⚠️注意带权周转时间反映调度公平性值越接近1越理想平均带权周转时间是评价算法性能的关键指标。四、经典调度算法计算例题已知条件5个进程的到达时间与服务时间如下忽略I/O与其他调度开销。进程到达时间服务时间A03B26C44D65E821. 先来先服务FCFS规则最早进入就绪队列的进程优先执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C4491392.25D651318122.4E821820126平均周转时间379121258.6平均周转时间 \frac{3791212}{5} 8.6平均周转时间537912128.6平均带权周转时间11.172.252.4652.56平均带权周转时间 \frac{11.172.252.46}{5} 2.56平均带权周转时间511.172.252.462.562. 短作业优先SJF- 非抢占式规则每次选择当前就绪队列中运行时间最短的进程执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C441115112.75D651520142.8E8291131.5平均周转时间371114357.6平均周转时间 \frac{3711143}{5} 7.6平均周转时间537111437.6平均带权周转时间11.172.752.81.551.84平均带权周转时间 \frac{11.172.752.81.5}{5} 1.84平均带权周转时间511.172.752.81.51.843. 短作业优先SJF- 抢占式最短剩余时间优先规则新就绪进程的剩余运行时间若短于当前运行进程的剩余时间则抢占CPU进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B26315132.17C444841D651520142.8E8281021平均周转时间313414257.2平均周转时间 \frac{3134142}{5} 7.2平均周转时间531341427.2平均带权周转时间12.1712.8151.59平均带权周转时间 \frac{12.1712.81}{5} 1.59平均带权周转时间512.1712.811.594. 高响应比优先HRRN规则每次选择当前就绪队列中响应比最高的进程执行进程到达时间服务时间开始执行完成时间周转时间带权周转时间A030331B263971.17C4491392.25D651520142.8E82131573.5平均周转时间37914758平均周转时间 \frac{379147}{5} 8平均周转时间53791478平均带权周转时间11.172.252.83.552.14平均带权周转时间 \frac{11.172.252.83.5}{5} 2.14平均带权周转时间511.172.252.83.52.14 总结与备考建议算法平均周转时间平均带权周转时间优势劣势FCFS8.62.56简单公平对短作业极不友好SJF非抢占7.61.84平均性能较好可能饥饿长作业SJF抢占7.21.59最优平均性能实现复杂频繁切换HRRN8.02.14兼顾长短作业需动态计算响应比✅考试重点提醒务必掌握四种算法的手动推演过程尤其是抢占式SJF的时间线划分高响应比的计算是高频考点注意等待时间当前时刻−到达时间等待时间 当前时刻 - 到达时间等待时间当前时刻−到达时间区分“非抢占”与“抢占”SJF的执行顺序差异背诵速记部分可直接用于简答题或选择题。闪电系列·期末闪学| 用最少的字拿最多的分如果这篇对你有帮助欢迎点赞、收藏⭐、关注三连支持更多操作系统速成内容敬请期待《内存管理》《文件管理》《死锁》等后续篇章评论区互动你在做调度算法题时最容易错在哪一步欢迎留言交流一起避坑