死鎖
思維導(dǎo)圖
是什么
線程死鎖是指由于兩個或者多個線程互相持有對方所需要的資源，導(dǎo)致這些線程處于等待狀態(tài)，無法前往執(zhí)行。
當(dāng)線程進(jìn)入對象的synchronized代碼塊時，便占有了資源，直到它退出該代碼塊或者調(diào)用wait方法，才釋放資源，在此期間，其他線程將不能進(jìn)入該代碼塊。
當(dāng)線程互相持有對方所需要的資源時，會互相等待對方釋放資源，如果線程都不主動釋放所占有的資源，將產(chǎn)生死鎖。
發(fā)生的必要條件
當(dāng)然死鎖的產(chǎn)生是必須要滿足一些特定條件的：
1.互斥條件：進(jìn)程對于所分配到的資源具有排它性，即一個資源只能被一個進(jìn)程占用，直到被該進(jìn)程釋放
2.請求和保持條件：一個進(jìn)程因請求被占用資源而發(fā)生阻塞時，對已獲得的資源保持不放。
3.不剝奪條件：任何一個資源在沒被該進(jìn)程釋放之前，任何其他進(jìn)程都無法對他剝奪占用
4.循環(huán)等待條件：當(dāng)發(fā)生死鎖時，所等待的進(jìn)程必定會形成一個環(huán)路（類似于死循環(huán)），造成永久阻塞。
死鎖的預(yù)防
前面介紹了死鎖發(fā)生時的四個必要條件，只要破壞這四個必要條件中的任意一個條件，死鎖就不會發(fā)生。這就為我們解決死鎖問題提供了可能。一般地，解決死鎖的方法分為死鎖的預(yù)防，避免，檢測與恢復(fù)三種（注意：死鎖的檢測與恢復(fù)是一個方法）。我們將在下面分別加以介紹。
死鎖的預(yù)防是保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的一種策略。它的基本思想是要求進(jìn)程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進(jìn)入死鎖狀態(tài)。
1. 打破互斥條件。
即允許進(jìn)程同時訪問某些資源。但是，有的資源是不允許被同時訪問的，像打印機(jī)等等，這是由資源本身的屬性所決定的。
所以，這種辦法并無實用價值。
2. 打破不可搶占條件。
即允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。
就是說，當(dāng)一個進(jìn)程已占有了某些資源，它又申請新的資源，但不能立即被滿足時，它必須釋放所占有的全部資源，以后再重新申請。
它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強(qiáng)占了。
這種預(yù)防死鎖的方法實現(xiàn)起來困難，會降低系統(tǒng)性能。
3. 打破占有且申請條件。
可以實行資源預(yù)先分配策略。即進(jìn)程在運行前一次性地向系統(tǒng)申請它所需要的全部資源。
如果某個進(jìn)程所需的全部資源得不到滿足，則不分配任何資源，此進(jìn)程暫不運行。
只有當(dāng)系統(tǒng)能夠滿足當(dāng)前進(jìn)程的全部資源需求時，才一次性地將所申請的資源全部分配給該進(jìn)程。
由于運行的進(jìn)程已占有了它所需的全部資源，所以不會發(fā)生占有資源又申請資源的現(xiàn)象，因此不會發(fā)生死鎖。
但是，這種策略也有如下缺點：
（1）在許多情況下，一個進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時是動態(tài)的，不可預(yù)測的；
（2）資源利用率低。無論所分資源何時用到，一個進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長期占著不用的狀況。這顯然是一種極大的資源浪費；
（3）降低了進(jìn)程的并發(fā)性。因為資源有限，又加上存在浪費，能分配到所需全部資源的進(jìn)程個數(shù)就必然少了。
4. 打破循環(huán)等待條件，實行資源有序分配策略。
采用這種策略，即把資源事先分類編號，按號分配，使進(jìn)程在申請，占用資源時不會形成環(huán)路。
所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的順序提出。
進(jìn)程占用了小號資源，才能申請大號資源，就不會產(chǎn)生環(huán)路，從而預(yù)防了死鎖。
這種策略與前面的策略相比，資源的利用率和系統(tǒng)吞吐量都有很大提高，但是也存在以下缺點：
（1）限制了進(jìn)程對資源的請求，同時給系統(tǒng)中所有資源合理編號也是件困難事，并增加了系統(tǒng)開銷；
（2）為了遵循按編號申請的次序，暫不使用的資源也需要提前申請，從而增加了進(jìn)程對資源的占用時間。
死鎖
死鎖的避免
上面我們講到的死鎖預(yù)防是排除死鎖的靜態(tài)策略，它使產(chǎn)生死鎖的四個必要條件不能同時具備，從而對進(jìn)程申請資源的活動加以限制， 以保證死鎖不會發(fā)生。
下面我們介紹排除死鎖的動態(tài)策略--死鎖的避免，它不限制進(jìn)程有關(guān)申請資源的命令， 而是對進(jìn)程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進(jìn)行資源分配。
就是說，在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。
1.安全序列
我們首先引入安全序列的定義：所謂系統(tǒng)是安全的，是指系統(tǒng)中的所有進(jìn)程能夠按照某一種次序分配資源，并且依次地運行完畢，這種進(jìn)程序列{P1，P2，...，Pn}就是安全序列。如果存在這樣一個安全序列，則系統(tǒng)是安全的；如果系統(tǒng)不存在這樣一個安全序列，則系統(tǒng)是不安全的。
安全序列{P1，P2，...，Pn}是這樣組成的：若對于每一個進(jìn)程Pi，它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進(jìn)程Pj當(dāng)前占有資源之和所滿足，則{P1，P2，...，Pn}為一個安全序列，這時系統(tǒng)處于安全狀態(tài)，不會進(jìn)入死鎖狀態(tài)。
雖然存在安全序列時一定不會有死鎖發(fā)生，但是系統(tǒng)進(jìn)入不安全狀態(tài)（四個死鎖的必要條件同時發(fā)生）也未必會產(chǎn)生死鎖。
當(dāng)然，產(chǎn)生死鎖后，系統(tǒng)一定處于不安全狀態(tài)。
2.銀行家算法
這是一個著名的避免死鎖的算法，是由Dijstra首先提出來并加以解決的。
- 背景知識
一個銀行家如何將一定數(shù)目的資金安全地借給若干個客戶，使這些客戶既能借到錢完成要干的事，同時銀行家又能收回全部資金而不至于破產(chǎn)，這就是銀行家問題。這個問題同操作系統(tǒng)中資源分配問題十分相似：銀行家就像一個操作系統(tǒng)，客戶就像運行的進(jìn)程，銀行家的資金就是系統(tǒng)的資源。
- 問題的描述
一個銀行家擁有一定數(shù)量的資金，有若干個客戶要貸款。每個客戶須在一開始就聲明他所需貸款的總額。
若該客戶貸款總額不超過銀行家的資金總數(shù)，銀行家可以接收客戶的要求。客
戶貸款是以每次一個資金單位（如1萬RMB等）的方式進(jìn)行的，客戶在借滿所需的全部單位款額之前可能會等待， 但銀行家須保證這種等待是有限的，可完成的。
例如：有三個客戶C1，C2，C3，向銀行家借款，該銀行家的資金總額為10個資金單位，其中C1客戶要借9各資金單位， C2客戶要借3個資金單位，C3客戶要借8個資金單位，總計20個資金單位。
某一時刻的狀態(tài)如圖所示。
銀行家算法
對于a圖的狀態(tài)，按照安全序列的要求，我們選的第一個客戶應(yīng)滿足該客戶所需的貸款小于等于銀行家當(dāng)前所剩余的錢款，可以看出只有C2客戶能被滿足：C2客戶需1個資金單位，小銀行家手中的2個資金單位，于是銀行家把1個資金單位借給C2客戶，使之完成工作并歸還所借的3個資金單位的錢，進(jìn)入b圖。同理，銀行家把4個資金單位借給C3客戶，使其完成工作，在c圖中，只剩一個客戶C1，它需7個資金單位，這時銀行家有8個資金單位，所以C1也能順利借到錢并完成工作。最后（見圖d）銀行家收回全部10個資金單位，保證不賠本。那麼客戶序列{C1，C2，C3}就是個安全序列，按照這個序列貸款，銀行家才是安全的。否則的話，若在圖b狀態(tài)時，銀行家把手中的4個資金單位借給了C1，則出現(xiàn)不安全狀態(tài)：這時C1，C3均不能完成工作，而銀行家手中又沒有錢了，系統(tǒng)陷入僵持局面，銀行家也不能收回投資。
綜上所述，銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶誰能完成其工作，然后假定其完成工作且歸還全部貸款，再進(jìn)而檢查下一個能完成工作的客戶，......。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。
從上面分析看出，銀行家算法允許死鎖必要條件中的互斥條件，占有且申請條件，不可搶占條件的存在，這樣，它與預(yù)防死鎖的幾種方法相比較，限制條件少了，資源利用程度提高了。
這是該算法的優(yōu)點。其缺點是：
〈1〉這個算法要求客戶數(shù)保持固定不變，這在多道程序系統(tǒng)中是難以做到的。
〈2〉這個算法保證所有客戶在有限的時間內(nèi)得到滿足，但實時客戶要求快速響應(yīng)，所以要考慮這個因素。
〈3〉由于要尋找一個安全序列，實際上增加了系統(tǒng)的開銷。
死鎖的檢測與恢復(fù)
一般來說，由于操作系統(tǒng)有并發(fā)，共享以及隨機(jī)性等特點，通過預(yù)防和避免的手段達(dá)到排除死鎖的目的是很困難的。這需要較大的系統(tǒng)開銷，而且不能充分利用資源。為此，一種簡便的方法是系統(tǒng)為進(jìn)程分配資源時，不采取任何限制性措施，但是提供了檢測和解脫死鎖的手段：能發(fā)現(xiàn)死鎖并從死鎖狀態(tài)中恢復(fù)出來。因此，在實際的操作系統(tǒng)中往往采用死鎖的檢測與恢復(fù)方法來排除死鎖。
死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機(jī)構(gòu)，當(dāng)死鎖發(fā)生時，該機(jī)構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，并能通過外力破壞死鎖發(fā)生的必要條件，從而使得并發(fā)進(jìn)程從死鎖狀態(tài)中恢復(fù)出來。
死鎖的檢測
圖中所示為一個小的死鎖的例子。這時進(jìn)程P1占有資源R1而申請資源R2，進(jìn)程P2占有資源R2而申請資源R1，按循環(huán)等待條件，進(jìn)程和資源形成了環(huán)路，所以系統(tǒng)是死鎖狀態(tài)。進(jìn)程P1，P2是參與死鎖的進(jìn)程。
下面我們再來看一看死鎖檢測算法。算法使用的數(shù)據(jù)結(jié)構(gòu)是如下這些：
占有矩陣A：n*m階，其中n表示并發(fā)進(jìn)程的個數(shù)，m表示系統(tǒng)的各類資源的個數(shù)，這個矩陣記錄了每一個進(jìn)程當(dāng)前占有各個資源類中資源的個數(shù)。
申請矩陣R：n*m階，其中n表示并發(fā)進(jìn)程的個數(shù)，m表示系統(tǒng)的各類資源的個數(shù)，這個矩陣記錄了每一個進(jìn)程當(dāng)前要完成工作需要申請的各個資源類中資源的個數(shù)。
空閑向量T：記錄當(dāng)前m個資源類中空閑資源的個數(shù)。
完成向量F：布爾型向量值為真（true）或假（false），記錄當(dāng)前n個并發(fā)進(jìn)程能否進(jìn)行完。為真即能進(jìn)行完，為假則不能進(jìn)行完。
臨時向量W：開始時W：=T。
算法步驟：
（1）W：=T，
對于所有的i=1，2，...，n，
如果A[i]=0，則F[i]：=true；否則，F(xiàn)[i]：=false
（2）找滿足下面條件的下標(biāo)i：
F[i]：=false并且R[i]〈=W
如果不存在滿足上面的條件i，則轉(zhuǎn)到步驟（4）。
（3）W：=W+A[i]
F[i]：=true
轉(zhuǎn)到步驟（2）
（4）如果存在i，F(xiàn)[i]：=false，則系統(tǒng)處于死鎖狀態(tài)，且Pi進(jìn)程參與了死鎖。什麼時候進(jìn)行死鎖的檢測取決于死鎖發(fā)生的頻率。如果死鎖發(fā)生的頻率高，那麼死鎖檢測的頻率也要相應(yīng)提高，這樣一方面可以提高系統(tǒng)資源的利用率，一方面可以避免更多的進(jìn)程卷入死鎖。如果進(jìn)程申請資源不能滿足就立刻進(jìn)行檢測，那麼每當(dāng)死鎖形成時即能被發(fā)現(xiàn)，這和死鎖避免的算法相近，只是系統(tǒng)的開銷較大。為了減小死鎖檢測帶來的系統(tǒng)開銷，一般采取每隔一段時間進(jìn)行一次死鎖檢測，或者在CPU的利用率降低到某一數(shù)值時，進(jìn)行死鎖的檢測。
死鎖的恢復(fù)
一旦在死鎖檢測時發(fā)現(xiàn)了死鎖，就要消除死鎖，使系統(tǒng)從死鎖狀態(tài)中恢復(fù)過來。
（1）最簡單，最常用的方法就是進(jìn)行系統(tǒng)的重新啟動，不過這種方法代價很大，它意味著在這之前所有的進(jìn)程已經(jīng)完成的計算工作都將付之東流，包括參與死鎖的那些進(jìn)程，以及未參與死鎖的進(jìn)程。
（2）撤消進(jìn)程，剝奪資源。終止參與死鎖的進(jìn)程，收回它們占有的資源，從而解除死鎖。這時又分兩種情況：一次性撤消參與死鎖的全部進(jìn)程，剝奪全部資源；或者逐步撤消參與死鎖的進(jìn)程，逐步收回死鎖進(jìn)程占有的資源。
一般來說，選擇逐步撤消的進(jìn)程時要按照一定的原則進(jìn)行，目的是撤消那些代價最小的進(jìn)程，比如按進(jìn)程的優(yōu)先級確定進(jìn)程的代價；考慮進(jìn)程運行時的代價和與此進(jìn)程相關(guān)的外部作業(yè)的代價等因素。
此外，還有進(jìn)程回退策略，即讓參與死鎖的進(jìn)程回退到?jīng)]有發(fā)生死鎖前某一點處，并由此點處繼續(xù)執(zhí)行，以求再次執(zhí)行時不再發(fā)生死鎖。雖然這是個較理想的辦法，但是操作起來系統(tǒng)開銷極大，要有堆棧這樣的機(jī)構(gòu)記錄進(jìn)程的每一步變化，以便今后的回退，有時這是無法做到的。
死鎖的場景
獲取鎖的順序?qū)е碌乃梨i
public class DeadLockDemo extends Thread {
private final String firstLock;
private final String secondLock;
public DeadLockDemo(String t1, String t2) {
this.firstLock = t1;
this.secondLock = t2;
}
@Override
public void run() {
synchronized (firstLock) {
// 成功占有 firstLock
System.out.println(Thread.currentThread().getName() + " success locked " + firstLock);
// 休眠一段時間
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
// 嘗試占有 secondLock，如果不能占有，該線程會一直等到
synchronized (secondLock) {
System.out.println(Thread.currentThread().getName() + " success locked " + secondLock);
}
}
}
}
- main()
public static void main(String[] args) {
final String resource1 = "resource1";
final String resource2 = "resource2";
// 兩個線程獲取鎖的順序相反
new DeadLockDemo(resource1, resource2).start();
new DeadLockDemo(resource2, resource1).start();
}
日志信息
Thread-0 success locked resource1
Thread-1 success locked resource2
然后進(jìn)入死鎖狀態(tài)。
遞歸死鎖
所謂遞歸函數(shù)就是自調(diào)用函數(shù)，在函數(shù)體內(nèi)直接或間接的調(diào)用自己，即函數(shù)的嵌套是函數(shù)本身。
遞歸方式有兩種:直接遞歸和間接遞歸，直接遞歸就是在函數(shù)中出現(xiàn)調(diào)用函數(shù)本身。間接遞歸，指函數(shù)中調(diào)用了其他函數(shù)，而該其他函數(shù)又調(diào)用了本函數(shù)。 那什么時候使用遞歸呢？
一般來說當(dāng)你要在某段代碼邏輯中使用循環(huán)迭代的時候但是迭代的次數(shù)在迭代之前無法知曉的情況下使用遞歸。
打個比方你要在一個文件夾中查找某個文件，而這個文件夾底下有N多子文件夾和文件，當(dāng)你在不知道有多少層文件夾和文件的情況下你就得用到遞歸了。
遞歸的優(yōu)點就是讓代碼顯得很簡潔，同時有些應(yīng)用場景不得不使用遞歸比如前面說的找文件。
遞歸是個好東西但是在某些時候也會給你帶來一些麻煩。
比如在多線程的環(huán)境下使用遞歸，遇到了多線程那么就不得不面對同步的問題。
而遞歸程序遇到同步的時候很容易出問題。
public class Test {
public void recursive(){
this.businessLogic();
}
public synchronized void businessLogic(){
System.out.println("處理業(yè)務(wù)邏輯");
this.recursive();
}
}
多線程的遞歸就是指遞歸鏈中的某個方法由另外一個線程來操作，以下代碼的意思都是這個意思即調(diào)用recursive()和businessLogic()并非一個線程
(如果是在一個線程中就不存在死鎖問題，例如上面的recursive變成private就不存在問題。)
以上這段代碼就是個能形成死鎖的代碼，事實上這個“synchronized”放在“businessLogic()”和“recursive()”都會形成死鎖，并且是多線程的情況下就會鎖住！
他的邏輯順序是先執(zhí)行recursive()方法然后接下來執(zhí)行businessLogic()方法同時將businessLogic()方法鎖住， 接下來程序進(jìn)入businessLogic()方法內(nèi)部執(zhí)行完打印語句后開始執(zhí)行recursive()， 進(jìn)入recursive()后準(zhǔn)備執(zhí)行businessLogic()，等等問題來了！
之前執(zhí)行的businessLogic()的鎖還沒有放開這次又執(zhí)行到這里了，當(dāng)然是過不去的了，形成了死鎖！
從這個例子我們總結(jié)出來一個規(guī)律就是在遞歸的時候在遞歸鏈上面的方法上加鎖肯定會出現(xiàn)死鎖（所謂遞歸鏈就是指recursive()鏈向businessLogic()，businessLogic()又鏈回recursive()），
解決這個問題的方法就是避免在遞歸鏈上加鎖，
請看以下的例子
public class Test {
public void recursive(){
this.businessLogic();
}
public void businessLogic(){
System.out.println("處理業(yè)務(wù)邏輯");
this.saveToDB();
this.recursive();
}
public synchronized void saveToDB(){
System.out.println("保存到數(shù)據(jù)庫");
}
}
saveToDB()不在這條遞歸鏈上面自然不會出現(xiàn)死鎖，所以說在遞歸中加鎖是件很危險的事情，實在逃不過要加鎖就加在最小的粒度的程序代碼上以減小死鎖的概率。
動態(tài)順序死鎖
// 轉(zhuǎn)賬
public static void transferMoney(Account fromaccount,
Account toAccount,
DollarAmount amount)
throws InsufficientFundsException {
// 鎖定匯賬賬戶
synchronized (fromAccount) {
// 鎖定來賬賬戶
synchronized (toAccount) {
// 判余額是否大于0
if (fromAccount.getBalance().compareTo(amount) < 0) {
throw new InsufficientFundsException();
} else {
// 匯賬賬戶減錢
fromAccount.debit(amount);
// 來賬賬戶增錢
toAccount.credit(amount);
}
}
}
}
上面的代碼看起來是沒有問題的：鎖定兩個賬戶來判斷余額是否充足才進(jìn)行轉(zhuǎn)賬！
但是，同樣有可能會發(fā)生死鎖：
如果兩個線程同時調(diào)用transferMoney()
線程A從X賬戶向Y賬戶轉(zhuǎn)賬
線程B從賬戶Y向賬戶X轉(zhuǎn)賬
那么就會發(fā)生死鎖。
協(xié)作對象之間發(fā)生死鎖
public class CooperatingDeadlock {
// Warning: deadlock-prone!
class Taxi {
@GuardedBy("this") private Point location, destination;
private final Dispatcher dispatcher;
public Taxi(Dispatcher dispatcher) {
this.dispatcher = dispatcher;
}
public synchronized Point getLocation() {
return location;
}
// setLocation 需要Taxi內(nèi)置鎖
public synchronized void setLocation(Point location) {
this.location = location;
if (location.equals(destination))
// 調(diào)用notifyAvailable()需要Dispatcher內(nèi)置鎖
dispatcher.notifyAvailable(this);
}
public synchronized Point getDestination() {
return destination;
}
public synchronized void setDestination(Point destination) {
this.destination = destination;
}
}
class Dispatcher {
@GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
public Dispatcher() {
taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
}
public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis.add(taxi);
}
// 調(diào)用getImage()需要Dispatcher內(nèi)置鎖
public synchronized Image getImage() {
Image image = new Image();
for (Taxi t : taxis)
// 調(diào)用getLocation()需要Taxi內(nèi)置鎖
image.drawMarker(t.getLocation());
return image;
}
}
class Image {
public void drawMarker(Point p) {
}
}
}
上面的getImage()和setLocation(Point location)都需要獲取兩個鎖的
并且在操作途中是沒有釋放鎖的 這就是隱式獲取兩個鎖(對象之間協(xié)作)..
這種方式也很容易就造成死鎖.....
避免死鎖：
在有些情況下死鎖是可以避免的。本文將展示三種用于避免死鎖的技術(shù)：
- 加鎖順序
- 加鎖時限
- 死鎖檢測
- 開放調(diào)用(針對對象之間協(xié)作造成的死鎖)
加鎖順序
當(dāng)多個線程需要相同的一些鎖，但是按照不同的順序加鎖，死鎖就很容易發(fā)生。
如果能確保所有的線程都是按照相同的順序獲得鎖，那么死鎖就不會發(fā)生。
看下面這個例子：
Thread 1:
lock A
lock B
Thread 2:
wait for A
lock C (when A locked)
Thread 3:
wait for A
wait for B
wait for C
如果一個線程（比如線程3）需要一些鎖，那么它必須按照確定的順序獲取鎖。它只有獲得了從順序上排在前面的鎖之后，才能獲取后面的鎖。
例如，線程2和線程3只有在獲取了鎖A之后才能嘗試獲取鎖C(譯者注：獲取鎖A是獲取鎖C的必要條件)。因為線程1已經(jīng)擁有了鎖A，所以線程2和3需要一直等到鎖A被釋放。然后在它們嘗試對B或C加鎖之前，必須成功地對A加了鎖。
按照順序加鎖是一種有效的死鎖預(yù)防機(jī)制。
但是，這種方式需要你事先知道所有可能會用到的鎖(譯者注：并對這些鎖做適當(dāng)?shù)呐判?，但總有些時候是無法預(yù)知的。
加鎖時限
另外一個可以避免死鎖的方法是在嘗試獲取鎖的時候加一個超時時間，這也就意味著在嘗試獲取鎖的過程中若超過了這個時限該線程則放棄對該鎖請求。若一個線程沒有在給定的時限內(nèi)成功獲得所有需要的鎖，則會進(jìn)行回退并釋放所有已經(jīng)獲得的鎖，然后等待一段隨機(jī)的時間再重試。這段隨機(jī)的等待時間讓其它線程有機(jī)會嘗試獲取相同的這些鎖，并且讓該應(yīng)用在沒有獲得鎖的時候可以繼續(xù)運行(譯者注：加鎖超時后可以先繼續(xù)運行干點其它事情，再回頭來重復(fù)之前加鎖的邏輯)。
以下是一個例子，展示了兩個線程以不同的順序嘗試獲取相同的兩個鎖，在發(fā)生超時后回退并重試的場景：
Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.
在上面的例子中，線程2比線程1早200毫秒進(jìn)行重試加鎖，因此它可以先成功地獲取到兩個鎖。這時，線程1嘗試獲取鎖A并且處于等待狀態(tài)。當(dāng)線程2結(jié)束時，線程1也可以順利的獲得這兩個鎖（除非線程2或者其它線程在線程1成功獲得兩個鎖之前又獲得其中的一些鎖）。
需要注意的是，由于存在鎖的超時，所以我們不能認(rèn)為這種場景就一定是出現(xiàn)了死鎖。也可能是因為獲得了鎖的線程（導(dǎo)致其它線程超時）需要很長的時間去完成它的任務(wù)。
此外，如果有非常多的線程同一時間去競爭同一批資源，就算有超時和回退機(jī)制，還是可能會導(dǎo)致這些線程重復(fù)地嘗試但卻始終得不到鎖。如果只有兩個線程，并且重試的超時時間設(shè)定為0到500毫秒之間，這種現(xiàn)象可能不會發(fā)生，但是如果是10個或20個線程情況就不同了。因為這些線程等待相等的重試時間的概率就高的多（或者非常接近以至于會出現(xiàn)問題）。 (譯者注：超時和重試機(jī)制是為了避免在同一時間出現(xiàn)的競爭，但是當(dāng)線程很多時，其中兩個或多個線程的超時時間一樣或者接近的可能性就會很大，因此就算出現(xiàn)競爭而導(dǎo)致超時后，由于超時時間一樣，它們又會同時開始重試，導(dǎo)致新一輪的競爭，帶來了新的問題。)
這種機(jī)制存在一個問題，在JAVA中不能對synchronized同步塊設(shè)置超時時間。你需要創(chuàng)建一個自定義鎖，或使用Java5中java.util.concurrent包下的工具。寫一個自定義鎖類不復(fù)雜，但超出了本文的內(nèi)容。后續(xù)的Java并發(fā)系列會涵蓋自定義鎖的內(nèi)容。
死鎖檢測
死鎖檢測是一個更好的死鎖預(yù)防機(jī)制，它主要是針對那些不可能實現(xiàn)按序加鎖并且鎖超時也不可行的場景。
每當(dāng)一個線程獲得了鎖，會在線程和鎖相關(guān)的數(shù)據(jù)結(jié)構(gòu)中（map、graph等等）將其記下。
除此之外，每當(dāng)有線程請求鎖，也需要記錄在這個數(shù)據(jù)結(jié)構(gòu)中。
當(dāng)一個線程請求鎖失敗時，這個線程可以遍歷鎖的關(guān)系圖看看是否有死鎖發(fā)生。
例如，線程A請求鎖7，但是鎖7這個時候被線程B持有，這時線程A就可以檢查一下線程B是否已經(jīng)請求了線程A當(dāng)前所持有的鎖。
如果線程B確實有這樣的請求，那么就是發(fā)生了死鎖（線程A擁有鎖1，請求鎖7；線程B擁有鎖7，請求鎖1）。
當(dāng)然，死鎖一般要比兩個線程互相持有對方的鎖這種情況要復(fù)雜的多。
線程A等待線程B，線程B等待線程C，線程C等待線程D，線程D又在等待線程A。
線程A為了檢測死鎖，它需要遞進(jìn)地檢測所有被B請求的鎖。
從線程B所請求的鎖開始，線程A找到了線程C，然后又找到了線程D，發(fā)現(xiàn)線程D請求的鎖被線程A自己持有著。這是它就知道發(fā)生了死鎖。
下面是一幅關(guān)于四個線程（A,B,C和D）之間鎖占有和請求的關(guān)系圖。像這樣的數(shù)據(jù)結(jié)構(gòu)就可以被用來檢測死鎖。
死鎖檢測
那么當(dāng)檢測出死鎖時，這些線程該做些什么呢？
一個可行的做法是釋放所有鎖，回退，并且等待一段隨機(jī)的時間后重試。這個和簡單的加鎖超時類似，不一樣的是只有死鎖已經(jīng)發(fā)生了才回退，而不會是因為加鎖的請求超時了。雖然有回退和等待，但是如果有大量的線程競爭同一批鎖，它們還是會重復(fù)地死鎖（編者注：原因同超時類似，不能從根本上減輕競爭）。
一個更好的方案是給這些線程設(shè)置優(yōu)先級，讓一個（或幾個）線程回退，剩下的線程就像沒發(fā)生死鎖一樣繼續(xù)保持著它們需要的鎖。如果賦予這些線程的優(yōu)先級是固定不變的，同一批線程總是會擁有更高的優(yōu)先級。為避免這個問題，可以在死鎖發(fā)生的時候設(shè)置隨機(jī)的優(yōu)先級。
開放調(diào)用避免死鎖
在協(xié)作對象之間發(fā)生死鎖的例子中，主要是因為在調(diào)用某個方法時就需要持有鎖，并且在方法內(nèi)部也調(diào)用了其他帶鎖的方法！
如果在調(diào)用某個方法時不需要持有鎖，那么這種調(diào)用被稱為開放調(diào)用！
我們可以這樣來改造：
同步代碼塊最好僅被用于保護(hù)那些涉及共享狀態(tài)的操作！
class CooperatingNoDeadlock {
@ThreadSafe
class Taxi {
@GuardedBy("this") private Point location, destination;
private final Dispatcher dispatcher;
public Taxi(Dispatcher dispatcher) {
this.dispatcher = dispatcher;
}
public synchronized Point getLocation() {
return location;
}
public synchronized void setLocation(Point location) {
boolean reachedDestination;
// 加Taxi內(nèi)置鎖
synchronized (this) {
this.location = location;
reachedDestination = location.equals(destination);
}
// 執(zhí)行同步代碼塊后完畢，釋放鎖
if (reachedDestination)
// 加Dispatcher內(nèi)置鎖
dispatcher.notifyAvailable(this);
}
public synchronized Point getDestination() {
return destination;
}
public synchronized void setDestination(Point destination) {
this.destination = destination;
}
}
@ThreadSafe
class Dispatcher {
@GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
public Dispatcher() {
taxis = new HashSet<Taxi>();
availableTaxis = new HashSet<Taxi>();
}
public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis.add(taxi);
}
public Image getImage() {
Set<Taxi> copy;
// Dispatcher內(nèi)置鎖
synchronized (this) {
copy = new HashSet<Taxi>(taxis);
}
// 執(zhí)行同步代碼塊后完畢，釋放鎖
Image image = new Image();
for (Taxi t : copy)
// 加Taix內(nèi)置鎖
image.drawMarker(t.getLocation());
return image;
}
}
class Image {
public void drawMarker(Point p) {
}
}
}
小結(jié)
我們對死鎖是什么？常見的場景等做了解答。
結(jié)合實際工作中，如何分析發(fā)現(xiàn)，以及如何解決提供了理論和實際的方案。
理解發(fā)生的原因，才能更好地解決問題。
關(guān)于死鎖檢測，是個不錯的思路。是否可以針對這個專門寫一套框架？提供優(yōu)雅的解決方案。小伙伴們有沒有想嘗試一下的？
希望本文對你有幫助，如果有其他想法的話，也可以評論區(qū)和大家分享哦。
