第三章练习题及答案doc资料

1、学习-好资料第三章练习题及答案1. 在单道环境下，某批处理有四道作业，已知它们进入系统的时刻、估计运行时间如下:作业进入时刻（h）运行时间（h）18.002.0028.500.5039.000.1049.500.20设系统每次只选择一个作业进入主机，分别给出在FCFS,SJF,HRNf法中这组作业的运行顺序、平均周转时间和平均带权周转时间。2. 为什么说多级反馈队列能较好地满足各种用户的需要？3. 有一个多道程序系统，有用户空间100KB,并规定作业相应程序装入内存连续区域，并不能被移动，作业调度和进程调度均采用FCFSI法。现有一批作业，已知条件如下：作业名进入输入井时间需计算时间（分）需内

2、存量（KB）A8:064215B8:183060C8:302450D8:362410E8:421220假定所有作业都是计算型作业并且忽略系统调度所化的时间。计算各作业被选中装入内存的时间、开始执行的时间、结束执行的时间、周转时间和带权周转时间。4. 上例中，其他假设条件不变，仅把作业的调度算法改为按 SF算法，进程仍采用FCFSI法。5. 作业调度的性能评价标准有哪些？这些性能评价在任何情况下都能反映调度策略的优 劣吗？6. 什么叫无限期圭寸锁（indefinite blocking） ?它在什么情况下出现？7. 作业调度算法选择作业的原则，可以是保证系统的吞吐量大、可以是对用户公平合理、可以

3、是充分发挥系统资源的利用率。请分别指出先来先服务、最短作业优先、I/O量大与CPI量大的作业搭配3种调度算法，体现了那种选择作业的原则？8. 假定待处理的三个作业的到达时间和运行时间如下，若采用调度算法、，这些 作业的平均周转时间是多少？作业名到达时间（时）执行时间10.0820.4431.01 FCFS: SJF; 考虑一下如何改善 SJF的性能，并计算新方法的平均周转时间?9.假定要在一台处理机上执行下列作业:作业执行时间优先级1103211323414552且假定这些作业达到的次序是1，2，3，4，5。给出Gantt图来说明分别使用 FCFS, RR（时间片=1），SJF以及非抢占优先调

4、度算法时 这些作业的执行情况；（注：Gantt图是描述进程/作业执行情况的一种直观形式，它展 示了作业/进程执行过程中瞬时段或时间片的变化分布情况。）针对上述每一调度算法，给出每个作业的周转时间；就上述每一调度算法，求出每个作业相应的等待时间；10. 设有5个就绪进程，它们的本次 CPU周期的长度、初始优先数及进入就绪队列的相对时刻 如下所示：进程CPU 周期(ms)优先数进入时刻（ms）P13250P2430P3850P4260P516416规定：小的优先数表示高的优先级。画出下列两种情况的Gantt图，计算它们的平均等待时间、平均周转时间和平均带权周转时间。非剥夺的静态设置方式；剥夺式的动

5、态设置方式，不妨设现行进程每连续执行12ms后，其优先数加 1 （即优先级降低），而就绪进程每 40ms后，其优先数减1。11. 有3道作业构成如下，它们在一个系统中运行，该系统有输入/输出设备各一台。A进程：输入32s,计算8s,输出5sB进程：输入21s，计算14s，输出35sC进程：输入12s，计算32s，输出15s问3道程序顺序执行时最短需要多少时间？为了充分发挥各设备效能，3道程序并发执行最短需要多少时间？（不计系统开销时间）12. 在一个实时系统中，有两个周期性实时任务A和 B,任务A要求每40 ms执行一次，执行时间为20 ms ;任务B要求每100ms执行一次，执行时间为 50

6、 ms。请参考课堂相关知识画出在200mS寸间内，任务A和B调度情况示意图。并标出任务 A和B每一次执行的时间。习题解答：1.解：下面我们用一张表帮助理解作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.0010.502.004.0039.000.1010.5010.601.6016.0049.500.2010.6010.801.306.50平均周转时间T=1.725(h) 平均带权周转时间 T'=6.875(h)6.9027.50FCFS算法的调度顺序为：1宀2宀3 t 4。作业进入时刻运行时间开始时刻完成

7、时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周转时间T=1.55(h) 平均带权周转时间T'=5.15(h)6.2020.60SJF算法的调度顺序为：1 t 3 t 4t 2。作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.1010.602.104.2039.000.1010.0010.101.1011.0049.

8、500.2010.6010.801.306.50平均周转时间T=1.625(h) 平均带权周转时间 T'=5.675(h)6.5022.70HRNI法的调度顺序为：1 t 3 t 2t 4。2.答：多级反馈队列是综合了 FCFS RR HPF三种算法的一种剥夺式的调度算法，它根据 进程运行情况的反馈信息动态地改变进程的优先级，按优先级级别组织设置各就绪队 列，并规定各就绪队列不同的 CPU寸间片，对同一队列中的各就绪进程按FCFS或RF算法调度，因而能较好地满足各种用户的需要。3. 解:作业名装入内存开始执行结束执行周转(分)带权周转A8:068:068:4842(1)42/42B8:

9、188:489:1860(2)60/30D8:369:189:4266(2.75)66/24C9:189:4210:0696(4)96/24E9:1810:0610:1896(8)96/125个作业的平均周转时间和带权周转时间为：T=72(分)，T'3.554. 解：作业名装入内存开始执行结束执行周转(分)带权周转A8:068:068:4842(1)42/42B8:188:489:1860(2)60/30D8:369:189:4266(2.75)66/24E9:189:429:5472(4)72/24C9:189:5410:18108(8)108/125个作业的平均周转时间和带权周转时

10、间为：T=69.6(分)，T'3.255. 答：对于批处理系统主要以作业的平均周转时间或平均带权周转时间来衡量调度策略的优劣；而对于分时系统，除了要保证系统的吞吐量大、资源利用率高之外，还应保证用户能容忍的响应时间；实时系统的主要标志则是满足用户要求的时限(截止)时间。6. 答:无限期封锁也叫饥饿(starvation),即一个具有低优先级的进程决无运行的机会。当CPU接连不断地被较高优先级的作业占用时就可能出现这样的情况。7. 答：系统的吞吐量大是最短作业优先算法，因为SJF使作业的平均周转时间有明显的改善，从而使系统在单位时间内处理的作业数增多。对用户公平合理是先来先服务算法。因为

11、对用户按照作业进入输入井时间的先后调度，先来先服务，对每个用户都是公平的。发挥系统资源的利用率是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

12、-1)+(6-0.4)+(14-0)/3=6.869. 解：执行情况的Gantt图如下所示：FCFS:1(10)2(1)3(2)4(1)5(5)RR:123451351515151SJF:24351Priority:25134与这些作业相对应的周转时间如下:作业FCFSRRSJFPriority110191916211211313741841442195191491与这些作业相对应的等待时间如下:作业FCFSRRSJFPriority1099621010031152164133118514942(注：等待时间指作业在就绪队列中等待所花费的时间，但有些书等待时间指的是进程 从进入就绪队列到获得

13、CPU时所经历的时间，这样对于 RR的等待时间就有两种不同的答 案。) SJF具有最小平均等待时间。10.解:执行情况如下：P2P1P5P3P40436526062平均等待时间 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)执行情况如下：354556P2P1P5P3P4P1041632404262平均等待时间 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+