扫码获取 VIP 码
添加管理员微信获取 VIP 码
在多道程序系统中，内存中同时驻留多个就绪进程，它们都在争抢CPU这一稀缺资源。CPU同一时刻只能执行一个进程，操作系统的进程调度器必须在就绪队列中做出选择：把CPU分配给谁，分配多长时间。这个决策机制就是进程调度，它是操作系统内核中最核心的功能模块之一，直接决定了系统的响应速度、吞吐量和公平性。
进程调度并非单一的决策动作，而是一个分层体系。从广义上讲，作业从提交到完成经历三个层次的调度：高级调度决定哪些后备作业被调入内存成为就绪进程，控制多道程序的并发度，在批处理系统中频繁使用，分时和实时系统中往往不设高级调度；中级调度负责在内存紧张时将暂时不能运行的进程换出到外存的挂起队列，条件满足时再换入内存；低级调度是狭义上的进程调度，决定就绪队列中哪个进程获得CPU，运行频率最高，大约每几十毫秒执行一次。
从调度时机来看，进程调度分为抢占式和非抢占式。非抢占方式下，进程获得CPU后一直运行到完成或主动阻塞，操作系统无权强行剥夺，实现简单但响应时间无法保证。抢占方式下，操作系统可在当前进程时间片用完或有更高优先级进程就绪时强占CPU。现代通用操作系统如Linux和Windows均采用抢占式调度，这是实现交互式响应和实时性的基础。
高级调度处理外存后备队列到内存就绪队列的迁移，控制系统的多道程序度。多道程序度过高会导致内存竞争和频繁上下文切换反而降低性能。中级调度处理内存与外存挂起队列之间的双向迁移，在虚拟存储系统中尤为重要——物理内存不足时挂起部分进程，等待事件完成后换入。低级调度直接从内存就绪队列挑选进程分配CPU，决策必须在几微秒内完成。
考生最容易混淆的是非抢占与抢占的场景边界。非抢占的触发事件有三个：进程正常终止、主动请求I/O进入阻塞态、执行原语主动让出CPU。抢占式调度除了这三种情况之外，时间片中断和更高优先级进程到达也是合法触发时机。需特别注意：即便在抢占式系统中，进程处于内核态执行系统调用时通常不被抢占，以保证内核数据结构的完整性。Linux内核在2.6版本引入了内核抢占机制，大幅降低了系统调用延迟。
先来先服务调度算法是最朴素、最易于理解的调度策略：按照进程进入就绪队列的先后顺序分配CPU，先到达的先执行，后到达的排队等待。这种算法从实现角度看几乎零开销，调度程序只需要维护一个FIFO队列，每次从队首取出一个进程投入运行即可。FCFS在非抢占方式下运行，一个进程一旦获得CPU就一直运行到完成或主动阻塞。
从性能指标分析，FCFS的平均周转时间和平均带权周转时间通常不是最优的。周转时间是完成时间减到达时间，带权周转时间是周转时间除以实际运行时间。FCFS对短作业极不友好：一个只需几毫秒的短进程如排在需运行数分钟的长进程后面，就必须等长进程执行完。这种现象称为护航效应，导致短作业的带权周转时间急剧膨胀。
护航效应的危害在批处理系统中尤为突出。设想三个进程：P1需100毫秒，P2需10毫秒，P3需10毫秒，先后到达。FCFS下P2和P3分别等待100和110毫秒才能完成，平均周转时间约143毫秒。但FCFS天然保证公平性——没有进程会被饿死，在嵌入式简单任务轮询或进程恰好按运行时间升序到达时也能取得不错效果。
短作业优先调度算法以进程的预估运行时间为排序依据，每次都选择就绪队列中估计运行时间最短的进程分配CPU。从数学上可以严格证明：在所有非抢占调度算法中，SJF具有最小的平均周转时间和最小的平均带权周转时间。这一结论源于排队论的经典推导——将短任务前置可以减少后续所有任务的等待时间累积，类似于日常生活中让办事快的人先办可以缩短所有人的平均等待时间。
SJF理论的优越性掩盖不了实践缺陷：它需要预知每个进程的准确运行时间，而这是无法精确做到的。批处理系统中用户常低估运行时间以尽早获得调度，交互式进程的运行时间更完全取决于用户行为，无从预测。现代操作系统可通过指数平均法利用历史CPU区间的加权平均值来估计下一次长度，但误差在行为模式突变时会显著增大。
SJF更致命的弱点是饥饿现象。一个长作业若进入不断有新短作业涌入的系统，理论上可能永远得不到执行——每次调度总有更短的进程排在前面。实际系统中极端情况很少发生，但长作业的响应时间确实可能无法接受。SJF的抢占式版本称为最短剩余时间优先，新进程到达时若剩余运行时间比当前运行进程更短则抢占CPU，进一步降低平均等待时间，但上下文切换开销和饥饿风险也需权衡。
优先级调度算法为每个进程分配一个优先级数值，调度时总是选择就绪队列中优先级最高的进程分配CPU。优先级可以基于进程类型静态设定，比如系统进程的优先级高于用户进程、前台交互进程的优先级高于后台批处理进程；也可以根据进程的运行行为动态调整，比如I/O密集型进程在完成I/O操作后提高优先级以便快速响应下一次I/O请求，CPU密集型进程在长时间占用CPU后降低优先级以避免饿死其他进程。
静态优先级在进程创建时一次性确定。Linux中实时进程优先级范围零到九十九，数值越大优先级越高，普通进程通过nice值调整，范围负二十到正十九。静态优先级实现简单但缺乏灵活性，不能反映进程运行中的动态特征变化。
动态优先级机制弥补了这一缺陷。操作系统的调度器根据进程最近的CPU使用情况、等待时间等因素动态调整优先级。最常见的设计是：进程每运行完一个时间片就降低其优先级，进程在就绪队列中每等待一段时间就提升其优先级。这种老化机制确保了长期等待的低优先级进程最终能被调度执行，从根源上防止了饥饿现象。Windows的调度器就采用了类似的动态优先级策略，线程每完成一个时间片配额后优先级会临时降低，而线程从等待状态唤醒后优先级会得到临时提升。
优先级调度面临一个棘手的问题——优先级反转。当一个高优先级进程试图获取一个被低优先级进程持有的互斥资源时，高优先级进程只能进入阻塞等待状态。如果此时有一个不需要该资源的中等优先级进程就绪并开始运行，低优先级进程因为优先级最低而得不到CPU，无法释放资源，高优先级进程也就被无限期阻塞。这种现象称为优先级反转，它实质上是中等优先级进程间接阻塞了高优先级进程，违反了优先级调度设计的基本假设。
解决优先级反转的经典方案是优先级继承协议。当高优先级进程阻塞在低优先级进程持有的资源上时，低优先级进程临时继承高优先级进程的优先级，直到它释放该资源后再恢复原优先级。这样中等优先级进程就无法抢占低优先级进程的CPU，低优先级进程可以尽快执行完临界区并释放资源，高优先级进程得以继续运行。优先级继承协议的实现代价不高，在VxWorks等实时操作系统中被广泛应用。更复杂的方案如优先级天花板协议在每个资源上预设一个最高优先级天花板，任何进程获取该资源时优先级自动提升到天花板值，进一步限制了阻塞链条的长度。
时间片轮转调度算法专门为分时交互系统设计，它的核心思想是公平地轮流为每个进程分配一小段CPU时间，这段固定的CPU时间长度称为时间片。就绪队列按FCFS组织为循环队列，调度程序每次从队首取出一个进程，分配一个时间片的CPU使用权。如果进程在一个时间片内运行完成或主动阻塞，则正常退出；如果时间片用完而进程尚未完成，调度程序将其放回就绪队列队尾，并从队首取出下一个进程。
时间片的大小是RR算法最关键的设计参数，它直接影响系统的响应时间和CPU利用率。时间片设得太短，系统的上下文切换开销占比过大，大量CPU时间浪费在保存和恢复进程上下文的操作上，实际用于执行进程有效工作的时间比例下降。假设每次上下文切换耗时一毫秒，时间片设为四毫秒，则CPU利用率只有百分之八十。时间片设得太长，RR调度就退化为FCFS调度，交互式进程的响应延迟增大，用户感觉到明显的卡顿。通常的时间片选择在十到一百毫秒之间，具体数值取决于系统的硬件性能和工作负载特征。现代Linux的CFS调度器不使用固定时间片，而是根据当前就绪进程的总数动态计
本篇完！