LRU m=4时 ，共 8 次缺页。
|
说明采用LRU算法，分得页框越多缺页率越低。
五、对于如图所示的优先图，用Parbegin/Parend语句及同步工具，写出并发程序。（10分）
答：
var Sem1,Sem2,Sem3,Sem4,Sem5:semaphore;
Sem1:=Sem2:=Sem3:=Sem4:=Sem5:=0;
parbegin
begin
S1; V(Sem1);V(Sem1);V(Sem1);
end;
begin
P(Sem1);S2; V(Sem2);V(Sem2);
end;
begin
P(Sem1);S3; V(Sem3);
end;
begin
P(Sem1);P(Sem2);S4; V(Sem4);
end;
begin
P(Sem3);P(Sem2);S5; V(Sem5);
end;
begin
P(Sem5);P(Sem4);S6;
end;
parend.
六、假设有三个进程P，Q，R。其中P负责从输入设备上读入信息并传送给Q；Q将信息加工后传送给R；R负责将信息打印出来。进程P，Q共享一个由m个缓冲区组成的缓冲池；进程R，Q共享另一个由n个缓冲区组成的缓冲池（假设缓冲区足够大，进程间每次传送信息的单位均小于等于缓冲区长度）。写出满足上述要求的并发程序。（10分）
答：
var mutex1,mutex2:semaphore;
empty1,full1,empty2,full2:semaphore;
mutex1:=mutex2:=1;empty1:=m;empty2:=n;full1:=full2:=0;
buffer1[0..m-1] of integer;
buffer2[0..n-1] of integer;
in1,in2,out1,out2:integer;
in1:=in2:=out1:=out2:=0;
cobegin
process P
begin
L1: 读入数据;
P(empty1);
P(mutex1);
Buffer1[in]:=数据;
in1:=(in1+1) mod m;
V(mutex1);
V(full1);
Go to L1;
end;
process Q
begin
L2:
P(full1);
P(mutex1);
取数据 从Buffer1[out1];
out1:=(out1+1) mod m;
V(mutex1);
V(empty1);
加工处理数据;
P(empty2);
P(mutex2);
Buffer2[in2]:=加工数据;
in2:=(in2+1) mod n;
V(mutex2);
V(full2);
Go to L2;
end;
process R
begin
L3: 读入数据;
P(full2);
P(mutex2);
取加工数据从Buffer1[out2];
out2:=(out2+1) mod n;
V(mutex2);
V(empty2);
Go to L3;
end;
coend.
七、在分页虚拟存储管理系统中，什么情况下发生页故障？描述页故障的处理过程。（12分）
答：当CPU发出访问的逻辑地址中的页号还未调入主存，由页表该页表项的中断位指示，发出硬件缺页中断。页故障的处理过程大致如下：首先判断内存中有否多余页框?如果没有的话，按照替换算法，找出一个页面进行淘汰，如果该页被修改过还需先写回磁盘。至此必能分得一个空闲页框，按页表项中该页磁盘地址把此页面调入内存，然后，重新启动刚才这条指令执行，这时就不再会发生页故障了。
哈尔滨工业大学2001年硕士入学操作系统试题参考答案
一、判断改错题（10分）（判断下列叙述是否正确，认为正确在括号内打“√”；若不正确打“X”，并改正。）
1.现代操作系统的两个基本特征是中断处理和系统资源共享。（ X ）
2．临界区是进程执行程序中对临界资源访问的那一段程序代码。（ √ ）
3．可执行目标程序是在经重定位后装入产生的。（ √ ）
4．采用SPOOLing技术，就可使独占设备增加，使用户同时面对独立的同类设备。（ √ ）
5．打开文件的目的是把该文件的有关目录表复制到主存中约定的区域，以建立用户和该文件的联系。（ √ ）
二、填空题（15分）
1．操作系统是对计算机进行（管理和控制 ）的程序，是（计算机 ）和用户的接口。
2．操作系统中进程的状态有许多种，但最基本的代表其生命周期的三种状态为（ 运行）、（就绪 ）、（ 阻塞 ）。这三种状态间的转换称为（状态变迁）。
3．调度算法中，FIFO算法也称为（ 先来先服务 ）法，它总是将处理机分配给（ 首先）进入就绪队列的进程。
4．存储管理的目的是（提高内存利用率）和（方便用户使用），它的功能是（存储分配和回收 ）、（存储共享和保护 ）和（存储扩充）。
5．通道是一种硬件设施，它是一种专用的、有很强（ 管理和控制I/O能力）的部件。
6．文件的安全管理，主要是通过设置（访问控制表 ）来控制用户对文件的访问。
三、简答题（30分）
- 程序顺序执行与并发执行有什么不同?
答：程序顺序执行具有操作的顺序性、执行环境的封闭性、运行结果的可再现性，因而，程序的编写、调试和校正都很方便，但资源不能充分利用、系统效率低。
程序并发执行具有间断性，失去了封闭的环境，执行结果是不可再现的。但如果控制好并发程序的制约关系，就能提高系统效率。
- 父进程创建子进程是否等价于主进程调用子程序？为什么？
答：不是。主进程调用子程序仅是同一程序中的过程调用，本质上还在一个程序中(—个进程在工作)。而父进程创建子进程需进入操作系统做创建工作，其结果形成了两个相对独立的进程，可并发执行。
- 什么是“内存碎片”？应怎样解决“内存碎片”问题？
答：内存中，小到无法利用的空闲区称“内存碎片”。如，固定分区分配时，一道程序很难确好把一个分区填满，被浪费的内存区就是“内存碎片”或“内存外碎片”。可采用动态分区按需分配，经常收集碎片成一个大的内存区供分配。也可用分页方式来减少“内存外碎片”。
- 缓冲技术主要包括哪几种方式？
答：引入缓冲技术能调节CPU和I/O设备之间速度不匹配的矛盾、实现I/O设备之间的并行操作、减少内外(I/O)交换次数，提高了系统效率。在OS的管理下，常开辟专用主存区用怍缓冲区服务于各种设备。支持I/O管理功能常用的缓冲技术分单缓冲、双缓冲、循环缓冲等。
缓冲区是临界资源，OS要管理缓冲区的申请、释放和互斥问题。例如，可把缓冲区分成空闲缓冲区、输入缓冲区、输出缓冲区。当输入设备需要输入数据时，从空闲缓冲队列取一个空缓冲区，待装满数据后，将其插入输入队列。当CPU处理输入数据时，就从输入队列取下一个数据缓冲区进行处理，处理完该缓冲区数据后将其插入空闲缓冲区队列。当CPU进行数据输出时，也作类似处理。
- 文件具有哪三大基本特征？
答：文件可按名存取、安全可靠、易被共享。首先，实现了“按名存取”，用广使用方便，特别，当文件存放位置作了改变，甚至更换了文件的存储设备，对文件的使用者也没有丝毫影响;其次，文件安全可靠，由于用户通过文件系统才能实现对文件的访问，而文件系统能提供各种安全、保密和保护措施，故可防止对文件信息的有意或无意的破坏或窃用。此外，在文件使用过程中可能出现硬件故障，这时文件系统可组织重执或恢复，对于硬件失效而可能造成文件信息破坏，可组织转储以提高文件的可靠性。最后，文件系统还能提供文件的共享功能，如不同的用户可以使用同名或异名的同一文件。这样，既节省了文件存放空间，又减少了传递文件的交换时间，进一步提高了文件和文件空间的利用率。把数据组织成文件形式加以管理和控制是计算机数据管理的重大发展。
6．选择调度方式和调度算法应遵循的准则是什么？
答：(1)资源利用率——使得CPU或其他资源的使用率尽可能高且能够并行工作。
(2)响应时间——交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务。这是分时系统和实时系统衡量调度性能的一个重要指标。
(3)周转时间——批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。这是批处理系统衡量调度性能的一个重要指标。
(4)吞吐率——使得单位时间内处理的作业数尽可能多。
(5)公平性——确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死情况。
当然，这些目标本身就存在着矛盾之处，操作系统在设计时必须根据其类型的不同进行权衡，以达到较好的效果。
四、单项选择题（15分）
1．对于给定的信号量S，等待操作wait（S）（又称P操作）定义为：
if S>=o then （A）else挂起调用的进程；
唤醒操作signal（S）（又称V操作）定义为：
if存在等待的进程then唤醒这个进程else（B）；
当S被初始化为1时，代码段：（C）；
｛临界区｝
（D）；
定义了一个临界区，这种临界区通常称为（E）。
选择：A～D：①S：=0 ②S：=S+1 ③S:=S-1 ④S：=1 ⑤signal（S+1） ⑥wait（S—1）
⑦signal（S） ⑧wait（S）
E：①模块②类程③管程④线程
A=③S:=S-1 B=④S：=1 C=⑧wait（S） D= ⑦signal（S） E= ③管程
2．虚拟存储器的作用是允许（A），它通常使用（B）作为它的一个主要组成部分，对它的调度算法与（C）基本相似，即把要经常访问的数据驻留在高速存储器中，因为使用了虚拟存储器，指令执行时（D）。在虚拟存储器系统中常使用相联存储器进行管理，它是（E）寻址的。
A：①直接使用外存代替内存 ②添加此地址字长允许的更多内存容量
③程序直接访问比内存更大的地址空间 ④提高内存的访问速度
B：①CD-ROM②硬盘③软盘④寄存器
C：①Cache②DMA③I/O④中断
D：①所需数据一定在内存中找到 ②必须事先使用复盖技术
③必须先进行“虚、实”地址变换 ④必须将常用子程序先调入内存
E：①按地址 ②按内容③寄存器 ④计算
A= ③程序直接访问比内存更大的地址空间 B=②硬盘 C= ①Cache D= ③必须先进行“虚、实”地址变换 E= ②按内容
3．进程是操作系统中的一个重要概念，进程是一个具有一定独立功能的程序在某个数据集合上的一次（A）。进程是一个（B）概念，而程序是一个（C）的概念。进程的最基本状态有（D）个。在一个单处理机系统中，若有6个用户进程，在非管态的某一时刻，处于就绪状态的用户进程最多有（E）个。
A：①单独操作 ②关联操作 ③进行活动 ④并发活动
B：①静态 ②动态 ③逻辑 ④物理
C：①物理 ②逻辑 ③动态 ④静态
D：①2 ②5 ③3 ④9
E：①5 ②6 ③1 ④4
A=④并发活动 B= ②动态 C= ④静态 D= ③3 E= ②6
五、在请求分页系统中，其页表项中包含哪些数据项?它们的作用是什么?请举一个例子说明页表的作用。（10分）
答：见教材
六、设有进程Pl和P2。并发执行，都需要享用资源Rl，R2。
使用资源情况如下：
Pl： P2：
申请资源R1， 申请资源R2：
： ：
申请资源R2： 申请资源R1
： ：
申请资源R1 申请资源R2
： ：
试判断是否会产生死锁，并加以解释及说明产生死锁的原因与必要条件。（10分）
答：会产生死锁。当它们推进速度不匹配，如P1得到了R1，P得到了R2。再并发执行下去，两个进程都会因申请不到另一个资源进入阻塞状态，出现死锁。
七、设在批处理系统中有四道作业，它们进入系统的时间及运行时间如表所示。
|
作业号 |
进入时间 |
运行时间（h） |
|
1 |
8:00 |
2.00 |
|
2 |
8:50 |
0.50 |
|
3 |
9:00 |
0.10 |
|
4 |
9:50 |
0.20 |
设系统每次只选择一个作业装入主机，分别给出在下列算法中这组作业的运行顺
序、平均周转时间和平均带权周转时间。
（1）FCFS算法；（2）SJF算法（最短者优先）；（3）HRN算法（最高响应比者优先）。（10分）
答：(1) FCFS算法，完成次序J1→J2→J3→J4。
(2) SJF 算法
说明：
8:00 作业1到达，开始运行。由于是仅一道作业进主机，在它结束前后来作业均进入作业
后备队列等待。
8:50 作业2到达，进后备队列等待。
9:00 作业3到达，进后备队列等待。
9;50 作业4到达，进后备队列等待。
10:00 作业1运行结束，根据SJF算法，后备队列中选作业3运行。
10:06 作业3运行结束，根据SJF算法，后备队列中选作业4运行。
10:18 作业4运行结束，作业2运行。
10:48 作业4运行结束。
所以，作业执行顺序：J1→J3→J4→J2。
J1周转时间=10:00-8:00=120 带权周转时间=120/120=1
J2周转时间=10:48-8:50=118 带权周转时间=118/30=3.93
J3周转时间=10:06-9.00=66 带权周转时间=66/6=11
J4周转时间=10:18-9:50=28 带权周转时间=28/12=2.34
平均周转时间=83分=1小时23分 平均带权周转时间=4.57小时
- HRN算法
说明：
8:00 作业1到达，开始运行。由于是仅一道作业进主机，在它结束前后来作业均进入作业
后备队列等待。
8:50 作业2到达，进后备队列等待。
9:00 作业3到达，进后备队列等待。
9:50 作业4到达，进后备队列等待。
10:00 作业1运行结束，计算作业2、作业3、作业4的响应比：
作业2的响应比=1+(10:00-8:50)/30=1+70/30
作业3的响应比=1+(10:00-9:00)/6=1+60/6
作业4的响应比=1+(10.00-9.50)/12=1+10/12
作业3响应比最高，开始运行。
10.06 作业3运行结束，计算作业2、作业4的响应比：
作业2的响应比=1+(10:06-8:50)/30=1+76/30
作业4的响应比=1+(10:06-9.50)/12=1+16/12
作业2响应比高，开始运行。
10.36 作业2运行结束，作业4运行。
10.48 作业4运行结束。
所以，作业执行顺序：J1→J3→J2→J4。
J1周转时间=10:00-8:00=120 带权周转时间=120/120=1
