操作系统试卷B

2010-20111学期考试试题卷

简单目录C.

二级目录.带交叉勾链的树型目录课程名称

《操作系统》 任课教师签名

9.文件系统的主要目的是 。出题教师签名

审题教师签名

实现虚拟存储题号四五六总分得分评卷人题号四五六总分得分评卷人一、单项选择题（220分）1在一个计算机系统中，特权指令（ ）下执行。A.只能在管态 B. 只能在用户态C.可在管态，也可在用户态 . 不能在管态，也不能在用户态实时操作系统必需在 内完成来自外部的事件。A.响应时间 B.周转时间 C.规则时间 .调度时间最适合分时系统的进程调度算法是 （） 。A.FCFSB.SSJFC. 优先数法 .轮转法进程从运行状态进入就绪状态的原因可能是 。A.被选中占有处理机 B.等待某一事C.等待的事件已发生.时间片用完设有五个进程共享一个互斥段 ，在同一时间最多允许一个进程进入互斥段 ，则所采用的互斥信号量初值应该是 。A.5 B.2 C.1 .0银行家算法在解决死锁问题中是用于的。A.预防死锁 B. 避免死锁 C. 检测死锁 .解除死锁在下列存储管理方案中不适应于多道程序设计的是 。A.单一连续分配 B.固定式分区分配C.可变式分区分配 . 段页式存储管理UNIX文件的目录结构采用 。

C.提高外存的读写速度 . 用于存储系统文件10.下列算法中用于磁盘移臂调度的是。A时间片轮转法 B丄RU 算法C.最短寻找时间优先算法.优先级高者优先算法（210分）1.采用多道程序设计的系统中系统的程序道数越多，2时间片越小系统的响应时间就越小系统的效率就越高。程序的并且发执行是指同一时刻有两个以上的程序 ，它们的指令在同一处理器上行。按最先适应算法分配的分区一定与作业要求的容量大小最接近。（210分）为实现CPU与外部设备的并且行工作，系统引入了 硬件机制。UNIX系统采用 结构存放文件物理块的地址。文件的符号名与物理地址的转换是经过 实现的。用户编程时使用 地址处理机执行程序时使用 地址。采用资源有序分配算法可以 死锁的发生。（520分）请介绍在文件存储空间的管理中几种常用的技术。为什么要引入SPOOLing系统SPOOLing系统可带来哪些好处？进程和线程的主要区别是什么？4产生死锁有四个必要条件？（40分）在一个飞机订票系统中多个用户共享一个数据库。多用户同时查询是可以接受的指但若一个用户要订票需更新数据库时 ，其余用户都不可以访问数据库。请画出用户查询与订票的逻辑框图。要求 ：当一个用户订票而需要更新数据库时 ，不能因有查询者的到来而使他长期等待。 (15分) 为一切的空闲文件建立一个单独的目录表。每个表目关于应一个空闲文件

，记录该空闲文件的起始块号和块数。空闲文件的分配与回收算法与内存管理中的可变式分区管理的方法相似，同样可以采用最先适应算法、最佳适应算法、最坏适应算法等。在一个请求分页存储管理系

闲块的分配与回收等。下面是三种在文件存储空间的管理中常用的技术 ：统中，一个程序的页面走向为

4,试诀别求出采用FCFS和LRU页面置(要求给出页面置换的进程)。(15分)4、3、2、1、4、3、5、

