操作系统复习应用题.docVIP

1．若程序A和B单独执行时分别需要1小时和1.5小时，其中CPU工作时间分别为18分钟和27分钟。若采用多道程序设计方法，让A和B并行工作，假定CPU利用率达到50％，另加15分钟系统开销，请问系统效率能提高多少? 解：在多道系统中，程序A和B共用的CPU时间为：(18十27)／50％＝90分钟 系统效率提高＝(A和B单独执行的时间总和－多道方式下总时间)／A和B单独执行的时间总和，即((60十90)－(90十15))／(60十90)＝45／150＝30％ 1. 假定在单CPU条件下有下列要执行的作业： 作业 运行时间 优先级 1 10 2 2 4 3 3 3 0 作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。 (1)用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。 (2)对于上述算法，各个作业的周转时间是多少?平均周转时间是多少? (3)对于上述算法，各个作业的带权周转时间是多少?平均带权周转时间是多少? 解： (1)非抢占式优先级算法作业的执行情况如下： 作业 到达时间 运行时间 完成时间 周转时间 带权周转时间 1 0 10 10 10 1.0 2 1 4 17 16 4.0 3 2 3 13 11 3.7 平均周转时间 12.3 平均带权周转时间 2.9 2．若在后备作业队列中等待运行的同时有三个作业1、2、3，已知它们各自的运行时间为 a、b、c，且满足关系a＜b＜c，试证明采用短作业优先调度算法能获得最小平均周转时间。 证明：由于短作业优先调度算法总是在后备作业队列中选择运行时间最短的作业作为调 度对象，因此对短作业优先调度算法而言，这三个作业的总周转时间为 T1=a+(a+b)+(a+b+c)=3a+2b+c …… (1) 若不按短作业优先调度算法来调度这三个作业，不失一般性，假定调度顺序为2、l、3，则其周转时间为 T2=b+(b+a)+(b+a+c)=3b+2a+c …… (2) 由(1)、(2)两式可得：T2-T1=b-a0 由此可见，短作业优先调度算法能获得最小平均周转时间。 3．设有4道作业，它们的提交时间及执行时间如下： 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。(时间单位：小时，以十进制进行计算。) 解：若采用先来先服务调度算法，则其调度顺序为1、2、3、4。 平均周转时间 T=(2.0十2.8十3.1十3.3)/4＝2.8 平均带权周转时间W=(1十2.8十6.2十11)／4=5.25 若采用短作业优先调度算法，则其调度顺序为1、4、3、2 平均周转时间为 T=(2.0+1.8+2.4+3.6)/4=2.45 平均带权周转时间 W=(1十6十4.8十3.6)/4=3.85 4．假设有四个作业，它们的提交、运行时间如下表所示。若采用高响应比优先调度算法，试问平均周转时间和平均带权周转时间为多少？ (时间单位小时，以十进制进行计算。) 解：根据响应比的定义每次调度前计算出各作业的响应比，得到四个作业的调度次序为：作业1、作业3、作业2、作业4。 平均周转时间为 T=(2.0十2.3十1.6十2.O)/4=1.975 平均带权周转时间W=(1十4.6十16十5)/4=6.65 5．有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采 用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先 数，且优先数越小优先级越高。 (1)列出所有作业进入内存时间及结束时间 (2)计算平均周转时间。 分析: 在本题中，每个作业的运行将经历两级调度：作业调度和进程调度。作业调度采用短作业优先调度算法，进程调度采用基于优先数的抢占式调度算法，高优先级的进程可以抢占系统处理机。只有当作业调度程序将作业装入内存后，方能参与进程调度。本题中的批处理系统是两道作业系统，因此每次只能有两道作业进入系统内存。本题中的作业和进程推进顺序如下： 10：00时，A作业到达。因系统的后备作业队列中没有其他作业，进程就绪队列中也没有进程，故作业调度程序将作业A调入内存并将它排在就绪队列上，进程调度程序调度它运行。 10：20时，B作业到达。因系统的后备作业队列中没有其他作业，故作业调度程序将作业B调入内存并将它排在就绪队列上。而作业B的优先级高于作业A的优先级，进程调度程序停止作业A的运行，将作业A放入就绪队列，调度作业B运行。此时，系统中已有两道作业在内存中运行，作业A已运行20分钟，还需运行20分钟才能完成。 10：30时，C作业到达。因系统中已有两道作业在内存中运行，故作业C只能在后备作业队列中等待作业调