?? 重点篇
文章目录
Banker’s algorithm 🏦
上一篇文章地址链接: 【操作系统⑨】——进程间通信的概述【kill() signal() shmget() shmat() 实例 共享存储通信 消息通信 管道通信 】.
下一篇文章地址链接: 正在施工中… 🚧 🚧
一、进程死锁的概念与条件
1.1 死锁定义
??● 背景：多道进程的并发执行可以改善系统的资源利用率，但也可能出现——“进程相互等待对方释放资源才能继续运行”的情况。
??● 死锁：系统中多个进程无限期地等待永远不会满足的条件，处于停滞状态，称为进程死锁。
1.2 死锁的典型场景
??● 申请同类资源：内存资源有 m 个分配单位，然而有 n(n>m) 个进程共享内存资源，进程每次只能申请一个单位满足总量才能使用，且每个进程使用完才一次性释放资源。（假如说，在一个神奇餐厅，有 2 根筷子，此时有 3 个人进来吃饭。①号老哥和②号小姐姐都需要用两根筷子才能吃饭，而③号小老弟只需要一根筷子就能吃饭。然后，他们三去“抢占”资源，如果出现这种情况——“①号和②号分别抢到一根筷子，③号没抢到”，则导致死锁）
??● 申请不同类资源：（假设在办公室里有一把扫把和一个簸箕。然后有两个不同班级的同学来拿“资源”去打扫各自教室的卫生。假如说每个同学一次只能拿走一个东西到各自教室，到教室后需要同时有扫把和簸箕才能开始打扫）
进程P1(): | 进程P2():
... | ...
申请用扫把 | 申请用簸箕
申请用簸箕 | 申请用扫把
clean(P1的教室) | clean(P2的教室)
释放簸箕 | 释放扫把
释放扫把 | 释放簸箕
... | ...
??● 说明：若 “P1” 拿了扫把后。不一会儿，“P2” 又把簸箕拿走了。这时就会导致死锁。两位同学就会在办公室里面傻傻地等着对方释放“资源”。
1.3 死锁的必要条件
??① 互斥使用(资源独占)：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
??② 不可强占(不可剥夺)：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
??③ 请求保持(部分分配，占有申请)：进程在申请新资源的同时保持对原有资源的占有。
??④ 循环等待(环路等待条件)：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合 {P0，P1，P2，···，Pn} 中的 P0 正在等待一个 P1 占用的资源；P1 正在等待 P2 占用的资源，……，Pn 正在等待已被 P0 占用的资源。
??● 理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和解除死锁。所以，在系统设计、进程调度等方面注意如何能够不让这四个必要条件成立，如何确定资源的合理分配算法，避免进程永久占据系统资源。
二、进程死锁的预防机制
2.1 机制原理
??● 预先确定资源分配，保证不发生死锁，通过破坏死锁 4 个必要条件之一来实现，但破坏 “互斥使用” 这一必要条件不现实。所以一般破坏其他 3 个。
2.2 解决方案
??① 破坏“不可剥夺”：
????<1> 允许进程动态申请资源
????<2> 进程在申请新资源不能得到满足而变为等待状态之前，必须释放已占有的资源
????<3> 若需要资源必须重新申请
??② 破坏“请求保持”：
????<1> 不允许进程动态申请资源
????<2> 进程运行前须一次性申请所需的所有资源
????<3> 进程所要资源均可满足时给予一次性分配
??（有缺陷 举例子：比如说，5 个大妈在河边洗衣服，资源区一共有 1 包洗衣粉、 5 个木桶、5 根打衣棒、5 个水坑位、5 个搓衣板。如果说1 位大妈同时需要 “ 1 个水坑位、 1 包洗衣粉、2 个木桶、1 个打衣棒、1 个搓衣板” 才能开始洗衣服，然后一次性申请这么多资源，只有当这位大妈洗完后才能释放资源。→→→ 这样就会导致资源利用率下降，因为这里只有 1 包洗衣粉，而大妈使用洗衣粉也就 10多秒，倒一些出来就完事，没必要一直占用者）
??③ 破坏“循环等待”：
????<1> 采用资源有序分配法
????<2> 对系统中所有资源进行编号
????<3> 进程须严格按资源编号的递增次序申请资源
????<4> 违反上述规则操作系统不予分配
??（这个主要是预防前面说的——“两个同学拿扫把簸箕打扫教室卫生”的死锁情况，但这个也可能导致资源利用率的下降）
三、进程死锁的避免机制
3.1 机制原理
??● 对进程发出的每一个资源申请进行动态检查，根据检查结果决定是否分配资源，若试分配后可能发生死锁，则不予分配，否则分配。
3.2 银行家算法(Dijkstra在1965年提出) ??????
??● 银行家算法是著名的死锁避免算法：这是一个银行家给多个顾客分发贷款的算法，可以类比到操作系统给进程分配资源。这时只要把银行家换成操作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。
????① 银行家拥有一笔周转资金
????② 客户要求分期贷款，如果能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
????③ 银行家应谨慎地贷款，防止出现坏账
????④ 银行家采用的具体方法是看是否有足够的剩余资金满足某一客户，如此反复下去
????⑤ 如果所有投资最终都被收回，则请求可以批准
3.2.1 安全状态
??● 为了描述银行家算法，下面先介绍一下系统的安全状态的概念：
????① 若在某一时刻，系统能按某种进程顺序，如
{
P
1
，
P
2
，
…
，
P
n
}
\{P_1，P_2，…，P_n\}
{P1?，P2?，…，Pn?} 为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成，则称此时系统的状态为安全状态。称这样的一个进程序列
{
P
1
，
P
2
，
…
，
P
n
}
\{P_1，P_2，…，P_n\}
{P1?，P2?，…，Pn?} 为安全序列。
????② 安全序列的实质：序列中的每一个进程
P
i
(
i
=
1
,
2
,
…
,
n
)
P_i(i= 1 ,2,… ,n)
Pi?(i=1,2,…,n) 到运行完成尚需的资源量 ≤ 系统当前剩余的资源量 + 所有在序列中排在它前面的进程当前所占有的资源量。
????③ 若在某一时刻，系统中不存在一个安全序列，则称系统处于不安全状态。
??◆ 需要注意：
????① 系统在某一时刻的安全状态可能不唯一，但这不影响对系统安全性的判断。
????② 安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅是可能进入死锁状态。
3.2.2 算法实质与思想
??● 银行家算法的实质：设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。
??● 银行家算法的程序思想：
????① 系统中的所有进程进入进程集合。
????② 在安全状态下系统收到进程的资源请求后，先把资源试探性地分配给它。
????③ 系统用剩下的可用资源和进程集合中其他进程还需要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程，从而，保证这个进程运行完毕后并能归还全部资源。
????④ 把这个进程从集合中去掉，系统的剩余资源更多了，然后反复执行上述步骤。
????⑤ 最后，检查进程集合，若为空则表明本次申请可行，系统处于安全状态，可实施本次分配；否则，有进程执行不完，系统处于不完全状态，本次资源分配暂不实施，让申请进程等待。
3.2.3 算法所需的相关数据结构
??● 考虑一个系统有 n 个进程和 m 种不同类型的资源，现定义包含以下向量和矩阵的数据结构：
??① 可利用资源向量 R e s o u r c e = ( R 1 ， R 2 ， . . . ， R m ) Resource = (R_1，R_2，...，R_m) Resource=(R1?，R2?，...，Rm?)。这是一个含有 m m m 个元素的数组，其中的而每一个元素代表一类可利用资源数目，其初始值是系统中所配置的该类全部可用资源的数目。其数值随该类资源的分配和回收而动态的改变。如果 R e s o u r c e [ i ] = K Resource[i]=K Resource[i]=K，则表示系统中现有 R i R_i Ri? 类资源 K K K 个。【注：后面，也可以用 Available 来表示 Resource】
??② 最大需求矩阵 M a x Max Max 。这是一个 n ? m n*m n?m 的矩阵，它定义了系统中 n n n 个进程中的每一个进程对 m m m 类资源的最大需求。如果 M a x [ i , j ] = K Max[i,j]=K Max[i,j]=K ；则表示进程 i i i 需要 R j R_j Rj? 类资源的最大数目为 K K K。
??③ 分配矩阵 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，则表示进程 i i i 当前已分得 R j R_j Rj? 类资源的数目为 K K K。
??④ 需求矩阵 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，则表示进程 i i i 还需要 R j R_j Rj? 类资源 K K K 个，方能完成任务。
??⑤ 设 R e q u e s t [ i , j ] Request[i,j] Request[i,j] 是进程 P i P_i Pi? 的申请向量，如果 R e q u e s t [ i , j ] = K Request [i,j]=K Request[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 o c a t i o n [ i , j ] Need[i,j]=Max[i,j]-Allocation[i,j] Need[i,j]=Max[i,j]?Allocation[i,j]
3.2.4 算法的设计思想
??● 设计思路如下：
??第一部分：银行家算法模块
??① 如果
R
e
q
u
e
s
t
≤
N
e
e
d
Request≤Need
Request≤Need，则转向 ②；否则，出错
??② 如果
R
e
q
u
e
s
t
≤
R
e
s
o
u
r
c
e
Request≤Resource
Request≤Resource，则转向 ③；否则等待
??③ 系统试探性分配请求的资源给进程
??④ 系统执行安全性算法
??第二部分：安全性算法模块
??① 设置两个参数
????<1>
工
作
向
量
W
o
r
k
工作向量Work
工作向量Work：值等于
R
e
s
o
u
r
c
e
Resource
Resource
????<2>
标
志
变
量
F
i
n
i
s
h
标志变量Finish
标志变量Finish：表示系统是否有足够资源分配给进程 (
T
r
u
e
：
有
True：有
True：有，
F
a
l
s
e
：
没
有
False：没有
False：没有) 。初始化为
F
a
l
s
e
False
False。
??② 若
F
i
n
i
s
h
[
i
]
=
F
a
l
s
e
??
&
&
??
N
e
e
d
<
=
W
o
r
k
Finish[i]=False\,\, \&\& \,\, Need<=Work
Finish[i]=False&&Need<=Work，则执行 ③；否则执行 ④ (
i
i
i 为资源类别)
??③ 进程
P
P
P 获得第
i
i
i 类资源，则顺利执行直至完成，并释放资源：
W
o
r
k
=
W
o
r
k
+
A
l
l
o
c
a
t
i
o
n
Work=Work+Allocation
Work=Work+Allocation；
F
i
n
i
s
h
[
i
]
=
t
r
u
e
Finish[i]=true
Finish[i]=true；转 ② 。
??④ 若所有进程的
F
i
n
i
s
h
[
i
]
=
t
r
u
e
Finish[i]=true
Finish[i]=true，则表示系统安全；否则，不安全！
3.2.5 算法的细节补充
??● 当
P
i
P_i
Pi? 发出资源请求后，系统按下述步骤进行检查：（对标第一部分）
??① 如果
R
e
q
u
e
s
t
i
[
j
]
<
=
N
e
e
d
[
i
,
j
]
Request i[j]<=Need[i,j]
Requesti[j]<=Need[i,j]，便转向步骤 ②；否则认为出错，因为它所需要的资源数已经超过它所申请的最大值。
??② 如果
R
e
q
u
e
s
t
i
[
j
]
<
=
A
v
a
i
l
a
b
l
e
[
i
,
j
]
Request i[j]<=Available[i,j]
Requesti[j]<=Available[i,j]，便转向步骤 ③；否则，表示尚无足够资源，
P
i
P_i
Pi? 需等待。
??③ 系统试探着把资源分配给进程
P
i
P_i
Pi?，并修改下面数据结构中的数值：
????
R
e
s
o
u
r
c
e
[
j
]
=
R
e
s
o
u
r
c
e
[
j
]
?
R
e
q
u
e
s
t
i
[
j
]
;
Resource[j]=Resource[j]-Request i[j];
Resource[j]=Resource[j]?Requesti[j];
????
A
l
l
o
c
a
t
i
o
n
[
i
,
j
]
=
A
l
l
o
c
a
t
i
o
n
[
i
,
j
]
+
R
e
q
u
e
s
t
i
[
j
]
;
Allocation[i,j]=Allocation[i,j]+Request i[j];
Allocation[i,j]=Allocation[i,j]+Requesti[j];
????
N
e
e
d
[
i
,
j
]
=
N
e
e
d
[
i
,
j
]
?
R
e
q
u
e
s
t
i
[
j
]
;
Need[i,j]=Need[i,j]-Request i[j];
Need[i,j]=Need[i,j]?Requesti[j];
??④ 系统再执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程
P
i
P_i
Pi?，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程
P
i
P_i
Pi? 等待。
??● 系统所执行的安全性算法可描述如下：（对标第二部分）
??① 设置两个参数
????<1>
工
作
向
量
W
o
r
k
工作向量Work
工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，它含有
m
m
m 个元素，在执行安全算法开始时，进行初始化赋值
W
o
r
k
=
R
e
s
o
u
r
c
e
Work=Resource
Work=Resource。
????<2>
标
志
变
量
F
i
n
i
s
h
标志变量Finish
标志变量Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做
F
i
n
i
s
h
[
i
]
=
f
a
l
s
e
Finish[i]=false
Finish[i]=false；当有足够资源分配给进程时，再令
F
i
n
i
s
h
[
i
]
=
t
u
r
e
Finish[i]=ture
Finish[i]=ture。
??② 从进程集合中找到一个满足下述条件的进程：
????<1>
F
i
n
i
s
h
[
i
]
=
f
a
l
s
e
Finish[i]=false
Finish[i]=false；
????<2>
N
e
e
d
[
i
,
j
]
<
=
W
o
r
k
[
j
]
Need[i,j]<=Work[j]
Need[i,j]<=Work[j]；若找得到，执行步骤 ③，否则，执行步骤 ④。
??③ 当进程
P
i
P_i
Pi? 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
????<1>
W
o
r
k
[
j
]
=
W
o
r
k
[
j
]
+
A
l
l
o
c
a
t
i
o
n
[
i
,
j
]
Work[j]=Work[j]+Allocation[i,j]
Work[j]=Work[j]+Allocation[i,j]；
????<2>
F
i
n
i
s
h
[
i
]
=
t
r
u
e
Finish[i]=true
Finish[i]=true；
????<3>
G
o
???
t
o
???
s
t
e
p
②
Go\,\,\, to\,\,\, step ②
Gotostep②；
??④ 如果所有进程的
F
i
n
i
s
h
[
i
]
=
t
r
u
e
Finish[i]=true
Finish[i]=true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
??● 流程图如下：
3.2.6 算法的实战(样例)
??● 题目描述：假定系统中有 5 个进程
{
P
0
,
P
1
,
P
2
,
P
3
,
P
4
}
\{P0,P1,P2,P3,P4\}
{P0,P1,P2,P3,P4} 和 3 类资源
{
A
,
B
,
C
}
\{A,B,C\}
{A,B,C} 各类资源的数目分别是10、5、7。已知
T
0
T_0
T0? 时刻资源分配情况如下：
??问题一：该系统是否是安全的？
??问题二：假设
P
1
P_1
P1? 请求资源
R
e
q
u
e
s
t
{
1
,
0
,
2
}
Request\{1,0,2\}
Request{1,0,2}，再判断该系统是否是安全的？
??● 问题一解答：接下来我们需求出这个状态下的安全序列，也就是将可利用的资源分配给某个 “需要资源小于可利用资源的” 进程，让这个进程运行完成。该进程运行完成之后将会释放资源(也就是将先前分配给该程序的资源重新添加到可利用的资源)，然后再执行同样的操作。只要能找到满足 N e e d Need Need 小于 A v a i l a b l e Available Available ，就能分配到资源，让该进程运行完成，最后将资源释放。如果最后每一个进程都能运行完成，就能得到了我们的安全序列，这时该系统就是安全的。否则，不安全。
??● 执行过程：
??① 将
A
v
a
i
l
a
b
l
e
Available
Available 和
N
e
e
d
Need
Need 对比，
P
0
P_0
P0? 的
N
e
e
d
>
A
v
a
i
l
a
b
l
e
Need>Available
Need>Available，不满足，往后找。
??② P 1 P_1 P1? 的 A v a i l a b l e Available Available 小于 N e e d Need Need，分配给 P 1 P_1 P1?。 P 1 P_1 P1? 就能运行完成，最后释放资源 { 2 , 0 , 0 } \{2,0,0\} {2,0,0} 。所以现在的资源就是 { 3 , 3 , 2 } + { 2 , 0 , 0 } = { 5 , 3 , 2 } \{3,3,2\}+\{2,0,0\}=\{5,3,2\} {3,3,2}+{2,0,0}={5,3,2}
??③ 然后继续向下找， P 2 P_2 P2? 不满足条件， P 3 P_3 P3? 满足条件，将资源分配给 P 3 P_3 P3?，让其运行完成，并释放空间 { 2 , 1 , 1 } \{2,1,1\} {2,1,1}，所以现在的资源就是 { 5 , 3 , 2 } + { 2 , 1 , 1 } = { 7 , 4 , 3 } \{5,3,2\}+\{2,1,1\}=\{7,4,3\} {5,3,2}+{2,1,1}={7,4,3}
??④ 依次类推得到安全序列为 { P 1 , P 3 , P 4 , P 2 , P 0 } \{P1,P3,P4,P2,P0\} {P1,P3,P4,P2,P0}。过程如下图，其中 F i n i s h Finish Finish 表示进程运行完成。
??所以，该系统是安全的。
??● 问题二解答：首先要检测看请求资源是不是比可利用资源、是不是比需要的资源小，如果其中一个或两个条件都不满足，进程等待，如果满足进接下来的操作。这里 { 1 , 0 , 2 } \{1,0,2\} {1,0,2} 是满足这两个条件的。我们进行的操作就是将请求资源加到 A l l o c a t i o n Allocation Allocation 上面，也就是已分配的资源得到扩充。同样的请求的资源一定是来自可利用资源的，所以可利用资源要减去请求资源的数目，因为 N e e d Need Need 和 A l l o c a t i o n Allocation Allocation 的和是一个固定值 M a x Max Max 所以相应的 A l l o c a t i o n Allocation Allocation 加上一个数值， N e e d Need Need 就要减上一个数值，变化之后如下图所示：
??● 然后再像前面一样，把这个表当成T0时刻的资源分配状态，再来找安全序列，判断系统是不是安全的即可。
四、进程死锁的检测与解决
4.1 机制原理
??① 允许死锁发生。
??② 系统不断监视进展情况，判断死锁是否发生。
??③ 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复运行。
??● 检测时机：定时检测、进程等待时、资源利用率下降时等。
??● 检测手段：进程-资源分配图(如下图所示)。
4.2 死锁检测
??● 检测模型：
????① 方框表示资源类
????② 黑圆点表示资源实例
????③ 圆圈中加进程名表示进程
????④ 资源实例指向进程的一条有向边来表示分配边
????⑤ 进程指向资源类的一条有向边来表示申请边
????⑥ 检测 “进程-资源分配图” 是否可完全简化
??● 检测步骤：（执行过程如下）
????① 找一个只有分配边的非孤立进程结点，去掉分配边将其变为孤立结点；若找不到则转 ③，否则转 ②。
????② 将资源分配给一个等待资源的进程，将某进程的申请边变为分配边，转 ①。
????③ 图中有进程不是孤立结点，则此图不可完全简化，满足死锁的充分条件，系统为死锁状态。
4.3 死锁解除
??● 资源剥夺法：从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态。
??● 撤消进程法：撤消全部死锁进程，恢复到正常状态，简单但代价太大。所以一般会按照某种顺序逐个撤消死锁进程，直到有足够的资源供其他未被撤消的进程使用，以消除死锁状态
五、进程死锁问题的思考
5.1 死锁原因
??① 系统资源不足
??② 进程运行推进的顺序不合适
??③ 资源分配不当
5.2 解决原则
??① 单独使用死锁预防、避免、检测与解除并不能全面解决操作系统中遇到的所有死锁问题。
??② 可将系统中的进程、资源分为若干类，对每一类进程、资源使用最适合它的办法解决死锁。
六、参考附录：
[1] 《操作系统A》
上课用的慕课
链接: https://www.icourse163.org/course/NJUPT-1003219004?from=searchPage.
[2] 《操作系统教程》
上课用的教材
上一篇文章地址链接: 【操作系统⑨】——进程间通信的概述【kill() signal() shmget() shmat() 实例 共享存储通信 消息通信 管道通信 】.
下一篇文章地址链接: 正在施工中… 🚧 🚧
操作系统系列文章正在更新中… ?? ??