第三章练习题及答案1．在单道环境下，某批处理有四道作业，已知它们进入系统的时刻、估计运行时间如下：作业进入时刻(h）运行时间（h)18.002. 0028.500. 5039.000.1049.500. 20设系统每次只选择一个作业进入主机，分别给出在FCFS,SJF，HRN算法中这组作业的运行顺序、平均周转时间和平均带权周转时间。2.为什么说多级反馈队列能较好地满足各种用户的需要？3.有一个多道程序系统，有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业调度和进程调度均采用FCFS算法。现有一批作业，已知条件如下：作业名进入输入井时间需内存量（KB）需计算时间（分）4215A8:06B30608:18c8:302450D8:362410E12208:42假定所有作业都是计算型作业并且忽略系统调度所化的时间。计算各作业被选中装入内存的时间、开始执行的时间、结束执行的时间、周转时间和带权周转时间。4.上例中，其他假设条件不变，仅把作业的调度算法改为按SF算法，进程仍采用FCFS算法。5.作业调度的性能评价标准有哪些？这些性能评价在任何情况下都能反映调度策略的优劣吗？6什么叫无限期封锁（indefiniteblocking）?它在什么情况下出现？作业调度算法选择作业的原则，可以是保证系统的吞吐量大、可以是对用户公平合理、7.可以是充分发挥系统资源的利用率。请分别指出先来先服务、最短作业优先、I/0量大与CPU量大的作业搭配3种调度算法，体现了那种选择作业的原则？8.假定待处理的三个作业的到达时间和运行时间如下，若采用调度算法①、②、③，这些作业的平均周转时间是多少？作业名执行时间到达时间(时)180.0240.431.01OFCFS:@SJF;③考虑一下如何改善SJF的性能，并计算新方法的平均周转时间？
第三章 练习题及答案 1. 在单道环境下，某批处理有四道作业，已知它们进入系统的时刻、估计运行时间如下： 作业 进入时刻(h) 运行时间(h) 1 8.00 2.00 2 8.50 0.50 3 9.00 0.10 4 9.50 0.20 设系统每次只选择一个作业进入主机，分别给出在FCFS,SJF,HRN算法中这组作业的运行顺 序、平均周转时间和平均带权周转时间。 2. 为什么说多级反馈队列能较好地满足各种用户的需要? 3. 有一个多道程序系统，有用户空间100KB，并规定作业相应程序装入内存连续区域，并 不能被移动，作业调度和进程调度均采用FCFS算法。现有一批作业，已知条件如下： 作业名 进入输入井时间 需计算时间（分） 需内存量（KB） A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 假定所有作业都是计算型作业并且忽略系统调度所化的时间。计算各作业被选中装入内存的 时间、开始执行的时间、结束执行的时间、周转时间和带权周转时间。 4. 上例中，其他假设条件不变，仅把作业的调度算法改为按SF算法，进程仍采用FCFS算法。 5. 作业调度的性能评价标准有哪些？这些性能评价在任何情况下都能反映调度策略的优 劣吗？ 6. 什么叫无限期封锁（indefinite blocking）?它在什么情况下出现？ 7. 作业调度算法选择作业的原则，可以是保证系统的吞吐量大、可以是对用户公平合理、 可以是充分发挥系统资源的利用率。请分别指出先来先服务、最短作业优先、I/O量大 与CPU量大的作业搭配３种调度算法，体现了那种选择作业的原则？ 8. 假定待处理的三个作业的到达时间和运行时间如下，若采用调度算法①、②、③，这些 作业的平均周转时间是多少？ 作业名 到达时间(时) 执行时间 1 0.0 8 2 0.4 4 3 1.0 1 ①FCFS： ②SJF； ③考虑一下如何改善 SJF 的性能，并计算新方法的平均周转时间？
9.假定要在一台处理机上执行下列作业：作业优先级执行时间3110211323441552且假定这些作业达到的次序是1，2，3，4，5。(1)给出Gantt图来说明分别使用FCFS，RR(时间片=1)，SJF以及非抢占优先调度算法时这些作业的执行情况：（注：Gantt图是描述进程/作业执行情况的一种直观形式，它展示了作业/进程执行过程中瞬时段或时间片的变化分布情况。）(2)针对上述每一调度算法，给出每个作业的周转时间；（3）就上述每一调度算法，求出每个作业相应的等待时间：10.设有5个就绪进程，它们的本次CPU周期的长度、初始优先数及进入就绪队列的相对时刻如下所示：进程CPU周期(ms)优先数进入时刻（ms)325P10430P2850P320P464P51616规定：小的优先数表示高的优先级。画出下列两种情况的Gantt图，计算它们的平均等待时间、平均周转时间和平均带权周转时间。(1)非剥夺的静态设置方式：(2)剥夺式的动态设置方式，不妨设现行进程每连续执行12ms后，其优先数加1（即优先级降低），而就绪进程每40ms后，其优先数减1。11.有3道作业构成如下，它们在一个系统中运行，该系统有输入/输出设备各一台。A进程：输入32s，计算8s，输出5sB进程：输入21s，计算14s，输出35sC进程：输入12s，计算32s，输出15s问(1)3道程序顺序执行时最短需要多少时间？(2)为了充分发挥各设备效能，3道程序并发执行最短需要多少时间？（不计系统开销时间12.在一个实时系统中，有两个周期性实时任务A和B，任务A要求每40ms执行一次，执行时间为20mS：任务B要求每100ms执行一次，执行时间为50mS。请参考课堂相关知识画出在200ms时间内，任务A和B调度情况示意图。并标出任务A和B每一次执行的时间。习题解答：1.解：下面我们用一张表帮助理解作业进入时刻带权周转运行时间开始时刻完成时刻1周转时间
9. 假定要在一台处理机上执行下列作业： 作业 执行时间 优先级 １ 10 3 ２ 1 1 ３ 2 3 ４ 1 4 ５ 5 2 且假定这些作业达到的次序是 1，2，3，4，5。 ⑴给出 Gantt 图来说明分别使用 FCFS，RR(时间片=1)，SJF 以及非抢占优先调度算法时 这些作业的执行情况；（注：Gantt 图是描述进程/作业执行情况的一种直观形式，它展 示了作业/进程执行过程中瞬时段或时间片的变化分布情况。） ⑵针对上述每一调度算法，给出每个作业的周转时间； ⑶就上述每一调度算法，求出每个作业相应的等待时间； 10. 设有5个就绪进程，它们的本次CPU周期的长度、初始优先数及进入就绪队列的相对时刻 如下所示： 进程 CPU 周期(ms) 优先数 进入时刻(ms) P1 32 5 0 P2 4 3 0 P3 8 5 0 P4 2 6 0 P5 16 4 16 规定：小的优先数表示高的优先级。画出下列两种情况的 Gantt 图，计算它们的平均等 待时间、平均周转时间和平均带权周转时间。 ⑴非剥夺的静态设置方式； ⑵剥夺式的动态设置方式，不妨设现行进程每连续执行 12ms 后，其优先数加 1（即优 先级降低），而就绪进程每 40ms 后，其优先数减 1。 11. 有3道作业构成如下，它们在一个系统中运行，该系统有输入/输出设备各一台。 A 进程：输入 32s，计算 8s，输出 5s B 进程：输入 21s，计算 14s，输出 35s C 进程：输入 12s，计算 32s，输出 15s 问⑴3 道程序顺序执行时最短需要多少时间？ ⑵为了充分发挥各设备效能，3 道程序并发执行最短需要多少时间？（不计系统开销时 间） 12. 在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 40 ms执行一次，执行 时间为 20 ms；任务B要求每100ms执行一次，执行时间为 50 ms。请参考课堂相关知识 画出在200ms时间内，任务A和B调度情况示意图。并标出任务A和B每一次执行的时间。 习题解答： 1. 解：下面我们用一张表帮助理解 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转
12.008.002.001. 008.0010.0022.008.500.5010.0010.504.0039. 000. 1010.5010.601. 6016. 0049.500. 201.3010.6010.806.50平均周转时间T=1.725(h)6.9027.50平均带权周转时间T=6.875(h)FCFS算法的调度顺序为：1→2→3→4。作业进入时刻运行时间完成时刻周转时间带权周转开始时刻412.008. 002.008.0010.001. 0028.500.5010.3010.802.304. 6039. 000. 1010. 001. 1010.1011.0049.500.800.2010.1010.304.00平均周转时间T=1.55(h)6. 2020.60平均带权周转时间T=5.15(h)SJF算法的调度顺序为：1→3→4→2。作业进入时刻完成时刻带权周转运行时间开始时刻周转时间18. 002. 008. 0010. 002. 001.0020. 502. 108.5010.1010.604.2039. 000. 1010. 001. 1011.0010.1049.500. 2010.6010.801. 306.50平均周转时间T=1.625(h)6.5022.70平均带权周转时间T=5.675(h)HRN算法的调度顺序为：1→+3-→2→4。2.答：多级反馈队列是综合了FCFS、RR、HPF三种算法的一种剥夺式的调度算法，它根据进程运行情况的反馈信息动态地改变进程的优先级，按优先级级别组织设置各就绪队列，并规定各就绪队列不同的CPU时间片，对同一队列中的各就绪进程按FCFS或RR算法调度，因而能较好地满足各种用户的需要。3.解：作业名装入内存开始执行结束执行周转（分）带权周转A428:068:068: 48(1)42/42B608:188:489:18(2)60/30D8:369:189:4266(2.75)66/24C969:189:4210:06(4) 96/24E9:1810:189610:06(8) 96/125个作业的平均周转时间和带权周转时间为：T=72（分），T=3.554.解：作业名装入内存开始执行结束执行周转（分）带权周转A428:068:068: 48(1)42/42B608:188:489:18(2)60/30
1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.00 10.50 2.00 4.00 3 9.00 0.10 10.50 10.60 1.60 16.00 4 9.50 0.20 10.60 10.80 1.30 6.50 平均周转时间 T=1.725(h) 平均带权周转时间 T’=6.875(h) 6.90 27.50 FCFS算法的调度顺序为：1→2→3→4。 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.30 10.80 2.30 4.60 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.10 10.30 0.80 4.00 平均周转时间 T=1.55(h) 平均带权周转时间 T’=5.15(h) 6.20 20.60 SJF算法的调度顺序为：1→3→4→2。 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.10 10.60 2.10 4.20 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.60 10.80 1.30 6.50 平均周转时间 T=1.625(h) 平均带权周转时间 T’=5.675(h) 6.50 22.70 HRN算法的调度顺序为：1→3→2→4。 2. 答：多级反馈队列是综合了FCFS、RR、HPF三种算法的一种剥夺式的调度算法，它根据 进程运行情况的反馈信息动态地改变进程的优先级，按优先级级别组织设置各就绪队 列，并规定各就绪队列不同的CPU时间片，对同一队列中的各就绪进程按FCFS或RR算法 调度，因而能较好地满足各种用户的需要。 3. 解： 作业名 装入内存 开始执行 结束执行 周转(分) 带权周转 A 8:06 8:06 8:48 42 (1)42/42 B 8:18 8:48 9:18 60 (2)60/30 D 8:36 9:18 9:42 66 (2.75)66/24 C 9:18 9:42 10:06 96 (4)96/24 E 9:18 10:06 10:18 96 (8)96/12 5 个作业的平均周转时间和带权周转时间为：T=72(分)，T’=3.55 4. 解： 作业名 装入内存 开始执行 结束执行 周转(分) 带权周转 A 8:06 8:06 8:48 42 (1)42/42 B 8:18 8:48 9:18 60 (2)60/30
D9:4266(2.75)66/248:369:18E9:54729:189:42(4)72/24c9:189:5410810:18(8)108/125个作业的平均周转时间和带权周转时间为：T=69.6（分），T"=3.255.答：对于批处理系统主要以作业的平均周转时间或平均带权周转时间来衡量调度策略的优劣；而对于分时系统，除了要保证系统的吞吐量大、资源利用率高之外，还应保证用户能容忍的响应时间：实时系统的主要标志则是满足用户要求的时限（截止）时间。6.答：无限期封锁也叫饥饿（starvation），即一个具有低优先级的进程决无运行的机会。当CPU接连不断地被较高优先级的作业占用时就可能出现这样的情况。7.答：系统的吞吐量大是最短作业优先算法，因为SF使作业的平均周转时间有明显的改善，从而使系统在单位时间内处理的作业数增多。对用户公平合理是先来先服务算法。因为对用户按照作业进入输入井时间的先后调度，先来先服务，对每个用户都是公平的。发挥系统资源的利用率是I/O量大与CPU量大的作业搭配算法。因为这种算法使I/O与CPU设备都忙碌，并行性好，系统的效率高。8.答：①FCFS:10.53((8-0)+(12-0.4)+(13-1)/3注意：应减去达到时间。②SJF:9.53③分析：由于我们事先并不知道两个较短的作业将很快到达，所以在时刻0，我们选择了作业1。如果让CPU在第一个时间单位空闲，然后使用SJF调度策略，该算法称为“未来知识调度算法FKS”。当然在本例中，由于作业1和2在空闲时间处于等待状态，它们的等待时间会增加。FKS:6.86((2-1)+(6-0.4)+(14-0)/3=6.869.解：①执行情况的Gantt图如下所示：FCFS:1(10)2(1)3(2)5(5)4(1)RR:1121314151131511151151151SJF:23514Priority:51324②与这些作业相对应的周转时间如下：作业FCFSRRSJFPriority11019191621121173134182414 4195191491③与这些作业相对应的等待时间如下：作业SJFFCFSRRPriority10996210100
D 8:36 9:18 9:42 66 (2.75)66/24 E 9:18 9:42 9:54 72 (4)72/24 C 9:18 9:54 10:18 108 (8)108/12 5 个作业的平均周转时间和带权周转时间为：T=69.6(分)，T’=3.25 5. 答：对于批处理系统主要以作业的平均周转时间或平均带权周转时间来衡量调度策略的 优劣；而对于分时系统，除了要保证系统的吞吐量大、资源利用率高之外，还应保证用 户能容忍的响应时间；实时系统的主要标志则是满足用户要求的时限（截止）时间。 6. 答：无限期封锁也叫饥饿（starvation），即一个具有低优先级的进程决无运行的机会。 当CPU接连不断地被较高优先级的作业占用时就可能出现这样的情况。 7. 答：系统的吞吐量大是最短作业优先算法，因为SJF使作业的平均周转时间有明显的改 善，从而使系统在单位时间内处理的作业数增多。对用户公平合理是先来先服务算法。 因为对用户按照作业进入输入井时间的先后调度，先来先服务，对每个用户都是公平的。 发挥系统资源的利用率是I/O量大与CPU量大的作业搭配算法。因为这种算法使I/O与CPU 设备都忙碌，并行性好，系统的效率高。 8. 答：①FCFS: 10.53 ((8-0)+(12-0.4)+(13-1))/3 注意：应减去达到时间。 ②SJF: 9.53 ③分析：由于我们事先并不知道两个较短的作业将很快到达，所以在时刻 0，我们 选择了作业１。如果让 CPU 在第一个时间单位空闲，然后使用 SJF 调度策略，该算法 称为“未来知识调度算法 FKS”。当然在本例中，由于作业１和２在空闲时间处于等 待状态，它们的等待时间会增加。 FKS:6.86 ((2-1)+(6-0.4)+(14-0))/3=6.86 9. 解： ①执行情况的 Gantt 图如下所示： FCFS: 1(10) 2(1) 3(2) 4(1) 5(5) RR: 1 2 3 4 5 1 3 5 1 5 1 5 1 5 1 SJF: 2 4 3 5 1 Priority: 2 5 1 3 4 ②与这些作业相对应的周转时间如下： 作业 FCFS RR SJF Priority 1 10 19 19 16 2 11 2 1 1 3 13 7 4 18 4 14 4 2 19 5 19 14 9 1 ③与这些作业相对应的等待时间如下： 作业 FCFS RR SJF Priority 1 0 9 9 6 2 10 1 0 0
35211164313118594214（注：等待时间指作业在就绪队列中等待所花费的时间，但有些书等待时间指的是进程从进入就绪队列到获得CPU时所经历的时间，这样对于RR的等待时间就有两种不同的答案。)④SJF具有最小平均等待时间。10.解：（1）执行情况如下：P2 P1P5P3P44036526062平均等待时间W=(4+0+52+60+(36-16))/5=27.2(ms)平均周转时间T=(36+4+60+62+(52-16))/5=39.6(ms)平均带权周转时间T=8.575(ms)(2）执行情况如下：553 546P2P1P5P3P4P1320416404262平均等待时间W=(（4+38)+0+32+40+0)/5=22.8(ms)平均周转时间T=(62+4+40+42+(32-16))/5=32.8(ms)平均带权周转时间T=5.99(ms)（分析：当进程P5于相对时刻16ms进入就绪队列时，因其优先数小于现行进程P1的优先数，故进程剥夺，同时P1因连续执行了12ms而优先数被加1：在P5和P3相继执行完后，P4因已连续等待40mS，故其优先数被减1，此时P4的优先数小于P1的优先数，于是P4先于P1执行。）11.解：（1)3道程序顺序执行时最短需要32+8+5+21+14+35+12+32+15=174（s)。(2)3道程序并发执行最短需要21+14+35+15+5=90（s）。2135A14IncOut1232:4BIncOut3285ccInOut
3 11 5 2 16 4 13 3 1 18 5 14 9 4 2 （注：等待时间指作业在就绪队列中等待所花费的时间，但有些书等待时间指的是进程 从进入就绪队列到获得 CPU 时所经历的时间，这样对于 RR 的等待时间就有两种不同的答 案。） ④SJF 具有最小平均等待时间。 10. 解：⑴ 执行情况如下： P2 P1 P5 P3 P4 0 4 36 52 60 62 平均等待时间 W=(4+0+52+60+(36-16))/5=27.2(ms) 平均周转时间 T=(36+4+60+62+(52-16))/5=39.6(ms) 平均带权周转时间 T’=8.575(ms) ⑵ 执行情况如下： 3 5 4 5 5 6 P2 P1 P5 P3 P4 P1 0 4 16 32 40 42 62 平均等待时间 W=((4+38)+0+32+40+0)/5=22.8(ms) 平均周转时间 T=(62+4+40+42+(32-16))/5=32.8(ms) 平均带权周转时间 T’=5.99(ms) (分析：当进程 P5 于相对时刻 16ms 进入就绪队列时，因其优先数小于现行进程 P1 的优先 数，故进程剥夺，同时 P1 因连续执行了 12ms 而优先数被加 1；在 P5 和 P3 相继执行完后， P4 因己连续等待 40ms，故其优先数被减 1，此时 P4 的优先数小于 P1 的优先数，于是 P4 先于 P1 执行。) 11. 解：⑴3道程序顺序执行时最短需要 32+8+5+21+14+35+12+32+15=174（s）。 ⑵3 道程序并发执行最短需要 21+14+35+15+5=90（s）。 32 32 8 In C Out A 21 14 35 5 In C Out C In C Out B 12 32 15