• https://tingwu.aliyun.com/doc/transcripts/3vl8qg62xaeonpr2?sl=1# 《2-3 处理机调度 720P》

处理机调度——深度解析与核心算法详解

导言：处理机调度的本质

在多道程序设计系统中，内存中通常会同时保留多个进程。为了提高 CPU 的利用率、系统吞吐量并保证系统的响应时间，操作系统必须以某种策略从就绪队列中挑选一个进程/线程，将其分配给处理机（CPU）运行。

• 核心问题：“如何挑选进程、线程上处理机？”

• 研究核心：调度时机、调度机制、调度算法及其性能指标。

一、 处理机调度的层次

处理机调度在操作系统中是分层次进行的。根据调度的时效性和作用范围，调度通常分为以下三个层次：

     [外存后备队列] (作业)
           │
           │  高级调度 (长程调度 / 作业调度)
           ▼
     [内存就绪队列] (进程) ◄──────────┐
           │                         │
           │  低级调度               │  中级调度
           │  (进程调度)             │  (内存调度 / 挂起态对换)
           ▼                         │
         [CPU] ──────────────────────┘

1. 高级调度（High-Level Scheduling）

• 又称：长程调度、作业调度。

• 对象：作业（作业是用户提交给系统的一个逻辑任务，而进程则是其在内存中的执行实体）。

• 机制：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。

• 应用场景：主要用于多道批处理系统。分时系统和实时系统对响应速度要求极高，通常不设置高级调度，而是直接将用户请求载入内存。

• 📝 学生手记：我感觉作业调度就像是一个“APP 的安装/冷启动过程”——把外存上的程序包调入内存，并初始化对应的进程。

2. 中级调度（Intermediate-Level Scheduling）

• 又称：内存调度。

• 对象：挂起态进程。

• 机制：为了提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存等待（此时进程处于挂起状态，如就绪驻外存或阻塞驻外存）。当它们具备运行条件且内存稍有空闲时，由中级调度决定将其重新调入内存，修改其状态为就绪状态。

• 本质：中级调度实际上是存储管理中的对换（Swapping）功能，用于平衡内存与外存之间的动态资源。

3. 低级调度（Low-Level Scheduling）

• 又称：短程调度、进程调度。

• 对象：进程/线程。

• 机制：根据某种算法，决定就绪队列中的哪个进程获得处理机，并由分派程序将 CPU 分配给该进程。

• 应用场景：低级调度是操作系统中最基本、最核心的一种调度。无论是批处理、分时还是实时操作系统，都必须配置低级调度。

🔄 知识点起承转合：三层调度的协同工作

三层调度并非孤立存在。在系统运行过程中，高级调度负责“控制多道程序度”，即决定有多少任务能进入内存竞争 CPU；中级调度负责“优化内存使用率”，在内存吃紧时进行换入换出；低级调度负责“毫秒级的 CPU 分配”，是决定最终谁能占用物理处理机运行的最后一道关卡。

二、 进程调度的任务、机制与时机

低级调度（进程调度）是整个处理机调度的核心。下面我们将深入剖析进程调度的底层任务、内部机制、调度方式及触发时机。

1. 进程调度的三大任务

当调度程序决定让某一个进程上处理机时，必须完成以下三个核心任务：

1. 保存 CPU 现场信息：进程调度发生时，首先需要保存当前进程的现场（上下文，即 Context），包括程序计数器（$PC$）、程序状态字（$PSW$）、通用寄存器、堆栈指针等，并将其存入该进程的 PCB 中。

2. 按照某种算法选取进程：调度程序从就绪队列中按照预设算法选取一个进程，将其状态改为运行状态。

3. 将 CPU 分配给进程：由分派程序（Dispatcher）把被选中进程 PCB 中保存的现场信息恢复到 CPU 寄存器中，并把控制权转交给该进程，使其从上次的断点处恢复运行。

2. 进程调度的机制（Linux 视角）

