处理机调度

🔥 高优先级

选择题必考内容，重点掌握 调度指标的计算 和 各种调度算法的实现细节 ，调度的实现和进程上下文切换相比之下考察比较少。

调度指标

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

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

系统层面

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

系统指标	含义
CPU 利用率	CPU 活跃时间与总观察时间的比率。通常表示为百分比
系统吞吐量	操作系统单位时间内系统完成的工作量或进程数

进程层面

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

进程调度指标	英文	含义
到达时间	AT, Arrival Time	进程在何时到达调度器，即何时被提交
等待时间	WT, Waiting Time	进程等待了多长时间才开始执行
要求服务时间	BT, Burst Time	进程从开始执行到结束需要多少时间
完成时间	CT, Completion Time	进程何时执行完成
周转时间	TAT, Turnaround Time	进程从提交到完成的时间， TAT = CT - AT = WT + BT

系统调度过程

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

Mid-term…Text is not SVG - cannot display

高级调度 （长程调度，Long-term Scheduling）:

功能：高级调度 主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
主要目标：保持内存中适当数量的进程。不要过多也不要过少。
当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器 从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。

中级调度 （中程调度，Mid-term Scheduling）:

功能：中级调度 涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器 可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
主要目标：为高级调度 和初级调度 器优化内存使用。
中级调度器 在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。

初级调度 （短程调度，Short-term Scheduling）:

功能：初级调度 决定哪个进程应当被赋予 CPU 时间片，即决定下一个运行在处理器上的进程。
主要目标：确保 CPU 的高效利用。
它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器 必须是非常快速的。

调度的实现

调度器

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

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

调度时机

调度的时机可能包括以下情况：

进程进入或退出系统
进程从运行状态变为阻塞状态
或者一个时间片结束。

调度方式

抢占式调度 （Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将 CPU 分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
非抢占式调度 （Non-Preemptive）：在这种方式下，一旦 CPU 分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待 I/O 操作）。

闲逛进程

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

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

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

system idle process

两种线程的调度

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

调度算法

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

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

先来先服务

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

最短作业优先

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

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

最高响应比优先

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

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

Response Ratio=BTWT+BT=BTTAT

其中 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 状态）。在此期间，即使有更高优先级的进程到达并加入就绪队列，当前进程也不会被中断，而是继续执行直到结束。

注意

在常见的操作系统和调度算法中，优先级的值越小，优先级越高 。

比如对于 Unix 系统，使用 nice 值来表示优先级：

nice 值越低，进程获得 CPU 时间的机会越多。

抢占式优先级调度

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

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

时间片轮转

时间片轮转（Round Robin，RR）这是一种基于 时间片 的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的 CPU 时间分配。

Process (Arrival Time, Burst Time)

上图中给出了每个进程的到达时间和要求服务时间，调度器按照轮询的方式依次遍历进程，每个进程只有执行时间片内的时间，之后便进入等待状态。

多级反馈队列

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

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

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

上下文切换

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

进程上下文内容

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

上下文切换流程

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