【JAVA 并发】四死锁种类

小灰灰 2022-09-30 03:58 20阅读 0赞

**死锁**

**银行家算法**

这是一个著名的避免死锁的算法，是由Dijstra首先提出来并加以解决的。

\[背景知识\]

一个银行家如何将一定数目的资金安全地借给若干个客户，使这些客户既能借到钱完成要干的事，同时银行家又能收回全部资金而不至于破产，这就是银行家问题。这个问题同操作系统中资源分配问题十分相似：银行家就像一个操作系统，客户就像运行的进程，银行家的资金就是系统的资源。

\[问题的描述\]

一个银行家拥有一定数量的资金，有若干个客户要贷款。每个客户须在一开始就声明他所需贷款的总额。若该客户贷款总额不超过银行家的资金总数，银行家可以接收客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。

例如：有三个客户C1，C2，C3，向银行家借款，该银行家的资金总额为10个资金单位，其中C1客户要借9各资金单位，C2客户要借3个资金单位，C3客户要借8个资金单位，总计20个资金单位。某一时刻的状态如图所示。

<table style="border-collapse:collapse"> 
 <tbody> 
 <tr style="height: 78px"> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: solid 0.5pt; border-bottom: solid 0.5pt; border-right: solid 0.5pt">人</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">-表示缺少的钱</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c1/c2借2,c3借4, banker剩余2</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c2借1</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c2满足3借款,将3还给bakner</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c3借4</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c3满足8借款,将8还给bakner</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: solid 0.5pt; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c4借7,满足9借款,将9还给bakner</td> 
 </tr> 
 <tr style="height: 18px"> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: solid 0.5pt; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c1</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">-9</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-7</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-7</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-7</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-7</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-7</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 </tr> 
 <tr style="height: 18px"> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: solid 0.5pt; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c2</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">-3</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2/-1</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">3</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 </tr> 
 <tr style="height: 18px"> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: solid 0.5pt; border-bottom: solid 0.5pt; border-right: solid 0.5pt">c3</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">-8</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">4/-4</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">4/-4</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">4/-4</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">8</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 </tr> 
 <tr style="height: 18px"> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: solid 0.5pt; border-bottom: solid 0.5pt; border-right: solid 0.5pt">banker</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">10</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">2</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">1</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">4</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">0</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">8</td> 
 <td style="padding-left: 7px; padding-right: 7px; border-top: none; border-left: none; border-bottom: solid 0.5pt; border-right: solid 0.5pt">10</td> 
 </tr> 
 </tbody> 
</table>

对于a图的状态，按照安全序列的要求，我们选的第一个客户应满足该客户所需的贷款小于等于银行家当前所剩余的钱款，可以看出只有C2客户能被满足：C2客户需1个资金单位，小银行家手中的2个资金单位，于是银行家把1个资金单位借给C2客户，使之完成工作并归还所借的3个资金单位的钱，进入b图。同理，银行家把4个资金单位借给C3客户，使其完成工作，在c图中，只剩一个客户C1，它需7个资金单位，这时银行家有8个资金单位，所以C1也能顺利借到钱并完成工作。最后（见图d）银行家收回全部10个资金单位，保证不赔本。那麽客户序列\{C1，C2，C3\}就是个安全序列，按照这个序列贷款，银行家才是安全的。否则的话，若在图b状态时，银行家把手中的4个资金单位借给了C1，则出现不安全状态：这时C1，C3均不能完成工作，而银行家手中又没有钱了，系统陷入僵持局面，银行家也不能收回投资。

**综上所述，银行家算法是从当前状态出发，逐个按安全序列检查各客户谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。**

从上面分析看出，银行家算法允许死锁必要条件中的互斥条件，占有且申请条件，不可抢占条件的存在，这样，它与预防死锁的几种方法相比较，限制条件少了，资源利用程度提高了。

这是该算法的优点。其缺点是：

1.  这个算法要求客户数保持固定不变，这在多道程序系统中是难以做到的。 
2.  这个算法保证所有客户在有限的时间内得到满足，但实时客户要求快速响应，所以要考虑这个因素。 
3.  由于要寻找一个安全序列，实际上增加了系统的开销。

在数据库系统的设计中考虑了检测死锁以及从死锁中恢复. 在执行一个事务 Transaction 时可能需要获得多个锁, 并一直持有这些说直到事务提交. 因此在两个事务之间很可能产生死锁, 但事实上这种情况并不多见. 如果没有外界干预,那么这些事务将等待下去,这样就造成了死锁. 但数据库不会让这样的情况发生. 当数据库从表示等待关系的有向图中搜索循环,检测到一组事务发生了死锁,数据库将放弃一个事物, 一使得其他的事务可以顺利完成, 然后数据库可以重新执行被放弃的事务, 这是资源将不在被占用了, 事务都会完成, 但此过程是相当耗用资源的 .

JVM在解决死锁问题方面并没有数据库那么强大. 当一组线程死锁,那么所有的线程将停留在原地, 而这些线程也不能再被使用了. 可能造成程序停止,系统停止,性能下降. 恢复应用程序唯一的办法将是重新启动它, 并希望不在发生同样的事情.

与许多的危险性相同, 死锁的造成不是立即显现出来. 如果一个类可能发生死锁, 那么会在高负载下更容易发生死锁,可谓是雪上加霜!!!

**锁循序 死锁**

leftRight , rightLeft 这两个方法分别会的left锁和right锁. 如果一个线程调用了leftRight, 而另一个线程调用了rightLeft,并且这两个线程的操作是交错执行, 那么他们会发生死锁.

![20170318020629069][]

![20170318020631835][]

![20170318020634648][]

[20170318020629069]: /images/20220708/2234a46674f241e393b21b7daf4ca333.png
[20170318020631835]: /images/20220708/0ed53a21b8894e03a0c408070f244474.png
[20170318020634648]: /images/20220708/9e72a32ce6cf46cbaaff93595e699626.png