106009-13-南大计算机系-软件学院本科历年考题及参考答案-5-操作系统(2006-12月)

1、计算机科学与技术系操作系统期终测验参考答案（2006年12月）一、解释题（共14分，每个2分）简述下列概念，及联系或区别：1. 并发与并行；2. 对换与切换；3. 管道与通道；4. 死锁与饥饿；5. 文件目录与目录文件；6. DAC 与 MAC；7. 集中分布资源管理与完全分布资源管理。答：1.若干个事件或活动在同一时刻发生称为并行；若干个事件或活动在同一 时间间隔内发生称为并发。并行是并发的特例，并发是并行的拓展。2. 对换是把内存中暂时不能运行的进程或暂时不用的程序和数据，换出到 外存上，腾出足够的内存空间，把已具备运行条件的进程或进程所需的程序和数 据换入内存。切换是指将CPU的使用权从

2、一个进程转到另一个进程。在某些系统 中，进程切换往往伴随着进程的对换。3. 管道是连接两个进程的共享文件，进程通过对该文件的读.写实现进程 间的通信。通道是实现I/O操作的硬件装置（I/O处理机）。通道对管道的实现提 供硬件支持。4. 死锁是因进程竞争资源或推进顺序不当而有可能造成的一种僵局，即系 统中两个或多个进程无限期地等待永远不会发生的条件，这些进程都不能向前推 进，称之为死锁。“饥饿”是指系统中的每个资源占用者都在有限的时间内释放它所占用的资 源，但是仍然存在申请者永远得不到资源的现象。饥饿未必死锁，死锁一定饥饿。 因此，在操作系统中，不仅要考虑防止“死锁S还要考虑避免“饥饿5. 文件

3、H录是文件和目录的列表，一种按名存取文件的工具，录文件是全 部山描述文件属性的FCB、即II录项所组成的系统文件。LI录文件是文件LI录的 物理存储。6. DAC是资源属主可以按照自已的意愿指定系统中的其他用户对其资源的 访问权限的一类访问约束机制。MAC用于将系统中的信息分密级和范畴进行管 理，保证每个用户只能够访问那些被标明能够山他访问的信息的一种访问约束机 制。MAC比DAC有更强的安全手段和设施，使用户不能通过意外事件和有意的误 操作逃避安全控制。7. 集中分布资源管理指一类资源有多个管理者，但每个具体资源仅有一个管 理者对其负责的资源管理方式。完全分布资源管理指每个资源山位于不同结点

4、上 的资源管理者共同来管，某个资源管理者在决定分配它管理的资源以前，必须和 其他资源管理者协商，要所有资源管理者一致同意后才能分配资源。主要区别在 于对一个具体资源的管理者有一个，还是多个。二、问答题（共12分，每个3分）1试从资源管理的角度，分析操作系统的角色和功能。答：I）资源管理是操作系统的重要任务之一，操作系统是能使诸用戸有效、方便地共享一 套计算机系统资源的一种系统软件2）资源指能分配给用户使用的硬件和软件设施的总称，资源管理包括处理机管理、存 储管理、设备管理、文件管理以及网络与通信管理等3）对资源进行抽象研究，找出各种资源共性和个性，有序地管理计算机中的硬件、软 件资源，跟踪资源

5、使用情况，监视资源的状态，满足用户对资源的需求，协调各程序对资源 的使用冲突：研究使用资源的统一方法，让用户简单、有效的使用资源，最大限度地实现各 类资源的共享，提髙资源利用率，从而，使得计算机系统的效率有很大提高。2内存利用率不高的原因有:1）内存中存在大量的.分散的.难以利用的碎 片；2） 一批暂时或长期不用的程序和数据占据了内存空间；3）当作业较大时 内存只能装入少量的作业，当大作业被阻塞时容易使CPU空闲，从而也降低了 内存的利用率；4）内存中存在着重复的拷贝。试针对每一种原因采用方法和途 径来提高内存利用率。答：可采用下列方法和途径来提高内存利用率：（1）采用移动技术，集中碎片供作业

6、使用；更好的方法是改连续分配方式 为离散分配，如分页管理，以减少内存的碎片；（2）增加对换机制，将暂时或长期不用的程序和数据从内存对换到外存；（3）采用虚拟存储管理技术和动态装入及链接机制，使更多的作业能装入 内存，使CPU更加忙碌；（4）引入存储共享机制，允许一个正文段或数据段被若干个进程共享，以 减少内存中的重复拷贝。3试讨论中断及异常。答：中断是指来自处理器和主存储器之外的信号引起的中断，乂叫外中断。包 括：电源故障中断、时钟中断、控制台中断、它机中断和I/O中断等。每个不同 的中断具有不同的中断优先级，在处理高一级中断时，往往会屏蔽部分或全部低 级中断。异常是指来自处理器和主存内部的中

7、断信号引起的中断，乂叫内中断。包括: 通路校验错、主存奇偶错、非法操作码、地址越界、页面失效、调试指令、访管 中断、算术操作溢出等各种程序性中断。其中访管中断是山机器指令提供的特殊 指令，该指令执行时将会引起内中断。异常是不能被屏蔽4.试讨论作业.进程和线程之间的关系。，答：（1）作业是用户向计算机提交计算的任务实体，而进程则是完成用户任务 的执行实体，它是向系统申请资源并负责保护资源的基本单位，其执行任务交给 它的组成部分一线程完成。（2）一个作业可以由多个进程组成，且必须至少由一个进程组成。（3）作业的概念主要用在批处理系统中，而进程/线程的概念则用在所有的 多道系统中。三、计算题（共3+

