p p p p p p 3) 22，114，246，318，170， 90， 92，268，396，228 4) 4/10
10. （6分）设有二维数组
var A:array[1..100] of array [1..100] of integer
其中数组元素A[1，1]存放在页面大小为200的分页存储管理系统的地址为200处，数组按行存储。使用该数组的一个较小的程序存放在第0页中（地址0-199），这样将只会从第0页开始取指令。
假定现有3个页面，第一个页面存放程序，其余两个页面为空。试问：若使用LRU置换算法，下面的数组初始化循环将会产生多少次缺页中断？
解：（6分）
（1）页访问串：0，1，2…49；共计50次。
（2）页访问串：0，1，2…49； 0，1，2…49； ….因此将发生50*100次缺页。 （满分需做详细分析）
11. （8分）假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的
请求者服务后，当前正在为访问125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，130
请回答下列问题：
a. 分别用先来先服务算法，最短寻找时间优先算法、电梯调度算法和单各扫描
算法来确定实际的服务次序。
b. 按实际服务计算上述算法下移动臂需移动的距离。 答：（8分）
a、当前柱面位置：125＃，采用不同的调度算法服务满足次序如： 先来先服务 （125）86.147.91.177.94.150.102.175.130
最短寻找时间优先 （125）130.147.150.175.177.102.94.91.86 电梯调度 （125）102.94.91.86.130.147.150.175.177 b、调度算法 移动臂的移动距离
先来先服务 39＋61＋56＋86＋83＋56＋48+73+45＝547 最短寻找时间优先 5+17+3+25+2+75+8+3+5=143 电梯调度 23+8+3+5+44+17+3+25+2=130
第 31 页 共 35 页
12. （8分）若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，
假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。 （1）先来先服务算法；
（2）最短寻找时间优先算法。 解：（6分） （1）3毫秒×292=876毫秒 （2）3毫秒×120=360毫秒
各算法使移动臂的移动次序和移动的柱面数如下： （1）40 → 20 → 44 → 40 → 4 → 80 → 12 → 76
（20） （24） （4） （36） （76） （68） （64） 共移动292柱面 （2）40 → 44 → 20 → 12 → 4 → 76 → 80
（4） （24） （8） （8） （72） （4） 共移动120柱面
13. （8分）若磁头当前位置为100磁道，磁头由外向内移动，现有一磁盘读写请求队
列：23，376，205，132，19，61，190，398，29，4，18，40。若采用先来先服务、最短寻道时间优先和扫描算法，试计算出平均寻道长度各为多少？ 解：（8分）
（1）算法思想：……（2分，未直接介绍算法思想的扣除，每打错1个扣1分） FCFS算法（先来先服务）的思想是根据磁盘读写请求的先后次序来访问。
SSTF算法（最短寻道时间优选）的思想是每次总是寻找离当前柱面（或磁道）最近的优先访问；
SCAN算法（电梯调度）的思想是除了要考虑最近之外，还要考虑是否在当前寻道方向上。
（2）平均寻道分析（每算法2分，不给出分析直接给答案的每个1分） 采用FCFS处理次序为：100-23-376-205-132-19-61-190-398-29-4-18-40，总柱面数为：1596，因此平均寻道长度为1596/12=133。
采用SSTF处理次序为： 100-132-190-205-61-40-29-23-19-18-4-376-398， 总柱面数为：700，因此平均寻道长度为700/12≈58.3。
采用SCAN处理次序为： 100-132-190-205-376-398-61-40-29-23-19-18-4， 总柱面数为：692，因此平均寻道长度为692/12≈57.7。
14. （8分）某一系统进程的资源分配“瞬间状态”为
已分配资源矩阵 最多资源矩阵 可用资源向量 P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2
第 32 页 共 35 页
P4 0 0 1 4 0 6 5 6 (1) 使用银行家算法回答：系统是否安全？
(2) 如果进程P1要求(0，4，2，0)，系统能否立即满足进程的要求？
解：（6分）
(1)利用安全算法对该时刻资源分配情况进行分析，如下图所示：
Work Need Allocation Work+Allocation Finish P0 1 5 2 0 0 0 0 0 0 0 1 2 1 5 3 2 true P2 1 5 3 2 1 0 0 2 1 3 5 4 2 8 8 6 true P3 2 8 8 6 0 0 2 0 0 6 3 2 2 14 11 8 true P4 2 14 11 8 0 6 4 2 0 0 1 4 2 14 12 12 true P1 2 14 12 12 0 7 5 0 1 0 0 0 3 14 12 12 true
由以上分析可知，在该时刻存在着一个安全序列{P0，P2，P3，P4，P1}，故系统是安全的。
(2)如果进程P1要求（0，4，2，0），系统假定可为P1分配资源，由此形成的资源变化情况如图示：
已分配资源矩阵 需求资源矩阵 最多资源矩阵 可用资源向量 P1 1 4 2 0 0 3 3 0 1 7 5 0 1 1 0 0 利用安全算法对该时刻资源分配情况进行分析，如下图所示：
Work Need Allocation Work+Allocation Finish P0 1 1 0 0 0 0 0 0 0 0 1 2 1 1 1 2 true P2 1 1 1 2 1 0 0 2 1 3 5 4 2 4 6 6 true P3 2 4 6 6 0 0 2 0 0 6 3 2 2 10 9 8 true P4 2 10 9 8 0 6 4 2 0 0 1 4 2 10 10 12 true P1 2 10 10 12 0 3 3 0 1 4 2 0 3 14 12 12 true 由以上分析可知，可找到一个安全序列{P0，P2，P3，P4，P1}，故系统能立即满足进程的要求。
15. （8分）某系统由R1、R2和R3三种资源，在T0时刻P1,P2,P3,P4四个进程对资
源的占有和需求情况如表1，此时系统的可用资源向量为（2，1，2），问题： 1）将系统中各种资源总数和此刻各进程对资源的需求数目用向量或矩阵表示出来。 2）如果此时P1和P2均发出资源请求向量Request(1,0,1)，为了保证系统的安全性，应如何分配资源给这两个进程？说明你所采用策略的原因。
3）如果2)中两个请求立即得到满足后，系统此刻是否处于死锁状态。
第 33 页 共 35 页
P1 P2 P3 P4 最大资源需求量 R1 3 6 3 4 R2 2 1 1 2 R3 2 3 4 2 已分配资源数量 R1 1 4 2 0 R2 0 1 1 0 R3 0 1 1 2 （8分）
1）资源总数[ 9，3，6 ] P1 P2 P3 P4 need R1 2 2 1 4 R2 0 0 0 2 R3 0 2 3 0 2）先满足p2，应为如果现在满足p1系统会进入不安全状态，而满足p2则保持安全状态。（详细安全检测过程略）
3）系统此刻不处于死锁状态。但已经处于不安全状态，在后续的资源分配后，系统会进入死锁。
16. （8分）设有两个优先权相同的进程P1,P2如下,令信
进程P2 号量S1,S2的初值均为0,已知Z=2,试问P1,P2执行进程P1 结束后,X=?,Y=?,Z=? ①Y:=1; ⑤X:=1; 解：（8分）
②Y:=Y+Z; ⑥X:=X+1; ①、②、⑤和⑥是不相交语句，可以任何次序交错执
P(S1); 行，而结果是唯一的。接着无论系统如何调度进程并V(S1); 发执行，当执行到语句⑦时，可以得到x=5，y=3。 ③Z:=Y+1; ⑦X:=X+Y; …………………（2分） P(S2); V(S2); 按Bernstein条件，语句③的执行结果不受语句⑦的影
④Y:=Z+Y; ⑧Z:=X+Z; 响，故语句③执行后得到z=4。最后，语句④和⑧并发执行，这时得到了两种结果为： 语句④先执行：x=5，y=7，z=9。 语句⑧先执行：x=5，y=12，z=9。
此外，还有第三种情况，语句③被推迟，直至语句⑧后再执行，于是依次执行以下三个语句：z:= x + z； z:=y+1; y:=z+y;
这时z的值只可能是y+1=4，故y=z+y=4+3=7，而x=5。 第三种情况为：x=5，y=7，z=4。
…………………（任意答对1个给3分，任意2个给6分）
第 34 页 共 35 页
17. （6分）某系统当前有同类资源10个，进程P、Q、
R所需资源总数分别为8、4、9。它们向系统申请资源的次序和数量如图所示，问： 1）系统采用银行家算法分配资源，请给出系统完成第6次分配后各进程的状态及所占资源量。（4分） 2）在以后各次的申请中，哪次的申请要求可以先得到满足？（2分）
次序 1 2 3 4 5 6 7 进程 R P Q P R Q R 申请量 2 4 2 2 1 2 3 2 3 解：（6分） 8 P 1)（3分） 9 R max need allocation available 进程 R 9 7 2 4 P 8 4 4 4 0 0 Q(完成) 2)（3分） 第8次的申请可以得到满足，即 P进程申请资源2个。
第 35 页 共 35 页