一、题目

• 分别按FCFS、SJF、HRRN调度算法写出四个作业的执行顺序、平均周转时间、平均带权周转时间,并说明哪种算法最好。

作业	到达时间	服务时间
(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)

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)

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)
• 选取高响应比的(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

• 第二轮计算响应比(优先权)(R_p=1+frac{等待时间}{服务时间})

  • (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_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)

4、性能对比

调度算法	性能(平均带权周转时间W)
FCFS	6.875
SJF	5.15
HRNN	5.675

• SJF的平均带权周转时间W最小，性能最优。