周转时间、带权周转时间、平均周转时间、平均带权周转时间

1. 计算公式

- 周转时间（Turnaround Time） = 完成时间 - 到达时间

例如： 一个作业在时刻0到达，完成时间为时刻10，则周转时间为10 - 0 = 10。

- 带权周转时间（Weighted Turnaround Time） = 周转时间 / 执行时间

例如： 如果周转时间为10，执行时间为5，则带权周转时间为10 / 5 = 2.0。

- 平均周转时间（Average Turnaround Time） = 所有作业的周转时间之和 / 作业数量

例如： 如果有三个作业的周转时间分别为10、5、15，则平均周转时间为 (10 + 5 + 15) / 3 = 10。

- 平均带权周转时间（Average Weighted Turnaround Time） = 所有作业的带权周转时间之和 / 作业数量

例如： 如果有三个作业的带权周转时间分别为2.0、1.5、3.0，则平均带权周转时间为 (2.0 + 1.5 + 3.0) / 3 = 2.17。

---

2. 调度算法的解释与示例

1. FCFS (First-Come, First-Served) 先来先服务

   • 定义：按作业到达的顺序依次调度，不考虑作业的执行时间或优先级。
   • 示例：假设有三个作业A、B、C按顺序到达，执行时间分别为4、3、5。则FCFS按A -> B -> C的顺序执行，完成顺序与到达顺序相同。

2. RR (Round Robin) 时间片轮转

   • 定义：按时间片轮流执行，每个作业在完成一个时间片后，如果未完成，则让给下一个作业。适合交互式系统。
   • 示例：假设有三个作业A、B、C，到达时的执行时间分别为4、3、5，时间片为1。A执行1个时间片后让位给B，B执行1个时间片后让位给C，再轮到A，以此循环直到作业完成。

3. SJF (Shortest Job First) 最短作业优先

   • 定义：选择执行时间最短的作业优先调度，减少整体等待时间。适用于作业长度已知的情况。
   • 示例：假设有三个作业A、B、C到达，执行时间分别为5、2、3，则SJF调度顺序为B -> C -> A，因为B的执行时间最短。

4. 非抢占式优先级调度

   • 定义：按照作业的优先级顺序调度，优先级高的作业先执行；相同优先级的按到达顺序执行。
   • 示例：假设有三个作业A、B、C，优先级从高到低依次为B、A、C，执行时间分别为4、3、5。则调度顺序为B -> A -> C，因为B的优先级最高。

---

在此问题中，我们有5个作业按优先级到达处理机并需要完成的时间和优先级分别如表所示。不同的调度算法将影响每个作业的执行顺序，从而影响平均周转时间和平均带权周转时间。我们将针对每种调度算法（FCFS, RR（时间片为1）, SJF, 非抢占式优先级调度）逐一计算周转时间和带权周转时间。

例题

作业	执行时间	优先级
1	10	3
2	1	1
3	2	3
4	1	4
5	5	2

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

按到达顺序执行作业，执行顺序：1, 2, 3, 4, 5。

作业	到达时间	执行时间	完成时间	周转时间（完成时间 - 到达时间）	带权周转时间（周转时间 / 执行时间）
1	0	10	10	10	1.0
2	0	1	11	11	11.0
3	0	2	13	13	6.5
4	0	1	14	14	14.0
5	0	5	19	19	3.8

• 平均周转时间 = (10 + 11 + 13 + 14 + 19) / 5 = 67 / 5 = 13.4
• 平均带权周转时间 = (1.0 + 11.0 + 6.5 + 14.0 + 3.8) / 5 = 36.3 / 5 = 7.26

2. RR（Round Robin）时间片轮转（时间片为1）

每个作业按时间片1轮流执行，直到完成。

时间	执行的作业	当前作业剩余执行时间
0-1	1	9
1-2	2	0 (完成)
2-3	3	1
3-4	4	0 (完成)
4-5	5	4
5-6	1	8
6-7	3	0 (完成)
7-8	5	3
8-9	1	7
9-10	5	2
10-11	1	6
11-12	5	1
12-13	1	5
13-14	5	0 (完成)
14-20	1	0 (完成)

计算周转时间：

作业	完成时间	周转时间	带权周转时间
1	20	20	2.0
2	2	2	2.0
3	7	7	3.5
4	4	4	4.0
5	14	14	2.8

• 平均周转时间 = (20 + 2 + 7 + 4 + 14) / 5 = 47 / 5 = 9.4
• 平均带权周转时间 = (2.0 + 2.0 + 3.5 + 4.0 + 2.8) / 5 = 14.3 / 5 = 2.86

3. SJF（Shortest Job First）最短作业优先

按作业执行时间从短到长依次执行，执行顺序：2, 4, 3, 5, 1。

作业	执行时间	完成时间	周转时间	带权周转时间
2	1	1	1	1.0
4	1	2	2	2.0
3	2	4	4	2.0
5	5	9	9	1.8
1	10	19	19	1.9

• 平均周转时间 = (1 + 2 + 4 + 9 + 19) / 5 = 35 / 5 = 7.0
• 平均带权周转时间 = (1.0 + 2.0 + 2.0 + 1.8 + 1.9) / 5 = 8.7 / 5 = 1.74

4. 非抢占式优先级调度

按优先级从高到低调度作业，优先级顺序：2, 5, 1, 3, 4。

作业	执行时间	完成时间	周转时间	带权周转时间
2	1	1	1	1.0
5	5	6	6	1.2
1	10	16	16	1.6
3	2	18	18	9.0
4	1	19	19	19.0

• 平均周转时间 = (1 + 6 + 16 + 18 + 19) / 5 = 60 / 5 = 12.0
• 平均带权周转时间 = (1.0 + 1.2 + 1.6 + 9.0 + 19.0) / 5 = 31.8 / 5 = 6.36

结果汇总

调度算法	平均周转时间	平均带权周转时间
FCFS	13.4	7.26
RR（时间片为1）	9.4	2.86
SJF	7.0	1.74
非抢占式优先级	12.0	6.36

从结果中可以看出，SJF 算法在平均周转时间和平均带权周转时间方面表现最佳，而 FCFS 算法由于简单，但在平均周转时间和带权周转时间上表现较差。RR 算法能较好地平衡各作业的响应时间，但在周转时间上表现不如 SJF。