8、3+3分）1现有三个同时到达的作业JI, J2, J3,其执行时间分别为：Tl, T2, T3,且 TlT2T3o系统单道方式运行且釆用短作业优先算法，试计算作业的平均周转 时间和带权平均周转时间。答：平均用转时间 T= （ 3T1+2T2+T3/3 ,带权平均用转时间 =W=（T 1/T1+（T1 +T2）/T2+（T 1 +T2+T3）/T3）/3 二 1 +（T 1 /T2+T1 /T3+T2/T3）/3 2.假定磁盘每个磁道有11个扇区，一个扇区正好存放文件F的一个逻辑记录。 设文件F有11个逻辑记录(记为RO, R2, -R10),存放同一磁道上。磁盘驱 动器的转速为44ms/周,处

9、理程序每读一个记录信息要花费4ms时间进行处理。 为顺序处理文件F的全部记录，在磁道上如何安装F的记录，对它的处理效率 才最高？答：RO R1 R2 R3 R4 R5 R6 R7 R8 R9 R10若记录顺序存放，当读出R0后，接着处理花4ms,由于转速为4ms每个记 录。故磁头己到达了 R2的位置，为了顺序处理R1,不得不转过一圈。为此，如 下安装记录，处理效率最高，RO R6 R1 R7 R2 R8 R3 R9 R4 RIO R53.假定某页式虚拟存储器，内存平均访问时间为1微秒.辅存平均访问时间 为10亳秒，试问如果希望虚存的平均访问时间仅比内存增加10%,则需要页面 失效率是多少？解：

10、设页面失效率为f,则虚存的平均访问时间为：(l-f)Xl 微秒+fX(10 亳秒+2 微秒)二 1 -f+10002f= l + 10001f如果希望虚存的平均访问时间仅比内存增加10%,也就是：l + 10%=l + 10001fl.l = l + 10001f 0.1=10001f解得fW0l/10001 = l/100010即要求每访问10万零10次，才允许缺页中断一次。四、综合5+8分)1在银行家算法中，若出现下述4类资源的分配情况。AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656

11、试问：(1)该状态是否安全？(2)如果进程P2提出请求Request! (1, 2, 2, 2)后，系统能否将资源分配给它？答:安全，可找岀安全序列POF3,P1,P4,P2。(2)不可以。2.有一个具有3道作业的多道批处理系统，作业调度采用短作业优先的调度 算法，进程调度釆用以优先数为基础的抢占式调度算法，在下表所示的作业序 列，作业优先数即为进程优先数，优先数越小优先级越高。作业名到达时间估计运行时间优先数A10： 0040分5B10： 2030分3C10： 3060分4D10： 5020分6E11： 0020分4F11： 1010分4试填充下列表格:作业进入内存时间运行结束时间作业周转时

12、间ABC D EF平均作业周转时间=答：每个作业运行将经过两个阶段：作业调度（SJF算法）和进程调度（优先数抢占式）。另 外，内存同时最多容纳3道作业，更多的作业将在后备队列等待。作业进入内存时间运行结朿时间作业周转时间A10:0012:40160分B10:2010;5030分C10:3011:5080分D10:5013:00130分E12:0012:2080分F11:5012:0050分平均作业周转时间=(160+30+80+130+80+50)/6=88.3五、编程题（11 + 11分）1过独木桥问题：有一座独木桥，两边的汽车串行过桥，但当另一 方提出过桥时，对方应阻止未上桥面的后继车辆，

13、待其已在桥面上的 汽车过完后，另一方汽车开始过桥，试用信号量和PV操作求解过桥 问题。解：stop用于当另一方提出过桥时，应阻止对方未上桥面的后继车2.设自行车生产线上有一只箱子，其中有N个位置（N为3的倍数，且工3）, 每个位置可存放一个车架或一个车轮。设有三个工人，其活动如下：worker 1的活动worker2的活动worker3的活动Ll：加工一个车架；L2：加工一个车轮：L3：在箱中取一个车架车架放入箱中：车轮放入箱中：在箱中取二个车轮；goto Ll：goto L2：组装为一台自行车；goto L3；试用管程实现这三个工人的合作生产活动（只需写出管程部分）O解：用HOARE方法。将

14、箱子的n个空间一分为2,分别装车架和车轮。 Type producebicycle=monitorVar boxl:array0.n/3-l of 车架；box2:array0.2n/3-l of 车轮；Sl,S2,S3:condition;Sl_count,S2_count,S3_counmt:integer;count 1 ,count2:=0:integer;in 1 ,in2,out 1 ,out2:integer;in 1 :=in2:=outl :=out2:=0;produre worker 1beginLl：加工一个车架；var stop,wait,mutex 1 ,mutex

15、2:semaphore; stop:=mutex 1 :=mutex2:= 1 ;wait:=O; counter l,counter2:=0:integer;process P左边汽车beginP(stop);P(mutexl); count 1+;if count 1 = 1 then P(wait);V(mutexl);V(stop);过桥；P(mutexl);Count 1-if count 1=0 then V(wait); V(mutexl);endprocess P右边汽车 begin p(stop); P(mutex2); count2+;if count2=l then P(

16、wait): V(mutex2); V(stop);过桥； P(mutex2); count2;if count2=0 then V(wait); V(mutex2);endif countl=n/3 then wait(Sl, Sl_countJM)车架放入box 1 (ini); inl:=(inl + l) mod n/3 count 1+;signal(S3, S3_countJM); go to LI;process worker2beginL2：加工一个车轮；if count2=2n/3 then wait(S2,S2_countJM)车轮放入box2(in2); in2:=(in2+l) mod 2n/3; count2+;if couin2/2=0 then signal(S3,S3_countJM)go to L2;end;process worker3beginL