2.2.5 CPU调度算法

教材导航 · 第2章

原书定位

印刷页P71起,对应PDF第82页。下文为目视整理的知识提要;完整内容见原书对照。

算法选择依据主要特点
FCFS到达顺序非抢占,简单;长作业可能拖延短作业
SJF/SPF估计服务时间最短有利短作业,长作业可能饥饿;抢占版本比较剩余时间
HRRN最高响应比Rp=(等待时间+服务时间)/服务时间R_p=(等待时间+服务时间)/服务时间,兼顾长短作业
优先级最高优先级可抢占或非抢占;动态优先级可缓解饥饿
RR就绪队列按时间片轮转适合交互;片太大接近FCFS,太小切换开销大
多级队列进程固定进入不同队列队列可使用不同算法
多级反馈队列按运行情况调整队列高层优先级高、时间片短;用完时间片后降级

做题时只在当时已到达且就绪的集合中选取。非抢占算法一旦开始运行,后来到达的短作业不能立即抢占。最短剩余时间算法需在新作业到达时重新比较。

公平调度区分“每进程公平”和“每用户公平”。保证调度通过比较已获得CPU时间与应得CPU时间的比值,优先补偿不足者。

多级反馈队列

多级反馈队列,原书P74。

调度算法比较

调度算法比较,原书P76。

对应练习

2.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P71,PDF第82页

原书对照,原书P72,PDF第83页

原书对照,原书P73,PDF第84页

原书对照,原书P74,PDF第85页

原书对照,原书P75,PDF第86页

原书对照,原书P76,PDF第87页