处理机调度

调度指标

在操作系统里，调度（Scheduling） 是把 CPU 时间合理分配给多个进程（或线程）的核心机制。调度的好坏直接决定系统的响应速度、吞吐能力以及资源利用效率。为了衡量调度策略的优劣，我们通常用一组 调度指标 来量化：

1. 系统层面的宏观指标——关注整个计算机系统的运行状态，如 CPU 的利用率、系统整体的吞吐量等。这类指标帮助我们了解系统在整体负载下是否“忙碌”或出现瓶颈。
2. 进程层面的微观指标——关注单个进程在调度器眼中的表现，包括它何时进入调度队列、等待多久才被分配 CPU、实际执行多长时间以及最终何时完成等。这类指标可以帮助我们比较不同调度算法（FCFS、SJF、RR、优先级调度等）对单个作业的影响。

系统层面

系统层面主要关注 CPU 利用率和吞吐量这两个指标：

进程层面

从进程视角而言，进程从被创建到执行结束会有一系列时间周期作为指标：

系统调度过程

为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度 主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度 涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
   • 主要目标：为高级调度和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，Short-term Scheduling）:
   • 功能：初级调度 决定哪个进程应当被赋予 CPU 时间片，即决定下一个运行在处理器上的进程。
   • 主要目标：确保 CPU 的高效利用。
   • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

• 调度器 是操作系统中负责决定下一个要执行的进程或线程的部分。
• 基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得 CPU 时间。
• 调度器 通常分为长程、中程和短程调度器，如前文所述。

调度时机

可能引发调度的事件大致有以下几类：

1. 当前进程主动让出 CPU：进程正常结束、异常终止，或因等待 I/O、等待信号量等原因由运行态转为阻塞态。
2. 有进程进入就绪队列：新进程被创建，或某个阻塞进程等待的事件已完成（如 I/O 完成）而转为就绪态。
3. 时间片用完：时钟中断到达，当前进程用完了分配给它的时间片。

其中第 1 类事件的共同点是 当前进程已经无法继续占用 CPU，因此无论采用哪种调度方式都必然发生调度；而第 2、3 类事件的共同点是 当前进程本来还可以继续运行，是否此刻切换进程，取决于系统采用的是抢占式还是非抢占式调度。

调度方式

非抢占式调度（Non-Preemptive，又称非剥夺方式）：一旦把 CPU 分配给某个进程，就让它一直运行下去，直到它 自己结束或主动转为阻塞态，才把 CPU 交给下一个进程。也就是说，只有上面第 1 类事件才会触发调度：

• 新进程创建、更高优先级的进程变为就绪 —— 不调度，新到达的进程只能在就绪队列中排队等待。
• 时间片到期 —— 不适用（非抢占式算法本身不使用时间片）。

抢占式调度（Preemptive，又称剥夺方式）：当进程正在运行时，操作系统可以强行中断它、把它放回就绪队列，再把 CPU 分配给另一个进程。除第 1 类事件外，第 2、3 类事件同样可能触发调度：

• 新进程创建，且其优先级（或剩余运行时间等指标）优于当前进程 —— 立即抢占，当前进程由运行态回到就绪态。
• 阻塞进程被唤醒进入就绪队列，且优于当前进程 —— 立即抢占。
• 时间片用完 —— 必然切换（如时间片轮转）。

因此，判断某个算法是否抢占式，一个直观的检验标准是：

一个新进程到达时，正在运行的进程会不会被打断？ 会，就是抢占式；不会，就是非抢占式。

下图以“P1 先到达、P2 后到达且优先级更高”为例，对比两种调度方式在 P2 到达这一时刻的不同处理：

闲逛进程

闲逛进程（Idle Process）是操作系统中的一个特殊进程，当系统没有任何其他可运行的进程时，调度器会将 CPU 的控制权交给这个进程。闲逛进程的主要目的是确保在没有任务可执行的情况下，CPU 不会空转，从而防止 CPU 进入不受控制的状态。

在 Linux 操作系统中，闲逛进程的进程 ID 通常是 0，被称为 swapper 或 idle task。它是系统启动时创建的第一个进程，始终在内核态运行，确保当没有其他可调度任务时，CPU 有事情可做。

在 Windows 系统中，闲逛进程被称为 System Idle Process，同样用于在系统空闲时占据 CPU 时间，以维持系统的运行稳定。如下图所示：

两种线程的调度

• 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
• 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
• 对于 内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
• 对于 用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比 内核级线程 更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

根据 是否可抢占 可以对调度算法进行如下分类：

• 非抢占型调度算法：先来先服务、最短任务优先、最高响应比优先
• 抢占型调度算法：时间片轮转、多级反馈队列

先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序 分配依次执行。先到达的进程先执行，后续进程等待直到前一个进程执行才能进一步执行。

最短作业优先

最短作业优先（Shortest Job First，SJF）算法在从就绪队列中选择进程时，会 选择运行时间最短 的进程进行执行。

在题目中进程的运行时间一般都是给定的，所以 SJF 算法比较容易实现。但是在真实的系统中进程的运行时间是不确定的，所以在使用该算法时操作系统需要对进程的运行时间进行预估。

最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）算法从就绪队列中选择 响应比 最高的进程进行执行。