进程切换的底层控制流程如下：

 进程 A (用户态) ────► 发生系统调用/中断 ────► 陷入内核态
                                              │
                                              ▼
 保存进程 A 上下文 ◄─── 执行分派程序 ◄─── 执行调度程序 (schedule())
        │
        ▼
 装入进程 B 上下文 ────► 进程 B (用户态运行)

• 主动切换：进程 A 通过系统调用（System Call，如 I/O 请求）主动让出 CPU。

• 被动切换：时钟中断触发，或者高优先级进程唤醒，引发中断处理。

• 闲逛进程（IDLE Process）： 如果系统中的就绪队列为空，没有可运行的进程，CPU 不能空转。操作系统会调度专门的 idle 进程 运行。它的优先级最低，其核心任务就是循环执行一条空操作指令或将 CPU 设为节能低功耗模式，直到被新的中断唤醒。

3. 进程调度的方式

进程在执行过程中，如何应对“后来者”的竞争？这决定了操作系统的调度方式：

① 非抢占调度方式（Non-preemptive Scheduling）

• 特点：一旦把处理机分配给某个进程，它就会一直运行下去，绝对不会因为时钟中断或其他原因被中途剥夺，直到该进程运行完毕、发生异常终止，或提出 I/O 请求主动进入阻塞状态。

• 适用场景：早期的批处理系统，不要求人机交互的系统。

② 抢占调度方式（Preemptive Scheduling）

• 特点：允许调度程序根据某种原则（如优先级、短进程优先、时间片等）暂停正在运行的进程，将其拥有的 CPU 重新分配给另一个进程。

• 适用场景：现代分时系统、实时系统。

• 📝 学生疑问解答：手写笔记中写到“抢占：某种原则抢占，这是不是一种优先级机制？”。 解答：是的。抢占的本质就是引入了一种“实时比较优先级”的动态机制。无论是“剩余时间短者抢占”（如抢占式 SJF）还是“高优先级抢占”（如静态优先级调度），都是在每一个调度决策点上对进程的当前特征进行加权计算（即优先级量化），凡是当前指标更优的进程就可以强行剥夺当前运行进程的 CPU 所有权。

4. 进程调度的时机与限制

🟢 可以进行进程调度的时机

• 主动放弃：

  1. 进程正常执行完毕，调用 exit 终止。

  2. 运行过程中发生异常（如越界、零除、缺页中断等）而终止。

  3. 进程请求阻塞（如发起 I/O、等待信号量 P 操作）。

• 被动放弃：

  1. 分配给当前进程的时间片用完。

  2. 在抢占式系统中，有更紧急、更高优先级的进程进入就绪队列。

🔴 不能进行进程调度的时机

1. 在处理中断的过程中：中断处理代码属于内核核心逻辑，需要极高的响应速度，在此期间如果进行进程上下文切换，会导致系统状态混乱。

2. 在进程处于内核态临界区，且该临界区涉及关中断/原子操作（Atomic Operation）时：此时为了保护内核临界资源，系统不允许被打断，通常会将中断屏蔽或锁定，因此无法发生调度。

三、 处理机调度性能指标

为了评估、比较不同调度算法的优劣，操作系统引入了以下几大评价指标：

1. CPU 利用率（CPU Utilization）

指 CPU 有效工作时间占总运行时间的比例：

$\text{CPU 利用率} = \frac{\text{CPU 有效工作时间}}{\text{CPU 有效工作时间} + \text{CPU 空闲等待时间}}$

2. 系统吞吐量（Throughput）

指单位时间内 CPU 完成的作业数量。

3. 周转时间（Turnaround Time）

指从作业提交（到达外存）到作业完成所经历的全部时间，包含在就绪队列中等待的时间。

$\text{周转时间} = \text{作业完成时间} - \text{作业提交时间}$

• 平均周转时间（设有 $n$ 个作业）：

  $\text{平均周转时间} = \frac{\sum_{i=1}^{n} \text{周转时间}_i}{n}$

