3．考虑由n个进程共享的具有m个同类资源的系统，如果：
（1）对i=1，2，3，…，n，进程Pi至少需要1个资源，最多需要m个资源；
（2）在任意时刻，所有进程对资源的需求量之和小于m+n；
（3）试证明，该系统是死锁无关的。
解1： 系统具有同类资源m个。由于进程Pi最多只需要m个资源，所以，
只要满足下式时，系统不会发生死锁：
n×(m-1)+1≤m
该式表明当n个进程都取得了最大数减1个即(m-1)个时，这时，只要系统还有一个资源可分配就行了。化简上式，
解1：-n+1≤m
再化简 n×m+1≤m+n
得到 n×m<m+n
这表明n个进程对资源的总需求量之和小于m+n，这是己知条件；故该系统是死锁无关的。
解2：
由(1)和(2)知道， n×m<m+n 是成立的，
等式变换 n×(m-1)+n<n+m
即 n×(m-1)<m
于是有 n×(m-1)+1<m+1
或 n×(m-1)+1≤m
这说明当n个进程都取得了最大数减1个即(m-1)个时，这时至少系统还有一个资源可分配。故该系统是死锁无关的。
4．现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串：1，2，3，4，5，3，4，1，6，7，8，7，8，9，7，8，9，5，4，5，4，2。分别采用FIFO，LRU，OPT页面替换算法，各将产生多少次缺页中断?
解：分别为13、12、11次。
国防科技大学2001操作系统试题参考答案
一、回答下列问题（58分）
- 假定有一个支持实时、分时和批处理的操作系统，对该系统应如何设计进程调度策略？（6分）
解：采用多级反馈队列调度算法能适应不同需求。算法的基本思路如下：设置多个就绪队列，并赋予各队列不同的优先权。就绪队列的设置按时间片大小划分，优先权越高的队列，其进程运行时获得的时间片越小。系统总是把新创建的进程首先排入优先级最高的队列，若它执行一个时间片后尚未完成，系统便把它放入下一级队伍的末尾、即进程的优先级动态地逐步降低。非最低优先级队列均采用时间片轮转的FCFS调度算法，而最低优先级队列可采用轮转法或其他调度算法。
- 什么是线程？为什么要引入线程？ （5分）
解：所谓线程（thread），从操作系统管理角度看线程是指“进程的一个可调度实体”，是处理机调度的基本单位；从编程逻辑看线程是指“程序内部的一个单一的顺序控制流”。线程是进程的一个组成部分。引入线程能减少系统调度开销，使系统并发性更好，从而，有效提高资源使用率和系统效率
- 某计算机系统设计成只有一级中断（该级中有多个中断）的中断系统，简述当中断发生时，是如何进入该中断处理程序的？ （6分）
解：由于仅一级中断，不分中断的优先级，所有中断源均在一级中。当发生中断时，应由硬件负责把中断字寄存器的内容保存至约定单元(或由专门指令保存)，中断服务程序响应中断时。依次扫描中断字。发现一个，处理一个，清除一个，直至结束退出中断，返回断点或进入调度程序。
- 在文件系统中为什么要引进“open”系统调用？操作系统是如何处理的？（5分）
解：通过open建立起用户和该文件之间的联系，open的主要工作为：在活动文件表中申请一个空目录项，以存放文件的FCB信息。根据文件名查目录文件，把找到的FCB调入文件占用栏。共享文件数加1。文件定位，卷标处理。
文件打开后，直到关闭前可反复使用，这样做能减少目录查找次数，加快文件查找速度，从而提高文件系统的效率。
- 假定存储器空闲块有如图所示的结构：请你构造一串内存请求序列，对该请求序列首次满足分配算法能满足，而最佳满足分配算法则不能。（5分）
解：400、150、200、200。
当用首次满足分配算法---
分400 空闲区为350 250 100
分150 空闲区为200 250 100
分200 空闲区为0 250 100
分200 空闲区为0 50 100
当用最佳满足分配算法---
分400 空闲区为350 250 100
分150 空闲区为350 100 100
分200 空闲区为 150 100 100
分200 已无空闲区可分。
6．为什么要在设备管理中引入缓冲技术？操作系统如何实现缓冲技术？（6分）
解：(1)调节CPU和I/O设备之间速度不匹配的矛盾 例如，如果不设缓冲，则程序输出时由于打印机速度跟不上而使CPU停下来等待，而在CPU计算时，打印机又因无数据输出而闲置。有了缓冲区，则程序可把输出数据预先输到缓冲区后继续运行，而打印机可从缓冲区取数慢慢打印，从而，CPU和I/O设备之间速度不匹配的矛盾得到缓和。
(2)实现I/O设备之间的并行操作 类似地，可以开出多缓冲，每个对应于一个设备，实现I/O设备和I/O设备之间的并行操作
(3)减少内外(I/O)交换次数 开设缓冲区后可以实现成组和分解操作，既减少了内外(I/O)交换次数，又充分利用了外存空间。同时，减少内外(I/O)交换次数，也减少了CPU处理I/O中断的次数，提高了系统效率。
缓冲区是临界资源，OS要管理缓冲区的申请、释放和互斥问题。例如，可设缓冲池，并分成空闲缓冲区、输入缓冲区、输出缓冲区。当输入设备需要输入数据时，从空闲缓冲队列取一个空缓冲区，待装满数据后，将其插入输入队列。当CPU处理输入数据时，就从输入队列取下一个数据缓冲区进行处理，处理完该缓冲区数据后将其插入空闲缓冲区队列。当CPU进行数据输出时，也作类似处理。
7．用什么方法可以破坏死锁的循环等待条件？为什么？（6分）
解：可用按序分配破坏死锁的循环等待条件。按序分配策略把系统的所有资源安排一个顺序，按顺序给每个资源一个编号，规定每个进程申请两个以上资源时，总是先申请编号小的再申请编号大的资源。这样，在进程集合中总存在某个进程，它占有了己申请资源中编号最大的资源，因而，它不再能申请其他资源，当它运行结束，就可以释放占用的全部资源。剩余的进程集合中又会有一个进程此时占有己申请资源中编号最大的资源，那么，它也能运行结束。以此类推，最终所有进程都能运行结束，故系统不会发生死锁。实质上，按序分配通过破坏死锁的循环等待条件而防止死锁。
8．进程的状态主要有哪些？当发生状态转换时，操作系统完成什么工作？ （6分）
解：基本状态有就绪、等待和运行三秆。当发生状态转换时，操作系统应该修改进程的状态(在PCB中)，并且从原有队列出队，并进入新的状态队列。
9．在文件系统中，为什么要设立“当前目录”？操作系统如何改变“当前目录”？（6分）
解：减少目录查找访盘次数，提高文件系统运转的效率。可通过设置和改变路径命令来改变成“当前目录”。
10．举例说明P，V操作为什么要用原语实现？操作系统如何实现这种原语操作？（7分）
解：信号量S是P,V均要操作的共享变量，每次它们有对S的加或减1操作。若不把P,V设计成原语，则它们交替在同一信号量上操作时会造成S值不惟一，更为严重的会造成某些进程处于永远等待状态。
例如，若S当前值为1，第一个P操执行后，进程是不会阻塞的。但若在第一个P操作执行 if S<0 then…之前，有另一个进程的P操作抢先执行S:=S-1，这时S=-1，而第一个执行P操作的进程被阻塞了。这是不符合P,V原定义的含义的。
二、设有四个进程Pl，P2，P3，P4，它们到达就绪队列的时间，运行时间及优先级如下所示。（12分）
题
|
进程 |
到达就绪队列的时间（基本时间单位） |
运行时间（基本时间单位） |
优先级 |
|
P1 |
0 |
9 |
1 |
|
P2 |
1 |
4 |
3 |
|
P3 |
2 |
8 |
2 |
|
P4 |
3 |
10 |
4 |
问：（1）若采用可剥夺的优先级调度算法，给出各个进程的调度次序以及每个进
程的等待时间：（2）若采用时间片轮换调度算法，且时间片为两个基本时间单位，给出各个进程的调度次序以及平均等待时间。
解：(1)
 |
