任命大学答案

1、操作系统2016年07月考试考前练习题一、综合应用题1. 某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用，水缸可容纳10桶水，水取自同一口井，水井径窄，每次只能容一个桶取水，水桶总数为3个，每 次入水取水仅为1桶水，且不可同时进行，试给岀有关从缸取水、入水的算法描述。2, 设A、B两个具有完成截止期限的周期性实时任务的执行轮廓如下表所示，请画岀采用以下调度算法进行调度的进程运行图：(1)固定优先级调度(A优先)；(2)固定优先级调度(B优先)；(3)最早完成截止时间调度。进程到达时间执行时间结束截止时间A (1)01020A (2)201040A (3)401060A (4

2、)601080A (5)8010100*B (1)02550B (2)5025100*3. 为什么要在操作系统中引入进程的概念？引入进程的概念会对系统产生怎样的影响？4. 设有四个作业 JI、J2、J3、J4，它们的到达时间和计算时间见下表，若这四个作业在一台处理器上按单道方式运行，采用最高响应比优先调度算法，试写岀各作业的执行顺序、各作业的周转时间及平均周转时间。作业至u达时间计算时间J18:002hJ28:3040minJ39:0025minJ49:3030min5. 有三个进程 P1、P2和P3并发工作，进程 P1需要资源S3和S1,进程P2需要资源S2和 S1,进程P3需要资源S3和S

3、2,问：(1) 若对资源分配不加限制，会发生什么情况？为什么？(2) 为保证进程正常运行，应采用怎样的分配策略？列岀所有可能的方法。6. 在单处理器系统中，如果用户级线程与内核级线程间是一对一的映射，那么，多线程程序比相同功能的单线程程序运行快，为什么？7. 请说明Linux系统中的进程状态中的不可中断(uninterruptible)状态的含义和用途。8. 若从存取速度、存储空间利用、易更新性的角度考虑文件系统的有效性，针对以下各种情形，什么样的文件组织的有效性最好：(1) 数据更新不频繁，按随机次序频繁存取；(2) 数据频繁更新，比较频繁地存取整个文件；(3) 数据频繁更新，按随机次序频繁

4、存取。9. 设一个层次式文件系统以空闲空间链表的方式管理空闲磁盘空间，请考虑：假如指向空闲空间的指针丢失，系统能否重构空闲空间链表？(2)试设计一个方案，确保单个内存故障不会导致指针丢失。10. 设某系统中既有就绪进程也有就绪/挂起进程，且至少有一个就绪/挂起进程的优先级比所有就绪进程都高，有两种极端的调度策略：(1)为减少交换，总是选择就绪进程运行；总是选择最高优先级的进程运行，哪怕引起不必要的交换。请你给出一种既考虑优先级也考虑性能的折中策略。11. 设A、B、C、D、E五个进程的到达时间和服务时间如下表所示，请分别画岀用循环调度算法(RR, q=l)、最短剩余时间优先算法(SRT)、最高

5、响应比优先算法(HRRN)进行调度的进程运行图。进程至U达时间服务时间A03B26C44D65E82附：参考答案1. 某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用，水缸可容纳10桶水，水取自同一口井，水井径窄，每次只能容一个桶取水，水桶总数为3个，每 次入水取水仅为1桶水，且不可同时进行，试给岀有关从缸取水、入水的算法描述。解答：从井中取水并放入水缸是一个连续的动作可以视为一个进程，从缸中取水为另一个进程。设水井和水缸为临界资源，引入well、vat;三个水桶无论从井中取水还是放入水缸中都是一次一个，应该给它们一个信号量 pail,抢不到水桶的进程只好等待。水缸满时，不可

