文章目录
1、死锁问题
\qquad
首先以一个生活中的例子为例，如下图所示，假设有一座桥，而通过桥的通道只有一条。
\qquad
当桥的两侧都有车辆需要通过时，由于流量只能在一个方向，所以会发生谁也不能过桥的情况。这种情况与死锁的情形十分类似，如果发生死锁，可以通过一辆车倒退来解决问题(抢占资源和回滚)，多数情况下发生死锁可能需要多辆和都一起倒退，这样就由可能导致桥的某一侧的车辆发生饥饿现象。
\qquad
死锁定义： 一组阻塞的进程持有一种资源等待获取另一个进程所占有的一个资源。i.e., 系统中有两个磁带驱动器，程序P1和程序P2各自占有一个，并且都需要另外一个时，就会发生死锁问题。死锁问题发生的原因在于程序都是并发执行的，各个程序都可以去抢占资源而导致死锁问题。
2、系统模型
\qquad
在介绍系统模型之前首先介绍资源的相关概念，资源的类型包括：
R
1
,
R
2
,
.
.
.
,
R
m
R_1, R_2, ..., R_m
R1,R2,...,Rm，i.e., CPU cycles, memory, I/O devices；每个资源类型
R
i
R_i
Ri都有
W
i
W_i
Wi个实例。
\qquad
可重复使用的资源： 在一个时间只能一个进程使用且不能被删除；进程获得资源，后来释放由其他进程重复使用；处理器，I/O通道，主和副存储器，设备和数据结构，如文件，数据库和信号量；如果每个进程拥有一个资源并请求其他资源，死锁可能发生。
\qquad
资源分配图: 一组顶点
V
V
V和边
E
E
E的集合；其中
V
V
V包括以下两种类型：
{
P
=
{
P
1
,
.
.
.
,
P
n
}
,
集
合
包
括
系
统
中
所
有
进
程
R
=
{
R
1
,
.
.
.
,
R
n
}
,
集
合
包
括
系
统
中
所
有
的
资
源
类
型
\begin{cases} P=\{P_1,...,P_n\},\qquad 集合包括系统中所有进程\\ R=\{R_1,...,R_n\},\qquad集合包括系统中所有的资源类型 \end{cases}
{P={P1,...,Pn},集合包括系统中所有进程R={R1,...,Rn},集合包括系统中所有的资源类型
\qquad
所以边
E
E
E也包括两种类型：
{
r
e
q
u
e
s
t
i
n
g
/
c
l
a
i
m
i
n
g
e
d
g
e
,
−
d
i
r
e
c
e
t
e
d
e
d
g
e
P
i
→
R
j
a
s
s
i
g
n
m
e
n
t
/
h
o
l
d
i
n
g
e
d
g
e
,
−
d
i
r
e
c
e
t
e
d
e
d
g
e
R
j
→
P
i
\begin{cases} requesting/claiming edge,\quad-direceted edge\ P_i→R_j\\ assignment/holding edge,\quad-direceted edge\ R_j→P_i \end{cases}
{requesting/claimingedge,−direcetededge Pi→Rjassignment/holdingedge,−direcetededge Rj→Pi
\qquad
下图没有死锁现象，因为当进程
P
3
P_3
P3使用完资源
R
3
R_3
R3之后，进程
P
2
P_2
P2便可以执行，之后进程
P
1
P_1
P1也可以进行执行。
\qquad
下图会产生死锁的情况，应为进程和资源之间形成了环路，互相等待对方释放资源，会产生死锁。
\qquad
下图不会产生死锁现象，因为进程
P
2
P_2
P2和进程
P
4
P_4
P4执行完毕释放资源
R
1
R_1
R1和
R
2
R_2
R2之后进程
P
1
P_1
P1和
P
3
P_3
P3便可以继续执行。
\qquad
通过上述可以总结出：如果图中不包括循环，则不会产生死锁；如果图中包括循环，则分为以下两种情况讨论：如果每一个资源类只有一个实例，则会产生死锁；如果每个资源类包括多个实例，则可能产生死锁。
3、死锁特征
\qquad
死锁可能出现的的四个必要条件：
\qquad
互斥： 在一个时间只能有一个进程使用资源；
\qquad
持有并等待： 进程保持至少一个资源正在等待获取其他进程持有的额外资源；
\qquad
无抢占： 一个资源只能被进程自愿释放，进程已经完成了它的任务之后；
\qquad
循环等待： 存在等待进程集合
P
0
,
P
1
,
.
.
.
,
P
n
{P_0,P_1,...,P_n}
P0,P1,...,Pn，
P
0
P_0
P0正在等待
P
1
P_1
P1所占用的资源，
P
1
P_1
P1正在等待
P
2
P_2
P2所占用的资源，…，
P
n
−
1
P_{n-1}
Pn−1正在等待
P
n
P_n
Pn所占用的资源。
4、死锁处理方式
\qquad
死锁处理方法包括以下四种：
\qquad
DeadLock Prevention-死锁预防
\qquad
DeadLock Avoidance-死锁避免
\qquad
DeadLock Detection-死锁检测
\qquad
Recory from DeadLock-死锁恢复
4.1 死锁预防
\qquad
死锁预防的方法就是针对上述死锁特征的四个必要条件，只要破坏其中一个条件，就构不成死锁。
\qquad
当破坏条件1时，使资源不互斥的话，那不能满足多进程同时处理同一个资源的准确性要求；
\qquad
当破坏条件2时，使得进程持有所有需要的资源再执行或者直接不执行，这样处理会使得资源利用率很低，造成饥饿现象；
\qquad
当破坏条件3时，某个新的进程需要某个旧的进程占用的资源时，直接让只占用没使用的旧进程释放掉资源，这样也会产生一定的饥饿现象；
\qquad
当破坏条件4时，只要将所有资源类型今次那个排序，并要求每个进程按照资源的顺序进行申请，则可以避免出现环路，但是也会造成一定的资源浪费和额外的排序开销。
4.2 死锁避免
\qquad
系统在分配给进程资源之前首先判断将资源分配给进程之后是否会产生死锁，如果会产生死锁，则系统不会将资源分配给进程，从而避免死锁的产生。判断是否会产生死锁的方式是判断是否会产生环路，若系统判断将某个资源分配给某个进程之后会形成环路，则系统会认定当前分配为不安全的分配，不会将资源分配给申请资源的进程。
银行家算法
\qquad
银行家算法是一个死锁避免的著名算法，是由Dijkstra在1965年提出的。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
\qquad 银行家算法的前提条件：首先由多个实例；每个进程都必须能最大限度地利用资源；当一个进程请求一个资源，就不得不等待；当一个进程获得所有的资源，就必须在一段有限的时间释放它们。
\qquad
银行家算法的数据结构：
\qquad
n
n
n：表示进程数量；
\qquad
m
m
m：表示资源类型数量；
\qquad
M
a
x
(
总
需
求
量
)
：
Max(总需求量)：
Max(总需求量)：是一个
n
×
m
n×m
n×m矩阵。如果
M
a
x
[
i
,
j
]
=
k
Max[i, j]=k
Max[i,j]=k，表示进程
P
i
P_i
Pi最多请求资源类型
R
j
R_j
Rj的
k
k
k个实例；
\qquad
A
v
a
i
l
a
b
l
e
(
剩
余
空
限
量
)
Available(剩余空限量)
Available(剩余空限量)：
长
度
为
长度为
长度为m
的
向
量
。
如
果
的向量。如果
的向量。如果Available[j]=k
表
示
有
k
个
类
型
为
表示有k个类型为
表示有k个类型为R_j$的资源实例可用；
\qquad
A
l
l
o
c
a
t
i
o
n
(
已
分
配
量
)
Allocation(已分配量)
Allocation(已分配量)：是一个
n
×
m
n×m
n×m矩阵。如果
A
l
l
o
c
a
t
i
o
n
[
i
,
j
]
=
k
Allocation[i, j]=k
Allocation[i,j]=k，表示进程
P
i
P_i
Pi当前分配了
k
k
k个
R
j
R_j
Rj实例；
\qquad
N
e
e
d
(
未
来
需
要
量
)
Need(未来需要量)
Need(未来需要量)：是一个
n
×
m
n×m
n×m矩阵。如果
N
e
e
d
[
i
,
j
]
=
k
Need[i, j]=k
Need[i,j]=k，表示进程
P
i
P_i
Pi当至少需要
k
k
k个
R
j
R_j
Rj实例来完成任务。
N
e
e
d
[
i
,
j
]
=
M
a
x
[
i
,
j
]
−
A
l
l
l
o
c
a
t
i
o
n
[
i
,
j
]
Need[i, j] = Max[i, j]-Alllocation[i, j]
Need[i,j]=Max[i,j]−Alllocation[i,j]
Safety State Estamating Algorithm
- work和Finish分别是长度为 m m m和 n n n的向量
- 初始化：
- w o r k = A v a i l a b l e \qquad work = Available \quad work=Available//当前资源剩余的空限量
- F i n i s h [ i ] = f a l s e f o r i i n { 1 , . . . , n } \qquad Finish[i] = false \ \ for\ \ i\ \ in\ \ \{1,..., n\} Finish[i]=false for i in {1,...,n}//线程i是否可以结 \qquad 束，即表示线程i是否得到全部所需要的资源
- 寻找Need比work小的进程i，其满足以下两个条件：
- \qquad (a) F i n i s h [ i ] = f a l s e Finish[i]=false Finish[i]=false
- \qquad (b) N e e d [ i ] ≤ w o r k Need[i] \leq work Need[i]≤work
- \qquad 若没有这种进程i，则转到 Line 12
- w o r k = w o r k + A l l o c a t i o n [ i ] work=work+Allocation[i] work=work+Allocation[i]
- F i n i s h [ i ] = t r u e Finish[i]=true Finish[i]=true
- 转到 Line 5
- I f F i n i s h [ i ] = = t r u e f o r a l l i , T h e n If \ Finish[i]==true \ for \ all \ i, \ Then If Finish[i]==true for all i, Then
- \qquad the system is in a safe state
- E l s e Else Else
- \qquad The system is not in a safe state//系统处于非安全状态，不应 \qquad 该将资源交给申请的进程
- E n d End End
Banker’s Algorithm
\qquad
初始化：Request=request vector for preocess
P
i
P_i
Pi. If Request[i][j]=k，Then process
P
i
P_i
Piwants k instances of resource type
R
j
R_j
Rj，while:
- 如果 R e q u e s t [ i ] ≤ N e e d [ i ] Request[i] \leq Need[i] Request[i]≤Need[i]，转到步骤2。否则，提出错误条件，因为进程已经超过了其最大需求。
- 如果
R
e
q
u
e
s
t
[
i
]
≤
A
v
a
i
l
a
b
l
e
Request[i] \leq Available
Request[i]≤Available，转到步骤3。否则
P
i
P_i
Pi必须等待，因为资源不可用。
3.通过修改状态来分配请求资源给 P i P_i Pi：生成一个需要判断状态是否安全的资源分配环境：
A v a i l a b l e = A v a i l a b l e − R e q u e s t [ i ] A l l o c a t i o n [ i ] = A l l o c a t i o n [ i ] + R e q u e s t [ i ] N e e d [ i ] = N e e d [ i ] − R e q u e s t [ i ] Available=Available-Request[i] \\ Allocation[i]=Allocation[i]+Request[i] \\ Need[i]=Need[i]-Request[i] Available=Available−Request[i]Allocation[i]=Allocation[i]+Request[i]Need[i]=Need[i]−Request[i] - 调用 Safety State Estamating Algorithm
- 如果返回 safe，则将资源分配给 P i P_i Pi
- 如果返回unsafe， 则 P i P_i Pi必须等待，直到旧的资源分配状态被恢复
4.3 死锁检测
\qquad
这种方法允许系统进入死锁状态，之后通过死锁检测算法将进入死锁状态的进程进行恢复。死锁检测算法的思路和上述Safety State Estamating Algorithm很类似，其算法流程如下所示：
\qquad
下面是一个应用死锁检测算法检测出死锁的例子：
4.4 死锁恢复
\qquad
将所有的死锁进程全部杀死
\qquad
在一个时间内终止一个进程直到死锁结束
\qquad
终止进程的顺序应该是：
- 按照进程的优先级
- 按照进程运行了多久以及需要多少时间才能完成
- 进程占用的资源
- 进程完成需要的资源
- 多少进程需要被终止
- 进程是交互还是批处理
\qquad 还有以一种死锁恢复的方式是资源抢占，选择一个"成本"最小的受害者，之后回滚到一些安全状态。但是会有一定问题，某一个进程可能会一直被选作受害者，造成饥饿现象。