一、什么是死鎖
當(dāng)兩個或兩個以上的線程在執(zhí)行過程中，因為爭奪資源而造成的一種相互等待的狀態(tài)，由于存在一種環(huán)路的鎖依賴關(guān)系而永遠(yuǎn)地等待下去，如果沒有外部干涉，他們將永遠(yuǎn)等待下去，此時的這個狀態(tài)稱之為死鎖。
經(jīng)典的 “哲學(xué)家進餐” 問題很好地描述了死鎖狀況：
5個哲學(xué)家去吃中餐，坐在一張圓桌旁，他們有5根筷子(而不是5雙)，并且每兩個人中間放一根筷子，哲學(xué)家們要么在思考，要么在進餐，每個人都需要一雙筷子才能吃到東西，并在吃完后將筷子放回原處繼續(xù)思考，有些筷子管理算法 (1) 能夠使每個人都能相對及時的吃到東西，但有些算法卻可能導(dǎo)致一些或者所有哲學(xué)家都"餓死"，后一種情況將產(chǎn)生死鎖：每個人都擁有其他人需要的資源，同時有等待其他人已經(jīng)擁有的資源，并且每個人在獲取所有需要的資源之前都不會放棄已經(jīng)擁有的資源。筷子管理算法(1)：一個饑餓的科學(xué)家會嘗試獲得兩根臨近的筷子，但如果其中一根正在被另一個科學(xué)家使用，那么他將放棄已經(jīng)得到的那根筷子，并在等待幾分鐘之后嘗試
死鎖：每個人都立即抓住自己左邊的筷子，然后等待自己右邊的筷子空出來，但同時又不放下已經(jīng)拿到的筷子，形成一種相互等待的狀態(tài)。
饑餓：哲學(xué)家們都同時想吃飯，同時拿起左手邊筷子，但是發(fā)現(xiàn)右邊沒有筷子，于是哲學(xué)家又同時放下左手邊筷子，然后大家發(fā)現(xiàn)又有筷子了，又同時開始拿起左手邊筷子，又同時放下，然后反復(fù)進行。
在線程A持有鎖L并想獲得鎖M的同時，線程B持有鎖M并嘗試獲得鎖L，那么這兩個線程將永遠(yuǎn)地等待下去，這種情況就是死鎖形式（或者稱為"抱死"）.
二、死鎖的四個必要條件
互斥條件：指進程對所分配到的資源進行排它性使用，即在一段時間內(nèi)某資源只由一個進程占用。如果此時還有其它進程請求資源，則請求者只能等待，直至占有資源的進程用完釋放。
請求和保持條件：指進程已經(jīng)保持至少一個資源，但又提出了新的資源請求，而該資源已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。
不剝奪條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。
環(huán)路等待條件：指在發(fā)生死鎖時，必然存在一個進程——資源的環(huán)形鏈，即進程集合{A，B，C，···，Z} 中的A正在等待一個B占用的資源；B正在等待C占用的資源，……，Z正在等待已被A占用的資源。
三、死鎖實例
/**
* 死鎖類示例
*/
public class DeadLock implements Runnable {
public int flag = 1;
//靜態(tài)對象是類的所有對象共享的
private static Object o1 = new Object(), o2 = new Object();
@Override
public void run() {
System.out.println("flag:{}"+flag);
if (flag == 1) {
//先鎖o1，再對o2加鎖，環(huán)路等待條件
synchronized (o1) {
try {
Thread.sleep(500);
}
catch (Exception e) {
e.printStackTrace();
}
synchronized (o2) {
System.out.println("1");
}
}
}
if (flag == 0) {
//先鎖o2，在鎖01
synchronized (o2) {
try {
Thread.sleep(500);
}
catch (Exception e) {
e.printStackTrace();
}
synchronized (o1) {
System.out.println("0");
}
}
}
}
public static void main(String[] args) {
DeadLock td1 = new DeadLock();
DeadLock td2 = new DeadLock();
td1.flag = 1;
td2.flag = 0;
//td1,td2都處于可執(zhí)行狀態(tài)，但JVM線程調(diào)度先執(zhí)行哪個線程是不確定的。
//td2的run()可能在td1的run()之前運行
new Thread(td1).start();
new Thread(td2).start();
}
}
1、當(dāng)DeadLock 類的對象flag=1時（td1），先鎖定o1,睡眠500毫秒
2、而td1在睡眠的時候另一個flag==0的對象（td2）線程啟動，先鎖定o2,睡眠500毫秒
3、td1睡眠結(jié)束后需要鎖定o2才能繼續(xù)執(zhí)行，而此時o2已被td2鎖定；
4、td2睡眠結(jié)束后需要鎖定o1才能繼續(xù)執(zhí)行，而此時o1已被td1鎖定；
5、td1、td2相互等待，都需要得到對方鎖定的資源才能繼續(xù)執(zhí)行，從而死鎖。
動態(tài)鎖順序死鎖：
// 資金轉(zhuǎn)賬到賬號
public static void transferMoney(Account fromaccount,
Account toAccount,
DollarAmount amount)
throws InsufficientFundsException {
// 鎖定匯款者的賬戶
synchronized (fromAccount) {
// 鎖定到賬者的賬戶
synchronized (toAccount) {
// 判斷賬戶的余額不能為負(fù)數(shù)
if (fromAccount.getBalance().compareTo(amount) < 0) {
throw new InsufficientFundsException();
} else {
// 匯款者的賬戶減錢
fromAccount.debit(amount);
// 到賬者的賬戶增錢
toAccount.credit(amount);
}
}
}
}
上面的代碼看起來都是按照相同的順序來獲得鎖的，按道理來說是沒有問題，但是上述代碼中上鎖的順序取決于傳遞給transferMoney()的參數(shù)順序，而這些參數(shù)順序又取決于外部的輸入
- 如果兩個線程（A和B）同時調(diào)用transferMoney()
- 其中一個線程(A)，從X向Y轉(zhuǎn)賬：transferMoney(myAccount,yourAccount,10);
- 另一個線程(B)，從Y向X轉(zhuǎn)賬 ：transferMoney(yourAccount,myAccount,20);
- 此時 A線程 可能獲得 myAccount 的鎖并等待 yourAccount的鎖，然而 B線程 此時已經(jīng)持有 yourAccount 的鎖，并且正在等待 myAccount 的鎖，這種情況下就會發(fā)生死鎖。
當(dāng)一組JAVA線程發(fā)生死鎖的時候，那么這些線程永遠(yuǎn)不能再使用了，根據(jù)線程完成工作的不同，可能會造成應(yīng)用程序的完全停止，或者某個特定的子系統(tǒng)不能再使用了，或者是性能降低，這個時候恢復(fù)應(yīng)用程序的唯一方式就是中止并重啟它，死鎖造成的影響很少會立即顯現(xiàn)出來，如果一個類發(fā)生死鎖，并不意味著每次都會發(fā)生死鎖，而只是表示有可能，當(dāng)死鎖出現(xiàn)的時候，往往是在最糟糕的時候——在高負(fù)載的情況下。
四、死鎖的避免與檢測
4.1 預(yù)防死鎖
- 破壞互斥條件：使資源同時訪問而非互斥使用，就沒有進程會阻塞在資源上，從而不發(fā)生死鎖
- 破壞請求和保持條件：采用靜態(tài)分配的方式，靜態(tài)分配的方式是指進程必須在執(zhí)行之前就申請需要的全部資源，且直至所要的資源全部得到滿足后才開始執(zhí)行，只要有一個資源得不到分配，也不給這個進程分配其他的資源。
- 破壞不剝奪條件：即當(dāng)某進程獲得了部分資源，但得不到其它資源，則釋放已占有的資源，但是只適用于內(nèi)存和處理器資源。
- 破壞循環(huán)等待條件：給系統(tǒng)的所有資源編號，規(guī)定進程請求所需資源的順序必須按照資源的編號依次進行。
4.2 設(shè)置加鎖順序
如果兩個線程（A和B）,當(dāng)A線程已經(jīng)鎖住了Z，而又去嘗試鎖住X，而X已經(jīng)被線程B鎖住，線程A和線程B分別持有對應(yīng)的鎖，而又去爭奪其他一個鎖（嘗試鎖住另一個線程已經(jīng)鎖住的鎖）的時候，就會發(fā)生死鎖，如下圖：
兩個線程試圖以不同的順序來獲得相同的鎖，如果按照相同的順序來請求鎖，那么就不會出現(xiàn)循環(huán)的加鎖依賴性，因此也就不會產(chǎn)生死鎖，每個需要鎖Z和鎖X的線程都以相同的順序來獲取Z和X，那么就不會發(fā)生死鎖了，如下圖所示：
- 這樣死鎖就永遠(yuǎn)不會發(fā)生。 針對兩個特定的鎖，可以嘗試按照鎖對象的hashCode值大小的順序，分別獲得兩個鎖，這樣鎖總是會以特定的順序獲得鎖，我們通過設(shè)置鎖的順序，來防止死鎖的發(fā)生，在這里我們使用System.identityHashCode方法來定義鎖的順序，這個方法將返回由Obejct.hashCode 返回的值，這樣就可以消除死鎖發(fā)生的可能性。
public class DeadLockExample3 {
// 加時賽鎖，在極少數(shù)情況下，如果兩個hash值相等，使用這個鎖進行加鎖
private static final Object tieLock = new Object();
public void transferMoney(final Account fromAcct,
final Account toAcct,
final DollarAmount amount)
throws InsufficientFundsException {
class Helper {
public void transfer() throws InsufficientFundsException {
if (fromAcct.getBalance().compareTo(amount) < 0)
throw new InsufficientFundsException();
else {
fromAcct.debit(amount);
toAcct.credit(amount);
}
}
}
// 得到兩個鎖的hash值
int fromHash = System.identityHashCode(fromAcct);
int toHash = System.identityHashCode(toAcct);
// 根據(jù)hash值判斷鎖順序，決定鎖的順序
if (fromHash < toHash) {
synchronized (fromAcct) {
synchronized (toAcct) {
new Helper().transfer();
}
}
} else if (fromHash > toHash) {
synchronized (toAcct) {
synchronized (fromAcct) {
new Helper().transfer();
}
}
} else {// 如果兩個對象的hash相等，通過tieLock來決定加鎖的順序，否則又會重新引入死鎖——加時賽鎖
synchronized (tieLock) {
synchronized (fromAcct) {
synchronized (toAcct) {
new Helper().transfer();
}
}
}
}
}
}
- 在極少數(shù)情況下，兩個對象可能擁有兩個相同的散列值，此時必須通過某種任意的方法來決定鎖的順序，否則可能又會重新引入死鎖。
- 為了避免這種情況，可以使用 “加時(Tie-Breaking)）”鎖，這獲得這兩個Account鎖之前，從而消除了死鎖發(fā)生的可能性
4.3 支持定時的鎖（超時放棄）
有一項技術(shù)可以檢測死鎖和從死鎖中恢復(fù)過來，就是使用Lock類中的定時public boolean tryLock(long time, TimeUnit unit) throws InterruptedException功能，來代替內(nèi)置鎖機制，當(dāng)使用內(nèi)置鎖的時候，只要沒有獲得鎖，就會永遠(yuǎn)等待下去，而tryLock可以指定一個超時時間(Timeout)，在等待超過時間后tryLock會返回一個失敗信息，如果超時時限比獲取鎖的時間要長很多，那么就可以在發(fā)生某個意外后重新獲得控制權(quán)。如下圖所示：
4.4 死鎖避免
死鎖防止方法能夠防止發(fā)生死鎖，但必然會降低系統(tǒng)并發(fā)性，導(dǎo)致低效的資源利用率，其中最具有代表性的避免死鎖算法是銀行家算法。
1、多個資源的銀行家算法
上圖中有五個進程，四個資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個為向量，而不是具體數(shù)值，例如 A=(1020)，表示 4 個資源分別還剩下 1/0/2/0。
檢查一個狀態(tài)是否安全的算法如下：
- 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統(tǒng)將會發(fā)生死鎖，狀態(tài)是不安全的。
- 假若找到這樣一行，將該進程標(biāo)記為終止，并將其已分配資源加到 A 中。
- 重復(fù)以上兩步，直到所有進程都標(biāo)記為終止，則狀態(tài)時安全的。
- 如果一個狀態(tài)不是安全的，需要拒絕進入這個狀態(tài)。
4.5 死鎖檢測
- 對資源的分配加以適當(dāng)限制可防止或避免死鎖發(fā)生，但不利于進程對系統(tǒng)資源的充分共享。
- 為每個進程和每個資源指定一個唯一的號碼
- Jstack命令
jstack用于生成java虛擬機當(dāng)前時刻的線程快照。線程快照是當(dāng)前java虛擬機內(nèi)每一條線程正在執(zhí)行的方法堆棧的集合，生成線程快照的主要目的是定位線程出現(xiàn)長時間停頓的原因，如線程間死鎖、死循環(huán)、請求外部資源導(dǎo)致的長時間等待，線程出現(xiàn)停頓的時候通過jstack來查看各個線程的調(diào)用堆棧，就可以知道沒有響應(yīng)的線程到底在后臺做什么事情，或者等待什么資源。
- JConsole工具
Jconsole是JDK自帶的監(jiān)控工具，在JDK/bin目錄下可以找到。它用于連接正在運行的本地或者遠(yuǎn)程的JVM，對運行在Java應(yīng)用程序的資源消耗和性能進行監(jiān)控，并畫出大量的圖表，提供強大的可視化界面。而且本身占用的服務(wù)器內(nèi)存很小，甚至可以說幾乎不消耗。
4.5 死鎖恢復(fù)
- 資源剝奪：剝奪陷于死鎖的進程所占用的資源，但并不撤銷此進程，直至死鎖解除
- 進程回退：根據(jù)系統(tǒng)保存的檢查點讓所有的進程回退，直到足以解除死鎖，這種措施要求系統(tǒng)建立保存檢查點、回退及重啟機制
- 進程撤銷：
1、撤銷陷入死鎖的所有進程，解除死鎖，繼續(xù)運行。2、逐個撤銷陷入死鎖的進程，回收其資源并重新分配，直至死鎖解除。 可選擇符合下面條件之一的先撤銷： 1.CPU消耗時間最少者 2.產(chǎn)生的輸出量最小者 3.預(yù)計剩余執(zhí)行時間最長者 4.分得的資源數(shù)量最少者后優(yōu)先級最低者
- 系統(tǒng)重啟：結(jié)束所有進程的執(zhí)行并重新啟動操作系統(tǒng)。這種方法很簡單，但先前的工作全部作廢。
