国防科技大学研究生院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，它们到达就绪队列的时刻，运行时间及优先级如下表所示：运行时间(基本时间单位)优先级进程 到达就绪队列时间(基本时间单位)P1 0 9 1P2 1 4 2P3 2 8 3P4 3 10 4问：(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分)在页式虚存管理系统中，什么情况下发生页故障？描述页面故障的处理过程。

国防科技大学研究生院2002年硕士生入学考试试题考试科目：519-操作系统题单号：50619（可不抄题）考生注意：1、考生注答案必须写在我校统一配发的专用答题纸上！2、统考生做：一、二、三、四、五；3、单独考生做一、二、三、六、七；一、（60分）回答如下问题1、（6分）将“I/O为主”的进程定义为：当此类进程单独运行时，用于I/O处理的时间远远多于处理机的处理时间；将“计算为主”的进程定义为：当此类进程单独运行时，处理机的处理时间远远多于I/O处理的时间。

若系统中运行的主要是这两类进程，采用什么样的调度算法更有利于提高系统资源的利用率？为什么？2、（8分）请给出PCB（进程控制块）的主要内容。

描述当进程发生下述状态转换时，就绪→运行，运行→阻塞，操作系统需要使用/修改PCB中的哪些内容。

3、（5分）请问，在一个进程中使用多线程有何优点？4、（5分）设系统中有下述解决死锁的办法：. 银行家算法. 检测死锁，中止死锁状态的进程、释放该进程占有的资源. 资源预分配请问哪种方法允许最大的并发性，也即，哪种办法允许更多的进程无等待的向前推进？请按“并发性”从大到小对上述三种办法排序。

5、（8分）请描述页式虚存管理系统中叶表项的主要内容。

请简要描述“缺页中断”的处理过程，并结合该过程，说明其中使用/修改了页表项的哪些内容。

6、（6分）简述OS对文件读/写的系统调用所完成的工作。

7、（6分）简述以程序中断I/O方式，从外设读入一包含N个字节的数据块的过程。

8、（8分）若允许文件能分别在开始、中间、末尾增长，试讨论在顺序式、链接式以及索引式文件物理组织下的开销。

9．（8分）（1）给出无忙等待的P、V操作的定义（１）考虑下述P、V操作的定义P（s）：if s.value>0Thens.value=s.value-1else beginplace this puocess in s.queue;block;end;V(s):if there is at least one process waiting on semaphore sthen beginRmove a process p from s.queuePlace process p on ready list end elses.value=s.value+1请问，当使用信号量和P、V 操作作进程的同步和互斥控制时，是否可以在不改动程序的情况下互换的使用（1）、（2）中的P、V 操作？这两组P、V 操作有何不同？ 二、（10分）某工厂有三个生产车间和一个装配车间，三个生产车间分别生产A、B、C 三种零件，装配车间的任务是把A、B、C 三种零件组装成产品。

三个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2和F3上，F1存放零件A，F2存放零件B，F3存放零件C，F1、F2和F3的容量均可以存放20个零件。

装配工人每次从货架上取一个A 零件、B 零件和一个C 零件，然后组装成产品。

试用P、V 操作给出各生产车间和装配工人的控制流程。

三（8分）假定一计算机系统中有4个进程，各进程的执行时间和均到达就绪队列的时间如下图所示：进程 到达就绪队列时间 总执行时间 （时间单位：基本时间单位）（时间单位：基本时间单位）试用本时间单位），分别给出各理，允许用户编程空间为32个页面（每页1KB），主存为16KB。

剥夺式短进程优先调度算法和时间片轮转调度（时间片为两个人个基进程的调度次序及平均周转时间。

四、（10）某操作系统采用页式虚存管如果一用户程序有10页长，且某时刻该用户进程的页表如下所示。

页号 物理页帧号 0 8 1 7 2 4 310如果分别遇到以下三个逻辑地址（十六进制）：0处的操作，试说明存储管理系统件共有9个记录，依次为R1，R2， ，R9，每锁的原因是什么？如何预防死锁？4个页帧，且已分配到4个AC5，1AC5，3AC5将如何处理（假定驻留集长度固定，4个叶幀）。

