2009操作系统试卷答案-王雅琴

山东农业大学课程考试专用注：考试期间试卷不允许拆开。第1页共5页2009-2010学年第1学期《操作系统》答案及评分标准A（课程代码：BF003002）考试方式闭卷考试时长100分钟一、单项选择（每题1分，共30分）BBCDBBDDABBBCACAADDBBBBACACCCC二、简答题（每题5分，共20分）1.使用位示图（20行、30列）表示空闲盘块状态。当分配的盘块号为132号时，其在位示图中的行、列数为（行为0-19、列为0-29，首盘块号为1）多少？答：行号i=(132-1)/30=4，(3分)列号j=(132-1)mod30=11（2分）2.在操作系统中引入线程概念的主要目的是什么？设进程A拥有1个用户级线程，进程B拥有100个用户级线程，则在系统调度时各占用几个时间片？设进程A拥有1个内核级线程，进程B拥有100个内核级线程，则在系统调度时各占用几个时间片？答：在操作系统中引入线程概念的主要目的是减少程序并发执行时所需付出的时空开销，提高程序执行的并发程度；（2分）A、B均占用1个时间片；（2分）A:1个时间片；B:100个时间片。（1分）3.在实时系统中，采用不可抢占处理机的优先数调度算法是否适宜?为什么?答：不适宜。（2分）因为：一旦一个低优先数、需要大量CPU时间的进程占用处理机，就会一直运行，直到运行结束，或者直到因某事件而阻塞。在此之前，即使高优先数的紧急任务到达，也得不到处理，因而可能延误对重要事件的响应和处理。（3分）4.对于如下存储管理方式来说，进程地址空间各是几维的？（1）页式；（2）段式；（3）段页式答：（1）页式存储管理中，进程地址空间是一维的；（1分）（2）段式存储管理中，进程地址空间是二维的；（2分）（3）段页式存储管理中，进程地址空间是二维的。（2分）三、综合应用题（共50分）1、（8分）假设一个活动头磁盘有200道，编号1-199,当前磁头正在143道上服务，并且刚刚完成了125道的请求，现有如下访盘请求序列（磁道号）山东农业大学课程考试专用注：考试期间试卷不允许拆开。第2页共5页86，147，91，177，94，150，102，175，130试给出采用下列算法后磁头移动的顺序和移动总量（总磁道数）(1)最短寻道时间优先(SSTF)磁盘调度算法(2)扫描法（SCAN）磁盘调度算法（假设沿磁头移动方向不再有访问请求，磁头沿相反方向移动）答：1)SSTF的移动顺序:143147150130102949186175177(2分)移动总量=4+3+20+28+8+3+5+89+2=162(2分)2)SCAN的移动顺序:143147150175177130102949186(2分)移动总量=4+3+25+2+47+28+8+3+5=125(2分)2、（8分）假定某磁盘的旋转速度是每圈20毫秒，格式化时每个盘面被分成10个扇区，现有10个逻辑记录A、B、C、D、E、F、G、H、I．J存放在同一磁道的各扇区中，具体安排如下：扇区号逻辑记录1A2B3C4D5E6F7G8H9I10J处理程序要顺序读出并处理这些记录，每读出一个记录后处理程序要花4毫秒的时间进行处理，然后再顺序读下一个记录并处理，直到处理完这些记录。假设第一个记录A已在磁头位置下，请回答：（1）顺序处理完这10个逻辑记录总共需花费多少时间？（2）请重新安排这10个逻辑记录，使处理程序能在最短时间内处理完这10个逻辑记录，并计算需花费的最短时间。答：（1）由于每读出一个记录并对它进行处理后磁盘已转过了两个记录的位置，故需等待16毫秒的时间下一个记录才能到达磁头位置下，因而除第一个逻辑记录外，对其余每个逻辑记录都要增加16毫秒的等待时间，即处理完这10个逻辑记录所花的总时间为：（2＋4）＋（16＋2＋4）*9=204（毫秒）(4分)山东农业大学课程考试专用注：考试期间试卷不允许拆开。第3页共5页（2）重新安排这10个逻辑记录，使得处理程序读出一个记录并处理结束时正好使下一个记录能旋转到磁头位置下,那么，处理程序不必等待。处理程序每读出一个记录并处理后就能立即读出下一个记录来处理，这样，处理这10个逻辑记录花费的时间最短。10个逻辑记录的安排可如下调整：扇区号逻辑记录扇区号逻辑记录1A6F2H7C3E8J4B9G5I10D读出并处理完这10个逻辑记录所需时间为：（2＋4）*10=60（毫秒）(4分)3、（6分）在分页存储管理系统中，逻辑地址的长度为16位，页面大小为4K，且第0、1、2页依此存放在物理块5、10、11中，现有一逻辑地址为2F6AH，问相应的物理地址是多少？答：由题目所给条件可知，逻辑地址结构如下图所示，页号占4位，页表长度为24=16。页号为2，没有越界。（3分）据题意第2页存放在11物理块中，块号为B，所以，物理地址为BF6AH。（3分）4、（8分）某请求分页存储管理系统中，设页面走向为1，2，3，1，2，3，2，1，2，5，4，2，5，主存容量为3页。试求：分别采用LRU（最近最久未使用）、FIFO(先进先出)、Optimal（最优）3种页面替换算法时的缺页次数。答：LRU算法：缺页5次（3分）FIFO算法：缺页6次（3分）Optimal算法：:缺页5次（2分）5、（8分）在系统中仅有m个同类资源，由n个进程互斥访问。如果每个进程对该类资源的最大需求量为w,那么当m,n,w分别取下表所列值时，问在表中(a)～(e)的各种情况下，哪种可能发生死锁？为什么？页号页内位移1512110001021111F011061010A0010页号111101101010页内位移山东农业大学课程考试专用注：考试期间试卷不允许拆开。第4页共5页(a)(b)(c)(d)(e)m22244n12233w21223答：c,e可能死锁！（4分）因为，对于情况c,当2个进程分别获得一个资源并想请求另一个资源时，系统已无剩余，从而造成死锁；对于情况e,当3个进程各获得1个资源时，系统只剩余1个资源，不能满足任何一个进程的最大需求，根据银行家算法可知，此时系统进入不安全状态，因此可能导致死锁。（4分）6、（12分）设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮;又设有三个工人，其活动分别为:工人1活动：do{加工一个车架;车架放入箱中;}while(1)工人2活动：do{加工一个车轮;车轮放入箱中;}while(1)工人3活动：do{箱中取一车架;箱中取二车轮;组装为一台车;}while(1)试采用信号量实现三个工人的合作，要求解中不含死锁。解答：定义三个信号量如下：semaphoreempty=N;//空位置semaphorewheel=0;//车轮数semaphoreframe=0;//车架数（2分）为防止死锁的发生，箱中车架的数量不可超过N-2，车轮的数量不可超过N-1，这些限制可以用两个信号量来表达。semaphores1=N-2;semaphores2=N-1;（2分）山东农业大学课程考试专用注：考试期间试卷不允许拆开。第5页共5页为此，可以给出不含死锁的完整解法如下：工人1活动：do{加工一个车架;wait(s1);wait(empty);车架放入箱中;signal(frame);}while(1)（2分）工人2活动：do{加工一个车轮;wait(s2);wait(empty);车轮放入箱中;signal(wheel);}while(1)（2分）工人3活动：do{wait(frame);箱中取一车架;signal(empty);signal(s1);wait(wheel);wait(wheel);箱中取二车轮;signal(empty);signal(empty);signal(s2);signal(s2);组装为一台车;}while(1)（4分）