操作系统第一套试卷
操作系统试卷一（附答案）
一、请描述在当前运行进程状态改变时，操作系统进行进程切换的步骤（8分）。
二、假设三个进程共享相同类型的四个资源，每个进程一次只能申请或释放一个资源，每一个进程至多需要两个资源，该系统会不会发生死锁？为什么（8分）？
三、考虑下面的进程，以及CPU的工作时间:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
假设进程按P1, P2, P3, P4, P5 的顺序同时提交，分别按照FCFS，SJF，非剥夺优先级算法(小的优先数表示大的优先级)和RR(m = 1) 求每个算法的平均周转时间是多少？平均等待时间是多少（12分）?
四、有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：
(1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？
(2) 用类Pascal语言和Wait, Signal操作写出这些进程间的同步算法（12分）。
五、假定有一个具有200个磁道（编号为0～199）的移动头磁盘，在完成了磁道125的请求后，当前正在磁道143处为一个请求服务。若请求列队以FIFO依次存放：86，147，91，177，94，150，102，175，130。对下列每一个磁盘调度算法，若要满足这些请求，则总的磁头移动次数是多少（20分）？
a. FCFS；
b. SSTF；
c. SCAN；
d. LOOK；
e. C-SCAN。
六、在一个请求页式存储系统中，一程序的页面走向为4.3.2.1.4.3.5.4.3.2.1.5，采取LRU页面置换算法，设分配给该程序的存储块数M分别为3和4时，请求出在访问过程中发生的缺页次数和缺页率，并比较所得结果，从中可得到什么启发（20分）？
七、下图是一种段页式管理配置方案。
a)根据给出的虚地址写出实地址。
b)描述地址映象过程。
c)从虚地址到实地址要经过几次访问主存？是哪几次？
d)一般采用什么设施提高映象速度？（20分）
试题答案
一、答：进程切换的步骤如下：
a)保存处理器内容。
b)对当前运行进程的PCB进行更新，包括改变进程状态和其他相关信息。
c)将这个进程的PCB移入适当的队列（就绪、因事件阻塞、就绪挂起等）。
d)挑选其他进程执行。
e)对挑选进程PCB进行更新，包括将其状态改为运行。
f)对存储器管理数据结构进行更新。
g)恢复被选择进程上次移出时的处理器状态。
二、答：假定该系统死锁，那么就隐含其中的每一进程已占有一资源并正等待另一资源。由于该系统只有三个进程且有四个资源，因此，必有一进程能获得两个资源，不必等待。于是该进程不再申请资源，而且当它执行完后将归还它占有的资源。故该系统不会发生死锁。
三、答：
周转时间：
FCFS RR SJF Priority
P1 10 19 19 16
P2 11 2 1 1
P3 13 7 4 18
P4 14 4 2 19
P5 19 14 9 6
等待时间：
FCFS RR SJF Priority
P1 0 9 9 6
P2 10 1 0 0
P3 11 5 2 16
P4 13 3 1 18
P5 14 9 4 1
四、答：
(1) 应编写1个程序；设置2个进程；进程与程序间的对应关系是：多对1。
(2) begin
S1:=100 (有100个座位)
S2:=0 (有没阅读者记录)
mutex: =1
cobegin
P1: repeat
P(S1);
P(mutex);
登记信息;
V(muetx);
V(S2)就座，阅读；
until false
P2: repeat
P(S2)
P(mutex);
消掉信息;
V(muetx);
V(S1);
离开阅览室;
until false
coend
end
计算可得各算法的磁头移动次数如下：
FCFS：565
SSTF：162
SCAN：169
LOOK：125
C-SCAN：386
六、解：
（1）当M＝3时：
∴缺页10次，缺页中断率为：10
×100%=83.3%12
（2）当M ＝4时：
∴缺页8次，缺页中断率为：
8
100%66.6%12
?= 所以，由结果我们可以看出在LRU 算法下，当M 增大时，缺页次数减少，缺页中断率也减少。 七、答：
1.主存实地址为14337.
2.地址映象过程为：段号6映象到段表为1003，在段表1006项查得页表地
址为6000。进而查得页表项6004内容为14000，加上位移量337即得实地址为14337。
3.共三次访问主存：第一次访问段表，第二次访问页表，第三次访问实地址。
4.因访问一个实地址需三次访问主存，故速度较慢。若段表、页表采用快表则可提高速度，快表是用联想存储器构成的（由高速寄存器组成）。因联想存储器的容量不能太大，故快表的大小有限，因此只存放常用的页面，故产生调页问题。
4 3 2 1 4 3
5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2 + + + + + + + 4 3 2 1 1 1 5 4 3
+