其中 响应比（Response Ratio）的计算公式如下：

其中 $W$ （Waiting Time）为进程的等待时间， $B$ （Burst Time）为进程的要求服务时间（从执行开始到结束所需时间）。

这种计算策略可以有效地避免饥饿现象，即一个进程等待了很长时间但仍没有得到执行。一个进程的等待时间越长，其 响应比 就会更大，进而优先得到执行机会。一个进程的执行时间很长，其 响应比 就会越小，会优先调度其他进程。

• 时刻 0：只有 P1 到达，执行 P1。
• 时刻 5：P1 执行完成。P2 的 响应比 为 (4 + 3) / 3 ≈ 2.33，P3 的 响应比 为 (3 + 8) / 8 = 1.375，P4 的 响应比 为 (2 + 6) / 6 ≈ 1.33，此时 P2 的 响应比 最大，执行 P2。
• 时刻 8：P2 执行完成。P3 的 响应比 为 (6 + 8) / 8 = 1.75，P4 的 响应比 为 (5 + 6) / 6 ≈ 1.83。此时 P4 的 响应比 更大，执行 P4。
• 时刻 14：P4 执行完成，只剩下 P3 了，最后执行 P3。

所以进程的执行顺序为 P1、P2、P4、P3，每个进程的时间指标如下表所示：

优先级调度

优先级调度是一种基于进程优先级的调度算法，广泛应用于操作系统中。根据是否允许中断当前正在执行的进程，优先级调度可分为 非抢占式优先级调度 和 抢占式优先级调度 两种形式。

在 非抢占式优先级调度 中，调度器总是从就绪队列（等待队列）中选择优先级最高的进程执行。一旦某个进程开始执行，它将持续运行直到完成（或主动释放 CPU，例如进入等待 I/O 状态）。在此期间，即使有更高优先级的进程到达并加入就绪队列，当前进程也不会被中断，而是继续执行直到结束。

抢占式优先级调度 旨在确保系统中任何时刻运行的进程始终是优先级最高的。当一个更高优先级的进程到达时，调度器会立即暂停当前运行的低优先级进程（将其挂起并加入就绪队列），然后将 CPU 分配给新到达的高优先级进程。

下图给出了两种优先级调度方式的实例对比，其中绿色的进程表示执行态，黄色表示就绪态：

时间片轮转

时间片轮转（Round Robin，RR） 是一种专门用于 分时系统 的调度算法。系统为每个进程分配一个固定大小的 时间片（time quantum），就绪进程按照 FIFO 顺序组织成就绪队列，CPU 按队列顺序轮流为进程分配时间片。

调度过程可以概括为：

1. 从 就绪队列队首 取出一个进程运行。
2. 若进程在一个时间片内 执行完毕，则进程退出，调度器从队列中选择下一个进程。
3. 若时间片用完而进程 尚未执行完毕，则发生一次 时间片中断，该进程重新进入 就绪队列队尾，CPU 转而执行队首的下一个进程。
4. 如果运行过程中有新的进程到达，则新进程进入 就绪队列队尾。
5. 重复上述过程，直到所有进程执行完毕。

因此，RR 的核心并不是简单地“按照进程编号轮流执行”，而是：

维护一个就绪队列，每次只允许队首进程最多运行一个时间片；未完成的进程重新排到队尾。

举个实际例子，假设时间片大小为 3，不同进程在不同时刻加入就绪队列，那么调度过程如下图所示：

调度器按照轮询的方式依次遍历进程，每个进程只有执行时间片内的时间，之后便进入等待状态：

时间片的影响

时间片 $q$ 的大小会显著影响 RR 的性能：

• 时间片过大：RR 会逐渐接近 FCFS。进程往往一次运行很长时间，交互响应性变差。
• 时间片过小：进程切换非常频繁，虽然响应时间较好，但会产生大量 上下文切换开销，降低 CPU 的有效利用率。
• 因此，实际系统需要选择一个合适的时间片，使 响应速度 和 上下文切换开销 之间取得平衡。

可以将其理解为：

而 $q$ 越小，进程之间的切换越频繁。

多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为 多个队列，每个队列有不同的优先级和时间片大小。

高优先级队列优先调度，时间片较短，适合交互型进程；低优先级队列时间片较长，适合计算密集型任务。新进程通常进入最高优先级队列，若在时间片内未完成，则移到下一级队列；若因 I/O 等待阻塞，完成后可能返回较高优先级队列。

多级反馈队列根据进程行为调整其优先级。例如，占用 CPU 过多的进程会被降级，而频繁等待 I/O 的进程可能被提升。这种设计兼顾了快速响应、公平性和资源利用率。

上下文切换

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为 上下文切换。

进程上下文内容

1. 寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
2. 程序计数器：表示进程的下一个指令的位置。
3. 虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
4. I/O 状态信息：包括打开的文件描述符、网络连接、I/O 指针等。
5. CPU 调度信息：例如进程优先级、计划器状态等。
6. 资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

1. 保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
2. 选择下一个要执行的进程：调度器决定下一个要运行的进程。
3. 恢复下一个进程的状态：操作系统从新进程的 PCB 中恢复其上下文信息，包括寄存器值、程序计数器等。
4. 开始执行新进程。