当前位置：首页 > news >正文

操作系统考试大题-处理机调度算法-详解-1

news 2025/7/3 6:45:48

先来先服务（FCFS）调度算法步骤详解

先来先服务（FCFS）是一种非抢占式调度算法，按照作业提交的顺序依次执行。以下是详细的调度过程和性能指标计算。

初始作业信息：

作业号	提交时间	运行时间
1	8.0	2.0
2	8.4	1.0
3	8.8	0.5
4	9.0	0.2

调度过程：

时间 8.0：作业1到达，开始执行作业1。
- 开始时间：8.0
- 完成时间：8.0 + 2.0 = 10.0
- 当前时间：10.0
时间 10.0：检查就绪队列：
- 已到达的作业：作业2（提交时间8.4）、作业3（提交时间8.8）、作业4（提交时间9.0）。
- 按提交顺序，执行作业2。
- 开始时间：10.0
- 完成时间：10.0 + 1.0 = 11.0
- 当前时间：11.0
时间 11.0：检查就绪队列：
- 已到达的作业：作业3、作业4。
- 按提交顺序，执行作业3。
- 开始时间：11.0
- 完成时间：11.0 + 0.5 = 11.5
- 当前时间：11.5
时间 11.5：检查就绪队列：
- 已到达的作业：作业4。
- 执行作业4。
- 开始时间：11.5
- 完成时间：11.5 + 0.2 = 11.7
- 当前时间：11.7

调度顺序：

作业1 → 作业2 → 作业3 → 作业4

8.0 --作业1-- 10.0 --作业2-- 11.0 --作业3-- 11.5 --作业4-- 11.7

计算各项时间：

作业号	提交时间	运行时间	开始时间	等待时间 (开始时间 - 提交时间)	完成时间	周转时间 (完成时间 - 提交时间)	带权周转时间 (周转时间 / 运行时间)
1	8.0	2.0	8.0	8.0 - 8.0 = 0	10.0	10.0 - 8.0 = 2.0	2.0 / 2.0 = 1.0
2	8.4	1.0	10.0	10.0 - 8.4 = 1.6	11.0	11.0 - 8.4 = 2.6	2.6 / 1.0 = 2.6
3	8.8	0.5	11.0	11.0 - 8.8 = 2.2	11.5	11.5 - 8.8 = 2.7	2.7 / 0.5 = 5.4
4	9.0	0.2	11.5	11.5 - 9.0 = 2.5	11.7	11.7 - 9.0 = 2.7	2.7 / 0.2 = 13.5

性能指标：

平均等待时间 = (0 + 1.6 + 2.2 + 2.5) / 4 = 6.3 / 4 = 1.575
平均周转时间 = (2.0 + 2.6 + 2.7 + 2.7) / 4 = 10.0 / 4 = 2.5
平均带权周转时间 = (1.0 + 2.6 + 5.4 + 13.5) / 4 = 22.5 / 4 = 5.625

最终表格：

作业号	提交时间	运行时间	开始时间	等待时间	完成时间	周转时间	带权周转时间
1	8.0	2.0	8.0	0.0	10.0	2.0	1.0
2	8.4	1.0	10.0	1.6	11.0	2.6	2.6
3	8.8	0.5	11.0	2.2	11.5	2.7	5.4
4	9.0	0.2	11.5	2.5	11.7	2.7	13.5

关键点说明：

非抢占式：作业一旦开始执行，必须运行完成才会处理下一个作业。
等待时间：作业从提交到开始执行的时间。
性能问题：FCFS算法对短作业不利，可能导致短作业等待时间过长（如作业4的带权周转时间高达13.5）。

最短剩余时间（SRT）调度步骤详解

在最短剩余时间（SRT）调度中，总是选择剩余服务时间最短的进程执行。这是一种抢占式调度算法，当新进程到达时，如果其服务时间比当前运行进程的剩余时间更短，则会抢占CPU。

初始进程信息：

进程	到达时间	服务时间
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

调度过程：

时间 0：只有进程 A 到达，开始执行 A。
- A 运行时间：0 → 2（此时 B 到达）
- A 剩余服务时间：3 - 2 = 1。
- 当前时间：2
时间 2：检查就绪队列：
- 已到达的进程：A（剩余 1）、B（服务时间 6）。
- A 的剩余时间更短，继续执行 A。
- A 运行时间：2 → 3（完成）
- 当前时间：3
时间 3：检查就绪队列：
- 已到达的进程：B（服务时间 6）。
- 执行 B。
- B 运行时间：3 → 4（此时 C 到达）
- B 剩余服务时间：6 - 1 = 5。
- 当前时间：4
时间 4：检查就绪队列：
- 已到达的进程：B（剩余 5）、C（服务时间 4）。
- C 的剩余时间更短，抢占 B 的执行。
- 执行 C。
- C 运行时间：4 → 8（此时 E 到达）
- C 剩余服务时间：4 - 4 = 0（完成）。
- 当前时间：8
时间 8：检查就绪队列：
- 已到达的进程：B（剩余 5）、D（到达时间 6）、E（服务时间 2）。
- 就绪进程：B、D、E。
- E 的剩余时间最短（2），执行 E。
- E 运行时间：8 → 10（完成）
- 当前时间：10
时间 10：检查就绪队列：
- 已到达的进程：B（剩余 5）、D（服务时间 5）。
- B 和 D 的剩余时间相同（5），选择先到达的 B。
- 执行 B。
- B 运行时间：10 → 15（完成）
- 当前时间：15
时间 15：检查就绪队列：
- 已到达的进程：D（服务时间 5）。
- 执行 D。
- D 运行时间：15 → 20（完成）
- 当前时间：20

