作业、进程调度练习()-其他
作业、进程调度练习()
一、题目
- 分别按FCFS、SJF、HRRN调度算法写出四个作业的执行顺序、平均周转时间、平均带权周转时间,并说明哪种算法最好。
作业
到达时间
服务时间
\(job_1\)
8:00
2h
\(job_2\)
8:30
30min
\(job_3\)
9:00
6min
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 |
|---|---|---|
| \(job_1\) | 8:00 | 2h |
| \(job_2\) | 8:30 | 30min |
| \(job_3\) | 9:00 | 6min |
| \(job_4\) | 9:30 | 12min |
二、解答
1、FCFS
- 按到达顺序执行
作业
到达时间
服务时间
完成时间
周转时间
带权周转时间
执行顺序
\(job_1\)
8:00
2h
10:00
2h
1
1
\(job_2\)
8:30
30min
10:30
2h
4
2
\(job_3\)
9:00
6min
10:36
96min
16
3
\(job_4\)
9:30
12min
10:48
78min
6.5
4
注意单位转换！
平均周转时间：\((120+120+96+78)/4=103.5\)
平均带权周转时间：\((1+4+16+6.5)/4=6.875\)
| 作业 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 带权周转时间 | 执行顺序 |
|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 10:30 | 2h | 4 | 2 |
| \(job_3\) | 9:00 | 6min | 10:36 | 96min | 16 | 3 |
| \(job_4\) | 9:30 | 12min | 10:48 | 78min | 6.5 | 4 |
注意单位转换！
注意单位转换！
- 平均周转时间：\((120+120+96+78)/4=103.5\)
- 平均带权周转时间：\((1+4+16+6.5)/4=6.875\)
2、SJF
- 刚开始执行最先到达的作业\(job_1\)
- \(job_1\)执行后所有作业都到达，在到达作业中取时间最短的\(job_3\)
- \(job_3\)执行后选取时间较短的\(job_4\)
- 最后执行\(job_2\)
作业
到达时间
服务时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
10:00
2h
1
1
\(job_2\)
8:30
30min
10:48
138min
4.6
4
\(job_3\)
9:00
6min
10:06
66min
11
2
\(job_4\)
9:30
12min
10:18
48min
4
3
平均周转时间：\((120+138+66+48)/4=93\)
平均带权周转时间：\((1+4.6+11+4)/4=5.15\)
| 作业 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 10:48 | 138min | 4.6 | 4 |
| \(job_3\) | 9:00 | 6min | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min | 10:18 | 48min | 4 | 3 |
- 平均周转时间：\((120+138+66+48)/4=93\)
- 平均带权周转时间：\((1+4.6+11+4)/4=5.15\)
3、HRNN
- 刚开始执行最小到达的作业\(job_1\)
- 第一轮计算响应比(优先权)\(R_p=1+\frac{等待时间}{服务时间}\)
\(R_2=1+(10:00-8:30)/30min=4\)
\(R_3=1+(10:00-9:00)/6min=11\)
\(R_4=1+(10:00-9:30)/12min=3.5\) - \(R_2=1+(10:00-8:30)/30min=4\)
- \(R_3=1+(10:00-9:00)/6min=11\)
- \(R_4=1+(10:00-9:30)/12min=3.5\)
- 选取高响应比的\(job_3\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
0
10:00
2h
1
1
\(job_2\)
8:30
30min
\(job_3\)
9:00
6min
1h
10:06
66min
11
2
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | |||||
| \(job_3\) | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min |
-
第二轮计算响应比(优先权)\(R_p=1+\frac{等待时间}{服务时间}\)
\(R_2=1+(10:06-8:30)/30min=4.2\)
\(R_4=1+(10:06-9:30)/12min=4\) - \(R_2=1+(10:06-8:30)/30min=4.2\)
- \(R_4=1+(10:06-9:30)/12min=4\)
- 选取高响应比的\(job_2\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
0
10:00
2h
1
1
\(job_2\)
8:30
30min
96min
10:36
126min
4.2
3
\(job_3\)
9:00
6min
1h
10:06
66min
11
2
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 96min | 10:36 | 126min | 4.2 | 3 |
| \(job_3\) | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min |
- 第三轮选取\(job_4\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
job_1
8:00
2h
0
10:00
2h
1
1
job_2
8:30
30min
156
10:36
126min
4.2
3
job_3
9:00
6min
1h
10:06
66min
11
2
job_4
9:30
12min
66min
10:48
78min
6.5
4
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| job_1 | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| job_2 | 8:30 | 30min | 156 | 10:36 | 126min | 4.2 | 3 |
| job_3 | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| job_4 | 9:30 | 12min | 66min | 10:48 | 78min | 6.5 | 4 |
平均周转时间：\((120+126+66+78)/4=97.5\)
平均带权周转时间：\((1+4.2+11+6.5)/4=5.675\)
- 平均周转时间：\((120+126+66+78)/4=97.5\)
- 平均带权周转时间：\((1+4.2+11+6.5)/4=5.675\)
4、性能对比
调度算法
性能(平均带权周转时间W)
FCFS
6.875
SJF
5.15
HRNN
5.675
SJF的平均带权周转时间W最小，性能最优。
| 调度算法 | 性能(平均带权周转时间W) |
|---|---|
| FCFS | 6.875 |
| SJF | 5.15 |
| HRNN | 5.675 |
- SJF的平均带权周转时间W最小，性能最优。
一、题目
- 分别按FCFS、SJF、HRRN调度算法写出四个作业的执行顺序、平均周转时间、平均带权周转时间,并说明哪种算法最好。
作业
到达时间
服务时间
\(job_1\)
8:00
2h
\(job_2\)
8:30
30min
\(job_3\)
9:00
6min
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 |
|---|---|---|
| \(job_1\) | 8:00 | 2h |
| \(job_2\) | 8:30 | 30min |
| \(job_3\) | 9:00 | 6min |
| \(job_4\) | 9:30 | 12min |
二、解答
1、FCFS
- 按到达顺序执行
作业
到达时间
服务时间
完成时间
周转时间
带权周转时间
执行顺序
\(job_1\)
8:00
2h
10:00
2h
1
1
\(job_2\)
8:30
30min
10:30
2h
4
2
\(job_3\)
9:00
6min
10:36
96min
16
3
\(job_4\)
9:30
12min
10:48
78min
6.5
4
注意单位转换！
平均周转时间：\((120+120+96+78)/4=103.5\)
平均带权周转时间：\((1+4+16+6.5)/4=6.875\)
| 作业 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 带权周转时间 | 执行顺序 |
|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 10:30 | 2h | 4 | 2 |
| \(job_3\) | 9:00 | 6min | 10:36 | 96min | 16 | 3 |
| \(job_4\) | 9:30 | 12min | 10:48 | 78min | 6.5 | 4 |
注意单位转换！
注意单位转换！
- 平均周转时间：\((120+120+96+78)/4=103.5\)
- 平均带权周转时间：\((1+4+16+6.5)/4=6.875\)
2、SJF
- 刚开始执行最先到达的作业\(job_1\)
- \(job_1\)执行后所有作业都到达，在到达作业中取时间最短的\(job_3\)
- \(job_3\)执行后选取时间较短的\(job_4\)
- 最后执行\(job_2\)
作业
到达时间
服务时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
10:00
2h
1
1
\(job_2\)
8:30
30min
10:48
138min
4.6
4
\(job_3\)
9:00
6min
10:06
66min
11
2
\(job_4\)
9:30
12min
10:18
48min
4
3
平均周转时间：\((120+138+66+48)/4=93\)
平均带权周转时间：\((1+4.6+11+4)/4=5.15\)
| 作业 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 10:48 | 138min | 4.6 | 4 |
| \(job_3\) | 9:00 | 6min | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min | 10:18 | 48min | 4 | 3 |
- 平均周转时间：\((120+138+66+48)/4=93\)
- 平均带权周转时间：\((1+4.6+11+4)/4=5.15\)
3、HRNN
- 刚开始执行最小到达的作业\(job_1\)
- 第一轮计算响应比(优先权)\(R_p=1+\frac{等待时间}{服务时间}\)
\(R_2=1+(10:00-8:30)/30min=4\)
\(R_3=1+(10:00-9:00)/6min=11\)
\(R_4=1+(10:00-9:30)/12min=3.5\) - \(R_2=1+(10:00-8:30)/30min=4\)
- \(R_3=1+(10:00-9:00)/6min=11\)
- \(R_4=1+(10:00-9:30)/12min=3.5\)
- 选取高响应比的\(job_3\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
0
10:00
2h
1
1
\(job_2\)
8:30
30min
\(job_3\)
9:00
6min
1h
10:06
66min
11
2
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | |||||
| \(job_3\) | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min |
-
第二轮计算响应比(优先权)\(R_p=1+\frac{等待时间}{服务时间}\)
\(R_2=1+(10:06-8:30)/30min=4.2\)
\(R_4=1+(10:06-9:30)/12min=4\) - \(R_2=1+(10:06-8:30)/30min=4.2\)
- \(R_4=1+(10:06-9:30)/12min=4\)
- 选取高响应比的\(job_2\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
\(job_1\)
8:00
2h
0
10:00
2h
1
1
\(job_2\)
8:30
30min
96min
10:36
126min
4.2
3
\(job_3\)
9:00
6min
1h
10:06
66min
11
2
\(job_4\)
9:30
12min
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| \(job_1\) | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| \(job_2\) | 8:30 | 30min | 96min | 10:36 | 126min | 4.2 | 3 |
| \(job_3\) | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| \(job_4\) | 9:30 | 12min |
- 第三轮选取\(job_4\)
作业
到达时间
服务时间
等待时间
完成时间
周转时间
带权周转
执行顺序
job_1
8:00
2h
0
10:00
2h
1
1
job_2
8:30
30min
156
10:36
126min
4.2
3
job_3
9:00
6min
1h
10:06
66min
11
2
job_4
9:30
12min
66min
10:48
78min
6.5
4
| 作业 | 到达时间 | 服务时间 | 等待时间 | 完成时间 | 周转时间 | 带权周转 | 执行顺序 |
|---|---|---|---|---|---|---|---|
| job_1 | 8:00 | 2h | 0 | 10:00 | 2h | 1 | 1 |
| job_2 | 8:30 | 30min | 156 | 10:36 | 126min | 4.2 | 3 |
| job_3 | 9:00 | 6min | 1h | 10:06 | 66min | 11 | 2 |
| job_4 | 9:30 | 12min | 66min | 10:48 | 78min | 6.5 | 4 |
平均周转时间：\((120+126+66+78)/4=97.5\)
平均带权周转时间：\((1+4.2+11+6.5)/4=5.675\)
- 平均周转时间：\((120+126+66+78)/4=97.5\)
- 平均带权周转时间：\((1+4.2+11+6.5)/4=5.675\)
4、性能对比
调度算法
性能(平均带权周转时间W)
FCFS
6.875
SJF
5.15
HRNN
5.675
SJF的平均带权周转时间W最小，性能最优。
| 调度算法 | 性能(平均带权周转时间W) |
|---|---|
| FCFS | 6.875 |
| SJF | 5.15 |
| HRNN | 5.675 |
- SJF的平均带权周转时间W最小，性能最优。