1.     下面关于死锁问题的叙述哪些是正确的, 哪些是错误的, 说明原因.         (1) 参与死锁的所有进程都占有资源;         (2) 参与死锁的所有进程中至少有两个进程占有资源;         (3) 死锁只发生在无关进程之间; (4) 死锁可发生在任意进程之间. 答：说法（1）是错误的，应该是参与死锁的所有进程都等待资源。 说法(2)正确。 参与死锁的进程至少有两个，设为p1,p2，p1占有资源r1而等待资源r2，p2占有资源r2而等待资源r1。 说法(3)错误。死锁也可能发生在相关进程之间。 说法(4)正确，死锁既可能发生在相关进程之间，也可能发生在无关进程之间。即死锁可发生在任意进程之间。 2.     试证明当每个资源类中仅有一个资源实例时，资源分配图中的环路是死锁的充要条件。 证明：先证明充分条件： 用反证法，假设每个资源类中仅有一个资源实例时，资源分配图的环路是可约简的，那么说明环路外至少有一个非孤立且没有请求边的进程节点pk占有一个资源类rk中的一个实例,而rk中的另外一个实例被环路中某个进程占有。说明rk中有两个以上的资源实例，与前提矛盾。所以说，每个资源类中仅有一个资源实例时，资源分配图的环路是不可约简的，根据死锁定理，得出结论每个资源类中仅有一个资源实例时，资源分配图若存在环路就产生死锁。    再证明必要条件：若死锁产生，则存在一个循环等待进程序列<p1,p2,p3……pn>,进程p1正等待资源类rk1中唯一的一个实例，而rk1又被进程p2所占用；进程p2正等待资源类rk2中唯一的一个实例，而rk2又被进程p3所占用；……; 进程pn正等待资源类rkn中唯一的一个实例，而rkn又被进程p1所占用。能看出，画出的资源分配图存在环路。 3.     什么叫饥饿？什么叫饿死？什么叫活锁？举例说明之． 答：在一个动态系统中，资源请求与释放是经常性发生的进程行为．对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。 资源分配策略可能是公平的(fair)，能保证请求者在有限的时间内获得所需资源；资源分配策略也可能是不公平的(unfair)，即不能保证等待时间上界的存在。 在后一种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待．当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。在忙式等待条件下发生的饥饿，称为活锁． 考虑一台打印机分配的例子，当有多个进程需要打印文件时，系统按照短文件优先的策略排序，该策略具有平均等待时间短的优点，似乎非常合理，但当短文件打印任务源源不断时，长文件的打印任务将被无限期地推迟，导致饥饿以至饿死。 4.     死锁与饿死之间有何相同点和不同点? 答：饿死与死锁有一定联系：二者都是由于竞争资源而引起的，但又有明显差别，主要表现在如下几个方面： (1) 从进程状态考虑，死锁进程都处于等待状态，忙式等待(处于运行或就绪状态)的进程并非处于等待状态，但却可能被饿死； (2) 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时限没有上界(排队等待或忙式等待)； (3) 死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁存在与否，但却不能检测是否有进程饿死； (4) 死锁一定涉及多个进程，而饥饿或被饿死的进程可能只有一个。 饥饿和饿死与资源分配策略(policy)有关，因而防止饥饿与饿死可从公平性考虑，确保所有进程不被忽视，如FCFS分配算法。 5.     何谓银行家算法的保守性? 举例说明之. 答：银行家算法的保守性是指银行家算法只给出了进程需要资源的最大量，而所需资源的具体申请和释放顺序仍是未知的，因而银行家只能往最坏处设想． 例如：书中举例p119页。例5.5。 6.     能否给出避免死锁的充要性算法? 为什么? 答：目前关于避免死锁的算法，如银行家算法是充分性算法，即确保系统时刻处于安全状态，这是在系统已知每个进程所需资源最大量的条件下可以给出的最好结果。如果系统不仅知道每个进程所需资源的最大量，而且知道进程有关资源的活动序列，在这个更强的条件下，则可以给出避免死锁的充要性算法（读者可以证明），但其复杂度是很高(NP完全)的。而且由于程序中分支和循环的存在，事先给出进程有关资源的命令序列一般是不可能的。 7. 设有一个Ｔ型路口, 其中A、B、C、D处各可容纳一辆车，车行方向如下图所示，试找出死锁并用有序分配法消除之. 要求资源编号合理. 解：(1)E方向两台车分别位于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 ：直行 P(s1); // 按序申请 P(s4); 驶入 D; 驶入 C; V(s4); 驶出 C; V(s1);     E ：左转 P(s2); 驶入 B; P(s3) ； 驶入 A; V(S2) P(s4) ； 驶入 D; V(s3) ； 驶出 D; V(s4);     S ：左转 P(s1); 驶入 C; P(s2) ； 驶入 B; V(S1) P(s3) ； 驶入 A; V(s2) ； 驶出 A; V(s3); 8. 设系统中仅有一个资源类, 其中共有M个资源实例, 使用此类资源的进程个数共有N个, 它们所需资源最大量总和为S, 试证明发生死锁的必要条件是S³M+N. 答：证明：假定发生死锁，那么Alloc(1)+Alloc(2)+…+Alloc(N)=M，(Alloc(i)表示第i进程已分配的资源量)。Need(1)+Need(2)+…Need(N) ³N。（Need(i)表示第i进程还需要的资源量) 所以，发生死锁时，所有进程所需资源的总量³SM+N。 9. 在银行家算法中，若出现如下资源分配情况：         Allocation           Need           Available                A B C D      A B C D      A B C D      P0: 0 0 3 2      0 0 1 2      1 6 2 3          P1: 1 0 0 0      1 7 5 0          P2: 1 3 5 4      2 3 5 6          P3: 0 3 3 2      0 6 5 2          P4: 0 0 1 4      0 6 5 6 试问：(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） 4）如果对于所有i，Finish[i] = true，则系统处于安全状态，否则处于不安全状态。 　令Work = Available=（1, 6, 2, 3） 运行安全性检测算法，Finish[0]=false并且Need[0]=(0 0 1 2)<Work, 则Work = Work + Allocation[0]=（1, 6, 2, 3）+（0, 0, 3, 2）=（1, 6, 5, 5）；Finish[0] = true； Finish[3]=false并且Need[3]=（0, 6, 5, 2）<Work, 则Work = Work + Allocation[3]=（1, 6, 5, 5）+（0, 3, 3, 2）=（1, 9, 8, 7）；Finish[3] = true； Finish[4]=false并且Need[4=（0, 6, 5, 6）<Work, 则Work = Work + Allocation[4]=（1, 9, 8, 7）+（0, 0, 1, 4 ）=（1, 9, 9, 11）；Finish[4] = true； Finish[1]=false并且Need[1]=（1, 7, 5, 0）<Work, 则Work = Work + Allocation[4]=（1, 9, 9, 11）+(1, 0, 0, 0 )=(2, 9, 9, 11)；Finish[1] = true； Finish[2]=false并且Need[2]=（2, 3, 5, 6）<Work, 则Work = Work + Allocation[4]=（2, 9, 9, 11）+（1, 3, 5, 4 ）=（3, 12, 14, 15）；Finish[2] = true； 可以找到一个安全进程序列<p0 ，p3 ，p4 ，p1 ,p2>，它使Finish=true，对于所有0≤i≤4，因而可以断言系统当前处于安全状态． （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           Need           Available                A B C D      A B C D      A B C D      P0: 0 0 3 2      0 0 1 2      0 4 0 1          P1: 1 0 0 0      1 7 5 0          P2: 2 5 7 6      1 1 3 4          P3: 0 3 3 2      0 6 5 2          P4: 0 0 1 4      0 6 5 6 运行安全性检测算法，Work=Available=（0, 4, 0, 1），Finish=false，此时所有Need£Work均不成立，结果Finish[i[均为false，不存在安全进程序列，系统处于不安全状态。系统将取消资源分配并恢复原来状态，进程p2等待。 10．某系统采用死锁检测手段发现死锁，设系统中资源类集合为{A，B，C}，资源类A中共有8个实例，资源类B中共有6个实例，资源类C中共有5个实例．又设系统中进程集合为{p1,p2,p3,p4,p5,p6}, 某时刻系统状态如下：        Allocation       Request         Available          A   B   C       A   B   C        A   B   C p1:    1   0   0       0   0    0       2    2   1 p2:    3   2   1       0   0    0 p3:    0   1   2       2   0    2 p4:    0   0   0       0   0    0 p5:    2   1   0       0   3    1 p6:    0   0   1       0   0    0 (1)    在上述状态下系统依次接受如下请求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；   Request[4]=(0,0,2)．给出系统状态变化情况，并说明没有死锁． 答：如果系统只是接受请求，但是没有分配资源给进程，那么系统状态变为： Allocation   Request   Available A B C      A B C    A B C p1:   1 0 0      1 0 0    2 2 1 p2:   3 2 1      2 1 0 p3:   0 1 2      2 0 2 p4:   0 0 0      0 0 2 p5:   2 1 0      0 3 1 p6:   0 0 1      0 0 0 在该状态下运行死锁检测算法，可以找到一个进程序列<p4,p1,p2,p3,p5,p6>，它使Finish=true，对于所有1≤i≤6，因而可以断言系统当前没有进入死锁状态。 (2)    在由(1)所确定的状态下系统接收如下请求：Request[1]=(0,3,1)，说明此时已发生死锁，并找出参与死锁的进程． 答：设在（1）的状态下系统接收如下请求：Request[1]=(0,3,1)，则系统状态变为： Allocation Request Available A B C     A B C   A B C p1:     2 0 0     0 3 1   1 2 1 p2:     3 2 1     2 1 0 p3:     0 1 2     2 0 2 p4:     0 0 0     0 0 2 p5:     2 1 0     0 3 1 p6:     0 0 1     0 0 0 在该状态下运行死锁检测算法，找不到一个进程序列使Finish=true，对于所有1≤i≤6，因为存在i∈{1，2，3，5}，使Finish=false，因而可以断言系统已经进入死锁状态，进程p1,p2,p3,p5卷入死锁． 11. 设有7个简单资源: A、B、C、D、E、F、G。 其申请命令分别为a、b、c、d、e、f、g; 释放命令分别为 a-、b-、c-、d-、d-、f-、g-; 又设系统中有P1、P2、P3三个进程，其活动分别为:       P1活动: a b a- b- e f g e- f- g-       P2活动: b c b- c- d a d- a- P3活动: c d c-d- e g f e- f- g- 试分析当P1、P2、P3并发执行时，是否有发生死锁的可能性，并说明原因。 解：不会有发生死锁的可能性。 在本题中，进程p1和p2都使用的资源集合是{a,b}，由于进程p2在申请a之前已经释放了b，不存在占有b并且申请a的情况，所以进程p1和p2之间不满足死锁的四个必要条件，不会产生死锁； 进程p1和p3都使用的资源集合是{e,f,g}，进程p1和p3都是先申请资源e，这两个进程同时申请资源，那么只能有一个进程先获得e，另一个进程将因为得不到e而阻塞，获得e的进程将进一步顺利获得资源f和g，从而运行结束，释放资源e,f和g，唤醒另一个进程运行。可见，进程p1和p3之间不会产生死锁； 进程p2和p3都使用的资源集合是{c,d}，由于进程p2在申请d之前已经释放了c，不存在占有c并且申请d的情况，所以进程p2和p3之间不满足死锁的四个必要条件，不会产生死锁。 综上所述，当P1、P2、P3并发执行时，没有发生死锁的可能性。