• 带权周转时间（$W$）：衡量作业在系统中的等待代价：

  $W = \frac{\text{作业周转时间}}{\text{作业实际运行时间}}$

• 平均带权周转时间：

  $\text{平均带权周转时间} = \frac{\sum_{i=1}^{n} \text{带权周转时间}_i}{n}$

4. 等待时间（Waiting Time）

指进程建立后，在就绪队列中等待 CPU 的时间之和。

5. 响应时间（Response Time）

指从用户提交请求到系统首次产生响应所用的时间。在分时系统中，该指标至关重要。

四、 经典调度算法详解

本章是考试和实际系统设计的重难点，我们将逐一讲解这些算法，并辅以直观的计算与甘特图。

💡 基础数据背景

为了便于对比各个算法，我们设定一个通用例题背景（以下简称为 “标准测试集”）： 现有 $4$ 个作业在不同时刻提交运行：

作业号	提交时间	运行时间
1	$0$	$3$
2	$1$	$4$
3	$2$	$2$
4	$3$	$1$

1. 先来先服务（FCFS, First-Come First-Served）

• 核心思想：按照作业/进程到达的先后次序进行调度。

• 调度方式：只能是非抢占式。

• 算法特点：

  • 极度偏爱长作业，对短作业极度不友好。

  • 有利于 CPU 繁忙型（CPU-bound）作业，不利于 I/O 繁忙型（I/O-bound）作业。

FCFS 甘特图：

 0        3              7        9    10 (时间)
 ┌────────┬──────────────┬────────┬────┐
 │  作业1  │    作业2     │ 作业3  │作业4│
 └────────┴──────────────┴────────┴────┘

FCFS 详细计算表：

作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
1	$0$	$3$	$0$	$0$	$3$	$3 - 0 = 3$	$\frac{3}{3} = 1.00$
2	$1$	$4$	$3$	$2$	$7$	$7 - 1 = 6$	$\frac{6}{4} = 1.50$
3	$2$	$2$	$7$	$5$	$9$	$9 - 2 = 7$	$\frac{7}{2} = 3.50$
4	$3$	$1$	$9$	$6$	$10$	$10 - 3 = 7$	$\frac{7}{1} = 7.00$

• 平均周转时间：$T_{avg} = \frac{3 + 6 + 7 + 7}{4} = 5.75$

• 平均带权周转时间：$W_{avg} = \frac{1 + 1.5 + 3.5 + 7}{4} = 3.25$

2. 短作业优先（SJF, Shortest Job First）

• 核心思想：优先调度估计运行时间最短的作业/进程。

• 调度方式：

  • 非抢占式（默认）：一旦开始运行，无法被剥夺。

  • 抢占式（即最短剩余时间优先 SRTF）：当新进程到达时，若其剩余运行时间短于当前运行进程，则剥夺 CPU。

• 算法特点：

  • 在所有调度算法中，SJF 能够获得最优的平均等待时间和平均周转时间。

  • 对长作业极度不利，容易引发饥饿（Starvation）现象。

① 非抢占式 SJF

调度决策流：

1. 时刻 $t=0$：只有作业 1 到达，作业 1 运行。

2. 时刻 $t=3$：作业 1 完成。此时作业 2, 3, 4 均已到达，它们的运行时间分别为 $4, 2, 1$。

3. 因为作业 4 最短（运行时间 $1$），故调度作业 4 运行。

4. 时刻 $t=4$：作业 4 完成。剩余作业 2, 3，作业 3 最短（运行时间 $2$），调度作业 3。

5. 时刻 $t=6$：作业 3 完成。调度作业 2。

6. 时刻 $t=10$：作业 2 完成。

非抢占式 SJF 甘特图：

 0        3    4        6              10 (时间)
 ┌────────┬────┬────────┬──────────────┐
 │  作业1  │作业4│  作业3  │    作业2     │
 └────────┴────┴────────┴──────────────┘

非抢占式 SJF 计算表：

