　　2.(8分)有一阅览室，读者进入时必须先在一张登记表上登记。该表中每个表项代表阅览室中的一个座位。读者离开时要消掉其登记信息。阅览室共有50个座位。登记表每次仅允许一位读者进行登记或注销。读者登记时，发现登记表满，他在阅览室外等待，直至有空位再登记进入。试用类Pascal语言和P、V操作，描述读者行为。

　　3.(12分)在页式虚存管理系统中，假定驻留集为m个页帧(初始所有页帧均为空)，在长为p的引用串中具有n个不同页号(n>m )，对于FIFO，LRU两种页面替换算法，试给出页故障数的上限和下限，说明理由，并举例说明。

　　4.(12分)旋转型存储设备上信息的优化分布能减少若干输入输出服务的总时间。例如，有10个扇区，每扇区存放一个记录，安排如下所示。现在要从该磁道上顺序地将A至J的10个记录，如果磁盘旋转速度为20ms转1周，处理程序每读出一个记录后花4ms进程处理。试问处理完10个记录的总时间是多少(从找到A记录开始计算)?为了缩短处理时间应进行优化分布，试问应如何安排这些记录，并计算处理的总时间(从找到A记录开始计算)?

　　扇区 1 2 3 4 5 6 7 8 9 10

　　记录号 A B C D E F G H I J

　　国防科技大学研究生院2000年硕士生入学考试

　　软件技术试题

　　操作系统部分参考答案(非标准答案)

　　一.(50分)操作系统部分

　　1. (共30分，每小题5分)回答如下问题：

　　(1) 进程的现场信息主要包含：所有通用寄存器内容，程序寄存器PC，程序状态字PSW，存储映象寄存器。这些内容用于在进程转换为执行状态时建立相应的运行现场。

　　(2) P(S1,S2):

　　While S1 <= 0 or S2 <= 0 do skip ;

　　S1 : = S1 – 1 ;

　　S2 : = S2 – 1 ;

　　V(S1,S2):

　　S1 : = S1 + 1 ;

　　S2 : = S2 + 1 ;

　　(3) 中断处理原则是对各类中断规定了不同的响应级别，把紧迫程度大致相当的中断源放在同一级，而把紧迫程度差别较大的中断源放在不同的级别，级别高的享有绝对优先响应的权利。

　　因而，象电源故障应设为最高级别31级;而用户进程应放在较低的中断级上运行。

　　(4) 顺序结构适合对文件的顺序访问，不便于增补和删除;而链接结构空间利用率比顺序结构高，文件操作灵活;而索引结构适合于逻辑记录系散存于外存的各物理介质中，可能文件记录数据达到较大。

　　(5) 系统“抖动”是指系统陷于不断地处理页故障的状态。主要因素是驻留集太小。

　　(6) 优先图如下：

　　begin {l , m , n 初值为0}

　　Parbegin

　　begin S1 ; V ( l ) ; end ;

　　begin S2 ; V ( m ) ; end ;

　　begin P ( l ) ; P ( m ) ; S3 ; V ( n ) ; end ;

　　begin P ( n ) ; S4 ; end ;

　　Parend ;

　　end ;

　　2. Begin {initial value of S is 50}

　　Parbegin

　　Begin {register }

　　P (S) ;

　　End;

　　Begin {leave off}

　　V (S) ;

　　End ;

　　End ; {finished}

　　3. 对于FIFO，页故障数的上限是P，下限是n，因为FIFO淘汰掉最先进来的页，而不管其页面以后是否会用到。极端情况下，可能刚淘汰掉的页又接着要使用。故页故障上限为P;而不同的页至少有一次页故障，故下项为n。

　　对于LRU页故障数上限为P，下限为n　，因为同样可能刚淘汰掉的页又要用到，导致淘汰掉接下来要用到的页，故页故障数上限是P，而n个不同页数必然至少一次面面失效，故下限为n。

　　举例说明：略。

　　4. 读A记录要花2ms　，随后处理及等到第二周旋转到B需要20ms。故处理完10个记录的总时间是T=2 +20 x 9=182ms.

　　为缩短时间，可以安排B记录存在第4扇区，C记录在7扇区，…，如下所示：

　　扇区 1 2 3 4 5 6 7 8 9 10

　　记录号 A H E B I F C J G D

　　这样，每当处理完前一记录时，恰好旋转到刚要读出的记录位置，使等待时间最小。这样，总的处理时间为：

　　T = ( 2 + 4 x 10 = 60 ms