操作系统综合题

1．若在一个单道批处理系统中4个作业（J1，J2，J3，J4），估计它们的提交时刻和需要运行的时间如下表所示。试用SJF算法计算各作业进入主存的时间和它们的平均周转时间。作业J1进入内存时间为10：00；作业J2进入内存时间为12：30；作业J3进入内存时间为13：30；作业J4进入内存时间为12：00；平均周转时间为：(2+3+3.17+1.17)/4=2.342．一个请求分页系统中，若系统分配给一个作业的物理块数为2块，且作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数，并计算它们各自的缺页率。（假设初始作业装入时已经依次装入了页号为1和2的两个页面）(1)FIFO：（5分）23215245325212331524532552122315245322×××××××××F=9/12=75%(2)LRU：（5分）23215245325212321524532522123215245325×××××××××F=9/12=75%3．假定某移动磁盘上，处理了访问56号柱面的请求后，现在正在70号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：73,68,100,120,60,108,8，50。请写出：（1）用最短查找时间优先算法，列出响应的次序。（2）用电梯调度算法，列出响应的次序。(1)用最短查找时间优先算法，响应的次序为68、73、60、50、8、100、108、120。作业名提交时刻运行时间（小时）SJFINOUTJ110：00210：0012：00J210：30112：3013：30J310：501.513：3015：00J411：200.512：0012：30（2）用电梯调度算法，响应的次序为73、100、108、120、68、60、50、8。一、综合分析题（每题10分，共20分）1、设系统中有五个并发进程（P1，P2，P3，P4，P5）共享系统中的三类资源（R1，R2，R3），它们的资源总数量分别为（16，5，19），在T0时刻系统状态如下图所示，系统采用银行家算法实施死锁避免策略。进程最大资源需求量已分配资源数量R1R2R3R1R2R3P1559212P2536402P34011405P4425204P5324314问题1：判断在T0时刻是否处于安全状态，为什么?A＝(1,3,2)；N5=(0,1,0)A,假分配P5，A＝(4,4,6)；N2=(1,3,4)A，假分配P2，A＝(8,4,8)；N1=(3,4,7)A，假分配P1，A＝(10,5,10)；N3=(0,0,6)A，假分配P3，A＝(14,5,15)；N4=(2,2,1)A，假分配P4，A＝(16,5,19).故T0状态是安全状态。问题2：在T0时刻若进程P2提出（1，0，1）的资源请求，是否实施分配？为什么？A＝(1,3,2)；R2=(1,0,1)A，假分配，A＝(0,3,1)，U2=(5,0,3)；N5=(0,1,0)A，假分配P5，A＝(3,4,5)；N2=(0,3,3)A，假分配P2，A＝(8,4,8)；N1=(3,4,7)A，假分配P1，A＝(10,5,10)；N3=(0,0,6)A，假分配P3，A＝(14,5,15)；N4=(2,2,1)A，假分配P4，A＝(16,5,19).实施分配，因为是安全的。2、有一只最多能装2只兔子的铁笼子，猎人仅能向笼子中放入兔子（每次只能放入1只），若笼子是满的，则猎人必须等待；饭店老板仅能从笼子中取兔子（每次只能取出1只），若笼子是空的则他也必须等待。假设初始时笼子是空的。定义信号量并初始化，使用P、V操作模拟猎人和饭店老板进程之间的同步与互斥。得分评分人mutex,empty,fullsemaphore;1分mutex=1,empty=2;full=0;2分以下内容7分cobeginpcocedureHunter(x)begin：P（empty）；P（mutex）；//放兔子；V（mutex）；V（full）；Gotobegin；pcocedureBoss(x)begin：P（full）；P（mutex）；//放兔子；V（mutex）；V（empty）；Gotobegin；coend;1．（10分）在分页存储管理系统中，存取一次内存的时间是6us，查询一次快表的时间是1us，缺页中断的时间是1000us，一个作业最多可保留3个页面在内存。现开始执行一进程，对进程的1、4、5、1、7、6、4、1页面上数据进行连续存取。假设页表的查询与快表的查询同时进行，快表容量是8。当查询页表时，如果该页在内存但快表中没有页表项，系统将自动把该页页表项送入快表。如分别采用FIFO、LRU和最优页面置换算法，试求：（1）每种面置换算法发生的缺页中断的次数。（2）每种面置换算法在存取上述页面序列时，存取每个页面上数据需要的时间（必须列式子）。（3）(10)分FIFOLRU.1.1:1000＋6*31:1000＋6*32.4:1000+6*34:1000＋6*33.5:1000+6*35:1000＋6*34.1:10+11:10＋15.7:1000+6*37:1000＋6*36.6:1000+6*36:1000＋6*37.4:1000+6*34:1000＋6*38.1:1000+6*31:1000＋6*37次缺页中断7次缺页中断OPT1.1:1000＋6*32.4:1000+6*33.5:1000+6*34.1:10+15.7:1000+6*36.6:1000+6*37.4:10+18.1:10+15次缺页中断3、在请求调页的动态分页系统中，一个程序的页面访问次序为：2，4，8，3，2，4，5，2，4，8，3，5。如果分配给此程序的页帧数为4，分别分析采用FIFO、LRU和OPT算法时的置换过程并计算页面缺页次数。（9分）解：请在单元格填写正确的页面号，并在发生缺页的列打勾√（每个算法3分）访问次序248324524835FIFO248333524835248883524832444835248222483524页面缺页（10）次√√√√√√√√√√访问次序248324524835LRU248324524835248324524832483245248248333524页面缺页（8）次√√√√√√√√访问次序248324524835OPT248333555533248888888552444444444222222222页面缺页（6）次√√√√√√4、有哪几种I/O控制方式？各适用于何种场合？（8分）答：1、程序I/O方式，适用于低速字节设备；2、中断方式，适用于中低速字节设备；3、DMA方式，适用于中高速块设备；4、通道方式，适用于各种类型的设备，尤其是高速块设备5、系统中有一组如右表所示的磁盘I/O请求等待服务，假设当前磁道为88，刚完成对100道的操作，分别计算先来先服务、最短寻找时间优先、电梯调度方法下的磁头移动的总道数。（9分）被访问的磁道=======901891301645解：先来先服务调度：2＋99＋59＋114＋29＝303（3分）最短寻找时间优先调度：2＋40＋59＋144＋29＝274（3分）电梯调度：43＋29＋74＋40＋59＝245（3分）1、某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号051102437则逻辑地址0A5D（H）所对应的物理地址是什么？（6分）0A5D（H）=00001010010111012号页对应4号块，所以物理地址是0001001001011101即125D（H）。2、设有三道作业，它们的提交时间及执行时间由下表给出:作业号提交时间执行时间18.52.029.21.639.40.5试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间(时间单位:小时，以十进制进行计算；要求写出计算过程)（10分）FCFS:作业号提交时间执行时间开始时间完成时间周转时间18.52.08.510.52.029.21.610.512.12.939.40.512.112.63.2平均周转时间=(2.0+2.9+3.2)/3=2.7(小时)SJF:作业号提交时间执行时间开始时间完成时间周转时间18.52.08.510.52.029.21.611.012.63.439.40.510.511.01.6平均周转时间=(2.0+3.4+1.6)/3=2.3(小时)3、假定当前磁头位于100号磁道，进程对磁道的请求序列依次为55，58，39，18，90，160，150，38，180。当采用先来先服务和最短寻道时间优先算法时，总的移动的磁道数分别是多少？（请给出寻道次序和每步移动磁道数）（8分）FCFS:服务序列依次为:55，58，39，18，90，160，150，38，180移动的磁道数分别是:45,3,19,21,72,70,10,112,142总的移动的磁道数是:494SSTF:服务序列依次为:90，58，55，39，38，18，150，160，180移动的磁道数分别是:10,32,3,16,1,20,132,10,20总的移动的磁道数是:24411．在一个请求分页系统中，有一个长度为5页的进程，假如系统为它分配3个物理块，并且此进程的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。（10分）解：FIFO：232152453252第1页222555333第2页33322255第3页1114442缺页中断次数=6LUR：232152453252第1页22225553第2页3352335第3页114422缺页中断次数=518、若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。（1）先来先服务算法；（2）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）（10分）解：（1）磁道访问顺序为：20，44，40，4，80，12，76寻道时间=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道访问顺序为：40，44，20，12，4，76，80寻道时间=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道访问顺序为：40，44，76，80，20，12，4寻道时间=（0+4+32+4+60+8+8）*3=116*3=348