作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
1	$0$	$3$	$0$	$0$	$3$	$3$	$1.00$
2	$1$	$4$	$6$	$5$	$10$	$9$	$\frac{9}{4} = 2.25$
3	$2$	$2$	$4$	$2$	$6$	$4$	$\frac{4}{2} = 2.00$
4	$3$	$1$	$3$	$0$	$4$	$1$	$\frac{1}{1} = 1.00$

• 平均周转时间：$T_{avg} = \frac{3 + 9 + 4 + 1}{4} = 4.25$

• 平均带权周转时间：$W_{avg} = \frac{1 + 2.25 + 2 + 1}{4} = 1.56$

3. 高响应比优先（HRRN, Highest Response Ratio Next）

• 核心思想：每次调度时，计算当前就绪队列中所有作业的响应比，选择响应比最高的作业投入运行。

• 📝 手写疑问解答：您的笔记本提到“响应比到底怎么计算，我不强求”。 解答：不要不强求！这个公式其实非常优美，是必须要掌握的考点：

  $\text{响应比} (R_p) = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}} = 1 + \frac{\text{等待时间}}{\text{要求服务时间}}$

• 算法特点：

  • 极佳的折中性能：

    • 当等待时间相同时，要求服务时间越短，响应比越高（等同于 SJF，有利于短作业）。

    • 当要求服务时间相同时，等待时间越长，响应比越高（等同于 FCFS）。

    • 长作业等待足够长的时间后，其等待时间增大，响应比也会提高，最终能够获得 CPU，有效克服了 SJF 的饥饿问题。

HRRN 调度决策流：

1. 时刻 $t=0$：仅作业 1 到达，直接调度运行。作业 1 于 $t=3$ 完成。

2. 时刻 $t=3$：此时作业 2, 3, 4 均在队列中，开始计算响应比：

   • 作业 2：等待时间 $= 3 - 1 = 2$，要求服务时间 $= 4$：

     $R_p(\text{作业2}) = \frac{2 + 4}{4} = 1.5$

   • 作业 3：等待时间 $= 3 - 2 = 1$，要求服务时间 $= 2$：

     $R_p(\text{作业3}) = \frac{1 + 2}{2} = 1.5$

   • 作业 4：等待时间 $= 3 - 3 = 0$，要求服务时间 $= 1$：

     $R_p(\text{作业4}) = \frac{0 + 1}{1} = 1.0$

   • 决策点：作业 2 与作业 3 的响应比相同（均为 $1.5$）。

     • 通常约定：若响应比相同，优先调度提交时间早/运行时间短的作业。在此我们选择运行时间更短的作业 3。

3. 时刻 $t=5$：作业 3 运行结束（耗时 $2$）。再次计算剩余作业响应比：

   • 作业 2：等待时间 $= 5 - 1 = 4$：

     $R_p(\text{作业2}) = \frac{4 + 4}{4} = 2.0$

   • 作业 4：等待时间 $= 5 - 3 = 2$：

     $R_p(\text{作业4}) = \frac{2 + 1}{1} = 3.0$

   • 决策点：由于 $3.0 > 2.0$，调度作业 4。

4. 时刻 $t=6$：作业 4 结束，调度唯一的作业 2 运行至 $t=10$。

HRRN 甘特图：

 0        3         5    6              10 (时间)
 ┌────────┬─────────┬────┬──────────────┐
 │  作业1  │  作业3   │作业4│    作业2     │
 └────────┴─────────┴────┴──────────────┘

4. 优先级调度算法（PSA, Priority-Scheduling Algorithm）

• 核心思想：给每个作业/进程定义一个优先级，每次调度时选取优先级最高的进程。

• 分类：

  • 非抢占式优先级算法。

  • 抢占式优先级算法。

• 新增简单例题： 假设有 3 个进程在 $t=0$ 时刻同时到达，其执行时间及优先级如下（数字越小，优先级越高）：

进程	运行时间	优先级
A	$10$	$3$
B	$1$	$1$
C	$2$	$2$

