进程调度算法作业

P1

如下作业序列：作业 1（提交时间 8:00,运行时间 1:00）,作业 2（提交时间 8:30,运行时间 3:00）,作业 3（提交时间 9:00,运行时间 0:10），作业 4（提交时间 9:30，运行时间 0:50）。试用 FCFS 和 STN 算法调度该作业序列。并分析哪一种调度算法性能更好。

FCFS 调度

• 8:00 作业 1 到达，开始执行
  • 完成时间 9:00
• 8:30 作业 2 到达，等待
• 9:00 作业 1 完成，作业 3 到达，等待
  • 作业 2 开始执行
  • 完成时间 12:00
• 9:30 作业 4 到达，等待
• 12:00 作业 2 完成
  • 作业 3 开始执行
  • 完成时间 12:10
• 12:10 作业 3 完成
  • 作业 4 开始执行
  • 完成时间 13:00

平均周转时间：

$$\frac{60+210+190+210}{4}=167.5min$$

STN 调度

选择当前已经到达且运行时间最短的作业执行时间

• 8:00
  • 到达作业：1（运行 1:00）
  • 可运行作业：1
  • 选择作业 1 执行
    • 完成时间 9:00
• 8:30
  • 到达作业：2 （运行 3:00）
  • 可运行作业：1 2
  • 作业 1 继续执行
• 9:00
  • 作业 1 完成
  • 到达作业：3（运行 0:10）
  • 可运行作业：2 3
  • 选择作业 3 执行
• 9:10
  • 作业 3 完成
  • 可运行作业：2（完成时间 12:10）
  • 选择作业 2 执行
• 9:30
  • 到达作业：4（运行 0:50）
  • 可运行作业：2 4（完成时间 10:20）
  • 作业 2 继续执行
• 12:10
  • 作业 2 完成
  • 可运行作业：4
  • 作业 4 执行
• 13:00
  • 完成

平均周转时间：

$$\frac{60+10+220+210}{4}=125min$$

从平均周转时间的角度来看，STN 更优

---

P2

一个批处理系统中，有两个作业进程。有一个作业序列，到达时间和估计服务时间如下。系统采用最高响应比优先的作业调度算法，作业进程的调度采用短作业优先的抢占式调度算法。请列出各作业的执行情况表。

作业	到达时间	服务时间
A	0	35
B	10	30
C	15	45
D	20	20
E	30	30

时间线模拟

即用 SRTF 在两个进程（进程队列）中选择运行，在 ready 队列（作业队列）里面采用 HRRN 发射任务

• 10:00 A 到达
  • 作业中只有 A，直接转化为进程运行
  • 运行 A，剩余时间 35
• 10:10 B 到达
  • 进程队列还有一个，加入进程队列，触发 SRTF
  • A 剩余 25，B 剩余 30，继续运行 A，B 等待
• 10:15 C 到达
  • 加入作业队列
• 10:20 D 到达
  • 加入作业队列
• 10:30 E 到达
  • 加入作业队列
  • 当前作业队列有：C D E
• 10:35
  • A 完成，进程队列释放一个位置，触发 HRRN
    • C：等待 $35-15=20$ 分钟，$H{R}_C=1.44$
    • D：等待 $35-20=15$ 分钟，$H{R}_D=1.75$
    • E：等待 $35-30=5$ 分钟，$H{R}_E=1.17$
    • D 的 HR 最高，加入进程队列
  • 进程队列中：B 剩余 30，D 剩余 20
  • 选择 D 运行
• 10:55
  • D 完成，进程释放一个位置，触发 HRRN
    • C：等待 40 分钟，$H{R}_C=1.89$
    • E：等待 25 分钟，$H{R}_E=1.83$
    • C 的 HR 更高，加入进程
  • 进程队列：B 剩余 30，C 剩余 45
  • 选择 B 运行
• 11:25
  • B 完成，E 加入进程队列
  • 进程队列：C 剩余 45，E 剩余 30
  • 选择 E 运行
• 11:55
  • E 完成，运行 C
• 12:40
  • C 完成

最终执行情况表

作业	到达时间	服务时间	开始时间	完成时间	周转时间	带权周转时间
A	0	35	0	35	35	1.0
D	20	20	35	55	35	1.75
B	10	30	35→55	85	75	2.5
E	30	30	85	115	85	2.83
C	15	45	85→115	160	145	3.22

---

P3

如下作业序列：有 5 个批处理作业（A,B,C,D,E）几乎同时到达一个计算中心，估计的运行时间分别为 2，4，6，8，10 分钟。它们的优先级分别为 1，2，3，4，5（1 为最低优先级）。对下面每种调度算法，分别计算作业的平均周转时间。

• 最高优先级优先
• 时间片轮转（时间片为 2 分钟）
• FCFS。（到达顺序为 C,D,B,E,A）
• 短作业优先

最高优先级优先

• 执行顺序：E（优先级 5）→ D（4）→ C（3）→ B（2）→ A（1）
• 完成时间（周转时间）：E（10）、D（18）、C（24）、B（28）、A（30）
• 平均周转时间：22 分钟

时间片轮转

假设初始队列顺序为 ABCDE

• A 完成于 2，B 完成于 12，C 于 20，D 于 26，E 于 30
• 平均周转时间：18 分钟

FCFS

• 执行顺序为 CDBEA
• 完成时间（周转时间）：C（6）、D（14）、B（18）、E（28）、A（30）
• 平均周转时间：19.2 分钟

短作业优先

• 执行顺序为 ABCDE
• 完成时间（周转时间）：A（2）、B（6）、C（12）、D（20）、E（30）
• 平均周转时间：14 分钟