操作系统三大经典调度算法FCFS、SJF、HRRN在前两篇我们搞懂了进程调度的触发时机、切换过程以及抢占 / 非抢占两种调度方式。今天我们拆解操作系统最经典的三款调度算法先来先服务FCFS、短作业优先SJF、高响应比优先HRRN我们统一用「奶茶店做单」做类比顾客 待调度的作业 / 进程制作奶茶的时间 进程需要的服务时间奶茶店店员 CPU调度算法 店员的做单顺序规则一、先来先服务FCFS最朴素的公平排队1. 算法思想与规则核心思想从「公平」角度出发完全按照到达的先后顺序服务和生活中排队买东西的逻辑完全一致。具体规则按照作业 / 进程到达后备队列 / 就绪队列的先后顺序先到的先分配 CPU 服务。1用于作业调度看哪个作业先到达外存后备队列2用于进程调度看哪个进程先进入内存就绪队列。2. 抢占属性纯非抢占式算法一旦进程开始运行就必须等它主动结束或阻塞才能切换下一个中途不能抢走 CPU。3. 优缺点分析优点规则绝对公平算法实现极其简单只需要一个普通队列就能实现缺点对短作业非常不友好。如果排在前面的是一个长作业后面所有短作业都要等待很久整体平均等待时间、平均周转时间很差用户体验糟糕。总结对长作业有利对短作业不利。4. 饥饿问题不会导致饥饿。只要一直排队早晚会轮到自己不会出现某个进程永远得不到服务的情况。举例奶茶店严格按排队顺序做单。第一个顾客点了 10 杯定制奶茶长作业要做 20 分钟后面三个顾客都只点了一杯基础款短作业2 分钟就能做好。 按照 FCFS 规则后面三个顾客必须等 20 分钟才能拿到自己的奶茶明明几分钟就能做完的事被长订单拖了很久短订单用户体验极差。二、短作业优先SJF追求极致的整体效率1. 算法思想与规则核心思想追求最少的平均等待时间、最少的平均周转时间让整体系统效率最高。具体规则每次调度时选择「要求服务时间最短」的作业 / 进程优先服务。1用于作业调度叫短作业优先SJF2用于进程调度叫短进程优先SPF, Shortest Process First。2. 两个版本非抢占式 抢占式非抢占式标准 SJF/SPF进程一旦开始运行就必须跑完中途不能被打断只有当前进程主动放弃 CPU 时才重新调度。抢占式最短剩余时间优先SRTN只要就绪队列里出现了比当前运行进程「剩余运行时间更短」的新进程就立刻抢占 CPU让更短的进程先跑。3. 易混点很多教材会说 “SJF 的平均等待时间、平均周转时间最少”这个表述不严谨。正确结论分两种情况所有进程几乎同时到达、同时可运行时非抢占式 SJF 的平均等待时间、平均周转时间确实是最少的进程陆续到达的场景下抢占式的最短剩余时间优先SRTN算法平均等待时间和平均周转时间比非抢占 SJF 更少是真正的 “最优”。简单记所有进程一起到SJF 最优陆续来SRTN 更优。4. 优缺点分析优点整体系统效率高平均等待时间、平均周转时间远优于 FCFS短作业用户体验好缺点不公平完全偏向短作业对长作业极其不友好作业的运行时间是用户预估提供的不一定真实可能出现 “假装短作业插队” 的情况无法做到绝对的短作业优先可能产生饥饿现象。5. 饥饿问题会导致饥饿严重时会饿死。如果源源不断有新的短作业到来长作业会一直被插队长时间甚至永远得不到服务。举例奶茶店改了规则优先做制作最快的订单。 如果一直有只点一杯奶茶的小订单进来那个点了 10 杯奶茶的大订单就会一直往后排等了半小时都轮不到他这就是 “饥饿”如果永远有小单大单永远做不上就是 “饿死”。三、高响应比优先HRRN公平与效率的折中方案1. 算法思想与核心公式核心思想综合考虑进程的「等待时间」和「服务时间」既照顾短作业也不让长作业一直等下去是 FCFS 和 SJF 的折中平衡。响应比计算公式响应比永远 ≥ 1。调度规则每次需要调度时先计算所有就绪进程的响应比选择响应比最高的进程优先服务。2. 抢占属性纯非抢占式算法只有当前运行的进程主动放弃 CPU结束、阻塞时才会重新计算响应比、执行调度运行中途不会被抢占。3. 优缺点分析它完美融合了前两种算法的优点等待时间相同时服务时间越短响应比越高 → 继承了 SJF 短作业优先的优点服务时间相同时等待时间越长响应比越高 → 继承了 FCFS 先来先服务的公平性对于长作业随着等待时间越来越久响应比会越来越高最终一定会被调度 → 彻底解决了长作业饥饿的问题。唯一的小缺点每次调度都要遍历计算所有进程的响应比比 FCFS、SJF 多了计算开销。4. 饥饿问题不会导致饥饿。长作业等待越久响应比越高最终一定会被调度执行。举例奶茶店升级了规则做单优先级不仅看制作时长还看顾客等了多久。两个顾客都点一杯奶茶先来的等了更久先做他的兼顾 FCFS 公平两个顾客同时来一个点 1 杯、一个点 10 杯先做 1 杯的兼顾 SJF 效率点 10 杯的顾客等了很久他的 “响应比” 越来越高哪怕一直有新的小单进来最终也会轮到他解决饥饿。四、三大算法核心对比表对比维度先来先服务 FCFS短作业优先 SJF非抢占高响应比优先 HRRN抢占属性非抢占式非抢占式抢占版为 SRTN非抢占式核心规则按到达先后顺序服务按服务时间短的优先按响应比高的优先公平性最公平最不公平偏向短作业折中兼顾公平与效率整体效率最差平均周转时间长最优同时到达场景中等短作业体验差最好较好长作业体验友好极差可能饥饿友好等待越久优先级越高是否饥饿不会会长作业可能饿死不会实现难度最简单简单中等需计算响应比适用场景简单系统、对公平要求高的场景追求整体系统效率、短作业多的场景通用批处理系统平衡公平与效率五、总结FCFS 是最朴素的排队算法公平简单但效率低对短作业不友好不会饥饿SJF 追求极致整体效率短作业体验最好但对长作业不公平会导致饥饿注意 “平均周转时间最短” 有前提抢占式 SRTN 在陆续到达场景更优HRRN 是折中方案用响应比综合等待时间和服务时间兼顾公平与效率彻底解决饥饿问题是批处理系统的经典选择。