国防科技大学研究生院2001年硕士生入学考试 操作系统试题
考生注意：1．答案必须写在我校统一配发的专用答题纸上 2．统考生做 一、二、三、四、五； 3．单独考生做一、二、三、六、七； 一．（58分）回答如下问题 1．（6分）假定有一个支持实时、分时和批处理的操作系统，对该系统应如何设计进程调度策略？ 2．（5分）什么叫线程？为什么要引进线程？ 3．（6分）某计算机系统设计成只有一级中断(该级中有多个中断)的中断系统，简述当中断发生时，是如何进入该中断处理程序的？ 4．（5分）在文件系统中为什么要引进“Open”系统调用？操作系统是如何处理的？ 5．(5分)假定存储器空闲块有如下结构：
请你构造一串内存请求序列，对该请求序列首次满足分配算法能满足，而最佳满足分配法则不能。
6．(6分)为什么要在设备管理中引入缓冲技术？操作系统如何实现缓冲技术？ 7．(6分)用什么办法可以破坏死锁的循环等待条件？为什么？
8．(6分)进程的状态主要有哪些？当发生状态转换时，操作系统完成哪些工作？ 9．(6分)在文件系统中，为什么要设立“当前目录”？操作系统如何实现改变“当前目录”？ 10．(7分)举例说明P、V操作为什么要用原语实现？操作系统如何实现这种原语操作？ 二．(12分)设有四个进程P1，P2，P3，P4，它们到达就绪队列的时刻，运行时间及优先级如下表所示：
问：(1)若采用可剥夺的优先级调度算法，给出各进程的调度次序以及每个进程的等待时间。 (2)若采用时间片轮转调度算法，且时间片为2个基本时间单位，试给出各进程的调度次序及平均周围时间。
三．(8分)假设系统由相同类型的m个资源组成，有 n 个进程，每个进程至少请求一个资源。证明：当n个进程最多需要的资源数之和小于m n时，该系统无死锁。
四．(12分)在页式虚存系统中，一程序的页面走向(访问串)为 1，2，3，4，1，2，5，1，2，3，4，5 ，设分配给该程序的驻留集为m，试分别计算m=3和m=4时，FIFO和LRU两种算法的页故障次数。结果说明了什么？
五．(10分)对于下述优先图，用Parbegin/Parend语句及操作系统提供的同步/互斥工具，写出并发程序。
六．(10分)假设有三个并发进程P，Q，R。其中P负责从输入设备上读入信息并传送给Q；Q将信息加工后传送给R；R则负责将信息打印输出。进程P、Q共享一个由m个缓冲区组成的缓冲池；进程Q、R共享另一个由n个缓冲区组成的缓冲池(假设缓冲区足够大，进程间每次传输信息的单位均小于等于缓冲区长度)。写出满足上述条件的并发程序。
七．(12分)在页式虚存管理系统中，什么情况下发生页故障？描述页面故障的处理过程。
国防科技大学研究生院1996年硕士生入学考试 编译原理和操作系统试题（操作系统部分）
注意：1．统考生做一、二、三、四、五、七、八、九、十、十一、十二题 2．单独考生做一、二、三、四、六、七、八、九、十、十一、十三题 3．答案只能写在答题纸上
一．选择题（在下列各小题的备选答案中，请把你认为正确答案的题号，填入题干后的括号内。多选、少选及选错不给分。每题3分，共15分） 1．分时操作系统需要使用下面哪些成份。（ ） ① 多道程序设计技术 ②作业说明书 ③ 终端命令解释程序 ④中断处理 ⑤ 优先级调度 ⑥系统调用 2．进程具有哪些特性。（ ）
①动态性 ②共享性 ③并发性 ④相互制约性 ⑤独立性 ⑥静态性
3. 在页式虚存管理系统中，若常发生抖动影响CPU的利用率，从系统管理员的角度，则下面哪些方法可改善CPU的利用率。（ ）
① 用一个更快的CPU ②用一个更大的辅存 ③减少多道程序的道数 ④ 增加多道程序的道数 ⑤增大主存 ⑥采用更快的I/O设备 4．在文件系统中，为实现文件保护一般应采用下面哪些方法。（ ）
① 口令 ② 密码 ③ 访问控制 ④ 复制 ⑤在读写文件之前使用OPEN系统调用 ⑥ 在读写文件之后使用CLOSE系统服务
5. 从资源分配角度，操作系统把外部设备分为( )
①独占型设备 ②共享型设备 ③快速型设备 ④慢速性设备 ⑤ 块设备 ⑥字符型设备 ⑦虚拟设备 二、（9分）对访问串:1,2,3,4,1,2,5,1,2,3,4,5, 指出在驻留集大小分别为3,4时，使用FIFO和LRU替换算法的页故障数。结果说明了什么？ 三．（8分）简述文件的二级目录组织形式。欲实现文件共享如何处理？ 四．（8分）假设有5道作业，它们的提交时间及运行时间由下表给出： 作业 提交时间（时） 运行时间（小时） 1 10 2 2 10．05 1
3 10．25 0．75 4 12．25 0．5 5 12．5 0．25
若采用FCFS和SJF两种调度算法，指出作业以单道串行方式运行时的被调度顺序及平均周转时间。 五．（10分）设有如下图所示的工作模型。
四个进程P0，P1,P2,P3和四个信箱M0,M1,M2,M3进程间借助相邻的信箱传递消息：
每次从 中取出一条消息，经加工送入 中。其中M0,M1,M2,M3分别设有3,3,2,2个格子，每个格子放一条消息，初始时，M0装满了三条消息，其余为空。写出使用信号量实现进程 （i=0,1,2,3）同步及互斥的流程。 六．（10分）设系统中仅有一类数量为M的独占型资源，系统中N个进程竞争该类资源，其中各进程对该类资源的最大需求量为W。当M、N、W分别取下列值时，试判断哪些情况
会发生死锁？为什么？
① M=2，N=2，W=1 ②M=3，N=2，W=2 ③M=3，N=2，W=3 ④M=5，N=3，W=2 ⑤M=6，N=3，W=3
国防科技大学研究生院1996年硕士生入学考试 编译原理和操作系统试题
操作系统部分参考答案（非标准答案） 一．选择题（每题3分，共15分） 1．（① ② ④ ⑥） 2．（① ③ ④ ⑤） 3.（③） 4．（① ② ③ ④） 5.(① ② ⑦)
二、当驻留集为3时，采用FIFO替换算法，页面故障数为9次；采用LRU替换算法时，页面故障数为10次。
当驻留集为4时，采用FIFO替换算法，页面故障数为10次；采用LRU替换算法时，页面故障数为8次。
结果表明，FIFO替换算法的故障数不随驻留集增大而减少；而LRU算法的故障数随驻留集增大而减少。 三．把记录文件的目录分成主文件目录和由其主管的若干个子目录，各子目录的位置由主目录中的一项指出。应用中常设一个主文件目录，而为系统中每一个用户设立一张主文件目录MFD，每个用户的所有文件均设立一个用户文件目录UFD，作为MFD中的一项。用以描述UFD的文件名和物理位置，即UFD是用户全部文件的文件控制块的全体。 在二级文件目录中，欲共享文件需给出一个文件的全路径名。由系统从根目录开始检索；或者用户将其当前目录指向另一用户的子目录上，以实现共享访问。 四．采用FCFS调度算法的被调度顺序为1à2à3à4à5
平均周转时间为T ＝（T1 T2 T3 T4 T5）/ 5 = (2 2.95 3.5 2 2) / 5 =2.49 (小时 ) 采用SJF调度算法的被调度顺序为1à3à5à4à2
平均周转时间为T=T1 T2 T3 T4 T5）/ 5 = (2 2.5 0.5 1.25 4.45 ) / 5 =2.14（小时） 五．定义如下公共信号量：
mutex0 ~ mutex3 : 分别用于控制互斥访问M0 ~ M 3，初值为1。 full0 ~ full3 : 分别用于控制同步访问M0 ~ M3 ,其中full0 初值为3，full1 ~ full3 初值为0，表示信箱中消息条数。
empty0 ~ empty3 : 分别用于同步控制对M0 ~ M3的访问。Empty0初值为0，empty2~ empty3初值为2，empty1初值为3，分别用于表示信箱中空格子个数。 另用send ( Mi , message )表示将消息送到（Mi mod 4）号信箱中；而用receive ( Mi，message )表示接收已存在于( Mi mod 4 )中的消息。
则使用信号量实现进程Pi (i = 0 , 1 ,2 ,3 )同步及互斥的流程如下： mutex0 , m utex 1, m utex2 , m utex3 : semaphore ; full0 , ful l1 , ful l2 , ful l3 : semaphore ;
empty0 , em pty1 , em pty2 , em pty3 : semaphore ; begin
mutex0 : = 1 ; mutex1 : = 1 ; mutex2 : = 1 ; mutex : = 1 ;
full0 : = 3 ; full1 : = 0 ; full2 : = 0 ; full3 : = 0 ;
empty0 : = 0 ; empty1 : = 3 ; empty2 : = 2 ; empty3 : = 2 ; Parbegin P0：begin repeat
P ( mutex0 ) ; P ( full0 ) ;
Receive ( M0,message); V (empty0 ) ;
Processing the message until finished; P ( mutex1 ) ; P ( empty1 ) ;
Send ( M1,message ) ; V ( full1 ) ; V ( mutex1 ) ; Until false ;
? end ; P1：｛可类似于P0实现之｝; P2：｛可类似于P0实现之｝; P3：｛可类似于P0实现之｝; Parend ; End;
六． ③可能会发生死锁。只要一个进程占用了少于3个独占型资源而另一个进程占用了其余的独占型资源，两个进程都会相互处于等待对方进程释放资源的状态。
⑤也可能会发生死锁。当每个进程都分配了两个资源时，3个进程都会彼此等待。
国防科技大学研究生院1999年硕士生入学考试 软件技术（操作系统部分）
考生注意：1．答案必须写在我校统一配发的答题纸上 2．统考生做 一、1,2,3 二、1,2,3,4 三、1,2,3，4，5（1）（3） 3．单独考生做一、1,2,4 二、1,2,3,5 三、1,2,3，4，5（1）（2） 一．（40分）操作系统部分
1． （共20分，每小题5分）回答如下问题：
（1） 在设备管理中，何谓设备独立性？如何实现设备独立性？
（2） 给出一个程序的优先图如下，试用并发语句parbegin / parend 写出相应的并发程序
（3） 下面的算法是解决两个临界段问题的解法，试判断其正确性。如果不正确，举例说明该算法违背了关于临界段问题的哪条准则。 两个进程P0，P1共享如下变量： Var flag : array [0?1] of Boolean; turn : 0..1;
其中flag数组元素初值均为false。turn的初值为0或1 进程Pi（i=0或1,j=1－i ）所对应的程序表示为： repeat
flag : = true ; while turn<> i do begin
while flag do skip ; turn : = i ; end;
?
Critical section ?
non_Critical section until false ;
（4） 在磁盘上有一个文件系统，磁盘每块512字。假定每个文件在目录中占有一个目录项，该目录项给出了文件名。第一个索引块的地址，文件长度（块数）。在索引块中（包括第一个索引项）前面511个字指向文件块，即第i个索引项（i = 0,1,?,510）指向文件的第i块，索引块中最后一个字指向下一个索引块，最后一个索引块中最后一个字为nil。假定目录在存储器中，每个文件的逻辑块号均从0开始编号，逻辑块长与物理块长相同。对这关的索引物理结构。该系统应如何将逻辑块号变换成物理块号？ 2．（11分）假定具有5个进程的进程集合P＝｛P0,P1,P2,P3,P4｝,系统中有三类资源A，B和C。其中A类资源有10个，B类资源有5个，C类资源有7个。假定在某时刻有如下状态：
Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2