调度顺序：

A (0-2) → A (2-3) → B (3-4) → C (4-8) → E (8-10) → B (10-15) → D (15-20)

0 --A-- 2 --A-- 3 --B-- 4 --C-- 8 --E-- 10 --B-- 15 --D-- 20

计算各项时间：

进程	到达时间	服务时间	完成时间	周转时间 (完成时间 - 到达时间)	带权周转时间 (周转时间 / 服务时间)
A	0	3	3	3 - 0 = 3	3 / 3 = 1
B	2	6	15	15 - 2 = 13	13 / 6 ≈ 2.17
C	4	4	8	8 - 4 = 4	4 / 4 = 1
D	6	5	20	20 - 6 = 14	14 / 5 = 2.8
E	8	2	10	10 - 8 = 2	2 / 2 = 1

平均时间：

平均周转时间 = (3 + 13 + 4 + 14 + 2) / 5 = 36 / 5 = 7.2
平均带权周转时间 = (1 + 2.17 + 1 + 2.8 + 1) / 5 ≈ 7.97 / 5 ≈ 1.59

最终表格：

进程	到达时间	服务时间	开始时间	完成时间	周转时间	带权周转时间
A	0	3	0	3	3	1
B	2	6	3	15	13	2.17
C	4	4	4	8	4	1
E	8	2	8	10	2	1
D	6	5	15	20	14	2.8

补充说明：

抢占时机：每次有新进程到达时，会比较新进程的服务时间与当前运行进程的剩余时间，选择更短的执行。
周转时间：从进程到达系统到完成的时间。
带权周转时间：周转时间与服务时间的比值，反映进程的相对等待时间。

最短作业优先（SJF）调度算法步骤详解

最短作业优先（SJF）是一种非抢占式调度算法，总是优先调度运行时间最短的作业。以下是详细的调度过程和性能指标计算。

初始作业信息：

作业号	进入时刻	运行时间
1	8.00	2.00
2	8.50	0.50
3	9.00	0.10
4	9.50	0.20

调度过程：

时间 8.00：作业1到达，开始执行作业1。
- 开始时刻：8.00
- 完成时刻：8.00 + 2.00 = 10.00
- 当前时间：10.00
时间 10.00：检查就绪队列：
- 已到达的作业：作业2（进入时刻8.50）、作业3（进入时刻9.00）、作业4（进入时刻9.50）。
- 按运行时间排序：作业3（0.10）、作业4（0.20）、作业2（0.50）。
- 执行运行时间最短的作业3。
- 开始时刻：10.00
- 完成时刻：10.00 + 0.10 = 10.10
- 当前时间：10.10
时间 10.10：检查就绪队列：
- 已到达的作业：作业2、作业4。
- 按运行时间排序：作业4（0.20）、作业2（0.50）。
- 执行运行时间最短的作业4。
- 开始时刻：10.10
- 完成时刻：10.10 + 0.20 = 10.30
- 当前时间：10.30
时间 10.30：检查就绪队列：
- 已到达的作业：作业2。
- 执行作业2。
- 开始时刻：10.30
- 完成时刻：10.30 + 0.50 = 10.80
- 当前时间：10.80

调度顺序：

作业1 → 作业3 → 作业4 → 作业2

8.00 --作业1-- 10.00 --作业3-- 10.10 --作业4-- 10.30 --作业2-- 10.80

计算各项时间：

作业号	进入时刻	运行时间	开始时刻	完成时刻	周转时间 (完成时刻 - 进入时刻)	带权周转时间 (周转时间 / 运行时间)
1	8.00	2.00	8.00	10.00	10.00 - 8.00 = 2.00	2.00 / 2.00 = 1.00
2	8.50	0.50	10.30	10.80	10.80 - 8.50 = 2.30	2.30 / 0.50 = 4.60
3	9.00	0.10	10.00	10.10	10.10 - 9.00 = 1.10	1.10 / 0.10 = 11.00
4	9.50	0.20	10.10	10.30	10.30 - 9.50 = 0.80	0.80 / 0.20 = 4.00