1. 调度的基本概念#

在多道程序系统中，进程的数量通常远多于CPU的个数，因此多个进程争用CPU的情况在所难免。CPU调度是指按照一定的算法（兼顾公平性与效率），从就绪队列中选择一个进程，并将CPU分配给它运行，从而实现多个进程的并发执行。

CPU调度是多道程序操作系统的基础，也是操作系统设计的核心问题之一。

2. 调度的层次#

一个作业从提交到完成，通常要经历以下三级调度。

3. 三级调度的联系#

在三级调度体系中，进程调度是最基本且不可或缺的，而作业调度和中级调度则根据系统类型和设计目标选择性配置。三级调度协同工作，共同完成作业从提交到终止的全过程：

1. 作业调度为进程活动做准备，将作业调入内存并创建进程，使其具备参与调度的资格。
2. 中级调度起调节作用，通过将暂时无法运行的进程换出至外存（挂起态），或在条件满足时将其重新换入内存（恢复为就绪态），动态调整内存中活跃进程的数量。
3. 进程调度驱动实际执行，从就绪队列中选择进程投入运行，是实现并发的核心机制。
4. 调度频率依次升高：作业调度频率最低，中级调度次之，进程调度频率最高。

1. 进程调度任务#

进程调度的任务主要包括：

1. 保存CPU现场信息。调度发生时，需要将当前进程的CPU状态（如程序计数器、通用寄存器等)完整保存至其PCB中，以确保后续能从断点恢复执行。
2. 选取待运行进程。调度程序依据特定算法（如时间片轮转、优先级调度等），从就绪队列中选取一个进程，将其状态由“就绪态”改为“运行态”。
3. 完成CPU分配。由分派程序将选中进程PCB中保存的CPU现场加载到处理器寄存器中，移交CPU控制权，使其从上次断点处恢复执行。

2. 调度程序（调度器）#

用于实现CPU调度与分派的软件组件称为调度程序，它通常由三部分组成。

1. 排队器。将系统中所有就绪进程按照特定策略组织成一个或多个就绪队列。每当有进程转换为就绪态时，排队器便将其插入相应的就绪队列，为后续调度选择提供基础。
2. 分派器。根据调度算法选定的进程，分派器负责执行实际的CPU分配操作，其主要任务包括：从就绪队列中移出目标进程、触发上下文切换，并将CPU控制权转交给该进程。
3. 上下文切换器。在对CPU进行切换时，会发生两对上下文的切换操作：第一对，将当前进程的上下文保存到其PCB中，再装入分派程序的上下文，以便分派程序运行；第二对，移出分派程序的上下文，将新选进程的CPU现场信息装入CPU的各个相应寄存器。

上下文切换需要执行大量load和store指令以保存寄存器内容，因此开销较大。目前已有硬件实现的方法来减少上下文切换时间。通常采用两组寄存器，一组供内核使用，另一组供用户使用。这样，在上下文切换时只需改变指针，使其指向当前所需的寄存器组即可。

3. 调度的时机、切换与过程#

调度程序是操作系统内核程序。只有当请求调度的事件发生后，才会运行调度程序；而在调度出新的就绪进程之后，才会进行进程切换。理论上，这三个步骤应按顺序执行，但在实际的操作系统内核运行中，即使发生了引发调度的条件，也不一定能够立即进行调度与切换。

现代操作系统中，通常在以下情况下需要进行进程调度与切换：

1. 创建新进程后，父进程和子进程都处于就绪态，因此需要决定是运行父进程还是子进程，调度程序可以合法地选择其中一个先运行。
2. 进程正常结束或异常终止后，必须从就绪队列中选择某个进程运行；若没有就绪进程，则通常运行一个系统提供的闲逛进程。
3. 当进程因I/O请求、信号量操作或其他原因而被阻塞时，必须调度其他进程运行。
4. 当I/O设备准备就绪后，发出I/O中断，原先等待I/O的进程由阻塞态转换为就绪态，此时需决定是让该新就绪进程投入运行，还是让中断发生时正在运行的进程继续执行。

此外，在支持抢占的系统中，若更高优先级的进程进入就绪队列，或当前进程的时间片用完，也会触发调度并可能剥夺当前进程的CPU。

进程切换通常紧随调度之后发生，其核心任务是保存原进程的执行现场，并恢复新进程的现场。具体而言，操作系统内核会将原进程的上下文（包括程序计数器、寄存器状态等）保存到其PCB或内核栈中；随后，从新进程的PCB或内核栈中加载其上下文，更新地址空间相关信息（如页表基址)，重置程序计数器，并开始执行新进程。

然而，在以下情况下不能进行进程调度与切换：

1. 处理中断的过程中。中断处理逻辑复杂，实现上难以安全地进行进程切换；同时，中断处理属于系统内核工作，逻辑上不隶属于任何用户进程，不应被剥夺CPU资源。
2. 执行原子操作的过程中。如加锁、解锁、中断现场的保护与恢复等操作，通常需要屏蔽中断以保证原子性。在此期间，连中断都被禁止，更不应进行进程调度与切换。

