– {.alignnone}
– {.alignnone}# 1.调度的概念
## 1.1 调度的基本概念
### 1. 什么是调度？
在多道程序环境中，内存中通常有多个进程等待执行，但 CPU 的核心数量是有限的。**调度**就是操作系统按照一定的**策略**，从就绪队列中选择一个进程，把 CPU 的使用权分配给它的过程。
– ## **根本目的：** 提高 CPU 利用率，让系统更高效、公平地运行。
## 1.2.调度的三个层次
操作系统中的三级调度分别是：**高级调度（作业调度）**、**中级调度（内存调度）**、**低级调度（进程调度）**。
以下是详细的层级拆解：
### 1. 高级调度 (High-Level / Job Scheduling)
– **别名：** 作业调度、长程调度 (Long-term Scheduler)。
– **生活类比：** **“医院大门口的安检和分流”**。
– 医院里的人（内存中的进程）已经很挤了，保安（高级调度）决定外面排队的人（磁盘上的作业）谁能进大厅，谁得在外面等着。
– **任务：** 决定哪些**作业 (Job)** 从外存（磁盘）调入内存，并为它们创建进程、分配必要的资源（如内存、IO设备）。
– **频率：** **最低**（可能几分钟一次）。
– **关键作用：** 控制**多道程序的度 (Degree of Multiprogramming)**。即决定系统里同时有多少个进程在跑。进得太多，系统会卡死（颠簸）；进得太少，CPU 没事干。
### 2. 中级调度 (Medium-Level / Memory Scheduling)
– **别名：** 交换调度、中程调度 (Medium-term Scheduler)。
– **生活类比：** **“在大厅等待区的调整”**。
– 如果大厅（内存）里人太多挤不动了，或者有病人正在等化验结果（阻塞），保安就把暂时不看病的人请到外面的休息区（挂起状态/外存交换区），腾出空间给急需看病的人。等休息区的人条件具备了，再叫回来。
– **任务：** 负责**进程在内存和外存之间的交换 (Swapping)**。
– **挂起 (Swap Out)：** 将暂时不能运行的进程调至外存，腾出内存空间。
– **激活 (Swap In)：** 当具备运行条件且内存有空闲时，再调回内存。
– **频率：** **中等**。
– **关键作用：** 提高**内存利用率**和系统吞吐量。
### 3. 低级调度 (Low-Level / CPU Scheduling)
– **别名：** 进程调度、短程调度 (Short-term Scheduler)。
– **生活类比：** **“叫号进诊室”**。
– 这是最频繁的动作。医生（CPU）看完一个病人，护士（低级调度）立马从候诊椅（就绪队列）上叫下一个病人进去。
– **任务：** 从**就绪队列**中挑选一个进程，将 CPU 分配给它。
– **频率：** **最高**（毫秒级，一秒钟可能发生几十上百次）。
– **关键作用：** 决定谁真正占有 CPU 干活。**这是操作系统中最核心的调度，也是必不可少的调度（前两种在简单的系统中可能没有）。**
——
### 三级调度对比总结表
| **调度类型** | **别名** | **调度对象** | **发生频率** | **核心任务** |
| ———— | ——– | —————— | ———— | ———————————————— |
| **高级调度** | 作业调度 | 作业 (磁盘->内存) | 低 (分钟级) | **“准入”**：决定谁能进内存，控制多道程序数量。 |
| **中级调度** | 交换调度 | 进程 (内存<->外存) | 中 | **“交换”**：内存不够时“腾笼换鸟”，优化内存利用。 |
| **低级调度** | 进程调度 | 进程 (就绪->CPU) | 高 (毫秒级) | **“执行”**：决定谁现在能用 CPU。 |
### 它们是如何协作的？
想象一个进程的一生：
1. **出生：** **高级调度**把它从磁盘拉进内存，变成了“进程”。
2. **排队：** 它进入就绪队列，等待**低级调度**选中它去用 CPU。
3. **波折：** 运行过程中，内存不够了，或者它在等很慢的 I/O，**中级调度**可能会把它踢出内存（挂起），过一会再接回来。
4. **工作：** 它在**低级调度**的指挥下，断断续续地使用 CPU。
5. **结束：** 任务完成，退出系统。
## 1.3三级调度的联系
### 1. 核心联系：全生命周期的接力
一个作业从进入系统到完成，实际上就是在这三级调度之间“接力”：
– **第一棒（高级调度）：** 负责**“进门”**。它决定谁有资格从磁盘进入内存，拿到“准考证”（创建进程，建立 PCB）。它为低级调度提供了**候选池**。
– **第二棒（低级调度）这是操作系统中最核心的调度，也是必不可少的调度（前两种在简单的系统中可能没有）：** 负责**“干活”**。它从高级调度送来的（或中级调度换回来的）就绪队列中，挑选进程上 CPU 运行。
– **救火队（中级调度）：** 负责**“调节”**。当高级调度放进来的人太多，导致内存不足或 CPU 忙不过来时，中级调度就把部分进程暂时踢回磁盘（挂起），等系统缓过气来再接回来。
### 2. 具体协作关系图解
我们可以通过**“多道程序的度” (Degree of Multiprogramming)** 这个指标来看它们的配合：
1. **高级调度**决定了**度的上限**。它控制最初有多少个进程能进入内存。
2. **中级调度**动态**降低度的数值**。当内存紧张时，它减少内存中的进程数，防止系统“死机”或颠簸。
3. **低级调度**在既定的度下，尽可能**提高利用率**。它负责在这些有限的进程间快速切换，保证 CPU 不闲着。
### 3. 状态转换视角 (The Connection in State Transitions)
三级调度的联系主要体现在进程状态的流转上：
– **新建态 $\rightarrow$ 就绪态**：**高级调度**说了算。
– **就绪态 $\rightarrow$ 运行态**：**低级调度**说了算。
– **就绪/阻塞态 $\leftrightarrow$ 挂起态**：**中级调度**说了算（挂起与激活）。
### 4. 总结：如果配合不好会怎样？
– **如果高级调度太激进：** 内存塞满，导致中级调度疯狂“交换”进程，磁盘读写频繁，CPU 反而空闲（系统颠簸）。
– **如果低级调度太慢：** 即使内存里有进程，CPU 也经常闲置，用户觉得电脑反应极慢。
– **如果中级调度缺席：** 内存一旦用完，新进程进不来，老进程卡住，系统弹性极差。
# 2.调度的实现
## 2.1调度程序(调度器)
它的核心职责只有一句话：**在众多的任务中，决定把“老板”（CPU）的时间分给谁。**
以下从 **定义、工作机制、核心组成、真实案例** 四个方面为你拆解：
### 1. 什么是调度程序？
它是一段操作系统的代码，负责管理 CPU 资源。它维护着一个**“任务清单”**（就绪队列），并根据特定的**算法**（策略），不断地从清单中选择一个进程/线程，让它在 CPU 上运行。
– **输入：** 一堆等待运行的进程（就绪队列）。
– **输出：** 下一个获得 CPU 使用权的进程。
### 2. 调度程序是怎么工作的？ (When & How)
调度程序不是一直在运行的，它需要被**“触发”**。通常在以下几种情况，调度程序会醒来干活：
1. **当前进程“由于自身原因”不干了：**
– 进程运行结束（Exit）。
– 进程需要等 I/O（读取磁盘、等键盘输入），主动放弃 CPU（Block）。
2. **当前进程“被迫”停止（抢占）：**
– **时间片用完了：** 闹钟响了（时钟中断），该轮到下一个人了。
– **有更重要的人来了：** 一个高优先级的进程突然就绪（比如你移动了鼠标，中断处理程序唤醒了相关进程）。
### 3. 核心双子星：调度器 vs 分派器
在很多教材中，会把“决定谁来跑”和“让它跑起来”区分开，这涉及两个概念：
– **调度器 (Scheduler)：** **“决策者”**。
– 它只负责**选**。它看着一堆进程，计算优先级、权衡公平性，最后手指一指：“下一个就是你！”
– **分派器 (Dispatcher)：** **“执行者”**。
– 它负责**搬**。它负责具体的**上下文切换 (Context Switch)**。
– **动作：** 保存当前进程的现场（寄存器、PC指针） -> 加载被选中进程的现场 -> 跳转到新进程的代码地址开始执行。
### 4. 现实中的调度程序长什么样？
理论上我们学 FCFS、轮转调度，但在真实的操作系统（如 Linux 和 Windows）中，调度程序要复杂得多，且通常是混合型的。
#### **A. Linux 的调度器 (CFS – Completely Fair Scheduler)**
– **设计哲学：** **公平**。它不单纯看优先级，而是看谁“占便宜”少了。
– **数据结构：** **红黑树 (Red-Black Tree)**。
– 不是简单的队列。它把所有等待的进程挂在一棵树上。
– 树的左边是“CPU 用得最少”的进程（vruntime 最小），树的右边是“用得很多”的进程。
– **策略：** 调度器每次闭着眼去抓**树最左边**的那个节点，让它运行。运行一会后，它的 vruntime 变大了，就把它插回到树的右边去，给别人机会。
#### **B. Windows 的调度器**
– **设计哲学：** **响应优先**（为了让界面不卡顿）。
– **数据结构：** **多级反馈队列 (32个优先级)**。
– Windows 简单粗暴地把进程分成 32 个等级（0-31）。
– 系统总是先扫描最高优先级的队列，如果有进程就运行；如果空了，才看下一级。
– **策略：** 抢占式 + 时间片轮转。为了防止前台窗口卡顿，Windows 会给当前聚焦的窗口（前台进程）**“开小灶”**，临时提升它的优先级或给更长的时间片。
### 总结
| **概念** | **比喻** | **关键点** |
| ————— | ————————– | —————————————— |
| **调度程序** | 拥有排班权力的**行政秘书** | 决定 **Who** (谁下一个运行) |
| **分派器** | 负责换座位的**后勤人员** | 负责 **Switch** (上下文切换) |
| **触发时机** | **闹钟响了**或**有人请假** | 时钟中断、I/O 阻塞、进程结束 |
| **Linux (CFS)** | **天平** | 用红黑树保证大家用的时间尽量**公平** |
| **Windows** | **VIP通道** | 用多级队列保证重要的任务（界面）**响应快** |
### 5. 调度程序的三个核心组件
#### **(1) 排队器 (Enqueuer)**
– **职责：** 它是调度程序的“预处理”部分。
– **工作：** 当一个进程变为**就绪态 (Ready)** 时（例如刚创建完成，或者时间片用完，或者 I/O 结束），排队器负责把它放到这就绪队列的**正确位置**。
– **关键点：** “按照一定的策略”。
– 如果是**先来先服务 (FCFS)**，就插到队尾。
– 如果是**优先级调度**，就插到优先级对应的位置。
– 如果是**多级反馈队列**，就插到对应的那个队列里。
#### **(2) 分派器 (Dispatcher)**
– **职责：** 它是调度程序的“执行”部分（取出者）。
– **工作：** 依据调度算法选定了一个进程后，分派器负责把这个进程从就绪队列里**取出来**，并准备把 CPU 给它。
– **注意：** 在这张图的定义里，它主要负责逻辑上的“取出”和“分配权利”。
#### **(3) 上下文切换器 (Context Switcher)**
– **职责：** 它是最底层的“搬运工”，负责硬件级别的状态切换。
– **工作：** 这是一个非常消耗资源的过程。文中提出了一个很多同学容易忽略的细节——**两对上下文切换**。
### 6. 重点难点：为什么是“两对”上下文切换？
– **第一对切换（当前进程 $\to$ 分派器）：**
1. **保存：** 将**当前进程**的上下文（寄存器、PC指针等）保存到它的 PCB 中。
2. **装入：** 装入**分派器程序**的上下文，以便分派器代码能够运行（去做“选择下一个进程”这个逻辑判断）。
– **第二对切换（分派器 $\to$ 新进程）：**
1. **移出：** 分派器工作做完了，移出分派器的上下文。
2. **装入：** 将**新选出的进程**的 CPU 现场信息装入寄存器，开始运行新进程。
> **思考：** 在现代操作系统（如 Linux）中，调度器通常是内核代码的一部分，并不一定需要完整的“加载分派器上下文”这一步（因为已经在内核态了），但**考研理论模型**中，通常强调这个“进程 A -> 调度程序 -> 进程 B”的完整过程。
### 7. 硬件优化：如何减少开销？
– **问题：** 上下文切换需要执行大量的 `load` (读取) 和 `store` (存储) 指令，把寄存器里的数据搬进搬出内存，非常慢。
– **解决方案（硬件支持）：** 采用**两组（或多组）寄存器**。
– 一组给**内核**使用。
– 一组给**用户**使用。
– **效果：** 切换时，不需要真的把数据搬来搬去，只需要**改变指针**，让 CPU 指向另一组寄存器即可。这能极大地提升切换速度（从“搬家”变成了“换房间”）。
## 2.2 调度的时机、切换和过程
# **调度程序是内核程序**
### 1. 调度的时机 (When to Schedule?)
操作系统并不是随时随地都能进行进程调度的。调度通常发生在**“CPU 此时无事可做”**或者**“当前进程不得不让出 CPU”**的时候。
我们可以把时机分为两类：
#### A. 主动放弃 (Voluntary / Non-preemptive)
当前进程因为自身的行为，无法继续运行，必须让出 CPU：
1. **进程终止 (Termination)：** 进程执行结束 (`exit`)，CPU 空闲了。
2. **发生阻塞 (Blocking)：** 进程请求 I/O（读磁盘、发网络包）、等待锁 (`mutex`) 或信号量。此时进程进入**阻塞态**，必须调度其他进程。
#### B. 被动抢占 (Involuntary / Preemptive)
当前进程还想跑，但操作系统强制把它踢下来：
1. **时间片用完 (Time Slice Expiration)：** 最常见的情况。时钟中断发生，内核发现当前进程配额用光了。
2. **更高优先级的进程到达 (Wakeup)：**
– 例如：你正在通过键盘输入（中断发生），等待输入的文本编辑器进程被唤醒。它的优先级通常高于后台正在跑的编译任务，因此发生抢占。
3. **硬件中断：** 某些硬件错误或异常导致必须切换。
> **⚠️ 考研/面试高频考点：什么时候不能调度？**
>
> – 在**中断处理程序 (ISR)** 执行过程中。（中断理应极快，不能被切走）
> – 进程在操作系统**内核临界区**中（且持有自旋锁 Spinlock）时。（这会导致死锁或数据不一致）
> – *注：在现代 Linux 中，普通的内核态代码是可以抢占的（Preemptible Kernel），但持有自旋锁时绝对不行。*
——
### 2. 进程切换 vs. 模式切换 (The Distinction)
这是初学者最容易混淆的概念，也是理解性能开销的关键。
#### A. 模式切换 (Mode Switch)
– **定义：** 用户态 $\leftrightarrow$ 内核态的切换。
– **场景：** 系统调用、中断、异常。
– **开销：** **小**。只需要保存很少的寄存器（PC, PSW 等）到内核栈。
– **关键点：** **进程没变**。还是同一个进程，只是执行权限变了。
#### B. 进程切换 (Process Context Switch)
– **定义：** 进程 A $\to$ 进程 B。
– **场景：** 调度器决定运行另一个进程。
– **开销：** **极大**。
– 需要保存/恢复所有通用寄存器。
– **最痛的代价：** 切换内存地址空间（修改 CR3 寄存器/页表基址）。这意味着 **TLB（页表缓存）会被刷空**，L1/L2 Cache 的命中率也会瞬间暴跌。
– **关键点：** **只有进程切换才涉及调度**。
——
### 3. 调度的具体过程 (The Procedure)
结合 Linux 内核逻辑，一个完整的进程调度过程可以拆解为以下四个微观阶段：
#### **第一阶段：触发 (Triggering)**
调度不是随时发生的，通常需要一个“契机”来打断当前进程。
– **中断/陷入 (Interrupt/Trap)**：
– 当发生**时钟中断**（时间片用完）或**系统调用**（如 IO 请求）时，CPU 会从用户态（User Mode）切换到内核态（Kernel Mode）。
– **延迟调度的检测 (Lazy Check)**：
– Linux 不会立即调度，而是设置一个标志位。
– **关键点**：当中断处理程序结束，准备**返回用户态**之前，内核会检查 `current_thread_info()->flags` 中的 **`TIF_NEED_RESCHED`** 标志位。
– 如果为真，说明内核决定要换人了，此时调用核心调度函数 `schedule()`。
#### **第二阶段：保存与选择 (Save & Pick)**
这是“大脑”进行决策的阶段。
– **保存现场 (Save Context)**：
– 将当前进程 A 的 CPU 状态（包括 PC 指针、通用寄存器、浮点寄存器等）保存到它的 **内核栈** 或 **`task_struct` (PCB)** 中。
– **执行调度算法 (Pick Next)**：
– 内核调用调度类（Scheduling Class），例如 **CFS (完全公平调度器)**。
– **逻辑**：根据红黑树上的 **`vruntime` (虚拟运行时间)**，找到最左边的节点。
– **结果**：选定下一个要运行的进程 B。
#### **第三阶段：切换 (The Heavy Lifting)**
这是最消耗性能的“体力活”，通常由 `context_switch()` 函数完成。
– **1. 切换内存空间 (`switch_mm`)**：
– **动作**：修改 CPU 的 **CR3 寄存器**（页表基址寄存器），将其指向进程 B 的页目录。
– **性能代价 (高)**：
– 一旦 CR3 改变，CPU 的 **TLB (快表)** 会被刷新（Flush）。
– 这意味着接下来的内存访问会有大量的 TLB Miss，导致 CPU 必须去查物理内存中的页表，速度瞬间变慢。*(注：这是上下文切换开销大的主要原因)*
– **2. 切换内核栈与硬件上下文 (`switch_to`)**：
– **动作**：这是一个汇编宏。它将 CPU 的 **SP (栈指针)** 和 **FP (帧指针)** 从进程 A 的内核栈切换到进程 B 的内核栈。
– **关键一跳**：最后恢复进程 B 之前保存的 **PC (程序计数器)**。
– **瞬间转移**：当 PC 被加载的那一刻，CPU 就开始执行进程 B 的指令了（通常是它上次被中断的地方）。
#### **第四阶段：恢复 (Restore)**
此时，CPU 已经是在运行进程 B 的代码逻辑了。
– **恢复用户态 (Return to User)**：
– 进程 B 的内核栈中，保存着它上次被打断时的**用户态寄存器**上下文。
– **指令**：执行 **`IRET`** (x86) 或类似指令。
– **效果**：CPU 特权级从 Ring 0 变回 Ring 3，栈指针切回用户栈，程序继续在用户空间运行。
### 4.四大调度时机
### 一、 四大调度时机
#### 1. 创建新进程后 (fork)
– **教材说法：** 父子进程谁先运行？调度器决定。
– **Linux 内核实战：**
– 当你调用 `fork()` 时，内核会通过 `do_fork` 创建子进程。
– **关键问题：** 谁先跑？在早期的 Unix 中，倾向于让子进程先跑，因为子进程往往紧接着调用 `exec()`（替换代码段），这样可以避免父进程先写内存导致 **COW (Copy-On-Write)** 发生不必要的页面复制。
– **现代 Linux (CFS)：** 完全公平调度器（CFS）会通过对比父子进程的 `vruntime`（虚拟运行时间）来决定。通常可以通过 `/proc/sys/kernel/sched_child_runs_first` 参数来控制这个偏好。
#### 2. 进程结束 (exit)
– **教材说法：** 进程结束了，必须选个新的，没得选就选“闲逛进程”。
– **Linux 内核实战：**
– **闲逛进程 (Idle Task, PID 0)：** 这不是一个普通的进程。当就绪队列为空时，CPU 会运行 `cpu_idle_loop`。
– **硬件联动：** Idle 进程通常会执行 `HLT` 指令（x86），让 CPU 进入休眠状态以省电，直到下一个中断（通常是时钟中断）把它“叫醒”。
#### 3. 进程阻塞 (Blocking)
– **教材说法：** 也就是**主动放弃**。比如 I/O 请求、信号量 (`P`操作 / `wait`)。
– **C++ 编程启示：**
– 这是高性能服务器最**忌讳**的场景。
– **反面教材：** 传统的 `cin >> x` 或 `read(fd, …)` 是阻塞的。一旦调用，你的线程就被踢出 CPU，发生了昂贵的上下文切换。
– **正面教材：** 现代 C++ 网络库（如你关注的 Reactor 模式、epoll）使用 **非阻塞 I/O (O_NONBLOCK)**。如果没有数据，函数立即返回错误（EAGAIN），线程**不让出 CPU**，而是去处理其他连接。这就避免了这里提到的“必须调度其他进程”，从而极大提升吞吐量。
#### 4. I/O 中断发生 (Interrupt / Preemption)
– **教材说法：** 比如磁盘读完了，发个中断。原来等待数据的进程醒了（变就绪）。此时是**抢占**的好时机。
– **场景还原：**
– 网卡收到一个数据包 $\to$ 触发中断 $\to$ 网卡驱动处理 $\to$ 唤醒正在 `epoll_wait` 的 Nginx 进程。
– **决策：** 调度器会立刻计算：这个刚醒来的 Nginx 进程，优先级是不是比当前正在跑的进程高？如果是，立刻抢占（Preempt）；如果不是，标记一下 `need_resched`，等当前进程时间片用完再说。
## 2.3进程调度的方式
### 一、 按照调度机制分类（两大模式）
这是最基础的分类，决定了操作系统是否可以强制剥夺一个正在运行的进程的 CPU 使用权。
#### 1. 非抢占式调度 (Non-preemptive Scheduling)
– **机制：** 一旦 CPU 分配给某进程，该进程就会一直运行，直到它**自动释放** CPU（例如：进程终止、执行 I/O 操作阻塞、或主动调用 `yield`）。
– **特点：** 实现简单，系统开销小（上下文切换少）。
– **缺点：** 响应时间差。如果一个进程死循环，整个系统可能卡死。
– **适用场景：** 批处理系统、简单的嵌入式系统。
#### 2. 抢占式调度 (Preemptive Scheduling)
– **机制：** 操作系统可以在进程未执行完时，强制剥夺其 CPU 使用权，暂停该进程并保存状态，将 CPU 分配给另一个进程。
– **触发条件：** 时间片耗尽（时钟中断）、更高优先级的进程进入就绪队列。
– **特点：** 响应快，公平性好，防止单一进程独占 CPU。
– **适用场景：** 现代通用操作系统（Windows, Linux, macOS, Android）。
——
### 二、 经典的调度算法
操作系统根据不同的目标（吞吐量、响应时间、周转时间），采用了不同的算法。
#### 1. 先来先服务 (FCFS – First-Come, First-Served)
– **原理：** 像超市排队结账一样，谁先进入就绪队列，谁先执行。
– **类型：** 非抢占式。
– **优点：** 简单，易于理解和实现。
– **缺点：** 存在**护航效应 (Convoy Effect)**。如果一个 CPU 密集型的大进程在前面，后面所有的小进程都要等待很久，导致平均等待时间很长。
#### 2. 最短作业优先 (SJF – Shortest Job First)
– **原理：** 选择预计运行时间（Burst Time）最短的进程先执行。
– **类型：** 可以是非抢占式，也可以是抢占式（称为 **SRTF**, Shortest Remaining Time First）。
– **优点：** 理论上能获得**最短的平均等待时间**。
– **缺点：**
– 难以准确预测进程的下一次 CPU 执行时间。
– **饥饿现象 (Starvation)：** 长作业可能永远抢不到 CPU。
#### 3. 优先级调度 (Priority Scheduling)
– **原理：** 每个进程有一个优先级，CPU 分配给优先级最高的进程。
– **类型：** 抢占式或非抢占式。
– **缺点：** 低优先级进程可能产生饥饿。
– **解决方案：** **老化 (Aging)** 技术——随着等待时间的增加，逐渐提高进程的优先级。
#### 4. 时间片轮转 (RR – Round Robin)
– **原理：** 专门为分时系统设计。将 CPU 时间划分为固定的**时间片 (Time Quantum)**（如 10ms – 100ms）。就绪队列中的进程轮流执行一个时间片。
– **类型：** 抢占式。
– **关键点：** 时间片的大小选择至关重要。
– *太大*：退化为 FCFS，响应变慢。
– *太小*：上下文切换（Context Switch）太频繁，浪费 CPU 资源。
– **优点：** 响应时间短，公平（每个进程都能获得 1/n 的 CPU 时间）。
#### 5. 多级反馈队列 (MLFQ – Multilevel Feedback Queue)
这是现代操作系统调度算法的雏形，最通用且复杂。
– **原理：** 设置多个就绪队列，每个队列优先级不同，且时间片大小也不同。
– **规则：**
– 新进程进入最高优先级队列。
– 如果进程在当前队列的时间片内没执行完，它会被降级到下一个优先级的队列（认为它是 CPU 密集型）。
– 只有高优先级队列为空时，才调度低优先级队列。
– **优点：** 兼顾了短作业（高响应）和长作业（高吞吐），且不需要预知进程运行时间。
## 2.4闲逛进程
在操作系统中，**闲逛进程**（Idle Process），通常也被称为 **System Idle Process** 或 **PID 0**，是系统中最特殊、最基础的进程之一。
简单来说，**它是操作系统在“无事可做”时运行的进程**。
以下是关于闲逛进程的核心概念、工作原理以及它存在的意义：
——
### 1. 核心定义
当操作系统的调度器（Scheduler）在就绪队列（Runqueue）中找不到任何其他处于“就绪”状态的进程时，CPU 就会切换到闲逛进程。
– **它的格言是**：“兜底”。
– **它的优先级**：是全系统**最低**的。任何其他进程只要准备好运行，都会立即抢占闲逛进程。
### 2. 为什么要有一个“闲逛进程”？
你可能会问，如果没任务做，CPU 直接停下来不就行了吗？
– **硬件特性**：CPU（中央处理器）是一个必须不断执行指令的电子元件。只要电脑开着，程序计数器（PC）就必须指向某个地址，CPU 必须不断地取指、解码、执行。它不能处于“真空”状态。
– **占位符**：因此，操作系统需要一个永远处于“就绪”状态的代码段，填补 CPU 的空闲时间。这就是闲逛进程。
### 3. 它具体在干什么？
在早期的操作系统或极其简单的嵌入式系统中，闲逛进程可能只是一个死循环：
C
“`
while(1) {
// 啥也不干，单纯烧电
}
“`
但在**现代操作系统**（如 Linux、Windows）中，闲逛进程承担着极其重要的**节能（Power Management）**任务：
1. **执行 HLT 指令**：闲逛进程的循环中通常包含特殊的 CPU 指令（如 x86 架构下的 `hlt`，或 ARM 下的 `wfi` – Wait For Interrupt）。
2. **进入睡眠**：当 CPU 执行到 `hlt` 指令时，它会停止执行后续指令，切断流水线的部分时钟信号，进入**低功耗状态**（C-State）。
3. **等待唤醒**：CPU 会一直保持这个状态，直到接收到**硬件中断**（比如时钟中断、键盘输入、网络包到达）。中断发生后，CPU 醒来，处理中断，调度器检查是否有新进程被唤醒。如果有，运行新进程；如果没有，继续运行闲逛进程并再次休眠。
### 4. 在 Linux 中的实现细节
在 Linux 内核中，闲逛进程有一些有趣的特性：
– **PID 0**：它通常被称为 **Process 0** 或 **swapper**。
– **不是通过 fork 创建的**：它是内核启动时手动创建的第一个进程。所有其他进程（包括 init 进程，PID 1）最终都是由它衍生或间接衍生出来的。
– **Per-CPU 变量**：在多核（SMP）系统中，**每个 CPU 核心都有一个属于自己的闲逛进程**。因为每个核心如果没事做，都必须独立地去执行闲逛循环。
– **代码路径**：在 Linux 内核源码中，核心逻辑通常位于 `cpu_startup_entry` 函数中，最终调用 `do_idle`。
### 5. 如何观察它？
– **在 Windows 上**：打开任务管理器，你会看到一个名为“System Idle Process”的进程。如果它的 CPU 占用率是 **99%**，不要惊慌，这实际上是好消息，说明你的电脑很空闲，CPU 正在休息。
– **在 Linux 上**：使用 `top` 或 `htop` 命令时，你通常看不到 PID 0，因为它是内核的一部分，不参与普通的用户态调度统计。但是 `top` 输出头部的 `%id` (idle) 字段就是 CPU 运行闲逛进程的时间比例。
### 总结
| **特性** | **描述** |
| ———— | ————————————————– |
| **优先级** | 最低（永远被抢占） |
| **功能** | 填补 CPU 空闲时间，执行节能指令 |
| **存在形式** | 每个 CPU 核心一个 |
| **状态** | 永远处于就绪态（Ready），除非 CPU 正在运行其他进程 |
## 2.5两种线程的调度
### 一、 用户级线程 (User-Level Threads, ULT)
**核心概念：** 线程的管理（创建、同步、销毁、调度）完全由用户空间的**线程库**（如早期的 Pthreads 库、Java 早期的 Green Threads、Go 语言的 Goroutines）负责。
– **对内核是透明的：** 操作系统内核完全不知道这些线程的存在。内核只看到一个单线程的进程。
– **调度者：** 应用程序内部的运行时系统（Runtime System）。
**调度方式：** 通常采用 **“多对一”模型 (Many-to-One)**。多个用户级线程映射到一个内核执行实体上。
– **优点：**
1. **切换极快：** 线程切换只需要保存/恢复用户寄存器，不需要切入内核态（无 System Call 开销），效率极高。
2. **调度策略灵活：** 应用程序可以根据自己的需求实现特定的调度算法，不依赖 OS。
3. **跨平台：** 可以在不支持多线程的操作系统上运行。
– **缺点：**
1. **无法利用多核：** 因为内核只把它看作一个进程，所以同一时刻只能在一个 CPU 核心上运行。
2. **阻塞问题：** 如果其中一个线程发起了阻塞的系统调用（如 `read`），内核会挂起整个进程，导致所有其他线程也被阻塞（因为内核不知道还有其他线程可以运行）。
——
### 二、 内核级线程 (Kernel-Level Threads, KLT)
**核心概念：** 线程的创建、调度和管理全部由**操作系统内核**直接负责。这是现代操作系统（Windows, Linux, macOS）的标准实现方式。
– **内核可见：** 内核维护了每个线程的上下文信息（TCB – Thread Control Block）。
– **调度者：** 操作系统内核调度器。
**调度方式：** 通常采用 **“一对一”模型 (One-to-One)**。每一个用户程序创建的线程，都直接对应一个内核线程。
– **优点：**
1. **真正的并发：** 多线程可以被内核分配到不同的 CPU 核心上并行执行。
2. **不阻塞：** 如果一个线程执行系统调用阻塞了，内核可以立即调度该进程中的其他线程继续执行。
– **缺点：**
1. **开销大：** 线程切换需要从用户态切换到内核态（Context Switch），开销比用户级线程大得多。
2. **资源消耗：** 每个线程都需要内核分配栈空间和 TCB，大量线程会给内核带来压力。
| **特性** | **用户级线程 (ULT)** | **内核级线程 (KLT)** |
| ———— | —————————- | ————————————– |
| **管理者** | 用户态的库 | 操作系统内核 |
| **内核感知** | 不可见 | 可见 |
| **切换开销** | 极小 (数十纳秒) | 较大 (数微秒) |
| **并行性** | 无法利用多核 | 可利用多核 |
| **阻塞影响** | 一人阻塞，全家阻塞 | 一人阻塞，他人照跑 |
| **常见例子** | Go Goroutine, Python asyncio | Linux Pthreads (NPTL), Windows Threads |
# 3.调度的目标
### 一、 五大核心衡量指标 (Quantitative Metrics)
这是我们在设计或评价一个调度算法好坏时的“数学标准”，也是研究生考试或面试中的重点。
#### 1. CPU 利用率 (CPU Utilization)
– **目标：** 让 CPU 尽可能忙碌，不要闲着。
– **理想状态：** 在重负载下，CPU 利用率应接近 100%（实际系统中 40%-90% 都很常见）。
– **反例：** 如果 I/O 操作频繁导致 CPU 经常空转，说明调度或系统架构有问题。
#### 2. 吞吐量 (Throughput)
– **定义：** 单位时间内完成的进程（或作业）数量。
– **目标：** **最大化**吞吐量。
– **适用：** 对于服务器和批处理系统至关重要。
#### 3. 周转时间 (Turnaround Time)
– 定义： 从进程提交（Create）到进程完成（Terminate）的总时间。
$$T_{周转} = T_{完成时刻} – T_{到达时刻}$$
– **目标：** **最小化**周转时间。
– **意义：** 用户最关心的指标之一——“我让电脑跑个程序，多久能跑完？”
#### 4. 等待时间 (Waiting Time)
– **定义：** 进程在**就绪队列 (Ready Queue)** 中等待 CPU 的总时间。
– **目标：** **最小化**等待时间。
– **重要性：** 这是调度算法**唯一能直接控制**的指标。进程在 CPU 上跑多久取决于程序逻辑，做 I/O 多久取决于硬件，唯独“排队等多久”是调度器决定的。
#### 5. 响应时间 (Response Time)
– **定义：** 从用户提交请求到系统产生**第一次响应**（而非完成）的时间。
– **目标：** **最小化**响应时间。
– **适用：** 交互式系统（如 Windows 桌面、游戏、终端输入）。如果不及时响应，用户会觉得“卡顿”。
——
### 二、 不同系统的调度目标侧重
没有一种算法能同时满足所有目标，因为它们往往是冲突的。操作系统根据用途权衡：
#### 1. 批处理系统 (Batch Systems)
– **场景：** 科学计算、大数据处理、编译大型 C++ 项目。
– **核心目标：**
– **最大化吞吐量** (单位时间处理更多任务)。
– **最小化周转时间**。
– **牺牲：** 响应时间。用户不在电脑前盯着，所以延迟几秒没关系。
#### 2. 交互式系统 (Interactive Systems)
– **场景：** 个人电脑、手机、Web 服务器。
– **核心目标：**
– **最小化响应时间** (Response Time)。
– **牺牲：** 吞吐量。为了快速响应鼠标点击，频繁切换上下文会消耗 CPU 资源，降低整体处理能力。
#### 3. 实时系统 (Real-Time Systems)
– **场景：** 汽车刹车控制、工业机器人、DPDK 网络包处理。
– **核心目标：**
– **满足截止时间 (Meeting Deadlines)**：必须在规定时间内完成，否则后果严重。
– **可预测性 (Predictability)**：调度行为必须是确定的，不能忽快忽慢。
——
### 三、 经典的“权衡困境” (Trade-offs)
理解调度目标的关键在于理解**冲突**：
1. **响应时间 vs. 吞吐量**
– 想要响应快，就必须把时间片切得很小（频繁切换）。
– 但是上下文切换（Context Switch）是有开销的。切换太频繁，CPU 都在忙着保存/恢复寄存器，干正事的时间就少了，导致吞吐量下降。
2. **公平性 vs. 优先级**
– 想要公平，就大家轮流坐庄（Round Robin）。
– 但是重要的任务（如内核中断处理）需要特权。如果完全公平，紧急任务就会被拖慢。
### 总结图表
| **指标** | **目标** | **谁最在乎？** |
| ————– | ——– | ———————– |
| **CPU 利用率** | Max | 资源管理者 (云服务商) |
| **吞吐量** | Max | 批处理系统 (编译服务器) |
| **周转时间** | Min | 批处理用户 |
| **响应时间** | Min | 交互式用户 (玩游戏的你) |
| **截止时间** | Meet | 实时系统 (嵌入式/工控) |
# 4.进程的切换
进程的生命周期（创建、撤销、IO、切换）都必须通过**系统调用 (System Call)** 进入内核来处理。
在进程看来，它好像在独占 CPU，但实际上是内核在背后不断地“暂停-保存-恢复-启动”，维持着多任务的假象。
——
### 1. 什么是进程切换？
在单核 CPU 中，同一时刻只能有一个进程在运行。为了让用户感觉到多个程序在并行，操作系统会将 CPU 时间划分为极短的时间片。当一个进程的时间片用完，或者因为它需要等待某些资源（如磁盘 IO）而阻塞时，内核就会暂停当前进程，并将 CPU 交给另一个进程。
——
### 2. 进程切换的核心：上下文 (Context)
进程切换最关键的工作是保存和恢复“上下文”。上下文主要包含以下信息：
– **程序计数器 (PC)**：下一条要执行的指令地址。
– **寄存器集合**：通用寄存器、状态寄存器、栈指针等。
– **内存管理信息**：页表、段表（用于虚拟地址映射）。
– **进程状态**：如运行、就绪、阻塞等。
这些信息通常存储在内核为每个进程维护的 **PCB (Process Control Block，进程控制块)** 中。
——
### 3. 进程切换的具体步骤
进程切换是一个复杂的过程，通常由内核态代码完成，主要步骤如下：
1. **保存当前进程 (A) 的上下文**：将 CPU 寄存器中的数据保存到进程 A 的 PCB 中。
2. **更新 PCB 状态**：将进程 A 的状态从“运行态”改为“就绪态”或“等待态”。
3. **选择新进程 (B)**：调度程序（Scheduler）根据调度算法（如时间片轮转、优先级调度）从就绪队列中选出下一个要运行的进程。
4. **更新进程 B 的状态**：将进程 B 的状态改为“运行态”。
5. **恢复进程 B 的上下文**：从进程 B 的 PCB 中读取之前保存的寄存器数值，载入到 CPU 中。
6. **跳转执行**：根据恢复后的程序计数器，从进程 B 上次中断的地方继续执行。
——
### 4. 触发进程切换的时机
进程切换不会无缘无故发生，通常由以下事件触发：
– **中断 (Interrupt)**：例如硬件时钟中断，表示当前进程的时间片已到。
– **系统调用 (System Call)**：进程主动请求内核服务（如读取文件），在等待结果时会被切换。
– **自愿放弃**：进程执行完毕或遇到无法继续执行的错误。
– **抢占 (Preemption)**：一个更高优先级的进程进入就绪状态，内核强制切换当前进程。
——
### 5. 进程切换的代价 (Overhead)
虽然进程切换让系统看起来很流畅，但它是有**开销**的：
– **CPU 周期消耗**：保存和恢复寄存器需要时间。
– **Cache 失效**：这是最大的隐藏成本。新进程载入后，原先缓存在 L1/L2 Cache 中的数据可能不再适用，导致大量缓存缺失（Cache Miss），降低运行速度。
– **内核开销**：调度算法本身也需要消耗计算资源。
> **注意：** 相比之下，**线程切换**的开销通常比进程切换要小，因为线程共享相同的内存地址空间，不需要切换页表。
>
> ### 1. 传统切换：软件保存 (Standard Software Context Switch)
>
> 在大多数通用处理器（如典型的 x86 或 ARM 处理器）中，进程切换是一个昂贵的软件操作：
>
> – **动作**：内核代码必须手动发出指令，将 CPU 当前所有寄存器的值（如通用寄存器、栈指针等）一一写入主内存中的 **PCB（进程控制块）** 或内核栈中。
> – **代价**：这涉及大量的访存操作。此外，切换后往往会伴随高速缓存（Cache）失效，导致新进程启动初期性能极低。
>
> ### 2. 切换技术：硬件寄存器组 (Multiple Register Sets)
>
> CPU 会在硬件内部直接集成**多套寄存器组**。其核心原理如下：
>
> – **硬件备份**：CPU 内部不只有一套 $R0-Rn$ 寄存器，而是有两套甚至更多。
> – **指针跳转**：当需要切换进程时，操作系统不需要搬运数据，只需修改一个名为 **CWP (Current Window Pointer，当前窗口指针)** 的硬件寄存器，指向另一套已经存在的寄存器组。
> – **近乎零耗时**：这种切换只需要一个或几个时钟周期，完全消除了将寄存器保存到内存的延迟。
### 6.模式切换 vs 上下文切换
| **维度** | **模式切换 (Mode Switch)** | **上下文切换 (Context Switch)** |
| ———— | ————————————————– | —————————————————— |
| **定义** | CPU 在用户态和内核态之间转换 | CPU 从一个进程切换到另一个进程运行 |
| **进程标识** | **不改变**。逻辑上还是同一个进程 | **改变**。切换前后是不同的进程 |
| **开销** | 较小。主要涉及栈指针和少量寄存器的切换 | 较大。涉及虚拟内存、页表、全局变量等资源的完全替换 |
| **关系** | 进程切换**一定**发生在内核态（意味着包含模式切换） | 模式切换不一定会导致进程切换（如仅仅是普通的系统调用） |
### 7.调度和切换
#### 调度 vs 切换：决策与执行
很多人容易混淆这两个概念，但它们在操作系统中分工明确：
– **调度 (Scheduling)**：**“大脑决策”**。调度程序（Scheduler）根据特定算法（如 RR 时间片轮转、CFS 完全公平调度）从就绪队列中**挑选**出下一个应该运行的进程。这是一种策略行为。
– **切换 (Switching)**：**“体力干活”**。一旦决定了新进程，内核的切换代码（Dispatcher）就会执行具体的动作：把 CPU 资源从旧进程手中**移交**给新进程。这是一种执行行为。
> **先后顺序**：通常是“先调度、后切换”。只有先选好了目标，才有切换的目标。
# 5.CPU调度算法
## 1.FCFS
**先来先服务（First-Come, First-Served, FCFS）** 是最简单、最直观的进程调度算法。它的核心思想正如其名：按照进程到达就绪队列的先后顺序来分配 CPU 资源。
以下是该算法的详细解析：
### 1. 算法原理
– **决策机制**：这是一种典型的“调度”行为，即决定将 CPU 资源分配给哪个进程。
– **执行方式**：系统维护一个就绪队列。每当有进程进入就绪态，就将其挂在队列末尾。每当当前运行的进程释放 CPU（运行结束或因 I/O 阻塞），调度程序就会选择队列头部的第一个进程。
– **性质**：属于**非抢占式（Non-preemptive）**算法。一旦一个进程获得了 CPU，除非它自己运行结束或发生阻塞，否则它会一直占用 CPU，不会被中途强制切换。
### 2. 算法优点
– **简单易行**：逻辑非常简单，只需要一个 FIFO（先进先出）队列即可实现。
– **公平性**：从“排队”的角度来看是公平的，每个进程最终都能获得执行机会，不会出现“饥饿”现象（某个进程永远等不到 CPU）。
### 3. 算法缺点（核心问题）
– **平均周转时间长**：如果一个长进程先到达，后面跟着几个短进程，那么短进程必须等待很长时间，导致系统整体的平均等待时间显著增加。
– **护送效应（Convoy Effect）**：
– 想象一个计算密集型的长进程先运行，后面跟着一堆 I/O 密集型的短进程。
– 这些短进程可能只需要极短的 CPU 时间来发起 I/O 请求，但由于 FCFS 的限制，它们必须死等长进程完成。这会导致 CPU 和设备利用率的不均衡。
– **不利于交互式系统**：响应时间无法保证，用户体验较差。
### 4. 性能衡量示例
假设有三个进程：
– **P1**：执行时间 24ms，0ms 时到达。
– **P2**：执行时间 3ms，1ms 时到达。
– **P3**：执行时间 3ms，2ms 时到达。
**在 FCFS 下：**
1. P1 先运行（0-24ms）。
2. P2 接着运行（24-27ms）。
3. P3 最后运行（27-30ms）。
– **平均等待时间**：$(0 + 24 + 27) / 3 = 17ms$。
对比（如果短进程先运行）：
如果顺序是 P2 -> P3 -> P1，平均等待时间仅为 $(0 + 3 + 6) / 3 = 3ms$。可以看出 FCFS 对作业长度非常敏感。
### 5. 适用场景
– 目前主要作为**辅助算法**，例如在多级反馈队列调度中，对同一优先级的就绪队列常采用 FCFS。
– 适用于**作业调度**（将作业从外存调入内存）。
– 在对响应时间要求不高的后台批处理系统中仍有使用。
| **进程类型** | **FCFS 待遇** | **原因** |
| ———————– | ————- | —————————————————- |
| **长作业 / CPU 繁忙型** | **优待** | 非抢占式确保其能连续、高效地完成大量计算。 |
| **短作业 / I/O 繁忙型** | **冷落** | 极短的请求被堵在长任务后，导致响应慢且设备利用率低。 |
## 2.SJF
**短作业优先（Shortest Job First, SJF）** 是一种以进程的 **CPU 执行时间（Burst Time）** 为调度依据的算法。它优先选择估计运行时间最短的进程，以追求最佳的系统性能指标。
以下是该算法的详细解析：
### 1. 核心原理
– **调度准则**：当 CPU 空闲时，从就绪队列中选择估计运行时间（CPU 区间）最短的进程，将处理机分配给它。
– **决策性质**：这是一种典型的以“作业长度”为优先级的调度策略。
### 2. 算法分类
根据是否允许中断正在运行的进程，SJF 分为两种形式：
– **非抢占式 SJF（Non-preemptive SJF）**：
– 一旦 CPU 分配给某个进程，它就会一直运行直到完成或发生阻塞，即使中途有更短的进程到达，也不会切换。
– **抢占式 SJF（也称为 最短剩余时间优先，SRTF）**：
– 如果新到达的进程的预计运行时间比当前正在运行进程的**剩余时间**更短，则系统会暂停当前进程，转而执行新进程。
——
### 3. 算法优点
– **“理论上”的最优平均等待时间**：在所有进程同时到达的情况下，SJF 能够实现最小的平均等待时间和平均周转时间。
– **提高系统吞吐量**：由于短作业能快速执行并退出系统，单位时间内完成的任务数量增加。
### 4. 算法缺点（核心难点）
– **“饥饿”现象（Starvation）**：这是 SJF 最严重的问题。如果系统中源源不断地有短作业进入，长作业可能会永远得不到 CPU 资源，从而产生“饿死”现象。
– **运行时间难以预估**：在实际的通用操作系统中，很难准确知道一个进程接下来需要运行多久。通常只能通过历史记录进行“加权平均”预测。
– **对长作业不公平**：虽然 FCFS 歧视短作业，但 SJF 则是极端地歧视长作业。
——
### 5. 性能对比示例
沿用之前 FCFS 的例子，假设 P1(24ms), P2(3ms), P3(3ms) 同时到达：
– **FCFS 顺序 (P1, P2, P3)**：平均等待时间 **17ms**。
– **SJF 顺序 (P2, P3, P1)**：
1. P2 运行（0-3ms）
2. P3 运行（3-6ms）
3. P1 运行（6-30ms）
– **平均等待时间**：$(0 + 3 + 6) / 3 = 3ms$。
– **结论**：SJF 的平均等待时间远优于 FCFS。
### 6. 适用场景
– 主要用于**早期批处理系统**中的作业调度（因为作业量化较明确）。
– 在现代交互式系统中，SJF 很少直接作为唯一的调度算法，但其“短任务优先”的思想被广泛借鉴。
## 3.高响应比优先调度算法
**高响应比优先（Highest Response Ratio Next, HRRN）** 调度算法是一种综合平衡了 FCFS（先来先服务）和 SJF（短作业优先）优缺点的动态优先级调度算法。
它的核心设计目标是：**既能照顾短作业，又能防止长作业因“饥饿”而死**。
——
### 1. 核心公式
HRRN 算法的核心在于“响应比”（Response Ratio, $R_p$）的计算。每当调度程序需要挑选进程时，会计算就绪队列中每个进程的响应比：
$$R_p = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$$
——
### 2. 算法逻辑
– **短作业优先**：当多个进程的**等待时间相同时**，要求服务时间越短，响应比越高，因此短作业会优先执行。
– **长作业不饿死**：对于长作业，虽然其分母（要求服务时间）较大，但随着它在队列中**等待时间不断增加**，其分子也会变大，最终响应比会提高到足以获得 CPU 的程度。
– **性质**：通常属于**非抢占式**算法。只有当当前进程运行完毕或主动阻塞时，才会计算并重新调度。
——
### 3. 算法优点
– **兼顾长短作业**：它在一定程度上保留了 SJF 降低平均周转时间的优点，同时又弥补了 SJF 可能导致长作业饥饿的缺陷。
– **较好的响应时间**：新到达的短作业能快速提升响应比，从而得到及时的响应。
### 4. 算法缺点
– **系统开销大**：每次调度前都需要计算就绪队列中所有进程的响应比。如果队列中进程很多，频繁的浮点运算会增加系统的 CPU 负担。
– **服务时间预估难**：和 SJF 一样，HRRN 仍然需要预知（或预测）进程的“要求服务时间”，这在实际的通用分时系统中很难做到准确。
## 4.优先级调度算法
**优先级调度算法（Priority Scheduling Algorithm）** 是一种更加灵活的调度策略，它为每个进程分配一个“优先级”，调度程序总是选择就绪队列中优先级最高的进程投入运行。
根据你之前上传的资料，调度是**决策行为**（决定给谁），而优先级就是这种决策的核心依据。
——
### 1. 算法核心机制
– **优先级表示**：通常用一个整数表示。注意，不同系统定义不同（有些系统数字越小优先级越高，如 Linux；有些则相反）。
– **调度准则**：当 CPU 空闲时，检查所有就绪进程，将 CPU 分配给优先级最高的那个。
### 2. 算法分类
优先级调度根据是否允许中途“换人”，分为两种模式：
– **非抢占式优先级调度**：一旦最高优先级的进程占有了 CPU，它就会运行到结束或主动阻塞。即使中途来了更高优先级的进程，也必须等当前进程放手。
– **抢占式优先级调度**：如果新到达的进程优先级比当前正在运行的进程还要高，内核会立即触发**进程切换**，保存当前进程上下文并运行新进程。
——
### 3. 优先级的类型
优先级可以根据是否改变分为两类：
– **静态优先级**：进程创建时确定，整个运行期间保持不变。
– *依据*：进程类型（系统进程 vs 用户进程）、资源需求、用户级别等。
– **动态优先级**：根据进程的运行情况动态调整。
– *典型例子*：你刚才提到的 **HRRN（高响应比优先）** 就是一种动态优先级调度，它的优先级随等待时间的增加而提高。
——
### 4. 核心问题：饥饿与老化
优先级调度算法面临的最大挑战是 **“饥饿” (Starvation)**。
– **问题**：如果系统中不断有高优先级的进程进入，低优先级的进程可能永远无法获得 CPU。据说在 1973 年关闭麻省理工学院的一台计算机时，发现一个 1967 年提交的低优先级作业一直没被运行。
– **解决方案：老化 (Aging)**：
– 这是一种增加在系统中等待很长时间的进程优先级的技术。
– 例如，每等待 1 分钟，就将该进程的优先级提升 1 级。最终，即使是优先级最低的作业也会变成最高优先级并被执行。
[Image explaining the Aging technique where process priority increases over time]
——
### 5. 优先级分配的常用原则
在操作系统内核设计中，通常遵循以下优先级逻辑：
1. **系统进程 > 用户进程**：内核相关的任务（如内存管理、中断处理）必须优先处理。
2. **交互式进程 > 批处理进程**：为了保证用户操作不卡顿。
3. **I/O 繁忙型 > CPU 繁忙型**：优先让 I/O 进程发起设备请求，从而让 I/O 设备和 CPU 并行工作，提高效率。
## 5.时间片轮询调度算法
**时间片轮转（Round Robin, RR）** 调度算法是专门为分时系统设计的。它的核心思想是：将所有就绪进程排成一个队列，并为每个进程分配一个固定的、极短的时间段，称为**时间片（Time Quantum）**。
以下是该算法的深度解析，结合了你提供的有关“进程切换”和“内核支持”的背景：
### 1. 算法工作原理
– **循环队列**：操作系统将 CPU 资源按顺序分配给就绪队列中的每个进程。
– **强制抢占**：这是一种**抢占式**算法。当一个进程的时间片用完时，即使它没有运行结束，系统也会由时钟装置发出中断信号，强制剥夺其 CPU 使用权。
– **循环往复**：被剥夺 CPU 的进程会被放回就绪队列的末尾，等待下一轮调度。
### 2. 核心性能指标：时间片的大小
时间片的选择是 RR 算法性能的关键。根据你提供的资料，这直接影响了系统的开销：
– **如果时间片太大**：它会退化为 **FCFS（先来先服务）** 算法。在这种情况下，短作业可能又要排在长作业后面等待很长时间，失去了“分时”的意义。
– **如果时间片太小**：虽然响应速度变快了，但会导致**极其频繁的上下文切换**。
– 每次切换都涉及“模式切换”（从用户态进入内核态）和“上下文保存与恢复”。
– 过多的切换会使 CPU 大量时间浪费在内核管理而非真正的业务计算上，导致系统整体效率大幅下降。
### 3. 算法优缺点
– **优点**：
– **极致公平**：每个进程都能定期获得 CPU，没有任何进程会“饥饿”。
– **响应快**：非常适合人机交互系统，用户能感觉到程序在“同时”运行。
– **缺点**：
– **平均等待时间长**：由于每个进程都走走停停，总的平均周转时间往往比 SJF（短作业优先）要长。
– **对进程类型不敏感**：它不区分 I/O 繁忙型还是 CPU 繁忙型，这可能导致 I/O 设备的利用率不够理想（相比于那些会优先调度 I/O 进程的算法）。
——
### 4. 深度关联：为什么 RR 依赖内核与硬件？
– **内核支持**：RR 调度完全是在**操作系统内核**的支持下实现的。每一次时间片到期，都必须通过中断进入内核态，由内核执行调度决策。
– **硬件加速的可能性**：如果 CPU 支持**多个寄存器组**，那么 RR 算法在切换时间片时的开销会显著降低，因为“上下文切换”只需要简单地改变寄存器组指针，而不需要繁重的内存读写。
– **执行行为**：RR 强调了“调度”和“切换”的紧密配合——时钟中断决定了“切换”的时机，而 RR 算法规则决定了“调度”给队列中的下一个谁。
## 6.多级队列调度算法
**多级队列调度算法（Multi-level Queue Scheduling, MLQ）** 是一种将就绪队列划分为多个独立队列的调度策略。它不是一种单一的算法，而是一个**组合调度框架**，旨在根据进程的性质（如重要性、响应需求）提供不同的处理方式。
以下是该算法的深度解析：
### 1. 核心设计思想：分类管理
在实际系统中，进程的类型多种多样。MLQ 算法将就绪队列永久地划分为若干个单独的队列。
– **分类标准**：通常根据进程的属性进行划分，如：
– **系统进程**（优先级最高）
– **交互式进程**（如前台窗口程序，需要快速响应）
– **批处理进程**（如后台计算，对响应时间不敏感）
– **固定归属**：在一个纯粹的多级队列算法中，**进程进入系统时就被固定分配到某个队列**，在运行过程中不能跨队列移动。
### 2. 双层调度机制
MLQ 涉及两个层次的调度决策：
– **内部调度（Intra-queue）**：每个队列可以根据其进程特点，使用**不同的调度算法**。
– 比如：前台队列使用 **时间片轮转（RR）** 以保证响应；后台队列使用 **先来先服务（FCFS）** 以减少切换开销。
– **外部调度（Inter-queue）**：决定哪一个队列优先获得 CPU。
– **固定优先级抢占调度**：通常系统进程队列优先级 > 交互队列 > 批处理队列。只要高优先级队列有进程，低优先级队列就必须等待。
– **给定时间配额**：为了防止低优先级队列完全饿死，可以给每个队列分配一定的 CPU 时间百分比（如交互队列占 80%，批处理占 20%）。
——
### 3. 算法优缺点
– **优点**：
– **针对性强**：可以为不同响应要求的进程量身定制算法。
– **低调度开销**：由于进程不需要在队列间移动，内核管理逻辑相对简单。
– **缺点**：
– **缺乏灵活性**：如果一个进程的性质在运行中发生了变化（比如从 I/O 繁忙型变成了 CPU 繁忙型），它无法调整位置。
– **饥饿问题（Starvation）**：如果高优先级队列一直有任务，低优先级队列的进程可能永远得不到执行。
——
### 4. 关键区分：多级队列 (MLQ) vs 多级反馈队列 (MLFQ)
这是很多学习者容易混淆的地方：
| **特性** | **多级队列 (MLQ)** | **多级反馈队列 (MLFQ)** |
| ————– | —————— | ——————————- |
| **队列间移动** | **不允许** | **允许**（根据运行表现升/降级） |
| **灵活性** | 较低 | 极高，是现代系统的首选 |
| **解决饥饿** | 较难，依赖时间配额 | 较好，通过“老化”或降级机制解决 |
## 7.多级队列反馈调度算法
**多级反馈队列调度算法（Multilevel Feedback Queue, MLFQ）** 是现代操作系统（如 Windows、Linux、macOS）中应用最广泛、最复杂的 CPU 调度算法。
它通过动态调整进程的优先级，完美解决了“短作业优先”需要预知运行时间的问题，同时也有效避免了长作业的“饥饿”现象。
——
### 1. 核心运行机制
MLFQ 将就绪队列划分为多个优先级不同的队列（如 $Q_0$ 到 $Q_n$），并遵循以下规则：
– **初始进入**：新进程进入系统时，首先被放入最高优先级的队列 $Q_0$。
– **按优先级调度**：调度程序总是优先执行优先级最高队列中的进程。只有当 $Q_0$ 为空时，才会调度 $Q_1$ 中的进程，以此类推。
– **时间片差异化**：优先级越高的队列，分配到的时间片越短；优先级越低的队列，时间片越长。
– 例如：$Q_0$ 时间片为 8ms，$Q_1$ 为 16ms，$Q_2$ 为 32ms。
– **动态反馈（升/降级）**：
– **降级**：如果一个进程在当前队列的时间片内没运行完，说明它是 **CPU 繁忙型**，它会被降入下一级低优先级队列。
– **保持/升级**：如果进程在时间片用完前因 I/O 阻塞（说明是 **交互型/IO 繁忙型**），它在就绪后会被放回原队列，或者在某些实现中被提拔到更高优先级队列。
——
### 2. 为什么它是“全能型”算法？
MLFQ 能够自动识别进程类型并采取不同的策略：
1. **对短作业友好**：短作业通常能在 $Q_0$ 的第一个时间片内完成，这使它的平均周转时间接近于“短作业优先（SJF）”。
2. **对交互式进程友好**：I/O 繁忙型进程频繁放弃 CPU，能长期留在高优先级队列，保证了极快的响应速度。
3. **防止饥饿（老化机制）**：为了防止长作业在底层队列被“饿死”，系统会定期执行“优先级提升（Priority Boost）”，将所有等待过长的进程全部移回 $Q_0$。
# 6.多处理机调度
## 1.多处理机调度的亲和性和负载均衡
### 1. 处理器亲和性 (Processor Affinity)
**亲和性**是指一个进程在某个给定的 CPU 上尽量长时间运行，而不被迁移到其他处理器的倾向。
– **核心原因（高速缓存命中率）**：当进程在 CPU 1 上运行时，它最近访问的数据会存留在 CPU 1 的一级/二级缓存（Cache）中。如果进程下次还在 CPU 1 上运行，它可以直接从缓存读取数据，速度极快。
– **迁移代价**：如果进程被迁移到 CPU 2，那么 CPU 2 的缓存中没有该进程的数据（“冷”缓存），进程必须从内存重新读取，这会产生明显的性能损耗。
– **两种类型**：
– **软亲和性 (Soft Affinity)**：操作系统内核**尽量**让进程留在原处理器上，但不做硬性保证。如果为了全局利益（如负载均衡），内核仍可能将其迁移。
– **硬亲和性 (Hard Affinity)**：通过系统调用（如 Linux 的 `sched_setaffinity`）显式将进程**绑定**到特定的一个或多个 CPU 核上运行。
——
### 2. 负载均衡 (Load Balancing)
**负载均衡**是指在对称多处理（SMP）系统中，为了充分利用所有 CPU 的计算能力，尝试将工作负载均匀地分配到每个处理器上。
– **必要性**：如果没有负载均衡，可能会出现一个 CPU 忙得不可开交，而另一个 CPU 却在“摸鱼”闲置的情况。
– **实现方式**：
– **推送迁移 (Push Migration)**：一个特定的内核任务会定期检查各 CPU 的负载。如果发现负载不平衡，它会主动将进程从繁忙的 CPU“推”向空闲的 CPU。
– **拉取迁移 (Pull Migration)**：当一个 CPU 运行完自己的队列而变得空闲时，它会主动从其他繁忙 CPU 的就绪队列中“拉”一个进程过来执行。
——
### 3. 亲和性与负载均衡的“矛盾”
这两个机制在设计目标上是冲突的：
– **负载均衡**要求频繁地迁移进程，以达到 CPU 利用率的最大化。
– **亲和性**则要求尽量减少迁移，以保证缓存命中率和执行速度。
> **现代系统的策略**：操作系统内核（如 Linux 的 CFS 调度器）会在这两者之间寻找平衡。它通常会划定“调度域”，在同一个物理 CPU 的不同核心（共享 L3 缓存）之间进行负载均衡时，迁移成本较低；而只有当负载极度失衡时，才会进行跨物理 CPU 的迁移。
## 2.多处理机调度方案
### 1. 非对称多处理 (Asymmetric Multiprocessing, ASMP)
也称为“主从式（Master-Slave）”模式。
– **分配方式**：系统中有一个特定的处理器作为“主处理器（Master）”，负责处理所有的调度决策、I/O 请求和其他系统活动。
– **从属处理器**：其他的“从处理器（Slave）”只负责执行用户代码。
– **优点**：由于只有一台机负责调度，避免了多处理器之间对共享数据结构的竞争，设计简单。
– **缺点**：主处理器容易成为系统的性能瓶颈；如果主处理器故障，整个系统都会瘫痪。
### 2. 对称多处理 (Symmetric Multiprocessing, SMP)
这是目前最主流的方案（如现代的 Windows、Linux、macOS 均采用此方案）。
– **平等地位**：每个处理器都是平等的，都可以进行调度决策。
– **自调度 (Self-Scheduling)**：每个处理器都会检查共同的就绪队列，或者使用自己的私有队列来选择进程执行。
– **实现细节**：
– **静态分配**：进程从创建到销毁都固定在某个 CPU 上。
– **动态分配**：进程可以在不同的 CPU 之间迁移，这需要**负载均衡**（如拉取迁移或推送迁移）来保证各核忙闲均匀。
——
### 3. 自调度与专用处理器分配
在多核环境下，调度策略可以更精细化：
– **自调度 (Self-Scheduling)**：使用一个全局的就绪队列，所有 CPU 空闲时都去这个队列“抢”任务。
– *优点*：负载最平衡。
– *缺点*：需要对全局队列加锁，可能导致竞争；此外，进程频繁在不同 CPU 间跳动会导致 **CPU 亲和性**下降，Cache 命中率变低。
– **成组调度 (Gang Scheduling)**：将一组相关的线程（如属于同一个并行作业的线程）同时调度到一组处理器上运行。这对于需要频繁通信的并行程序非常有效。
– **专用处理器分配 (Dedicated Processor Assignment)**：在程序运行期间，为其专门分配一组处理器。这通常用于高性能计算，避免了任务切换带来的开销。
# 7.为什么要进行CPU调度
进行 **CPU 调度**（CPU Scheduling）是多任务操作系统能够高效运行的基础。如果不进行调度，计算机同一时间只能运行一个程序，且在程序等待输入输出（I/O）时，昂贵的 CPU 资源将被白白浪费。
根据你提供的资料和操作系统设计原理，进行 CPU 调度主要有以下几个核心原因：
——
### 1. 实现多任务处理 (Multitasking)
CPU 调度是多任务操作系统中的一个**必需的特性**。
– **并发执行**：通过调度，操作系统可以在多个进程之间快速切换，使用户感觉到多个程序正在“同时”运行。
– **身份切换**：调度程序负责决定“换哪个演员上场”，从而实现从一个进程到另一个进程的上下文切换。
### 2. 提高 CPU 利用率 (CPU Utilization)
这是调度最直接的目的。
– **避免闲置**：当一个进程因为等待 I/O（如读取磁盘、等待网络响应）而阻塞时，如果不进行调度，CPU 就会处于空闲状态。
– **资源转换**：调度程序会立即做出决策，将 CPU 分配给另一个处于“就绪”状态的进程，确保 CPU 尽可能保持繁忙。
### 3. 改善系统吞吐量 (Throughput)
– **任务管理**：通过合理的调度决策（如短作业优先 SJF），系统可以在单位时间内完成更多的进程任务。
– **效率最大化**：调度算法通过平衡 CPU 繁忙型和 I/O 繁忙型进程，使系统各部件（CPU 和外设）都能充分联动。
### 4. 保证公平性与防止“饥饿” (Fairness)
– **资源分配**：调度是一种**决策行为**，旨在决定如何公平地将资源分配给各个进程。
– **防止独占**：如果没有调度（如简单的 FCFS 遇到长作业），短作业或高优先级任务会被一直阻塞。调度算法（如时间片轮转或多级反馈队列）确保每个进程都有机会获得 CPU。
### 5. 缩短响应时间 (Response Time)
– **用户体验**：在交互式系统中，用户不希望点击鼠标后等待太久。调度程序通过优先处理交互式进程，确保系统能够快速响应用户操作。
– **内核支持**：这种快速响应必须在操作系统内核的支持下实现，通过频繁的模式切换和上下文切换来维持流程度。
——
### 总结：决策与执行的配合
如你上传的图片所述：
– **调度（决策）**：解决“**给谁**”分配资源的问题。
– **切换（执行）**：解决“**如何**”实际移交资源的问题。
正是因为有了 CPU 调度，计算机才能从单一任务的“计算器”进化为能够同时处理办公、娱乐、后台下载的“智能终端”。
# 8.调度算法有哪几种
### 1. 基础/批处理系统算法 (注重效率与平衡)
这些算法通常用于对实时性要求不高的场景。
– **先来先服务 (FCFS)**：按到达顺序排队，简单但对短作业不友好（护卫效应）。
– **短作业优先 (SJF)**：优先执行时间短的任务，能实现**最短的平均等待时间**。
– **高响应比优先 (HRRN)**：根据 $R_p = 1 + \frac{\text{等待时间}}{\text{服务时间}}$ 动态计算优先级，兼顾长短作业并防止饥饿。
——
### 2. 分时操作系统调度 (注重交互性与公平)
**分时系统（Time-sharing OS）**（如 Linux、Windows）的主要目标是提供流畅的人机交互，让每个用户感觉独占 CPU。
– **时间片轮转 (RR)**：
– **原理**：每个进程轮流执行一个固定的时间片。
– **核心**：完全依赖于**内核**发出的时钟中断进行强制抢占。
– **挑战**：由于切换极快，**上下文切换**开销成为瓶颈，此时硬件提供的**多组寄存器**优化能极大提升响应速度。
– **多级反馈队列 (MLFQ)**：
– **原理**：设置多个优先级队列，时间片随优先级降低而增大，且进程能在队列间动态升降。
– **优势**：它是目前工业界最成熟的方案，能自动区分 I/O 繁忙型（高优）和 CPU 繁忙型（低优）进程。
——
### 3. 实时操作系统调度 (注重确定性与截止时间)
**实时系统（RTOS）**（如车载控制、工业控制系统）的核心不是“快”，而是“**准**”，即必须在规定的**截止时间 (Deadline)** 前完成任务。
– **固定优先级抢占调度 (RMS, Rate Monotonic Scheduling)**：
– **原理**：属于静态优先级。周期越短（发生频率越高）的任务，优先级越高。
– **应用**：目前大多数商用 RTOS（如 VxWorks, uC/OS）都基于此理论。
– **最早截止时间优先 (EDF, Earliest Deadline First)**：
– **原理**：属于动态优先级。截止时间越近的任务，优先级越高。
– **挑战**：虽然它能实现最高的 CPU 利用率，但实现复杂且在任务过载时系统行为难以预测。
——
### 总结：三种系统的核心差异
| **特性** | **批处理系统** | **分时操作系统** | **实时操作系统** |
| ———— | ————– | ———————- | ————————— |
| **典型算法** | FCFS, SJF | **RR, MLFQ, CFS** | **RMS, EDF** |
| **首要目标** | 吞吐量 | **交互响应时间** | **任务截止时间 (Deadline)** |
| **底层要求** | 较少的切换开销 | 频繁、高效的上下文切换 | 极低的**中断响应延迟** |
| **调度性质** | 非抢占为主 | **必须具备抢占能力** | **极高优先级的强制抢占** |
# 9.补充
1. | **调度级别** | **术语名称** | **形象比喻** | **核心目的** |
| ———— | ———— | ———————————————————— | ————————— |
| **高级调度** | 作业调度 | **大门保安**：决定哪些应聘者（作业）可以进厂变成正式员工（进程）。 | **控制多道程序度** |
| **中级调度** | 内存调度 | **宿舍宿管**：把暂时没活干的员工送去校外宿舍（硬盘），给新员工腾床位。 | **提高内存利用率/节省内存** |
| **低级调度** | 进程调度 | **流水线组长**：决定谁现在上机器操作（CPU），频率极高。 | **提高 CPU 利用率** |
2. **互斥性 (Mutual Exclusion)：** **注意：** 互斥性是**进程同步与通信**的概念，属于“并发控制”范畴。它要求同一时间只有一个进程访问临界资源。调度算法的任务是决定“谁先用”，而不是“如何保证独占”。因此，它不是调度算法的设计指标
3. **进程上下文 (Process Context)** 是指操作系统为了让一个进程在被中断（挂起）后能重新恢复运行，而必须保存的所有信息。它通常分为以下几部分：
1. **用户级上下文 (User-level Context)**：包含进程的用户程序、用户数据、**用户堆栈 (D)** 等。
2. **寄存器上下文 (Register Context)**：包含程序计数器 (PC)、状态寄存器、通用寄存器、堆栈指针等，这被称为**进程现场信息 (A)**。
3. **系统级上下文 (System-level Context)**：包含 **进程控制信息 (B)**（即 PCB 中的内容，如 PID、调度优先级等）、进程页表、内核栈等。
4. #### 为什么“中断向量”不属于进程上下文？
– **中断向量 (Interrupt Vector)** 是指中断服务程序的入口地址，通常存储在内存中的一个固定表格（中断向量表）里。
– 它是**操作系统内核**在处理中断请求时使用的全局资源，由硬件和内核维护，用于确定发生某种中断时应该跳转到哪段代码去执行。
– 中断向量与特定的进程无关，它不随进程的切换而改变。因此，它不属于任何特定进程的“上下文”。
5. **临界区 $\neq$ 不可调度**
– 进程在临界区被调度可能会导致其他想进入同一临界区的进程阻塞，但这不代表系统“无法”进行调度。
6. 上下文切换主要涉及 **CPU 寄存器**、**内核栈** 和 **PCB 信息** 的保存与恢复。进程的代码和数据通常保留在**主存 (RAM)** 中。只有在发生“页面置换”或“进程挂起（Swapping）”时，才会将数据移至磁盘。如果每次切换都读写磁盘，系统性能将因磁盘 I/O 过慢而彻底崩溃。
7. | **切换类型** | **程序计数器 (PC)** | **寄存器与栈指针** | **虚拟地址空间 (页表)** | **进程资源 (文件表等)** |
| ——————– | ——————- | —————— | ———————– | ———————– |
| **进程切换** | 更新 | 更新 | **更新** | **更新** |
| **同一进程线程切换** | 更新 | 更新 | **不更新** | **不更新** |
8. 时间片轮询算法是据对可抢占的
9. 在操作系统中，作业和进程是两个既有联系又有区别的概念：
1. **单位属性不同（答案B的核心）**：
– **作业**是用户向计算机提交任务的任务实体。它是**以用户任务为单位**的，用户将程序、数据和操作说明书组织在一起形成一个作业。
– **进程**是操作系统进行资源分配和调度运行的基本单位。它是**以操作系统控制为单位**的，代表了程序在处理机上的一次执行过程。
2. **存在形式不同**：
– 作业主要存在于**外存**（磁盘）中，处于“后备状态”。
– 进程则是**动态**的，它存在于内存中，拥有自己的生命周期（创建、运行、撤销）。
3. **对应关系**：
– 一个作业通常由一个或多个进程组成。当系统决定执行某个作业时，会为其创建一个或多个进程。
——
### 排除其他选项：
– **A. 两者执行不同的程序段**：错误。作业中的程序段最终就是通过进程来运行的，两者执行的代码内容是一致的。
– **C. 前者是批处理的，后者是分时的**：错误。作业和进程的概念在批处理系统和分时系统中都存在。
– **D. 后者是可并发执行，前者则不同**：错误。作业在后备队列中也可以看作是某种形式的并发准备，且多个作业对应的多个进程是在系统中并发执行的