五、（12分）如磁盘的每个磁道分成9段，现有一文个记录的大小与段的长度相等。

若磁盘的转速为6000转/分，每读出一段(即一个记录)后需要2.5ms 处理时间，然后再读下一段所放记录，忽略其它辅助时间。

如果在磁盘的某磁道上顺序存放这些记录，读出该文件需要多少时间？六、（10分）什么是死锁？产生死七、（12分）假定一计算机系统采用页式虚存管理，一进程的驻留集为页帧，如下表所示（所有数字均为十进制数，且以0开始）：虚拟页号 访问位 修改位 装入时间 最近访问时间 页帧号2 0 1 60 161 01 0 0 130 160 10 1 0 26 162 23 1 1 20 163 3页时，产生障（缺页，分别用LRU决定断处理当进程访问第四页故）中断FIFO、页故障中程序的处理过程。

国防科技大学研究生院2001年硕士生入学考试试题考试科目：离散数学注：1、不用抄题，答案必须写在统一配发的答题纸上!2、统考生做：第一、二、三、四、五、六、七、八、九、十题；3、单独考生做：第一、二、三、四、五、六、七、十一、十二、十三题。

一、(每小题5分，共15分)设A= { 1，2，… , 6 } , B = { 1 , 2 , … , 8 } , 函数f ：A Æ B 和 g ：A Æ B 定义如下：x 1 2 3 4 5 6 f (x) g (x)1 44 55 52 55 68 7若B 上的二元关系R = { <f(x) , g (x)> | x = 1 ,2 ,3 ,4 ,5 ,6 } ,试求i ) R 的关系图 i i )t ( R )R;i i i ) tsr ( R ) 的简化关系图和B/tsr(R) 。

二、(每小题5分，共15分)设< A ， >和 < B ，>为两个半序结构，函数F ：AB 和 G ：BA 均为保序映射。

若对任意aA 和 bB 皆有F(a) b 当且仅当 a G( b ).则对每个 b B 皆有：i ) FG( b ) b; i i ) FGFG(b )FG( b ) ;i i i ) FG( b ) = FGFG( b )。

(注：函数F ：AB 称为保序映射，如果对于任意 a1, a2A 且a1a2 ,必有F(a1)F(a2) )。

三、(10分)。

今有111人购买A ，B ，C 三种股票，已知只买了一种股票的共75人，买了A 股和B 股的共有20人，买了B 股和C 股的共有9人，买了A 股和C 股的共17人，只买了A 股的共31人，只买了B 股的共23人。

试求：i ) 三种股票都买的有几人 ？ i i ) 买A 股、B 股和C 股的各几人？ 四、(各小题 依次为4分，4分，2分，共10分)设 为非空集合A 上的半序，且S 为A 的非空子集。

试直接利用 和作谓词将下列命题符号化： i ) S 有极小元 ；i i )S 有上界 ； i i i ) S 有上确界。

五、(10分)。

设G=< V ，E ，>为n 阶简单有向图，结点v V 的出度分别用六、(10分)若简单无向图G 中恰有两个奇结点，则这两个奇结点之间必存在路径可达。

七、(5分)设合式公式试求A的主析取范式。

本页的八、九、十题只需统考生做，单独考生不做。

八、(每小题5分，共10分)明：九、(每小题5分，共10分)用自然推理系统证明：十、(5分)设P为一元谓词，试判断合式公式是否为永真式，并说明理由。

本页的十一、十二、十三题只需单独考生做，统考生不做。

十一、(每小题5分，共10分)设R为集合A上的二元关系，且R为反自反的。

i ) 若R为对称的，则R不是传递的；i i ) 若R为传递的，则R为反对称的。

十二、(每小题5分，共10分)用自然推理系统证明：十三、(5分)设Q为二元谓词，试判断合式公式是否为永真式，并说明理由。