• 调度结果：

  1. $t=0$：调度优先级最高的 B 运行，$t=1$ 时完成。

  2. $t=1$：调度优先级第二高的 C 运行，$t=3$ 时完成。

  3. $t=3$：调度 A 运行，$t=13$ 时完成。

  • 甘特图：

     0  1     3             13 (时间)
     ┌──┬─────┬─────────────┐
     │ B│  C  │      A      │
     └──┴─────┴─────────────┘

5. 时间片轮转调度（RR, Round-Robin）

• 核心思想：主要用于分时系统。所有就绪进程按 FCFS 排成一个就绪队列。系统每隔一个固定的时间（称为时间片，Time Slice）产生一次时钟中断，调度程序剥夺当前运行进程的 CPU，送往队尾，再将 CPU 分配给新的队首进程。

• 关键因素：时间片的大小。若时间片取得太大，RR 调度就会退化为 FCFS 调度；若取得太小，频繁的上下文切换会产生极大的系统开销。

6. 多级队列调度（Multilevel Queue Scheduling）

• 核心思想：在就绪队列中，根据进程性质的不同设置多个就绪队列。不同的就绪队列拥有不同的优先级，队列内部可以实行各自不同的调度算法。

• 例如：

  • 系统进程队列：优先级最高，采用优先级调度算法。

  • 交互式进程队列：中等优先级，采用时间片轮转（RR）算法。

  • 批处理进程队列：最低优先级，采用先来先服务（FCFS）算法。

7. 多级反馈队列调度（Multilevel Feedback Queue Scheduling）

多级反馈队列调度算法集成了前述所有算法的优点（时间片、优先级、短进程优先、公平性），是现代操作系统中最常用且公认最优秀的调度算法。

🛠️ 核心运行思想：

1. 设置多级队列，优先级递减，时间片递增： 设置 $N$ 个就绪队列，其中 1 级队列优先级最高，后续队列优先级依次降低。优先级越高的队列，分配的时间片越小（例如：1级为 $1\text{ms}$，2级为 $2\text{ms}$，3级为 $4\text{ms}$）。

2. 新进程进入 1 级队列： 新进程到达时，首先放入 1 级队列的末尾，按照 FCFS 规则等待调度。

3. 时间片未用完与用完的差异处理：

   • 如果该进程在 1 级队列分配的时间片内运行完毕，则直接撤离系统。

   • 如果时间片用完时进程仍未完成，调度程序将其放入 2 级队列的末尾等待调度。依次类推，直到降至最后一级队列。在最后一级队列中，进程通常采用 RR（时间片轮转） 方式运行。

4. 严格的抢占机制： 仅当第 $1 \sim (i-1)$ 级队列均为空时，系统才会调度第 $i$ 级队列中的进程。如果系统正在运行第 $i$ 级队列中的进程时，突然有新进程进入了更高优先级的队列（第 $1 \sim i-1$ 级），新进程会强行抢占当前运行进程的 CPU，被抢占的进程会回到它原来所在队列的队尾。

五、 综合大考题精析：“小试牛刀”

本题来自于视频及原件资料中的课后压轴大题，旨在通过极其细腻的动态时间线计算，帮助我们彻底掌握 非抢占式短进程优先 与 抢占式短进程优先。

📋 作业/进程基本信息：

进程名	到达时间	运行时间
P1	$0.0$	$9$
P2	$0.4$	$4$
P3	$1.0$	$1$
P4	$5.5$	$4$
P5	$7.0$	$2$

第一问：非抢占式短进程优先调度（SJF）

🧭 动态执行推理过程：

1. $t = 0.0$：只有 $P_1$ 到达。因为是非抢占式，$P_1$ 必须直接运行至结束。

   • 运行区间：$[0.0, 9.0]$。

2. $t = 9.0$：$P_1$ 运行结束。此时 $P_2, P_3, P_4, P_5$ 均已到达。

   • 它们的估计运行时间分别为：$P_2(4)$、$P_3(1)$、$P_4(4)$、$P_5(2)$。

   • 决策点：$P_3$ 最短（$1$），故调度 $P_3$。

   • 运行区间：$[9.0, 10.0]$。

