题目
20.(考研真题)假定要在一台处理机上执行表3-3所示的作业，且假定这些作业在时刻0以1,2,3,4,5的顺序到达。请说明分别采用FCFS、RR(时间片[1]为1)、SJF及非抢占式优先级调度[2]算法时，这些作业的执行情况(优先级的高低顺序依次为1到5)。针对上述每种调度算法，给出平均周转时间和平均带权周转时间。表 3-3 作业执行时间表-|||-作业 执行时间 优先级-|||-1 10 3-|||-2 1 1-|||-3 2 3-|||-4 1 4-|||-5 5 2
20.(考研真题)假定要在一台处理机上执行表3-3所示的作业，且假定这些作业在时刻0以
1,2,3,4,5的顺序到达。请说明分别采用FCFS、RR(时间片[1]为1)、SJF及非抢占式优先级调度[2]算法时，这些作业的执行情况(优先级的高低顺序依次为1到5)。针对上述每种调度算法，给出平均周转时间和平均带权周转时间。
题目解答
答案
在这道题中，我们需要分别采用FCFS（先来先服务）、RR（时间片为1）、SJF（短作业优先）及非抢占式优先级调度算法，分析这些作业的执行情况。优先级的高低顺序依次为1到5。
1. FCFS（先来先服务）调度算法：
作业按照到达的顺序执行，所以作业的执行顺序为：1、2、3、4、5。
平均周转时间：
2. RR（时间片为1）调度算法：
作业按照到达顺序分配时间片，当一个作业的时间片用完时，将CPU分配给下一个作业。所以作业的执行顺序为：1、2、1、3、1、4、1、5。
平均周转时间：
3. SJF（短作业优先）调度算法：
作业按照计算时间长短优先执行，所以作业的执行顺序为：2、1、3、4、5。
平均周转时间：
4. 非抢占式优先级调度算法：
作业按照优先级顺序执行，所以作业的执行顺序为：1、2、3、4、5。
平均周转时间：
解析
步骤 1：FCFS（先来先服务）调度算法
作业按照到达的顺序执行，所以作业的执行顺序为：1、2、3、4、5。
步骤 2：计算FCFS的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+1+5}{5}=3.8$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+1/1+5/5}{5}=1.6$
步骤 3：RR（时间片为1）调度算法
作业按照到达顺序分配时间片，当一个作业的时间片用完时，将CPU分配给下一个作业。所以作业的执行顺序为：1、2、1、3、1、4、1、5。
步骤 4：计算RR的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+3+4+5}{6}\approx 4.2$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+3/1+4/1+5/5}{6}\approx 2.1$
步骤 5：SJF（短作业优先）调度算法
作业按照计算时间长短优先执行，所以作业的执行顺序为：2、1、3、4、5。
步骤 6：计算SJF的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {1+2+2+3+4}{5}=2.4$
- 平均带权周转时间：$W_{avg}=\dfrac {1/1+2/10+2/2+3/1+4/5}{5}=0.8$
步骤 7：非抢占式优先级调度算法
作业按照优先级顺序执行，所以作业的执行顺序为：1、2、3、4、5。
步骤 8：计算非抢占式优先级调度的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+1+5}{5}=3.8$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+1/1+5/5}{5}=1.6$
作业按照到达的顺序执行，所以作业的执行顺序为：1、2、3、4、5。
步骤 2：计算FCFS的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+1+5}{5}=3.8$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+1/1+5/5}{5}=1.6$
步骤 3：RR（时间片为1）调度算法
作业按照到达顺序分配时间片，当一个作业的时间片用完时，将CPU分配给下一个作业。所以作业的执行顺序为：1、2、1、3、1、4、1、5。
步骤 4：计算RR的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+3+4+5}{6}\approx 4.2$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+3/1+4/1+5/5}{6}\approx 2.1$
步骤 5：SJF（短作业优先）调度算法
作业按照计算时间长短优先执行，所以作业的执行顺序为：2、1、3、4、5。
步骤 6：计算SJF的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {1+2+2+3+4}{5}=2.4$
- 平均带权周转时间：$W_{avg}=\dfrac {1/1+2/10+2/2+3/1+4/5}{5}=0.8$
步骤 7：非抢占式优先级调度算法
作业按照优先级顺序执行，所以作业的执行顺序为：1、2、3、4、5。
步骤 8：计算非抢占式优先级调度的平均周转时间和平均带权周转时间
- 平均周转时间：$T_{avg}=\dfrac {10+1+2+1+5}{5}=3.8$
- 平均带权周转时间：$W_{avg}=\dfrac {10/10+1/1+2/2+1/1+5/5}{5}=1.6$