搜索
应用题一、处理机调度1.假定在单CPU条件下有下列要执行的作业：作业运行时间优先级1102243335作业到来的时间是按作业编号顺序进行的（即后面的作业依次比前一个作业迟到一个时间单位）（1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。（2）对于上述算法，求各个作业的周转时间、带权周转时间？并求出平均周转时间以及平均带权周转时间是多少？答：（1）作业1作业3作业21111418（2）周转时间：作业1：10作业2：16作业3：11平均周转时间：（10＋16＋11）/3＝37/3带权周转时间：作业1：1作业2：4作业3：11/3平均带权周转时间：26/9上述题目也可这样求：132作业运行时间开始执行时间结束时间周转时间带权周转时间1101111013311141111/3241418164平均周转时间为：（10+11+16）/3=37/3=12.3平均带权周转时间为：(1+11/3+4)/3=26/9=2.89若将该题改为短作业优先（非抢占式）结果一样。2.假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：作业进入系统时间估计运行时间/分钟18:004028:203038:301249:001859:105(1)如果应用先来先服务的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408:008:404028:20308:409:105038:30129:109:225249:00189:229:404059:1059:409:4535作业平均周转时间T=43.4（分钟）（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。作业进入系统时间估计运行时间/分钟开始时间结束时间周转时间/分钟18:00408:008:404028:20308:529:226238:30128:408:522249:00189:279:454559:1059:229:2717作业平均周转时间T=37.2（分钟）实际执行序列为：132543.有4个进程P1、P2、P3、P4，它们进入系统的时刻和要求的运行时间如下表所示：进程进入时刻要求运行时间P10.0003P21.0016P34.0014P46.0012（1）画图分别说明，系统采用先来先服务和短进程优先调度算法（非抢占式）时，它们的执行情况。（2）分别计算上述两种情况下进程的平均周转时间和平均带权周转时间。解：(1)FCFS：进程进入时刻要求运行时间开始时间完成时间周转时间带权周转时间P10.00030.0003.00031P21.00163.0009.0007.9997.999/6P34.00149.00013.0008.9998.999/4P46.001213.00015.0008.9998.999/2SPF:进程进入时刻要求运行时间开始时间完成时间周转时间带权周转时间P10.00030.0003.00031P21.00163.0009.0007.9997.999/6P46.00129.00011.0004.9994.999/2P34.001411.00015.00010.99910.999/4(2)平均周转时间为：FCFS（3+7.999+8.999+8.999）/4=28.997/4=7.25SPF:（3+7.999+4.999+10.999）/4=26.997/4=6.7平均带权周转时间：FCFS（1+7.999/6+8.999/4+8.999/2）/4=9/4=2.25SPF:（1+7.999/6+4.999/2+10.999/4）/4=5.25/4=1.34.设有5个进程P1、P2、P3、P4和P5；它们到达时间和要求服务时间如下表（单位为ms），求非抢占方式下，采用SPF调度算法时：（1）写出进程调度顺序（2）计算平均带权周转时间进程：P1P2P3P4P5到达相对时刻：035913要求服务时间：761082答：（1）进程P1P2P5P4P3到达时刻031395服务时间762810开始时刻07131523完成时刻713152333周转时间71021428带权周转110/6114/828/10所以实际的调度序列是P1、P2、P5、P4、P3（2）平均带权周转时间为：（1+10/6+1+14/8+28/10）/5=493/60/5=1.64二、银行家算法1.假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在t0时刻的资源分配情况如下表所示。MaxAllocationneedavailable进程R1R2R3R1R2R3R1R2R3R1R2R3P1322100222112P2613511102资源情况P3314211103P4422002420试问：（1）t0时刻是否安全？（2）P2发出请求向量request2（1,0,1），系统能否将资源分配给它？（3）在P2申请资源后，若P1发出请求向量request1（1,0,1），系统能否将资源分配给它？（4）在P1申请资源后，若P3发出请求向量request3（0,0,1），系统能否将资源分配给它？答案：（1）调用安全性算法进程资源Work+AlloAllocationNeedFinishR1R2R3R1R2R3R1R2R3P2623511102TRUEP1723100222TRUEP3934211103TRUEP4936002420TRUE在t0时刻存在一个安全序列{P2，P1，P3，P4}，故系统是安全的。（2）当P2发出请求request2（1,0,1），因为request2（1,0,1）need2(1,0,2)，并且request2（1,0,1）available(1,1,2),所以进行假分配，修改：Allocation=（5,1,1）+（1,0,1）=（6,1,2）Need=（1,0,2）-（1,0,1）=（0,0,1）Available=（1，1,2）-（1,0,1）=（0,1,1）调用安全性算法：进程资源Work+AlloAllocationNeedFinishR1R2R3R1R2R3R1R2R3P2623612001TRUEP1723100222TRUEP3934211103TRUEP4936002420TRUE可以找到一个安全序列{P2，P1，P3，P4}，故系统是安全的，可以将P2所申请的资源分配给它。（3）当P1发出请求request1（1,0,1），因为request1（1,0,1）need1（2,2,2），但是request1（1,0,1）并不小于等于available，因此暂时不能分配，P1阻塞（4）若P3发出请求向量request3（0,0,1），因为request3（0,0,1）need3(1,0,3),request3（0,0,1）available(0,1,1),所以进行假分配，修改：Allocation=（2,1,1）+（0,0,1）=（2,1,2）Need=（1,0,3）-（0,0,1）=（1,0,2）Available=（0,1,1）-（0,0,1）=（0,1,0）调用安全性算法：work=（0,1,0），不能满足任何进程的最大需求，因此此前的假分配将被撤销，进程P3阻塞2.设系统中有三类资源（A，B，C）和5个进程（P1，P2，P3，P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20，T0时刻的系统状态见下表进程最大资源需求量ABC已分配资源数量ABCP1P2P3P4P55595364011425424212402405204314（1）T0时刻是否为安全状态？若是，请给出安全序列？（2）在T0时刻若进程P2请求资源（0，3，4），是否能实施资源分配，为什么（3）在（2）的基础上，若进程P4请求资源（2，0，1），是否能实施资源分配，为什么？（4）在（3）的基础上，若进程P1请求资源（0，2，0），是否能实施资源分配，为什么？3.假设系统中有5个进程（P0，P1，P2，P3，P4）和三种类型的资源（A，B，C），全部资源的数量为（35,16,32）；在T0时刻的资源分配情况如下表：ProcessMaxAllocationNeedABCABCABCP01595605990P1797315482P211810957233P3889805084P417611812959（1）（6分）试问T0时刻状态是否安全？若安全，给出一个安全序列；否则说明不安全的原因。答：Available=（35，16，32）-（34，7，24）=（1，9，8）则Work=（1，9，8）WorkNeedAlloWork+Allo完成情况P31980848059913TP0991399060515918TT0时刻是安全的，安全序列为：{P3，P0，P1，P2，P4}说明：P3一定作为序列中的第一个，其它顺序任意（2）（8分）如果进程P1提出请求Request（1,0,1）后，系统能否将资源分配给P1？答：当P1提出请求Request（1，0，1）时，首先调用银行家算法进行检查：(1)Request（1，0，1）Need(4,8,2)(2)Request(1,0,1)Available(1,9,8)(3)进行假分配，修改：Available=（1，9，8）-（1，0，1）=（0，9，7）Need=（4，8，2）-（1，0，1）=（3，8，1）Allocation=（3，1，5）+（1，0，1）=（4，1，6）（4）调用安全性算法此时Work=（0，9，7）WorkNeedAlloWork+Allo完成情况P30970848058912TP18912381416121018T121018因为能找到安全序列：{P3，P1，P2，P4，P0}，所以可以将Request（1，0，1）分配给P1说明：P3必须是第一位，第二位可以是P1或P2，不能是P0和P4三、分页和分段存储管理1.一个由3个页面(页号为0、1、2)，每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下：逻辑页号主存块号041721请根据页表，计算下列给出的逻辑地址对应的绝对地址。(1)100(2)2617(3)5196答：首先根据逻辑地址查页表，得到主存的块号，再根据公式绝对地址=块号×块长+页内地址进行计算。（1）100的页号为0（100/2048=0），页内地址为100mod2048=100；查表得主存块号为4，于是绝对地址=4×2048+100=8292；（2）2617的页号为1（2617/2048=1），页内地址为2617mod2048=569；查表得主存块号为7，于是绝对地址=7×2048+569=14905；（3）5196的页号为2（5196/2048=2），页内地址为5196mod2048=1100；查表得主存块号为1，于是绝对地址=1×2048+1100=3148；（注：mod为取模运算，即求余数）2.在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问：（1）逻辑地址084B（H）对应的物理地址是多少？（用十六进制表示）答：084B（H）对应的二进制为0000100001001011，因为每页大小为1K，即二进制数低址部分的10位是页内偏移，高址部分为页号，可得页号为2，查找页表，找到对应的块号为4，转换成二进制即为：0001000001001011，对应的16进制数为：104B（H）（2）逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示）答：5000除以1024得页号为4，页内偏移为904。查找页表得对应的块号为12，所以5000对应的物理地址为：12×1024+904=13192（3）当该用户进程欲访问24A0（H）单元时，会出现什么现象？答：通过前面的方法得出页号为9，大于页表的长度，因此产生越界中断页号块号03172