【操作系统】死锁
Chapter 7死锁
一、基本概念
1、死锁：指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进
2、死锁产生的必要条件：
（1）互斥
（2）占有并等待
（3）不可抢占
（4）循环等待
3、资源分配图
请求边是进程出发的箭头指向资源，反过来是分配边。
（1）没有环，没有死锁
（2）有环：①每种类型的资源只有一个实例，有死锁②每种类型的资源有不止一个实例，可能死锁
（3）"死锁定理"：S为死锁状态的充分条件是当且仅当S的资源分配图不可完全简化。
二、处理策略
1、预防、避免
（1）prevention：破坏四个条件中的一个。例如静态分配、按序分配等。
（2）avoidance
①资源分配图算法
a、需求边（claim edge）：虚线箭头。表示进程可能会请求某个资源。
b、请求边（request edge）：表示进程请求一个资源。
c、分配边（assignment edge）表示进程占有了一个资源。
d、算法步骤：
step1 假设进程Pi申请资源Rj。只有在需求边P i -> R j 变成分配边 R j ->P i 而不会导致资源分配图形成环时，才允许申请。
step2用算法循环检测，如果没有环存在，那么资源分配会使系统处于安全状态。如果存在环，资源分配会使系统不安全。进程Pi必须等待。
②银行家算法
a、数据结构：
1）available：长度m的向量，available[i]=k表示Ri类资源有k个可用
2）max：n x m matrix, if Max [i,j] = k, then process P i may request at most k instances of resource type R j
3）allocation：n x m matrix. If Allocation[i,j] = k then P i is currently allocated k instances of R j
4）need：n x m matrix. If Need[i,j] = k, then P i may need k more instances of R j to complete its task. Need [i,j] = Max[i,j] – Allocation [i,j]
b、辅助方法——安全检测
（1）需要work和finish两个向量，work=available， finish每一项都是false
（2）若finish[i]=false且need[i]<=work，goto （3）；如果这样的i不存在，goto（4）
（3）finish=true，work=work+allocation goto （2）
（4）如果发现所有finish[i]=true，系统安全
c、Resource-Request Algorithm
2、检测、恢复
（1）检测（detection）
①基本概念：
wait-for graph， pi->pj表示pi等pj。可以由资源分配图得到wait-for graph：
②数据结构
available、allocation、request、work、finish
③算法步骤
step1 Let Work and Finish be vectors of length m and n,respectively Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocation i<>0, then Finish[i] = false;otherwise, Finish[i] = true.
step2 Find an index i such that both:(a) Finish[i] == false (b) Request i<=Work
If no such i exists, go to step4.
step3 Work = Work + Allocation i
Finish[i] = true ，go to step 2.
step 4 If Finish[i] == false, for some i, 1<=i<= n, then the system is in deadlock state. Moreover, if Finish[i] == false, then P i is deadlocked.
Algorithm requires an order of O(m x n 2) operations to detect whether the system is in deadlocked state.
一些例题：
1、A system has 3 concurrent processes, each of which requires 4 items of resource R. What is the minimum number of resource R in order to avoid the deadlock.（10）
2、Assume that a system has 9 instances of 1 resource type shared by 4 processes. How many resource instances can a process be allowed to request in order to avoid deadlock?（3）
解：满足进程数*（申请数-1）<总资源数，即4（x-1）<9，则x最大取3
3、There are N processes which share M mutual exclusive resources, each process can hold W resources at most. Which of the following condition may cause a deadlock?
A、M=4,N=2,W=3
B、M=2,N=2,W=1
C、M=4,N=3,W=2
D、M=2,N=1,W=2
(选A。只有A不满足N*(W-1)<M)
————————————————————————（更新）
补充一些题：
（1）假设系统配有相同类型的m个资源，系统中有n个进程，每个进程至少请求一个资源(最多不超过m)。请证明，当n个进程最多需要的资源数之和小于(m+n)时，该系统不会发生死锁。
证明：设N个进程请求的最大资源量分别为xi，i＝1，2,…n。根据条件 ∑xi＜m+n, 从而 ∑(xi-1)＜m, ∴∑(xi-1)+1＜=m．资源申请最坏的情况是每个进程已得到了(xi-1)个资源，现均要中请最后一个资源，由上式可知系统至少还有一个剩余资源可分配给某个进程，待它归还资源后就可供其他进程使用，因此该系统不会发生死锁。
（2）可以证明，M个同类资源被N个进程共享时，若x为每个进程能够申请资源的最大量，当不等式_____成立时一定不会发生死锁。
解：N(x-1)+1<=M