操作系统 多处理机习题.docx

1. 有两个程序，程序A依次使用CPU计10s，使用设备甲计5s，使用CPU计5s，使用设备乙计10s，使用CPU计10s。 程序B依次使用设备甲计10s，使用CPU计10s，使用设备乙计5s，使用CPU计5s，使用设备乙计10s。在单道程序环境下先执行程序A再执行程序B，计算CPU的利用率是多少？在多道程序环境下，CPU的利用率是多少？解答： 单道环境下，CPU运行时间为（10+5+10）s+(10+5)s=40s,两个程序运行总时间为40s+40s=80s,故利用率是40/80=50% 多道环境下，运行情况如下图所示，CPU运行时间为40s，两个程序总时间为45s，故利用率为40/45=88.9%2. 设某计算机系统有一个CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图（可以用甘特图），并说明：（1） 开始运行后，CPU有无空闲等待？若有，在哪些时间内等待？计算CPU的利用率。（2） 进程A运行时有无等待现象？若有，在什么时候发生等待现象？（3） 进程B运行时有无等待现象？若有，在什么时候发生等待现象？进程运行情况如下：1）CPU在100-150ms时间段内空闲，利用率为250/300=83.3%2）进程A为无等待现象3）进程B为有等待现象，0-50ms， 180-200ms3. 设内存中有3道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O操作的时间见表1-1。假设3道程序使用相同设备进行I/O操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图（调度程序的执行时间忽略不计）。在两种情况下，完成3道程序分别需要多长时间（多道运行时采用抢占式调度策略）。 表1-1 程序执行情况程序操作ABC计算306020I/O操作403040计算101020单道批处理系统中，有四个作业，其有关情况如下表所示，在采用响应比高者优先调度算法时分别计算其平均周转时间T和平均带权周转时间W。作业J1J2J2J3提交时间/h8.08.68.89.0运行时间/h2.00.60.20.5答：分析响应比高者优先调度算法是指每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高的投入运行。在第8小时，因为只有作业J1到达，系统先将作业J1投入运行。作业J1运行两个小时后完成。这时三个作业都已到达，要计算三个作业的响应比，然后使响应比最高的投入运行。三个作业的响应比为：作业J2的响应比=1+（10.0-8.6）/0.6=3.33作业J3的响应比=1+（10.0-8.8）/0.2=7作业J4的响应比=1+（10.0-9.0）/0.5=3从计算的结果来看，作业J3的响应比最高，所以让作业J3先执行，作业J3执行0.2小时后完成，此时作业J2和作业J4的响应比为：作业J2的响应比=1+（10.2-8.6）/0.6=3.67作业J3的响应比=1+（10.2-9.0）/0.5=3.4从计算结果来看，作业J2的响应比最高，所以再让J2执行。可见，四个作业的执行次序为：作业J1，作业J3，作业J2，作业J4. 计算结果如下表：作业号到达时间运行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02.01.028.60.610.210.82.23.6738.80.210.010.21.4749.00.510.811.32.34.6平均周转时间为： T=（2.0+2.2+1.4+2.3）/4=1.975平均带权周转时间为： W=（1.0+3.67+7+4.6）/4=3.98假定要在一台处理机上执行下列作业：作业执行时间优先级1103211323414552且假定这些作业在时刻0以1,2,3,4,5,的顺序到达。说明分别使用FCFS、RR（时间片=1）、SJF以及非剥夺方式优先级调度算法时，这些作业的执行时间。针对上述每种调度算法，给出平均周转时间和平均带权周转时间。解答：算法时间类型P1P2P3P4P5平均时间运行时间1012153.8FCFS周转时间101113141913.4加权周转时间1116.5143.87.26RR周转时间19274149.2加权周转时间1.923.542.82.84SJF周转时间1914297加权周转时间1.91221.81.74优先级周转时间1611819612加权周转时间1.619191.26.36所以，FCFS的平均周转时间为13.4，平均加权周转时间为7.26 RR的平均周转时间为9.2，平均加权周转时间为2.84 SJF的平均周转时间为7，平均加权周转时间为1.74 非剥夺式优先级调度算法的平均周转时间为12，平均加权周转时间为6.36 结论：SJF的平均周转时间肯定是最短的，计算完毕后可以利用这个性质检验。在一个单道批处理系统中，一组作业的提交时间和运行时间如下表所示：作业提交时间运行时间（小时）18:001.028:500.5039:000.2049:100.10试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W：（1） 先来先服务（2） 短作业优先（3） 响应比高者优先解答FCFS调度算法的作业调度情况见下表作业提交时间运行时间开始时间结束时间周转时间带权周转时间18.01.08.09.01.01.028.50.59.09.51.02.039.00.29.59.70.73.549.10.19.79.80.77.0平均周转时间平均带权周转时间SJF调度算法的作业调度情况见下表：作业提交时间运行时间开始时间结束时间周转时间带权周转时间18.01.08.09.01.01.028.50.59.39.81.32.639.00.29.09.20.21.049.10.19.29.30.22.0平均周转时间平均带权周转时间响应比高者优先：8.0时只有1号作业，所以肯定是1号得到CPU，9.0时1号作业执行完毕，2号作业响应比为（9.0-8.5+0.5）/0.5=2， 3号作业响应比为（9.0-9.0+0.2）/0.2=1, 2号的响应比大于3号，9.0时调度2号作业，9.5时2号作业执行完毕，此时3号作业响应比为（9.5-9.0+0.2）/0.2=3.5， 4号作业响应比为（9.5-9.1+0.1）/0.1=5，4号的响应比大于3号，所以先调度4