操作系统考试大题-处理机调度算法-详解-2
抢占式优先级调度步骤详解
在抢占式优先级调度中，当更高优先级的进程到达时，当前运行的进程会被中断，调度器会选择更高优先级的进程执行。调度顺序基于进程的优先级，优先级高的先执行（假设数字越小优先级越高）。
初始进程信息：
| 进程 | 到达时间 | 服务时间 | 优先级 |
|---|---|---|---|
| A | 0 | 3 | 3 |
| B | 2 | 6 | 2 |
| C | 4 | 4 | 4 |
| D | 6 | 5 | 1 |
| E | 8 | 2 | 5 |
调度过程：
-
时间 0：只有进程 A 到达，开始执行 A。
-
A 运行时间：0 → 2（此时 B 到达）
-
当前时间：2
-
-
时间 2：检查就绪队列：
-
已到达的进程：B（优先级 2）、A（优先级 3）。
-
B 的优先级高于 A，抢占 A 的执行。
-
A 剩余服务时间：3 - 2 = 1。
-
执行 B。
-
B 运行时间：2 → 6（此时 D 到达）
-
当前时间：6
-
-
时间 6：检查就绪队列：
-
已到达的进程：A（剩余 1）、B（剩余 6 - 4 = 2）、C（到达时间 4）、D（优先级 1）、E（未到达）。
-
就绪进程：A、B、C、D。
-
优先级顺序：D（1）、B（2）、A（3）、C（4）。
-
D 的优先级最高，抢占 B 的执行。
-
B 剩余服务时间：6 - (6 - 2) = 2。
-
执行 D。
-
D 运行时间：6 → 11（此时 E 到达）
-
当前时间：11
-
-
时间 11：检查就绪队列：
-
已到达的进程：A（剩余 1）、B（剩余 2）、C（到达时间 4）、E（优先级 5）。
-
就绪进程：A、B、C、E。
-
优先级顺序：B（2）、A（3）、C（4）、E（5）。
-
B 的优先级最高，继续执行 B。
-
B 运行时间：11 → 13
-
当前时间：13
-
-
时间 13：检查就绪队列：
-
就绪进程：A（剩余 1）、C、E。
-
优先级顺序：A（3）、C（4）、E（5）。
-
执行 A。
-
A 运行时间：13 → 14
-
当前时间：14
-
-
时间 14：检查就绪队列：
-
就绪进程：C、E。
-
优先级顺序：C（4）、E（5）。
-
执行 C。
-
C 运行时间：14 → 18
-
当前时间：18
-
-
时间 18：检查就绪队列：
-
就绪进程：E。
-
执行 E。
-
E 运行时间：18 → 20
-
当前时间：20
-
调度顺序：
A (0-2) → B (2-6) → D (6-11) → B (11-13) → A (13-14) → C (14-18) → E (18-20)
0 --A-- 2 --B-- 6 --D-- 11 --B-- 13 --A-- 14 --C-- 18 --E-- 20计算各项时间：
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 (完成时间 - 到达时间) | 带权周转时间 (周转时间 / 服务时间) |
|---|---|---|---|---|---|
| A | 0 | 3 | 14 | 14 - 0 = 14 | 14 / 3 ≈ 4.67 |
| B | 2 | 6 | 13 | 13 - 2 = 11 | 11 / 6 ≈ 1.83 |
| C | 4 | 4 | 18 | 18 - 4 = 14 | 14 / 4 = 3.5 |
| D | 6 | 5 | 11 | 11 - 6 = 5 | 5 / 5 = 1 |
| E | 8 | 2 | 20 | 20 - 8 = 12 | 12 / 2 = 6 |
平均时间：
-
平均周转时间 = (14 + 11 + 14 + 5 + 12) / 5 = 56 / 5 = 11.2
-
平均带权周转时间 = (4.67 + 1.83 + 3.5 + 1 + 6) / 5 ≈ 17 / 5 ≈ 3.4
最终表格：
| 进程 | 到达时间 | 服务时间 | 优先级 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|---|
| A | 0 | 3 | 3 | 0 | 14 | 14 | 4.67 |
| B | 2 | 6 | 2 | 2 | 13 | 11 | 1.83 |
| D | 6 | 5 | 1 | 6 | 11 | 5 | 1 |
| C | 4 | 4 | 4 | 14 | 18 | 14 | 3.5 |
| E | 8 | 2 | 5 | 18 | 20 | 12 | 6 |
非抢占式优先级调度步骤详解
在非抢占式优先级调度中，进程一旦开始执行就会一直运行到完成，不会被更高优先级的进程打断。调度顺序基于进程的优先级，优先级高的先执行（假设数字越小优先级越高）。
初始进程信息：
| 进程 | 到达时间 | 服务时间 | 优先级 |
|---|---|---|---|
| A | 0 | 3 | 3 |
| B | 2 | 6 | 2 |
| C | 4 | 4 | 4 |
| D | 6 | 5 | 1 |
| E | 8 | 2 | 5 |
调度过程：
-
时间 0：只有进程 A 到达，开始执行 A。
-
A 运行时间：0 → 3
-
当前时间：3
-
-
时间 3：检查就绪队列：
-
已到达的进程：B（到达时间 2）、C（到达时间 4，未到达）、D（到达时间 6，未到达）、E（到达时间 8，未到达）。
-
就绪进程：B。
-
执行 B（优先级 2）。
-
B 运行时间：3 → 9
-
当前时间：9
-
-
时间 9：检查就绪队列：
-
已到达的进程：C（到达时间 4）、D（到达时间 6）、E（到达时间 8）。
-
就绪进程：C、D、E。
-
优先级顺序：D（1）、C（4）、E（5）。
-
执行 D（优先级最高）。
-
D 运行时间：9 → 14
-
当前时间：14
-
-
时间 14：检查就绪队列：
-
就绪进程：C、E。
-
优先级顺序：C（4）、E（5）。
-
执行 C（优先级更高）。
-
C 运行时间：14 → 18
-
当前时间：18
-
-
时间 18：检查就绪队列：
-
就绪进程：E。
-
执行 E。
-
E 运行时间：18 → 20
-
当前时间：20
-
调度顺序：
A → B → D → C → E
0 --A-- 3 --B-- 9 --D-- 14 --C-- 18 --E-- 20计算各项时间：
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 (完成时间 - 到达时间) | 带权周转时间 (周转时间 / 服务时间) |
|---|---|---|---|---|---|
| A | 0 | 3 | 3 | 3 - 0 = 3 | 3 / 3 = 1 |
| B | 2 | 6 | 9 | 9 - 2 = 7 | 7 / 6 ≈ 1.17 |
| C | 4 | 4 | 18 | 18 - 4 = 14 | 14 / 4 = 3.5 |
| D | 6 | 5 | 14 | 14 - 6 = 8 | 8 / 5 = 1.6 |
| E | 8 | 2 | 20 | 20 - 8 = 12 | 12 / 2 = 6 |
平均时间：
-
平均周转时间 = (3 + 7 + 14 + 8 + 12) / 5 = 44 / 5 = 8.8
-
平均带权周转时间 = (1 + 1.17 + 3.5 + 1.6 + 6) / 5 ≈ 13.27 / 5 ≈ 2.65
最终表格：
| 进程 | 到达时间 | 服务时间 | 优先级 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|---|
| A | 0 | 3 | 3 | 0 | 3 | 3 | 1 |
| B | 2 | 6 | 2 | 3 | 9 | 7 | 1.17 |
| D | 6 | 5 | 1 | 9 | 14 | 8 | 1.6 |
| C | 4 | 4 | 4 | 14 | 18 | 14 | 3.5 |
| E | 8 | 2 | 5 | 18 | 20 | 12 | 6 |
最高响应比优先（HRRN）调度步骤详解
最高响应比优先（HRRN）是一种非抢占式调度算法，选择响应比最高的进程执行。响应比的计算公式为：
$$
[ R = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} ]
$$
初始进程信息：
| 进程 | 到达时间 | 服务时间 |
|---|---|---|
| A | 0 | 3 |
| B | 2 | 6 |
| C | 4 | 4 |
| D | 6 | 5 |
| E | 8 | 2 |
调度过程：
-
时间 0：只有进程 A 到达，开始执行 A。
-
A 运行时间：0 → 3（完成）
-
当前时间：3
-
-
时间 3：检查就绪队列：
-
已到达的进程：B（到达时间 2）、C（到达时间 4，未到达）、D（到达时间 6，未到达）、E（到达时间 8，未到达）。
-
就绪进程：B。
-
执行 B。
-
B 运行时间：3 → 9（完成）
-
当前时间：9
-
-
时间 9：检查就绪队列：
-
已到达的进程：C（到达时间 4）、D（到达时间 6）、E（到达时间 8）。
-
计算响应比：
-
-
C 的响应比最高，执行 C。
-
C 运行时间：9 → 13（完成）
-
当前时间：13
-
-
时间 13：检查就绪队列：
-
已到达的进程：D（到达时间 6）、E（到达时间 8）。
-
计算响应比：
-
-
E 的响应比最高，执行 E。
-
E 运行时间：13 → 15（完成）
-
当前时间：15
-
-
时间 15：检查就绪队列：
-
已到达的进程：D（到达时间 6）。
-
执行 D。
-
D 运行时间：15 → 20（完成）
-
当前时间：20
-
调度顺序：
A → B → C → E → D
0 --A-- 3 --B-- 9 --C-- 13 --E-- 15 --D-- 20计算各项时间：
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 (完成时间 - 到达时间) | 带权周转时间 (周转时间 / 服务时间) |
|---|---|---|---|---|---|
| A | 0 | 3 | 3 | 3 - 0 = 3 | 3 / 3 = 1 |
| B | 2 | 6 | 9 | 9 - 2 = 7 | 7 / 6 ≈ 1.17 |
| C | 4 | 4 | 13 | 13 - 4 = 9 | 9 / 4 = 2.25 |
| E | 8 | 2 | 15 | 15 - 8 = 7 | 7 / 2 = 3.5 |
| D | 6 | 5 | 20 | 20 - 6 = 14 | 14 / 5 = 2.8 |
平均时间：
-
平均周转时间 = (3 + 7 + 9 + 7 + 14) / 5 = 40 / 5 = 8
-
平均带权周转时间 = (1 + 1.17 + 2.25 + 3.5 + 2.8) / 5 ≈ 10.72 / 5 ≈ 2.14
最终表格：
| 进程 | 到达时间 | 服务时间 | 开始时间 | 完成时间 | 周转时间 | 带权周转时间 | 响应比（选择时） |
|---|---|---|---|---|---|---|---|
| A | 0 | 3 | 0 | 3 | 3 | 1 | - |
| B | 2 | 6 | 3 | 9 | 7 | 1.17 | - |
| C | 4 | 4 | 9 | 13 | 9 | 2.25 | 2.25 |
| E | 8 | 2 | 13 | 15 | 7 | 3.5 | 3.5 |
| D | 6 | 5 | 15 | 20 | 14 | 2.8 | 2.4 |
关键点说明：
-
响应比计算：
-
在时间 9：C、D、E 的响应比分别为 2.25、1.6、1.5，选择最高的 C。
-
在时间 13：D、E 的响应比分别为 2.4、3.5，选择最高的 E。
-
-
非抢占式：进程一旦开始执行，会一直运行到完成。
-
性能指标：
-
平均周转时间：8（时间单位）
-
平均带权周转时间：2.14
-