CPU 调度

本节导读

大纲在「CPU 调度与上下文切换」下列了：调度的基本概念与目标，调度的实现（调度器、调度时机与调度方式、闲逛进程、内核级与用户级线程调度），CPU 调度算法，多处理机调度，上下文及其切换机制。常见资料称其中「CPU 调度算法」「多处理机调度」两项是 2025 年版新增的条目（2022 年版写的是「典型调度算法」，列了先来先服务、短作业优先、时间片轮转、优先级、高响应比优先、多级反馈队列六种）。

这一节的综合应用题常要画出调度过程、算周转时间和等待时间。学完你应该能对任一组作业按指定算法画出时间线，并算出平均周转时间、平均带权周转时间。

调度的概念与目标

调度分三级：高级调度（作业调度，从外存后备队列选作业调入内存、创建进程）、中级调度（内存调度，把暂时不能运行的进程挂起到外存或换回）、低级调度（进程调度，从就绪队列选一个进程分配 CPU）。低级调度最频繁。

评价指标：

指标	含义
CPU 利用率	CPU 忙的时间占总时间的比例
吞吐量	单位时间完成的作业数
周转时间	完成时间 − 到达（提交）时间
带权周转时间	周转时间 ÷ 实际运行时间，不小于 1
等待时间	在就绪队列中等待的时间之和
响应时间	从提交请求到首次产生响应的时间

调度的实现

调度程序（调度器）由三部分组成：排队器（把就绪进程按策略排成队列）、分派器（取出选中的进程并分配 CPU）、上下文切换器。

调度时机：当前进程运行结束、因等待事件而阻塞、时间片用完、有更高优先级的进程进入就绪队列（抢占方式下）。在处理中断的过程中、进程处于操作系统内核程序的临界区中、执行原子操作时，不能进行调度与切换，要等这些工作完成后再调度。

调度方式：非抢占方式下，进程一直运行到结束或阻塞才让出 CPU；抢占方式下，系统可以按规则（优先级、时间片、更短的作业到来）剥夺正在运行的进程的 CPU。没有就绪进程时，系统运行闲逛进程（idle），它优先级最低，只要有进程就绪就让出 CPU，它不需要 CPU 以外的资源，也不会被阻塞。

线程的调度：用户级线程由线程库在进程内部调度，内核仍以进程为单位分配时间片；内核级线程由内核直接调度，同一进程的线程可以分到不同的处理器上。

调度算法

算法	规则	特点
先来先服务 FCFS	按到达先后	非抢占；简单公平，对短作业不利
短作业优先 SJF	选估计运行时间最短的	平均周转时间最短（非抢占时对同时到达的作业组而言）；长作业可能饥饿
最短剩余时间优先 SRTN	SJF 的抢占版：新作业的运行时间比当前作业的剩余时间短就抢占	平均周转时间更短；长作业可能饥饿
优先级	选优先级最高的，分抢占与非抢占、静态与动态优先级	静态优先级可能使低优先级进程饥饿，动态提高等待者的优先级可以缓解
时间片轮转 RR	按到达顺序轮流运行一个时间片，用完排到队尾	抢占；适合分时系统；时间片太大退化为 FCFS，太小切换开销大
高响应比优先 HRRN	选响应比最高的，响应比 = $\dfrac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}$要求服务时间等待时间+要求服务时间​	非抢占；兼顾短作业和等待久的作业，不会饥饿
多级反馈队列	设多个优先级递减、时间片递增的队列；新进程进入第 1 级队尾，一个时间片内没做完就降到下一级；高级队列空了才调度低级队列	兼顾短作业、交互作业和长作业；不断有新进程到来时低级队列的进程可能饥饿

做计算题时，先画出每个时刻就绪队列里有谁，再按规则选；时间片轮转题要看清题目的约定——同一时刻既有新进程到达、又有进程时间片用完时谁先进入队尾（本课约定新到达的进程先入队）。