法的。又Request[2]=(0,1)￡Available=(0,1)，故该请求系统当前能够满足。假定分配，系统状态变化如下：
Claim AllocationNeed Available ABABABAB
p1:11100100 p2:110110
运行安全性检测算法发现此时系统处于不安全状态，因而取消分配，p2等待。实际上如果真正实施分配系统并不会进入死锁状态，因为分配后按照p2(),p1(b),p1(),p1(),p2
(b),p2(a),p2(),p2()的次序两个进程可以执行完，这是一个p1和p2交叉执行的次序，而不是一个顺序执行的次序，银行家算法不能判断。
6． 能否给出避免死锁的充要性算法? 为什么?
答：目前关于避免死锁的算法，如银行家算法是充分性算法，即确保系统时刻处于安全状态，这是在系统已知每个进程所需资源最大量的条件下可以给出的最好结果。
如果系统不仅知道每个进程所需资源的最大量，而且知道进程有关资源的活动序列，在这个更强的条件下，则可以给出避免死锁的充要性算法（读者可以证明），但其复杂度是很高(NP完全)的。而且由于程序中分支和循环的存在，事先给出进程有关资源的命令序列一般是不可能的。
7． 设有一个Ｔ型路口，其中A、B、C、D处各可容纳一辆车，车行方向如下图所示，试
找出死锁并用有序分配法消除之。要求资源编号合理。
W：直行-> A D B C <- E：左转 /\\ | S:左转 解：(1)Ｅ方向两台车分别位于A和B；S方向一台车位于C；W方向一台车位于D。(2)S方向两台车分别位于B和C；E方向一台车位于A；W方向一台车位于D。
设位置资源C、B、A、D的编号从低到高依次为1、2、3、4，管理四个位置的信号量分别为s1,s2,s3,s4，信号量的初值均为1。车辆活动如下： semaphore s1=1,s2=1,s3=1,s4=1; W：直行
E：左转 S：左转 31
P(s1); //按序申请 P(s4); 驶入D; 驶入C; V(s4); 驶出C; V(s1); P(s2); 驶入B; P(s3)； 驶入A; V(S2) P(s4)； 驶入D; V(s3)； 驶出D; V(s4); P(s1); 驶入C; P(s2)； 驶入B; V(S1) P(s3)； 驶入A; V(s2)； 驶出A; V(s3); 8． 设系统中仅有一个资源类，其中共有M个资源实例，使用此类资源的进程个数共有N
个，它们所需资源最大量总和为S，试证明发生死锁的必要条件是S3M+N。
证明：假定发生死锁，且参与死锁的进程个数为n(2￡n￡N)，参与死锁的n个进程已经占有系统中全部M个资源实例，而还没够(因它们处于无限期等待状态)，每个进程至少还需要一个资源实例，因而参与死锁进程所需要资源总量3M＋n。每个未参与死锁进程至少需要一个资源实例(若不需要则不属于N集合中，它们没有参与死锁是因为它们在得到并使用完资源后已经将其释放)，由于共有N-n个未参与死锁的进程，它们所需资源总量3N-n。由此可知，全部进程所需要的资源总量S3(M+n)+(N-n)=M+N。
9． 在银行家算法中，若出现如下资源分配情况：
Allocation NeedAvailable ABCDABCDABCD P0:003200121623 P1:10001750 P2:13542356 P3:03320652 P4:00140656
试问：(1)当前状态是否安全？
(2)如果进程P2提出安全请求Request[2]=(1,2,2,2),系统能否将资源分配给它？说明原因．
解：（1）当前状态是安全状态。 运行安全性检查算法如下：
1）Work = Available；Finish = false； 2）寻找满足如下条件的i:
Finish[i]==false并且Need[i]≤Work[i]； 如果不存在，则转步骤4）；
3）Work = Work + Allocation[i]；Finish[i] = true； 转步骤2）
32
4）如果对于所有i，Finish[i] = true，则系统处于安全状态，否则处于不安全状态。 令Work = Available=（1, 6, 2, 3）
运行安全性检测算法，Finish[0]=false并且Need[0]=(0 0 1 2)
（2）运行银行家算法，由于Request[2]=（1, 2, 2, 2）￡Need[2]=（2, 3, 5, 6），因而请求合法。进一步，Request[2]=（1, 2, 2, 2）￡Available=（1, 6, 2, 3），故该请求是可以满足的。假设将资源分配给p2，则系统状态变为: Allocation NeedAvailable ABCDABCDABCD P0:003200120401 P1:10001750 P2:25 761134 P3:03320652 P4:00140656
运行安全性检测算法，Work=Available=（0, 4, 0, 1），Finish[i]=false，此时所有Need[i]￡Work[i]均不成立，结果Finish[i]均为false，不存在安全进程序列，系统处于不安全状态。系统将取消资源分配并恢复原来状态，进程p2等待。
10． 某系统采用死锁检测手段发现死锁，设系统中资源类集合为{A，B，C}，资源类A中共有8个实例，资源类B中共有6个实例，资源类C中共有5个实例．又设系统中进程集合为{p1,p2,p3,p4,p5,p6}，某时刻系统状态如下： Allocation RequestAvailable ABCAB CA B C
p1: 10 000 02 2 1 p2: 3 2 10 0 0 p3: 0 1220 2 p4: 00000 0 p5: 21003 1 p6: 00100 0
11． 在上述状态下系统依次接受如下请求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；Request[4]=(0,0,2)。给出系统状态变化情况，并说明没有死锁。在由(1)所确定的状态下系统接收如下请求：Request[1]=(0,3,1)，说明此时已发生死锁，并找出参与死锁的进程。
33
解：（1）①如果系统只是接受请求，但是没有分配资源给进程，那么系统状态变为： Allocation RequestAvailable ABCAB CA B C
p1: 10 010 02 2 1 p2: 3 2 12 1 0 p3: 0 1220 2 p4: 00000 2 p5: 21003 1 p6: 0 0100 0
在该状态下运行死锁检测算法，可以找到一个进程序列
p1: 20 00 0 012 1 p2: 3 2 12 1 0 p3: 0 1220 2 p4: 00000 2 p5: 21003 1 p6: 00100 0
在该状态下运行死锁检测算法，可以找到一个进程序列
p1: 10 013 12 2 1 p2: 3 2 12 1 0 p3: 0 1220 2 p4: 00000 2 p5: 21003 1 p6: 00100 0
在该状态下运行死锁检测算法，可以找到一个进程序列
34
ABCAB CA B C
p1: 20 003 11 2 1 p2: 3 2 12 1 0 p3: 0 1220 2 p4: 00000 2 p5: 21003 1 p6: 00100 0
在该状态下运行死锁检测算法，找不到一个进程序列使Finish[i]=true，对于所有1≤i≤6，因为存在i∈{1，2，3，5}，使Finish[i]=false，因而可以断言系统已经进入死锁状态，进程p1,p2,p3,p5卷入死锁． 六、 存储管理习题及解答:
1．考虑下述存储管理方式中，进程空间和逻辑空间的编址情况： （1）界地址存储管理方式，进程空间的首地址； （2）页式存储管理，进程空间的首地址； （3）段式存储管理，进程空间各段的首地址； （4）段页式存储管理，进程空间各段的起始地址。
答：（1）界地址存储管理方式，进程空间的首地址从0开始编址；（2）页式存储管理，进程空间的首地址从0开始编址；（3）段式存储管理，进程空间各段的首地址从0开始编址；（4）段页式存储管理，进程空间各段的起始地址从0开始编址。
2．对于如下存储管理方式来说，进程地址空间各是几维的？
（1）页式；（2）段式；（3）段页式
答：（1）页式存储管理中，进程地址空间是一维的；（2）段式存储管理中，进程地址空间是二维的；（3）段页式存储管理中，进程地址空间是二维的。
3．在页式存储管理中，页的划分对用户是否可见？在段式存储管理中，段的划分对用户
是否可见？在段页式存储管理中，段的划分对用户是否可见？段内页的划分对用户是否可见？
答：(1)在页式存储管理中，分页对于用户是透明的，一个进程由若干个页构成，所有页的长度相同；(2)在段式存储管理中，分段对于用户是可见的，一个进程由若干个段构成，各个段的长度可以不同，一个段恰好对应一个程序单位；(3)在段页式存储管理中，段的划分对用户是可见的，段内页的划分对用户是透明的，一个段由若干个页构成，所有页的长度相同。
4．为什么空闲页面链适合管理内存空间，而不适合管理外存空间？
35