空闲文件目录。一个空闲文件是由文件存储器上连续的空闲块组成的。系统空闲块链。空闲块链把文件存储设备上的一切空闲块链接在一起。当申请者需要空闲块时分配程序从链首取下所需的空闲块 ，然后调整链首指针。反之当回收4、3、2、1、5,设分配给该程序的存储块数为换算法时，发生缺页中断的次数和缺页中断率磁盘请求的柱面按 10,22,20,2,40,6,38 的次序到达磁盘的驱器寻道时每个柱面移动需要6ms计算按以下算法调度时的寻道时间 ：(1)先来先服务；(2)下一个最邻近的柱面；(3)电梯算法。假设以上一切情况磁头臂均起始于柱面 20,并且刚刚完成了19号柱面的请求。(10分)操作系统试卷B 答案、单项选择题(每空2分，共20分)12345678910ACCBAAC1.错2.关于1.错2.关于3.错4.错[5?错三、填空题(5*2分)中断和通道索引文件目录逻辑物理预防四、简答题(4*5分)1.由于文件存储设备是分成若干个大小相等的物理块 ，并且以块为单位来交换信息的 ，此文件存储空间的管理实质上是空闲块的组织和管理问题 ，它囊括空闲块的组织、空

空闲块时，把释放的空闲块逐个插入空闲链上。这种方法的优点是分配和回收一个空闲块的进程都非常简单，缺陷是空闲块链可能很长。改进的办法是采用空闲盘区链接法或成组链接法。(3)位示图。位示图利用一个二进制位来记载一个物理块的使用情况。系统为每个文件存储设备建立一张位示图反映文件存储设备一切物理块的使用情况。每个物理块关于应位示图上的一位，如果该位为0,则表示所关于应的块是空闲的反之，则表示所关于应的块已分配。利用位图来进行空闲块分配时 ，只需查找图中为0的位并且将其置1;反之回收时只需把相应的位由10。由于位示图很小可以将它保存在内存中。2.一切字符设备都是独享设备并且属于慢速设备 ，本质上属于顺序存取设备。因此，一个程在某台字符设各上进行数据交换时 ，往往要等待较长时间并且且在该数据交换完成之前其他进程不能同时访问这台设备。而且动态分配也不能真正提高这类设备的利用率当个进程正在使用这类设备进行一次较大量的数据交换时 ，其他需要同时访问该设备的进程就要等待较长的时间，从而降低了整个系统的并且发能力。 SPOOLing术正是针关于上述问题提出的一种设备管理技术。SPOOLing系统可带来的好处如下：字符设备和各虚拟设备之间的数据交换由 SPOOLing进程统一调度实施而这种数据交换以并且行方式进行系统呈现出高度的并且行性：用户使用的是虚拟设备可以减少用户进程的等待时间。在多道程序系统中，用程序模拟脱机输入输出时外围控制机的功能，这样便可在主机的直接控制下实现脱机输入/输出功能。此时的外围操作与CPU关于数据的处理同时进行这种在联机情下实现的外围设备同时操作称为 SPOOLing,也称伪脱机。SPOOLing系统的核心思想是利用一台可共享、 高速、大容量的块设备磁盘)来模拟独占设备的操作，使一台独占设备变成多台可并且行使用的虚拟设备。 SPOOLing系统主要由输入井和输出井、输入缓冲区和输出缓冲区、输入进程和输出进程三部分组成。它的处是提高了I/O操作的速度，将独占设备改造为共享设备，实现了虚拟设备的功能。3.进程和线程是构造操作系统的两个基本元素 ，两者之间的主要区别是：调度方面线程作为调度分派的基本单位。并且发性方面进程之间可以并且发执行。拥有资源方面进程是拥有资源的基本单位本上不拥有资源，到进程环境的切换

，线程除少量必不可少的资源外 ，系统开销进程间切换时要涉及，开销比较大：而线程间切换

H4-t-{y.P(S) P(S)只需保存和设置少量的寄存器内容系统开销。4.

，因此进程间切换的系统开销远大于线程间切换的,在一段时间内一个资源仅能被互斥控制。进程关于所要求的资源进行排它控制一个进程使用。

,不能被其它进程剥夺。即使该不可剥夺控制。进程所获得的资源在未释放前 ,只有等待占有该资源的进程进程处于阻塞态，它所占资源也不能被其它进程使用放后才能给别的进程使用。请求和保持。为了提高资源利用率 ，进程在运行进程中可随时提出关于各种资的请求当进程因请求资源而阻塞时关于已获得的资源保持不放。环路等待条件。在发生死锁时进程的资源状态图必构成环路即前一进程保存着后一进程所要求的资源。五、计算(40分)1.(15分)本题是典范的读者一写者问题。查询操作是读者 ，订票操作是写者而且要求写优先。为了达到这一控制效果可以引入一个变量 rc，用于记录当前正在运行的读者进程数。每个读者进程进入系统后需关于 rc值加1。当rc值由O变为1时说明是第一个时刻123456789101112页面走向432143543215M=44+3+2+1+115+4+3+2+1+5+读者进程进入因此需要该读者进程关于控制写者进程的信号量 Srw进行P操作，以便与写者进程互斥运行：当rc值由非0值增加时说明不是第一个读者进程此时控制写者进程的信号量已经过P操作控制禁止写者进程进入因此不需要再次关于该信号量进行 P操作。当读者进程退出时需关于rc做减1时刻123456789101112页面走向432143543215M=44+3+2+1+115+4+3+2+1+5+

2. (15分)

用户查询与订票的逻辑框图进行互斥访问控制。为了提高写者的优先级 ，我们还增加了一个信号量 S,用以在写程到达时封锁其后续的读者进程。用户查询与订票的逻辑框图如图所示。查询者

FCFS算法的页面置换如下:33321543244④③②①⑤④3+++++++43422434222154321标志+++4+3②4+3②1+11⑤④标志+++++3+时刻123456789101112页面走向432143543215M=44+3+2+1+435+432+1+5+4 32143543214321435432缺页次数F=8,缺页中断率8/12=67%3. (10分)该题的解题方法是先计算出每种算法的柱面移动总量。因为每个柱面移动需要所以,寻道时间=柱面移动总量x6ms

6ms,(1)先到先服务算法的调度顺序为

：10,22,20,2,40,6,38柱面移