3. $t = 10.0$：$P_3$ 结束。剩余就绪进程：$P_2(4)$、$P_4(4)$、$P_5(2)$。

   • 决策点：$P_5$ 最短（$2$），调度 $P_5$。

   • 运行区间：$[10.0, 12.0]$。

4. $t = 12.0$：$P_5$ 结束。剩余进程：$P_2(4)$、$P_4(4)$。

   • 决策点：运行时间相同，按先来先服务（FCFS），$P_2$ 提交时间（$0.4$）早于 $P_4$（$5.5$），故调度 $P_2$。

   • 运行区间：$[12.0, 16.0]$。

5. $t = 16.0$：调度 $P_4$。

   • 运行区间：$[16.0, 20.0]$。

非抢占式 SJF 性能分析表：

进程名	到达时间	运行时间	完成时间	周转时间 ($完成 - 到达$)	带权周转时间 ($\frac{周转}{运行}$)
P1	$0.0$	$9$	$9.0$	$9.0 - 0 = 9.0$	$\frac{9.0}{9} = 1.00$
P2	$0.4$	$4$	$16.0$	$16.0 - 0.4 = 15.6$	$\frac{15.6}{4} = 3.90$
P3	$1.0$	$1$	$10.0$	$10.0 - 1.0 = 9.0$	$\frac{9.0}{1} = 9.00$
P4	$5.5$	$4$	$20.0$	$20.0 - 5.5 = 14.5$	$\frac{14.5}{4} = 3.63$
P5	$7.0$	$2$	$12.0$	$12.0 - 7.0 = 5.0$	$\frac{5.0}{2} = 2.50$

• 平均周转时间：

  $T_{avg} = \frac{9.0 + 15.6 + 9.0 + 14.5 + 5.0}{5} = \frac{53.1}{5} = 10.62$

• 平均带权周转时间：

  $W_{avg} = \frac{1.00 + 3.90 + 9.00 + 3.63 + 2.50}{5} = \frac{20.03}{5} = 4.01$

第二问：抢占式短进程优先调度（SRTF）

这是经典的高频考点和难点。系统在每一个新进程到达时都会重新计算并对比就绪队列中所有进程的剩余运行时间，以此来决定是否剥夺当前进程的 CPU。

🧭 动态执行推理过程：

1. $t = 0.0$：只有 $P_1$ 到达。$P_1$ 开始运行。

2. $t = 0.4$：新进程 $P_2$ 到达。

   • 当前各进程剩余时间：$P_1$（剩余 $9.0 - 0.4 = 8.6$）、$P_2$（剩余 $4.0$）。

   • 决策点：由于 $4.0 < 8.6$，$P_2$ 抢占 CPU，开始运行。

3. $t = 1.0$：新进程 $P_3$ 到达。

   • $P_2$ 已运行了 $0.6$ 秒（自 $t=0.4$ 到 $1.0$）。

   • 当前各进程剩余时间：$P_1$（剩余 $8.6$）、$P_2$（剩余 $4.0 - 0.6 = 3.4$）、$P_3$（剩余 $1.0$）。

   • 决策点：由于 $1.0 < 3.4 < 8.6$，$P_3$ 抢占 CPU，开始运行。

4. $t = 2.0$：$P_3$ 耗时 $1.0$ 运行完毕，退出系统。

   • 当前时刻无新进程到达，只需对比剩余进程：$P_1$（剩余 $8.6$）、$P_2$（剩余 $3.4$）。

   • 决策点：选择最短的 $P_2$ 恢复运行。

5. $t = 5.4$：$P_2$ 刚好耗时 $3.4$ 运行完毕，退出系统。

   • 当前时刻无新进程到达，只能调度唯一的就绪进程 $P_1$。

