2.3 CPU 调度与上下文切换

三级调度，调度的时机、方式与评价指标，调度程序与上下文切换；先来先服务、短作业优先、高响应比优先、优先级、时间片轮转与多级反馈队列调度算法。

调度的概念

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

一个作业从提交开始直到完成，往往要经历以下三级调度：

调度的时机与方式

不能进行进程调度与切换的情况：

1. 在处理中断的过程中：中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源；
2. 进程在操作系统内核临界区中：进入临界区后，需要独占式地访问，理论上必须加锁，以防止其他并行进程进入，在解锁前不应切换到其他进程，以加快临界区的释放；
3. 其他需要完全屏蔽中断的原子操作过程中：如加锁、解锁、中断现场保护、恢复等原子操作。

应该进行进程调度与切换的情况：发生引起调度条件且当前进程无法继续运行下去时（非抢占）——当前进程运行结束、进程因请求 I/O 或 P 操作而阻塞；中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换（抢占）。

• 非抢占调度方式（非剥夺方式）：当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程运行完成或发生某种事件而进入阻塞态时，才把处理机分配给其他进程。实现简单、系统开销小，适用于早期的批处理系统，但它不能用于分时系统和大多数的实时系统；
• 抢占调度方式（剥夺方式）：当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则允许调度程序根据某种原则去暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。对提高系统吞吐率和响应效率都有明显的好处，但”抢占”不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

调度的评价指标

• CPU 利用率 = CPU 有效工作时间 / (CPU 有效工作时间 + CPU 空闲等待时间)；
• 系统吞吐量：单位时间内 CPU 完成作业的数量；
• 周转时间 = 作业完成时间 − 作业提交时间；平均周转时间 = Σ 周转时间 / n；
• 带权周转时间 = 作业周转时间 / 作业实际运行时间（$\geq 1$）；
• 等待时间：进程处于等待处理机的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间；
• 响应时间：从用户提交请求到系统首次产生响应所用的时间，在交互式系统中常用响应时间而不用周转时间作为评价指标。

调度程序与上下文切换

调度程序（调度器）通常由三部分组成：排队器（将系统中的所有就绪进程按照一定的策略排成一个或多个队列）、分派器（依据调度程序所选的进程，将其从就绪队列中取出，将 CPU 分配给新进程）、上下文切换器（在对处理机进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的 CPU 现场信息装入处理机的各个相应寄存器）。

闲逛进程（idle）：如果系统中没有就绪进程，就会调度闲逛进程运行。闲逛进程的优先级最低，没有其他就绪进程时才会运行它，它不需要 CPU 之外的资源，不会被阻塞。

典型的调度算法

即时练习