处理机调度

调度的指标

系统调度过程

进程调度是计算机操作系统中的一种核心功能，它决定了哪个进程应该在给定的时间段内使用处理器。为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
   • 主要目标：为高级和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，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 时间，以维持系统的运行稳定。如下图所示：

两种线程的调度

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

调度算法

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

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

先来先服务

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

最短作业优先

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

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

最高响应比优先

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

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

$$\text{Response Ratio} = \frac{W + B}{B}$$

其中 $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，每个进程的时间指标如下表所示：

优先级调度

优先级调度（Priority Scheduling）可以是非抢占式的，也可以是抢占式的。

非抢占式优先级调度总是从等待队列中选取一个优先级最高的进程进行执行。当有进程正在执行时，其他进程必须等待

抢占式优先级调度要确保系统中每个时刻中正在执行的进程的优先级都是最高的。所以当优先级更高的进程到达时，调度器要立刻执行该进程，正在执行的优先级更低的进程会被挂起加入等待队列。

时间片轮转

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

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

多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为多个队列，每个队列有不同的优先级和时间片大小。新创建的进程进入最高优先级队列，如果没有完成，它将下降到较低优先级的队列，直到完成。

上下文及其切换机制

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

进程上下文内容

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

上下文切换流程

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