6. $t = 5.5$：新进程 $P_4$ 到达。

   • $P_1$ 仅运行了 $0.1$ 秒（自 $5.4$ 到 $5.5$）。

   • 当前各进程剩余时间：$P_1$（剩余 $8.6 - 0.1 = 8.5$）、$P_4$（剩余 $4.0$）。

   • 决策点：由于 $4.0 < 8.5$，$P_4$ 抢占 CPU，开始运行。

7. $t = 7.0$：新进程 $P_5$ 到达。

   • $P_4$ 已运行了 $1.5$ 秒（自 $5.5$ 到 $7.0$）。

   • 当前各进程剩余时间：$P_1$（剩余 $8.5$）、$P_4$（剩余 $4.0 - 1.5 = 2.5$）、$P_5$（剩余 $2.0$）。

   • 决策点：由于 $2.0 < 2.5 < 8.5$，$P_5$ 抢占 CPU，开始运行。

8. $t = 9.0$：$P_5$ 耗时 $2.0$ 运行完毕，退出系统。

   • 剩余进程：$P_1$（剩余 $8.5$）、$P_4$（剩余 $2.5$）。

   • 决策点：选择剩余时间最短的 $P_4$ 恢复运行。

9. $t = 11.5$：$P_4$ 耗时 $2.5$ 运行完毕，退出系统。

   • 只剩下 $P_1$ 运行。

10. $t = 20.0$：$P_1$ 耗时 $8.5$ 运行完毕，退出系统。

抢占式 SRTF 甘特图：

 0    0.4   1.0   2.0         5.4 5.5       7.0   9.0      11.5                20.0 (时间)
 ┌────┬─────┬─────┬───────────┬─┬───────────┬─────┬────────┬───────────────────┐
 │ P1 │ P2  │ P3  │    P2     │P1│    P4     │ P5  │   P4   │        P1         │
 └────┴─────┴─────┴───────────┴─┴───────────┴─────┴────────┴───────────────────┘

抢占式 SRTF 性能分析表：

进程名	到达时间	运行时间	完成时间	周转时间 ($完成 - 到达$)	带权周转时间 ($\frac{周转}{运行}$)
P1	$0.0$	$9$	$20.0$	$20.0 - 0.0 = 20.0$	$\frac{20.0}{9} = 2.22$
P2	$0.4$	$4$	$5.4$	$5.4 - 0.4 = 5.0$	$\frac{5.0}{4} = 1.25$
P3	$1.0$	$1$	$2.0$	$2.0 - 1.0 = 1.0$	$\frac{1.0}{1} = 1.00$
P4	$5.5$	$4$	$11.5$	$11.5 - 5.5 = 6.0$	$\frac{6.0}{4} = 1.50$
P5	$7.0$	$2$	$9.0$	$9.0 - 7.0 = 2.0$	$\frac{2.0}{2} = 1.00$

• 平均周转时间：

  $T_{avg} = \frac{20.0 + 5.0 + 1.0 + 6.0 + 2.0}{5} = \frac{34.0}{5} = 6.8$

• 平均带权周转时间：

  $W_{avg} = \frac{2.22 + 1.25 + 1.00 + 1.50 + 1.00}{5} = \frac{6.97}{5} = 1.394$

六、 总结：核心调度算法横向对比

算法名称	调度方式	偏好进程/作业	优点	缺点	是否会导致饥饿
FCFS	非抢占式	长进程	简单、公平	对短进程等待时间长	否
SJF	抢占/非抢占	短进程	平均等待/周转时间最短	偏爱短作业，导致长进程饥饿	是
HRRN	非抢占式	响应比最高进程	折中性能极佳，考虑等待时间	每次调度需要重新计算响应比，开销稍大	否
PSA	抢占/非抢占	高优先级进程	能区分进程紧急程度，实时性好	静态优先级可能导致低优先级进程饥饿	是
RR	抢占式	每一个就绪进程	分时交互性好，公平性高	时间片选择困难，频繁切换有开销	否
多级反馈队列	抢占式	短进程（快速执行完）	兼顾短作业、长作业及交互需求	设计复杂，难以调优	是（极极端情况）