进程调度算法全解析：从2009年408真题看饥饿与调度指标

做408真题的朋友大多数第一轮复习到进程调度算法的时候都会觉得内容很简单无非就是先来先服务、短进程优先、时间片轮转、优先级、多级反馈队列各自背好特点就能上考场。但真的做到2009年第24题的时候不少人会愣一下——这道题既没有给进程列表也没有要求算周转时间而是直接考你对调度算法“性格”的理解。网上关于这道题的讨论一直不少有人说是送分题有人说选项有歧义。在我看来这道题的价值恰恰不在那个唯一答案而在于它逼你把调度指标、抢占时机、饥饿条件这些零散知识点串成一条线。今天这篇文章就来把这条线全部理清楚并且带你把调度算法有关的手算题也一并解决掉。1. 为什么2009年第24题值得反复做它把“调度指标”摆在了最前面1.1 真题不直接问“哪个算法最好”而是问“哪个指标对应哪个算法”教材里介绍进程调度算法通常按“算法名称—基本原理—优缺点”的顺序展开。这种顺序有个副作用很多人背完了“短进程优先平均周转时间最短”之后遇到实际问题反而不知道怎么用。2009年第24题有趣就有趣在它没有问你某个算法的流程而是给出一组“评价指标”和“算法特征”的对应关系让你判断哪条叙述是正确的。这就把题目从“记忆层次”抬到了“理解层次”。为了方便讨论我根据平时复习时见到的回忆版整理了一个大同小异的版本——因为不同机构整理的这道题A、B、C、D的顺序和措辞不完全一样甚至有些版本把“作业”写成“进程”但内核不变。题目大致是这样下列叙述中正确的是 A. 短进程优先调度算法不会导致进程饥饿 B. 时间片轮转调度算法会导致长进程饥饿 C. 先来先服务调度算法有利于短作业不利于长作业 D. 多级反馈队列调度算法可以兼顾短进程与交互式进程这道题标准答案习惯上给D。但如果你手里真题集的选项不是这一版也不用担心你只需要把下面几个考点对照着看就会发现命题人翻来覆去就是在考那么几件事。举个最简单的例子如果一个选项说“时间片轮转调度算法可以保证较小的平均周转时间”这句话对不对乍一看好像轮转算法很公平每个进程都能分到CPU周转时间应该不大。但实际上RR算法的平均周转时间通常比SJF长因为短进程明明可以先跑完却要被长进程拖慢。反过来如果你说“SJF平均等待时间一定最优”也不严谨因为这是对“所有进程几乎同时到达”的批处理场景而言如果进程是陆续到达的加上抢占与非抢占的区别SJF的指标表现会发生变化。这种细节正是真题喜欢设坑的地方。1.2 四个核心指标周转时间、等待时间、响应时间、带权周转时间要读懂这道题首先要把评价调度算法的指标体系拉出来。常用的指标就四个周转时间从作业提交到作业完成的时间等于等待时间加上运行时间。对系统而言平均周转时间越短越好。带权周转时间周转时间与运行时间的比值。带权周转时间越接近1说明这个进程几乎没有被耽误。等待时间在就绪队列中等待CPU的总时间不包括运行时间和I/O时间。响应时间从提交到第一次获得CPU的时间交互式系统特别看重这个指标。这四个指标经常互相打架。比如SJF能压低平均周转时间但会让一个长作业等得非常久它的响应时间就很难看。RR能让每个进程很快得到响应但平均周转时间不一定理想。所以题目里凡是说“某个算法在所有指标上都最优”的选项几乎一定是错的。1.3 指标之间的互相制约关系饥饿与公平再往深一层指标背后还藏着一个“公平性”问题。所谓饥饿就是某个进程长期得不到CPU无法推进。饥饿和“等待时间长”不是一回事。一个进程等再久只要最终能上CPU就不能叫饥饿必须是一直被后来者插队永远轮不到才是饥饿。选择这个判断词也是这道题的关键。比如SJF算法下只要源源不断有更短的进程到达原先进来的长进程就可能永远排不上——这就是典型的饥饿。而FCFS虽然可能让短作业等长作业但每个进程按到达顺序排队最后一定能轮上所以不会饥饿。这些结论不要死记要理解成因才能应对选项里的各种变体。2. 六个经典进程调度算法的“性格”记不住就是在这道题丢分2.1 先来先服务FCFS公平但不合理FCFS按到达顺序排队实现最简单维护一个就绪队列即可。它的优点是公平、不会饥饿因为队首总会慢慢移动。缺点是“短作业被长作业连带拖累”。假如一个耗时100ms的长作业先到后面排了10个只需要1ms的短作业那么这10个短作业平均要等将近100ms平均周转时间被拉得极高。真题里只要出现“FCFS不利于短作业”或“FCFS会使短作业等待过久”基本就是正确的表述。2.2 短进程优先SJF/SPF效率高但有“慢性饥饿”短进程优先是理论上的“平均周转时间最优”算法但它有个致命短板进程的“运行时间”通常无法预知而且长短是相对的。在不可抢占版本中一个正在运行的长进程不能被短进程打断这还算温和在可抢占版本SRTF中只要有更短的新进程到达当前进程立刻被换下这时候长进程一旦排在后面就可能被持续到来的“短进程潮”碾压形成饥饿。所以SJF系列的选项里如果出现“不会饥饿”字样大概率是错的。2.3 时间片轮转RR响应优先但片长选择是艺术RR把CPU时间切成长度固定的时间片按到达顺序轮流分配。时间片到立刻剥夺回到队列尾部重新排队。RR的最大优势是响应时间有上限任何就绪进程最多等一个完整轮转周期就能上CPU因此它特别适合分时系统。但RR也有软肋——时间片太大就退化成FCFS时间片太小进程切换开销会吃掉大量CPU。真题经常用“时间片大小对系统性能的影响”来设问比如问“时间片小于进程切换开销会发生什么”。答案自然是CPU几乎都在切换用户进程基本跑不动。2.4 优先级调度HPF抢占/非抢占的陷阱优先级调度给每个进程分配一个优先级高优先级先运行。这里最大的考点是“抢占”和“非抢占”的区别。非抢占式优先级调度中只有当正在运行的进程运行完才让出CPU即使这时来了更高优先级的进程也要等抢占式中只要有更高优先级进程进入就绪队列立刻剥夺当前进程的CPU。两者都会导致低优先级进程饥饿尤其在高优先级进程频繁到达的情况下。另外注意优先级分为静态和动态动态优先级的典型例子就是下面要讲的高响应比优先和多级反馈队列。2.5 多级反馈队列MFQ把前四者揉在一起多级反馈队列是现代操作系统用得最多的一种调度策略设置多个就绪队列第1级队列时间片最短、优先级最高第2级次之依次递增。新进程进入第1级队列如果时间片用完还没完成就降到下一级队列。这样短进程在第一级就能快速完成长进程也不至于饿死因为系统会在较低级队列中按时间片轮转调度最终仍能获得CPU。MFQ兼顾了响应时间、等待时间和公平性因此很多教材把它当作“综合调度算法”的典范。但要注意MFQ也并非绝对不会饥饿如果配置参数不当例如高优先级队列总是有进程低优先级队列也可能长时间得不到调度。2.6 高响应比优先HRRN妥协的折中方案高响应比优先的优先级计算公式是优先权 (等待时间 要求服务时间) / 要求服务时间也就是1 等待时间/要求服务时间。这个算法兼顾了“等待时间越长越优先”和“运行时间越短越优先”而且随着等待时间增长长作业也有机会被调度所以不会饥饿。它通常是非抢占式的在每次调度时刻重新计算所有就绪进程的响应比。408选择题喜欢把它放在选项中作为“综合了长短作业优点”的正确表述。以上这些“性格”一定要能脱口而出。我去年带学弟冲刺时专门让他把每个算法用一句话写出来FCFS是“排队”SJF是“短者先跑”RR是“排队轮流跑一段”HPF是“厉害的人先跑”MFQ是“跑得快就留第一层跑得慢就往下掉”HRRN是“比值大的先跑”。就因为这六句话他做概念辨析题再也没错过。3. 把“饥饿”这个考点彻底讲透2009年这道题最大的陷阱3.1 什么是饥饿和死锁的区别先建立一个清晰定义进程饥饿指的是进程在就绪队列中等待了无限长时间始终无法获得CPU虽然它并没有阻塞调度所需的资源也不缺但就是排不上队。死锁则完全不同死锁是多个进程互相等待对方占有的资源谁也前进不了而且如果没有外力介入永远保持阻塞。饥饿的进程可能一直“就绪”但无法运行死锁的进程处于“阻塞”状态饥饿可以靠算法调整或运气解决死锁必须靠预防、避免、检测或解除机制。这道题里有选项会拿“饥饿”和“死锁”做文字游戏比如“SJF算法可能导致死锁”这是错的SJF导致的是饥饿而不是死锁。3.2 哪些算法必然饥饿哪些不会哪些有可能我们把常见的六个算法按“饥饿相关”分三类整理成一张表算法是否饥饿原因FCFS不会严格按到达顺序队首总会推进RR不会前提是时间片公平轮转每个队列成员都能周期获得CPUHRRN不会等待时间越大优先级越高最终会轮到SJF/SPF会短进程连续到达时长进程永远插不上优先级静态会高优先级进程存在时低优先级进程永远等待MFQ可能参数不当或高优先级队列持续有进程时低层队列可能被饿着这个表格在复习后期非常有用可以直接抄进笔记。但要加一句RR“不会饥饿”的前提是就绪进程都公平轮转如果系统允许进程因I/O或阻塞而退出队列再重新进入是否饥饿要看具体策略。不过408默认情况下不会在轮转算法里设饥饿陷阱题目更爱在SJF和优先级上做文章。3.3 优先级反转与饥饿的关联说到优先级调度不得不提优先级反转Priority Inversion。它指的是高优先级进程被低优先级进程阻塞的现象经典场景是低优先级进程占用了高优先级进程需要的资源高优先级进程只能等待此时若中优先级进程抢占CPU并且不停运行低优先级进程就无法释放资源高优先级进程也永远卡住——这看起来很像饥饿但根因是“资源竞争抢占调度”的组合。408中“优先级反转”不是必考但在真题解析里常作为扩展。解决优先级反转的办法是优先级继承低优先级临时继承高优先级和优先级天花板等。看到这里你就能理解为什么有些复习得好的同学拿到一道“调度算法”题能联想到一连串知识点这就是把真题吃透的效果。4. 手算时间片轮转调度一道大题模板顺便解决选择题里的“时间轴题”很多同学以为这道真题只考概念不会考计算这是误解。选择题里同样可能出现“时间片轮转调度后的平均周转时间”这类问题大题更是重灾区。所以这里我完整推演一个例子把你可能踩的坑全标出来。4.1 一个五进程实例的全过程推演假设五个进程都在时间0到达执行时间分别为P1: 10P2: 1P3: 2P4: 1P5: 5单位ms。采用时间片轮转调度时间片为2ms忽略进程切换开销。时间轴运行如下0~2P1运行剩8被换下。2~3P2运行运行1ms完成。P2用完所需时间后立刻结束剩余时间片作废CPU紧接着调度下一个进程。3~5P3运行运行2ms完成。5~6P4运行运行1ms完成。6~8P5运行剩3被换下。8~10P1运行剩6被换下。10~12P5运行剩1被换下。12~14P1运行剩4被换下。14~15P5运行运行1ms完成。15~19P1运行运行为4ms分两个时间片实际上从15开始P1还有4ms时间片2ms15~17运行2ms剩2被换下此时队列中已无其他进程P5已完成所以P1立即又被调度17~19运行2ms完成。最终P1在19时刻完成。重新总结完成时间P119, P23, P35, P46, P515。等待时间完成时间-到达时间-服务时间P119-109P23-12P35-23P46-15P515-510。平均等待时间(923510)/55.8ms。周转时间完成时间-到达时间完成时间P119, P23, P35, P46, P515平均周转时间(1935615)/59.6ms。带权周转时间P119/101.9P23/13P35/22.5P46/16P515/53平均带权周转时间(1.932.563)/53.28。你可以用同样的进程序列分别算FCFS和SJF非抢占得到对比表算法平均周转时间平均等待时间FCFS按P1,P2,P3,P4,P5(1011131419)/513.4(010111314)/59.6SJF按P2,P4,P3,P5,P1(124919)/57.0(00249)/53.0RR(q2)9.65.8从这个例子可以直观看到RR平均周转时间大于SJF但每个进程从提交到第一次运行的时间都很短P1第0ms就跑了P5第6ms跑最长才等6ms而SJF下的P1可能要等到第9ms才第一次被调度。这就是“响应时间”和“周转时间”的权衡。4.2 时间片轮转调度的时间轴画法与常见丢分点第一个坑是“完成进程的剩余时间片怎么办”。比如P2只需要1ms时间片是2ms它运行完的瞬间就应该调度下一个进程不能等到时间片边界。第二个坑是“到达时间不同”的情况。如果进程不是同时到达新到达的进程通常插入就绪队列队尾而不是插队。第三个坑是“抢占发生在时间片结束时”如果在某时刻既有进程时间片用完又有新进程到达先处理完时间片切换再把新进程插入队尾。做题时最好先自己画一个Gantt图再对答案用图表辅助能减少一半错误。这个例子也反过来印证了前面说的内容P2、P4是短进程在RR中它们第一轮就运行完了没有被拖太久而P1在SJF下会被排在最后平均周转时间反而更低。所以看到“RR平均周转时间一定最优”这种选项直接排除。5. 从选择题到大题408调度算法命题的三种套路与应对5.1 套路一概念辨析直接拿指标做选项2009年第24题属于这一类。它的标准考法就是给四个叙述让你判断正误。应对策略只有一条把前面总结的“算法性格表”和“饥饿表”刻在脑子里。做题时注意几个高频陷阱词“一定”“都能”“所有指标”“不会饥饿”这些绝对化表述往往就是错点。比如“RR算法在所有情况下都不会饥饿”在408语境下基本是对的但如果说“RR是平均周转时间最优算法”错。所以不是看到“绝对化”就选错而是看它对应哪个算法的哪条性质。5.2 套路二给定进程到达时间和运行时间算指标这是大题最常考的形式。给3~5个进程告诉你到达时刻和服务时间让你分别求FCFS/SJF/RR下的调度顺序、完成时间、平均周转时间、平均带权周转时间。这类题没有技巧就是画表。我建议用统一的表头| 进程 | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 |每一列按公式推导周转时间完成时间-到达时间等待时间开始时间-到达时间如果是非抢占单CPU等待时间也等于完成时间-到达时间-服务时间。注意多个进程同时到达时按进程编号或题目约定排序。遇到可抢占SJFSRTF还要在每次新进程到达的瞬间重新判断谁剩余时间最少这个步骤最容易漏。5.3 套路三综合比较算法优劣写一段“判断依据”有些年份的408大题不让你算而是要求“选择一种合适的调度算法并说明理由”。比如设计一个操作系统既要支持交互式任务又要保证批处理任务不饥饿该怎么选标准答法一般是“多级反馈队列”。理由可以分三步写第一短进程和交互式进程在高优先级队列中能快速响应第二进程用完后降级兼顾了长任务第三最底层队列采用时间片轮转保证所有任务最终都能执行避免饥饿。如果题目强调“平均周转时间最短”可以提短进程优先如果强调“兼顾公平和响应”优先提RR或MFQ。关键是写理由时一定要联系指标不要空谈。5.4 我在反复刷题中总结的三条保命原则最后分享三条我踩过坑之后总结出来的原则。第一条做题前先看题目问的是“可能”还是“一定”。饥饿问题里“可能”选项往往正确“一定”选项往往错误因为只要设计者加一些额外机制就可以避免饥饿。第二条算时间片轮转时永远不要忘记“进程运行完毕就立刻退出调度剩余时间片直接作废”否则时间轴会整体后移算出的完成时间全部错误。第三条遇到SJF、SRTF优先考虑“到达时间”是否相同如果不同必须在每次到达事件处重新检查要不要抢占。这三条保住了我很多分希望你也直接用上。做真题不是为了对答案而是为了从一道题里拽出一张知识网。2009年第24题就是这样一道题它表面只考进程调度算法的一个小分支实际却把调度指标、饥饿边界、抢占机制全部串联了起来。你把本文的知识点吃透之后再回看这道题应该会有一种“原来如此”的感觉。如果后续复习时间充足建议你把PV操作和文件管理的真题也按同样的方式拆一遍收获会非常明显。