操作系统期末复习题

2023年12月2日发(作者：)

操作系统期末复习题一．银行家算法类例题1：在银行家算法中，某T0时刻的资源分配情况如下：（有三类资源A、B、C，五个进程P0、P1、P2、P3、P4）Max Allocation Need AvailableA B C A B C A B C A B CP0 7 5 3 0 1 0 7 4 3 3 3 2P1 3 2 2 2 0 0 1 2 2P2 9 0 2 3 0 2 6 0 0P3 2 2 2 2 1 1 0 1 1P4 4 3 3 0 0 2 4 3 1试问：1.该状态是否安全？答：这是安全状态：P1的需求小于可用资源数，先满足P1的请求，然后回收P1资源：可用资源变为（3,3,2）＋（2,0,0）＝（5,3,2）；这时P3可分配，P3结束后回收资源，可用资源为（5,3,2）＋（2,1,1）＝（7,4,3）这时P0可分配，P0结束后回收资源，可用资源为（7,4,3）＋（0,1,0）＋（7,5,3）接下来是P2，结束后可用资源为（7,5,3）＋（3,0,2）＝（10,5,5）最后分配P4，结束后可用资源为（10,5,5）＋（0,0,2）＝（10,5,7）这样得到一个安全序列：P1－P3－P0－P2－P4，所以T0状态是安全的。2.在T0时刻，P1发出请求Request(1，1，2)，系统能否满足？为什么？答：T0时刻P1请求（1,1,2）<可用资源数（3,3,2），可以直接满足。例题2：某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。系统对这四类资源的拥有量为:A类3个、B类14个、C类12个、D类12个。进程对资源的需求和分配情况如下：进程已占有资源最大需求数A B C D A B C DP1 0 0 1 2 0 0 1 2P2 1 0 0 0 1 7 5 0P3 1 3 5 4 2 3 5 6P4 0 6 3 2 0 6 5 2P5 0 0 1 4 0 6 5 6按银行家算法回答下列问题：（1）现在系统中的各类资源还剩余多少答：剩余：A:1 B:5 C:2 D:0因为P1已经满足最大需求数，则P1资源最终是可回收，则可看做剩余：A:1 B:5 C3 D:2（2）现在系统是否处于安全状态？为什么答：是安全状态；因为按照剩余：A:1 B:5 C3 D:2（此时P1已经结束）分别按照顺序满足各进程的最大需求是可以把全部进程完成的（顺序可为：P3 --> P4 --> P5 --> p2）（3）如果现在进程P2提出需要A类资源0个、B类资源4个、C类资源2个和D类资源0个，系统能否去满足它的请求？请说明原因系统会去满足；若此时去满足，则剩余资源为：A:1 B:1 C1 D:2此时，各进程的状态：已占有资源最大需求数A B C D A B C DP1 0 0 0 0 0 0 1 2 （已结束）P2 1 4 2 0 1 7 5 0P3 1 3 5 4 2 3 5 6P4 0 6 3 2 0 6 5 2P5 0 0 1 4 0 6 5 6按照各进程状态以及剩余资源，可以知道之后P3，即可回收已分配的资源，即处安全状态二．磁道算法类1. 先来先服务（FCFS，First Come First Servered）这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。图示有9个进程先后提出磁盘I/O请求时，FCFS算法进行调度的情况，其平均寻道距离较大，故FCFS算法仅适用于请求磁盘I/O的进程数目较少的场合。2. 最短寻道时间优先（SSTF,Shortest Seek Time First）该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次寻道的时间最短。但这种算法不能保证平均寻道时间最短。可能导致一些请求无限期推延，产生饥饿现象。3.电梯调度算法SCAN：不仅考虑当前磁道的距离，更优先考虑在磁道前进方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动，排除磁头在盘面上的往复运动，避免了出现“饥饿”现象。CAN将进程分成N个队列，用FCFS算法处理每一个队列，而这堆队列则是SCAN算法的处理对象。FCFS（处理每个队列）SCAN（处理总体）FCFS（处理每个队列）FCFS（处理每个队列）将进程分成两个队列，一个是正在处理的，用SCAN算法处理。另一个是摆放新请求的进程，留待完成正在处理的队列后执行。例题：设有三道作业，它们的提交时间及执行时间由下表给出:作业号提交时间执行时间1 8.5 2.02 9.2 1.63 9.4 0.5试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间(时间单位:小时，以十进制进行计算；要求写出计算过程)（10分）FCFS: 作业号提交时间执行时间开始时间完成时间周转时间1 8.5 2.0 8.5 10.5 2.02 9.2 1.6 10.5 12.1 2.93 9.4 0.5 12.1 12.6 3.2平均周转时间=(2.0+2.9+3.2)/3=2.7(小时)SJF: 作业号提交时间执行时间开始时间完成时间周转时间1 8.5 2.0 8.5 10.5 2.02 9.2 1.6 11.0 12.6 3.43 9.4 0.5 10.5 11.0 1.6平均周转时间=(2.0+3.4+1.6)/3=2.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总的移动的磁道数是三．信号量实现前趋图类Var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbegin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c); signal(d); end;begin wait(b); S3; signal(e); end;begin wait(c); S4; signal(f); end;begin wait(d); S5; signal(g); end;begin wait(e); wait(f); waite(g); S6; end;parendend四．信号量生产者消费者. 假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）；（2）指出算法中所用信号量的名称、作用及初值。解S1:阅览室可供使用的空座位，其初值为50S: 是否可通过阅览室，其初值为1Process READ_in（i=1…50）{到达阅览室入口处;P(S1);P(S);在入口处登记座位号;V(s);进入座位并阅读;}Process READ_out（j=1…50）{结束阅读到达阅览室入口处;P(S);在入口处注销座位号;V(S1);V(S);离开入口处;}五．页面置换算法1.最佳置换算法淘汰标准是下次访问时间越远越优先淘汰。例：假定系统为某进程分配三个物理块，并考虑有以下页号引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7 , 0 , 1其置换图如下(PS:箭头表示该页进入内存)2. 先进先出(FIFO)页面置换算法该算法优先淘汰最先进入内存的页面。2, 0,3. 最近最久未使用(LRU)置换算法该算法利用“最近的过去”作为“最近的将来”的近似，优先淘汰长时间 未被使用的页面，要求有两类硬件之一的支持：寄存器和栈，以记录时间7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 4 4 4 0 1 1 1 * 0 0 0 0 0 0 3 3 3 0 0 * * 1 1 3 3 2 2 2 2 2 7Clock 置换算法为每页设置一位访问位，再将内存中的所有页面1。置换算法在选择一页淘汰时，只需检查页的访问位。如果0，就选择该页换出；如果是1，则重新将它置0，暂不换出，而再按照FIFO 算法检查下一个页面。1，则返回队首置换算法1类（A=0,M=0）：最近既未被访问，又未被修改，最佳淘汰页； 2类（A=0,M=1）：最近未被访问，但已被修改，不是很好的淘汰页； 3类（A=1,M=0）：最近已被访问，但未被修改，该页有可能再被访问； 4类（A=1,M=1）：最近已被访问且修改过，可能再被访问。6. 最少使用(LFU)置换算法7. 页面缓冲(PBA)置换算法六．逻辑地址到物理地址的转换计算例题：某虚拟存储器的用户编程空间共32个页面，每页为1KB ，内存为16KB 。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。 解题过程：首先要知道页式存储管理的逻辑地址分为两部分：页号和页内地址。物理地址分为两部分：关系为：逻辑地址＝ 页号＋页内地址物理地址＝块号＋页内地址；分析题：已知：用户编程空间共３２个页面，２?５＝３２得知页号部分占５位，由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，２^４＝１６得知块号占4位。逻辑地址0A5C（H）所对应的二进制表示形式是：００００１０１００１０１１１００，后十位１００１０１１１００是页内地址，０００１０为为页号，页号化为十进制是２，在对照表中找到２对应的物理块号是１１,１１转换二进制是１０１１，即可求出物理地址为１０１１１００１０１１１００，化成十六进制为２Ｅ５Ｃ；即则逻辑地址0A5C(H)所对应的物理地址是２Ｅ５Ｃ；例题：分页存储管理系统中逻辑地址长度为16位，页面大小为4KB，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，求相应物理地址。Step1:逻辑地址2F6AH转二进制16位0010 1111 0110 10102 F 6 A HStep2:由于页面大小为4KB(∵4KB=4*1KB,4=22,1KB=2^10,∴4KB=2^12)所以逻辑地址的后12位为“页内地址”(又叫“偏移量”，“页内位移”)Step3:∵后12位为页内地址∴前4位是页号0010 1111 0110 10102号页页内地址Step4: 页号物理块号0 5110211由于页号为2，所以物理块号为11。Step5:∴物理地址为物理块号页内地址(11B)1011 1111 0110 1010 即BF6AH。例题：七．关于作业调度及进程调度的周转时间、带权周转时间的计算例题：设有三道作业，它们的提交时间及执行时间由下表给出:作业号提交时间执行时间1 8.5 2.02 9.2 1.63 9.4 0.5试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间(时间单位:小时，以十进制进行计算；要求写出计算过程)（10分）FCFS: 作业号提交时间执行时间开始时间完成时间周转时间1 8.5 2.0 8.5 10.5 2.02 9.2 1.6 10.5 12.1 2.93 9.4 0.5 12.1 12.6 3.2平均周转时间=(2.0+2.9+3.2)/3=2.7(小时)SJF: 作业号提交时间执行时间开始时间完成时间周转时间1 8.5 2.0 8.5 10.5 2.02 9.2 1.6 11.0 12.6 3.43 9.4 0.5 10.5 11.0 1.6平均周转时间=(2.0+3.4+1.6)/3=2.3(小时)