Java Concurrency #3: 死鎖 — Deadlock

Charlie Lee
Bucketing
Published in
4 min readJul 13, 2020

開發多執行緒最容易遇到的問題,效率的成本Deadlock

Photo by Peter Nguyen on Unsplash

文章項目

  • 從上一篇文章最後的範例看
  • 死鎖的四個條件
  • 如何打破死鎖

回顧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套件去破解,互斥則是多執行緒避免可見性和原子性的必備要素所以不可以破解。

--

--