时仃
时
时刻0 P1到达，开始运行。
时刻1 P2到达，因优先级高于P1，故P2运行，P1等待。
时刻2 P3到达，优先级仍然P2高，故P2运行，P1和P3等待。
时刻2 P4到达，优先级P4最高，故P4运行，P1、P2和P3等待。
时刻13 P4运行结束，优先级P2高，故P2运行，P1和P3等待。
时刻15 P2运行结束，优先级P3高，故P3运行，P1等待。
时刻23 P3运行结束，P1运行。
时刻31 P1运行结束。
故调度次序：P1、P2、P4、P2、P3、P1。平均等待时间=(31+14+21+10)/4=19。
(2)采用两个时间片的轮换调度算法，调度次序如下：
时刻0 P1到达，得到2个时间片开始运行。
时刻1 P2到达，在就绪队列等待。
时刻2 P1时间片到，进就绪队列等待，P2等待了1个单位时间，得到2个时间片开始运行。同时P3到达，并进就绪队列等待。就绪队列有P1、P3在等待。
时刻3 P4到达，并进就绪队列等待。就绪队列有P1、P3、P4在等待。
时刻4 P2时间片到，进就绪队列等待。P1运行。就绪队列有P3、P4、P2在等待。
P2至时刻12结束。P1至时刻25结束。P3至时刻27结束。P4至时刻31结束。
平均等待时间=(25+11+25+28)/4=22.25
三、假设系统由相同类型m个资源组成，系统有n个进程，每个进行至少请求一个资源。证明当n个进程最多需要的资源数之和小于m+n时，该系统没有死锁。（8分）
解：由题意知道， n×m<m+n 是成立的，
等式变换 n×(m-1)+n<n+m
即 n×(m-1)<m
于是有 n×(m-1)+1<m+1
或 n×(m-1)+1≤m
这说明当n个进程都取得了最大数减1个即(m-1)个时，这时至少系统还有一个资源可分配。故该系统是死锁无关的。
四、假定某请求页式虚拟系统中，某进程的页面访问踪迹（页面走向）为：1，2，3，4，1，2，5，1，2，3，4，5。设分配给该进程的驻留集为m，试分别计算m=3和m=4时，FIFO和LRU两种淘汰算法的页故障次数。结果说明了什么?（12分）
答：
FIFO m=3时 ，共9次缺页。
|
FIFO m=4时 ，共10次缺页。
|
说明当进程没有得到全部页面时，采用FIFO会产生Belady现象、即分给页框越多，缺页率越高。
LRU m=3时 ，共 10 次缺页。
|