若在上述不可调度期间发生了调度条件，系统会设置一个调度请求标志，待当前临界区或中断处理完成后，再根据该标志执行相应的调度与切换操作。

4. 进程调度的方式#

所谓进程调度方式，是指当某个进程正在CPU上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先级更高的进程进入就绪队列，此时系统应如何分配CPU。

通常有以下两种进程调度方式：

1. 非抢占调度方式，也称非剥夺方式。指当一个进程正在CPU上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，系统仍让当前进程继续执行，直到该进程运行完成(例如正常结束或异常终止)，或者因发生某种事件(如等待I/O操作、在进程通信或同步中执行了Block原语)而主动进入阻塞态，此时才会将CPU分配给其他进程。

   非抢占调度方式的优点是实现简单、系统开销小，适用于早期的批处理系统；但它无法满足分时系统和大多数实时系统对及时响应的要求。

2. 抢占调度方式，也称剥夺方式。指当一个进程正在CPU上执行时，若出现更高优先级的就绪进程，调度程序可依据一定策略暂停当前进程，将CPU分配给更紧迫的进程。

   抢占调度方式对提高系统吞吐率和响应效率都有明显好处。但“抢占”并不是一种任意的行为，必须遵循一定的原则，主要有优先级、短进程优先和时间片原则等。

5. 闲逛进程#

当进程切换发生时，若系统中没有就绪进程，操作系统会调度闲逛进程(Idle Process)运行，它的PID为0。闲逛进程的优先级最低，仅在无其他就绪进程时运行；一旦有新进程进入就绪队列，它会立即让出CPU。其主要任务是在空闲循环中不断检测中断请求。

闲逛进程不占用除CPU外的其他系统资源，也不会因等待事件而被阻塞。

6. 两种线程的调度#

1. 用户级线程调度。由于内核并不知道线程的存在，因此内核仍以进程为单位进行调度，将CPU时间分配给整个进程。当内核将CPU分配给某进程后，由该进程内部的用户级线程库决定具体运行哪个线程。线程切换在同一进程内完成，仅需保存少量寄存器状态，开销极小。但缺点是：若一个线程执行阻塞操作（如I/O），整个进程都会被阻塞。
2. 内核级线程调度。内核直接感知并管理每个线程，调度时选择的是特定线程，而非进程。每个线程拥有独立的内核上下文，可被单独赋予时间片；若时间片用完或被更高优先级线程抢占，则该线程会被强制挂起。由于涉及完整的上下文切换、地址空间更新（在跨进程线程间)以及可能的TLB刷新和缓存失效，其切换开销远高于用户级线程，通常高出数倍。

(1) 上下文切换#

将CPU切换到另一个进程，需保存当前进程的状态，并恢复另一个进程的状态，这个任务称为上下文切换。进程上下文由其PCB表示，包括CPU寄存器的值、进程状态、内存管理信息等。当进行上下文切换时，内核将旧进程的状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。在切换过程中，进程的运行环境发生实质性的变化。上下文切换的流程如下。

1. 挂起当前进程，将其CPU上下文保存到其PCB中。
2. 将该进程的PCB移入相应的队列，例如就绪队列，或因等待某事件而进入的阻塞队列。
3. 选择另一个进程执行，并更新其PCB中的相关信息。
4. 恢复新进程的CPU上下文。
5. 跳转到新进程PCB中的程序计数器所指向的位置，开始执行该进程。

(2) 上下文切换的消耗#

上下文切换是一项开销较大的操作，需要执行大量寄存器的保存与恢复指令。尽管单次切换所需的时间仅为微秒量级，但在高负载系统中，若每秒发生数十甚至上百次切换，则累积的CPU时间消耗将十分可观。为减少这一开销，某些处理器架构提供多个寄存器组，通过切换寄存器组指针即可完成上下文切换；但大多数通用处理器仍需完整保存和恢复寄存器状态。

(3) 上下文切换与模式切换#

模式切换（用户态和内核态之间的切换）与上下文切换是两个不同的概念。模式切换发生在同一进程内部，如用户进程因系统调用或中断进入内核态执行，完成后返回用户态继续执行该进程。此过程中，当前进程并未改变，因此不涉及上下文切换。而上下文切换则意味着从一个进程切换到另一个进程，必须保存旧进程的上下文并恢复新进程的上下文。由于该操作涉及内核数据结构（如PCB）的访问与修改，上下文切换只能由内核完成，且整个切换过程运行在内核态。

NOTE

调度和切换的区别：调度是决策行为，即决定将CPU分配给哪个进程；切换是执行行为，即实际完成CPU控制权的转移。通常，先由调度程序做出调度决策，随后触发上下文切换以实现该决策。