Java多線程死鎖避免方法

一、什么是死鎖
當兩個或兩個以上的線程在執行過程中，因為爭奪資源而造成的一種相互等待的狀態，由于存在一種環路的鎖依賴關系而永遠地等待下去，如果沒有外部干涉，他們將永遠等待下去，此時的這個狀態稱之為死鎖。
經典的 “哲學家進餐” 問題很好地描述了死鎖狀況：
5個哲學家去吃中餐，坐在一張圓桌旁，他們有5根筷子(而不是5雙)，并且每兩個人中間放一根筷子，哲學家們要么在思考，要么
在進餐，每個人都需要一雙筷子才能吃到東西，并在吃完后將筷子放回原處繼續思考，有些筷子管理算法 (1) 能夠使每個人都能相對及
時的吃到東西，但有些算法卻可能導致一些或者所有哲學家都"餓死"，后一種情況將產生死鎖：每個人都擁有其他人需要的資源，
同時有等待其他人已經擁有的資源，并且每個人在獲取所有需要的資源之前都不會放棄已經擁有的資源。
筷子管理算法(1)：一個饑餓的科學家會嘗試獲得兩根臨近的筷子，但如果其中一根正在被另一個科學家使用，那么他將放棄已經得到的
那根筷子，并在等待幾分鐘之后嘗試
死鎖：每個人都立即抓住自己左邊的筷子，然后等待自己右邊的筷子空出來，但同時又不放下已經拿到的筷子，形成一種相互等待的狀態。
饑餓：哲學家們都同時想吃飯，同時拿起左手邊筷子，但是發現右邊沒有筷子，于是哲學家又同時放下左手邊筷子，然后大家發現又有筷子了，又同時開始拿起左手邊筷子，又同時放下，然后反復進行。
在線程A持有鎖L并想獲得鎖M的同時，線程B持有鎖M并嘗試獲得鎖L，那么這兩個線程將永遠地等待下去，這種情況就是死鎖形式（或者稱為"抱死"）.
二、死鎖的四個必要條件
互斥條件：指進程對所分配到的資源進行排它性使用，即在一段時間內某資源只由一個進程占用。如果此時還有其它進程請求資源，則請求者只能等待，直至占有資源的進程用完釋放。
請求和保持條件：指進程XM代理申請www.kaifx.cn/broker/xm.html已經保持至少一個資源，但又提出了新的資源請求，而該資源已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。
不剝奪條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。
環路等待條件：指在發生死鎖時，必然存在一個進程——資源的環形鏈，即進程集合{A，B，C，···，Z} 中的A正在等待一個B占用的資源；B正在等待C占用的資源，……，Z正在等待已被A占用的資源。
三、死鎖實例
/**

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