Java Concurrency #3: 死鎖 — Deadlock
開發多執行緒最容易遇到的問題，效率的成本Deadlock
文章項目
- 從上一篇文章最後的範例看
- 死鎖的四個條件
- 如何打破死鎖
回顧Java Concurrency (2) 什麼是鎖 — Lock文章最後一個範例
在Account object裡面，提供了一個轉帳的方法transfer，會先將自己和餘額操作相關的行為全部鎖起來，再去呼叫source account object的withdraw將錢從source轉到目前的Account object中，
有個非常關鍵的細節，在Account執行withdraw方法時會鎖住自己和餘額相關的操作，如果同時有兩個Account在Concurrency情況下，要互相轉帳就有可能發生下面類似的情形
- A和B Account都同時呼叫Transfer
- 都各自拿到本身物件的Balance Lock
- 向對方(A->B B->A)呼叫withdraw method
- 各自的withdraw method都因為lock被transfer拿走了所以無限等待
這種情況下發生的情形，就是所謂的DeadLock
死鎖的四個條件
- 禁止搶占（no preemption）：系統資源不能被強制從Thread退出。
- 持有和等待（hold and wait）：Thread可以在等待時持有系統資源。
- 互斥（mutual exclusion）：資源只能同時分配給一個Thread，無法多個行程共享。
- 循環等待（circular waiting）：Thread互相持有其他Thread所需要的資源，並且等待已被占用的資源。
只要符合上述的四個條件(四個都要)，那應用程式就可能會發生Deadlock的情形，而若是真的發生Deadlock情形，唯一解就是重啟應用程式了。
破解死鎖的方法
而要如何預防與破解Deadlock情形，可以根據在學演算法時，將主要問題分成子問題的方式破解，只要打破造成Deadlock循環四條件其中一個條件，那就苦盡甘來。接下來開始分析如和逐一擊破Deadlock四個條件:
- 禁止搶佔(no preemption): 當拿不到lock時，可以主動釋放目前擁有的資源(讓其它Prcoess先使用)
目前為止的文章內容，鎖都是透過Java最一般的方法執行(Synchronized / object lock)，要破解禁止搶佔會在後續的文章用JUC(Java util concurrency)展示，因為如果使用Synchronized那是沒有機會釋放鎖的，程式當遇到Synchronized就會進入等待，開發者無法將他跳出。
- 持有和等待(hold and wait) : 將需要的lock都拿走，一口氣拿走在執行完後再一口氣釋放，就不會有拿不到的問題
範例程式碼:
可以透過自行設計調度者(Allocator)，管理lock資源，將lock管理抽出程式邏輯，不過現在的設計有個缺點，Lock的申請是透過poll(輪詢)的方式會比較耗費CPU資源。
- 互斥(mutual exclusion)：這一點因為要避免原子性和可見性問題，所以互斥是必須的，無法從這此預防或破解
- 循環等待（circular waiting）：給每個Thread權限值，制定權限值的相關規則
範例程式碼:
這一段程式賦予每個Account ID值，讓在匯款時比對ID值，ID高的先鎖住在鎖住ID低的 Account，這個方法可以初步的打破循環等待的問題，但是若是Account一多還是有可能會Deadlock，進階解法會在後續文章使用JUC(Java util concurrency)展示。
總結
此篇文章，介紹了死鎖與造成死鎖的四個必要條件，在後半段透過兩個範例程式碼講解如何打破其中兩個特性，而其中禁止搶佔需要在之後的文章透過JUC套件去破解，互斥則是多執行緒避免可見性和原子性的必備要素所以不可以破解。