6、能再放水，设置empty信号量控制入水量；水缸空时，不可以取水，设置full信号量来控制。本 题需要设置5个信号量来控制：semaphore well=l;用于互斥地访问水井semaphore vat=l;用于互斥地访问水缸用于表示水缸中剩余空间能容纳的水的桶数表示水缸中的水的桶数表示有多少个水桶可以用，初值为3semaphore empty=10;semaphore full=O;semaphore pail=3;/老和尚while(l)(P(full);P(pail);P(vat);从水缸中打一桶水；V(vat);V(empty);喝水；V(pail);/小和尚while(l)(p(emp

7、ty);P(pail);p(well);从井中打一桶水；V(well);p(vat);将水倒入水缸中；V(vat);V(full);V(pail);2, 设A、B两个具有完成截止期限的周期性实时任务的执行轮廓如下表所示，请画岀采 用以下调度算法进行调度的进程运行图：(1) 固定优先级调度(A优先)；(2) 固定优先级调度(B优先)；(3) 最早完成截止时间调度。进程到达时间执行时间结束截止时间A (1)01020A (2)201040A (3)401060A (4)601080A (5)8010100*B (1)02550B5025100*解答:BldeadlineB2deadlineA4 A

8、5deadline deadlineArrival times, executionAIA2A3A4I'limes, and deadlinesB1B2A! A2 A3 deadlinedeadlinedeadlinee ID串 30 J)申 中 7()申 90Time (ms)Fixed-priority scheduling;A has priorityAlIi1A2 Bl A3IIiIAM1 I'A5JB21I! (missed) !<!.| Al | Bl A2 | Bl A3 B2 A4 | B2 A5 |B2|i I I:- I j | aIBl j | 们A

9、3 B2 | KAl A2 Bl A3 j A4 ! A5, B2Fixed-priority scheduling; B has priorityEarliest-dead line schedulingusing completion deadlines3. 为什么要在操作系统中引入进程的概念？引入进程的概念会对系统产生怎样的影响？解答：在操作系统中引入进程的概念，是为了实现多个程序的并发执行。传统的程序不能与其他程序并发执行，只有在为其创建进程后才能与其他程序（进程）并发执行。这是因为并发执行的程序（即进程）是“走走停停”地执行的，只有在为其创建进程后，在停下时才能将其现场信息保存在它的

10、PCB中，等下次被调度时再从 PCB中恢复CPU现场并继续执行，而传统 的程序 无法满足上述要求。建立进程所带来的好处是使多个程序能并发执行，这极大地提高了资源利用率和系统吞吐量。但管理进程也需要付岀一定代价，包括PCB以及协调各运行机构所占用的内存空间开销，以及为进行进程间切换、同步和通信等所付出的时间开销。4. 设有四个作业Jl、J2、J3、J4,它们的到达时间和计算时间见下表，若这四个作业在一台处理器上按单道方式运行，采用最高响应比优先调度算法，试写岀各作业的执行顺序、各作业的周转时间及平均周转时间。作业到达时间计算时间J18:002hJ28:3040minJ39:0025min解答：作

11、业的响应比可表示为等待时间+要求服务时间响应比=要求服务时间在8:00时刻，系统中只有一个作业J1,故系统将它投入运行。在J1完成（即10： 00）时，J2、J3、J4 的响应比分别为：（90+40） /40, （ 60+25） 125, （ 30+30） /30,即 3.25、3.4、 2, 故应先将J3投入运行。在 J3完成（即10： 25）时，J2、J4的响应比分别为（115+40） /40、（55+30）/30,即3.875、2.83，故应先将J2投入运行，待它运行完毕时（即 11: 05）,再将J4投 入运行，J4的结束时间为11 ： 35 0可见作业的执行次序为JI、J3、J2、J

12、4,各作业的运行情况见下表，它们的周转时间分另V为120min> 155min> 85min> 125min, 平均周转时间为121.25min。作业号提交时间开始时间执行时间结束时间周转时间18 :008:002h10:00120 min28 :3010:2540 min11 :05155 min39 :0010:0025 min10:2585 min49 :3011 :0530 min11 :35125 min5, 有三个进程 PI、P2和P3并发工作，进程 P1需要资源S3和S1进程P2需要资源S2和 S1,进程P3需要资源S3和S2,问：（1）若对资源分配不加限制，会

13、发生什么情况？为什么？（2）为保证进程正常运行，应采用怎样的分配策略？列岀所有可能的方法。解答：1） 可能会发生死锁。满足发生死锁的四大条件，例：P1占有S1申请S3, P2占有S2申请 SI, P3占有S3申请S2。2）可有以下几种答案：A. 采用静态分配：由于执行前已获得所需的全部资源，故不会岀现占有资源又等待别的资源的现象（或不会岀现循环等待的现象）。B. 采用按序分配：不会岀现循环等待的现象。C. 采用银行家算法：因为在分配时，保证了系统处于安全状态。6, 在单处理器系统中，如果用户级线程与内核级线程间是一对一的映射，那么，多线程程序比相同功能的单线程程序运行快，为什么？解答：问题的关

14、键在于 CPU是否要等待I/O操作。在内核级多线程的进程中，当一个内核级线程调用引起阻塞的系统调用时，其他内核级线程可以继续运行，在单处理器系统中，单线程进程调用此类系统调用时，该进程将被阻塞，但是，内核级多线程的进程可以继续执行。7, 请说明Linux系统中的进程状态中的不可中断（uninterruptible ）状态的含义和用途。解答：与可中断状态类似，不可中断状态也是一种阻塞状态，两者的区别是：在不可中断状态，进程直接等待硬件条件的发生，因而不处理任何信号。不可中断状态用于进程必须不受中断地等待的场合，或者，预期事件会很快发生的场合。例如，当一个进程打开一个设备文件而相应的设备驱动程序开

15、始探测相应的硬件设备时，进程进入不可中断状态，因为在探测完成之前驱动程序不能被中断，否则，硬件设备很可能会被置于意想不到的状态。8. 若从存取速度、存储空间利用、易更新性的角度考虑文件系统的有效性，针对以下各种情形，什么样的文件组织的有效性最好：（ 1） 数据更新不频繁，按随机次序频繁存取；（ 2） 数据频繁更新，比较频繁地存取整个文件；（ 3） 数据频繁更新，按随机次序频繁存取。 解答：（ 1） 索引文件（ 2） 索引顺序文件（ 3） 散列或索引文件9. 设一个层次式文件系统以空闲空间链表的方式管理空闲磁盘空间，请考虑：（ 1） 假如指向空闲空间的指针丢失，系统能否重构空闲空间链表？（ 2）

16、 试设计一个方案，确保单个内存故障不会导致指针丢失。解答：（ 1 ） 可以重构。首先，建立一个位图（bitmap ） , 用于表示磁盘中的每一个盘块，初值置为全 0; 然后，从文件系统的根目录（即目录）开始对整个文件系统进行遍历，把每个文件占用的每个盘块在位图中对应的位置标记为1;遍历结束后，位图中0 对应的块便是空闲 块，可以为它们重新构建链表。（ 2） 在磁盘上一处或多处保存空闲空间链接指针的副本，指针更新时，同时更新相应 副本，这样，就算内存和磁盘块出现故障，也有办法借助副本获得有效的指针值。10. 设某系统中既有就绪进程也有就绪 / 挂起进程，且至少有一个就绪 / 挂起进程的优先 级比所有就绪进程都高，有两种极端的调度策略：（1）为减少交换，总是选择就绪进程运行;（ 2）总是选择最高优先级的进程运行，哪怕引起不必要的交换。请你给出一种既考虑优先级也考虑性能的折中策略。解答：以降低 N 个优先级（如 N=2 或 3）的方式看待就绪 / 挂起进程，只有当就绪 /挂起进程的优