扫码获取 VIP 码
添加管理员微信获取 VIP 码
操作系统最核心的职责之一，就是在多个就绪进程之间分配CPU时间。这个分配决策的过程，就是进程调度。理解调度算法之前，必须先建立一个基本认知：CPU在同一时刻只能执行一个进程的指令流，而系统中往往有几十上百个进程同时在争抢这个唯一的执行资源。调度的本质问题，就是回答两个问题——下一个让谁跑，以及让它跑多久。
这两个问题看似简单，但回答它们的策略直接影响着整个系统的响应速度、吞吐量和公平性。不同的应用场景对这三个指标有不同的偏好：交互式系统更看重响应速度，批处理系统更看重吞吐量，实时系统则把可预测性放在首位。正是这种需求的分化，催生了多种截然不同的调度算法。软考对进程调度的考查，不仅要记住每种算法的规则，更要理解背后的权衡取舍——当周转时间和响应时间不可兼得时，算法选择了站在哪一边。
操作系统中，进程在其生命周期内会在多种状态之间迁移。就绪态是进程等待CPU调度时所处的状态，运行态是进程正在CPU上执行的状态，阻塞态则是进程等待某个事件完成而暂时无法继续执行的状态。调度算法只在就绪队列中选择下一个要运行的进程，而触发调度决策的时机主要有四种场景：当前运行进程主动放弃CPU、当前进程被更高优先级进程抢占、当前进程时间片用完、以及进程从阻塞态被唤醒进入就绪态。这四种场景分别对应非抢占调度和抢占调度的不同策略。
在评价任何一种调度算法之前，有三个核心指标必须精确理解。周转时间指的是从进程提交到进程完成所经历的全部时间，它等于完成时刻减去到达时刻。等待时间则是进程在就绪队列中等待CPU的时间总和，不包括进程实际在CPU上运行的时间，也不包括进程等待输入输出操作完成的时间。响应时间是交互式系统中最重要的指标，指从用户提交请求到系统首次产生响应的时间间隔。软考选择题特别喜欢在这三个概念之间设陷阱，比如出一道题说某个调度算法"平均等待时间最短"，选项里塞一个"平均周转时间最短"来混淆视听——两个概念描述的是不同的东西，不能互换。
调度算法可以按是否支持抢占划分为两大类。非抢占调度的规则是：一旦CPU被分配给某个进程，该进程将一直持有CPU直到主动释放——可能是进程执行完毕正常退出，也可能是进程发起一次输入输出操作而主动进入阻塞状态。在此期间，即使有一个更紧急或更短小的进程到达就绪队列，也必须等待当前进程主动让出CPU。非抢占调度的缺点显而易见：一个长时间运行的CPU密集型作业会阻塞所有后续进程，但其优点也值得注意——实现简单，没有抢占引发的额外上下文切换开销。
抢占调度则允许操作系统在特定时机强行收回CPU控制权。最典型的抢占触发条件是时间片中断：当时钟中断到来且当前进程已用尽分配给它的时间片，调度器就被激活，把当前进程放回就绪队列尾部，从就绪队列中选择下一个进程运行。抢占调度需要额外的机制来保存和恢复进程上下文，单次切换开销虽然只有几十到几百微秒，但在频繁抢占的场景下累积起来不容忽视。
先来先服务调度算法，英文缩写为FCFS，是所有调度算法中最简单也最符合直觉的一种。它的规则只有一条：就绪队列按进程到达的先后顺序排列，每次调度选择队首进程分配CPU。这就像是排队买票，先到先得，天经地义。FCFS的实现可以用一个简单的先进先出队列来完成，整个过程不需要任何复杂的优先级计算或排序操作，调度决策的开销极低。
但FCFS有一个致命的弱点：它完全无视进程的执行时间差异。如果一个需要运行一百秒的进程排在了队列最前面，那么后面所有进程——哪怕只需要一两秒就能跑完——也要白白等待九十九秒。这种现象被称为"护航效应"，就像一条缓慢的货船堵在运河入口，后面所有的快艇都只能按它的节奏缓慢通过。FCFS还有一个特性值得注意：它对CPU密集型进程天然有利，对输入输出密集型进程不够友好。一个典型的输入输出密集进程的运行模式是短时间使用CPU后主动放弃CPU去等待输入输出完成，在FCFS下它每次从阻塞返回后都需要重新排到队尾，与所有新到达的进程公平竞争。
FCFS的周转时间严重依赖于进程的到达顺序。假设有三个进程先后到达：进程A需要执行二十四个时间单位，B需要三个，C需要三个。如果到达顺序是A先到、然后B、最后C，那么A的周转时间为二十四，B必须等A跑完需要等二十四、周转为二十七，C要等A和B都跑完需要等二十七、周转为三十。平均周转时间为二十七。但如果顺序反过来——C先到、B第二个、A最后——则C周转三，B等待三周转六，A等待六周转三十，平均周转降到十三。同样的三个进程，仅因到达顺序不同，平均周转时间相差一倍以上。
短作业优先调度算法的英文缩写是SJF或者SPF。它的核心思想非常直接：在所有已到达的就绪进程中，挑选预估执行时间最短的那个优先分配CPU。如果几个进程的执行时间相同，则按FCFS规则选择最先到达的那个。这个算法的理论优势非常突出：在所有非抢占调度算法中，SJF能给出最短的平均等待时间。这不是经验观察，而是可以通过数学严格证明的最优性结论。
SJF的直觉依据很容易理解。如果把进程调度看作一个排队问题，让短作业排在长作业前面执行，那么短作业的等待时间被压缩到最小，长作业虽然要多等一会儿，但因为它本来就需要跑很久，多等的这点时间对它的总周转时间影响比例较小。反之如果让长作业先跑，所有短作业都要等上很长时间，每个短作业的周转时间都被不成比例地拉长，平均下来自然不理想。
但SJF在实际系统中面临一个根本性的困难：调度器怎么事先知道每个进程的执行时间？在批处理系统中，用户提交作业时可以给出估计的执行时间上限；在交互式系统中，可以通过进程的历史行为进行启发式预测——如果某个进程过去几次CPU突发的时间都很短，那么它下一次CPU突发大概率也比较短。但这种预测永远不可能是精确的，一旦估计偏差较大，SJF的优势就会大打折扣。软考中经常出现SJF的抢占版本，称为"最短剩余时间优先"——每当新进程到达时，比较新进程的剩余执行时间和当前运行进程的剩余执行时间，如果新进程的剩余时间更短，就抢占当前进程。
SJF的另一个严重缺陷是饥饿现象。如果系统中持续不断地有短作业到达，一个长作业可能永远得不到CPU。在实际系统中解决饥饿问题通常采用"老化"技术——一个进程等待的时间越长，它的优先级就逐步提高，最终总能获得执行机会。
高响应比优先调度算法，英文缩写为HRRN，是为克服SJF长作业饥饿问题而设计的一种折中方案。它的核心机制是为每个进程计算一个"响应比"，响应比越高的进程优先获得CPU。响应比的计算公式体现了这个算法的哲学：响应比等于等待时间加上要求服务时间后除以要求服务时间，也就是一加上等待时间除以要求服务时间的商。
这个看似简单的公式蕴含了巧妙的权衡逻辑。对于一个短作业，分母很小，即使等待时间不长，响应比也会迅速攀升，因此短作业天然具有更高的响应比优势。但对于一个长作业，分母很大，如果等待时间也非常长了，分子中等待时间的贡献终将超过分母带来的劣势，响应比同样可以上升到较高水平。这意味着长作业不会永远饥饿——只要等得足够久，它的响应比终将超过那些刚刚到达的短作业。HRRN由此同时兼顾了短作业的周转效率优势和长作业的防饥饿需求。
HRRN的一个关键特性是它既不是单纯的FCFS也不是单纯的SJF，而是一种动态优先级算法。每个进程的优先级不是固定不变的，而是随着等待时间的增长而
本篇完！