死鎖-有解無憂

文章目錄

- 一.簡介
- 二.預防死鎖
- - 2.1 破壞占用且等待條件
  - 2.2 破壞不可搶占條件
  - 2.3 破壞回圈等待條件
  - 2.4 小結

一.簡介

根據上一篇文章互斥鎖

死鎖實驗，死鎖定義：一組互相互相競爭資源的執行緒因互相等待，導致“永久”阻塞的現象，

class Account {
  private int balance;
  // 轉賬
  void transfer(Account target, int amt){
    // 鎖定轉出賬戶
    synchronized(this){     ①
      // 鎖定轉入賬戶
      synchronized(target){ ②
        if (this.balance > amt) {
          this.balance -= amt;
          target.balance += amt;
        }
      }
    }
  } 
}

我們假設執行緒 T1 執行賬戶 A 轉賬戶 B 的操作，賬戶 A.transfer(賬戶 B)；同時執行緒 T2 執行賬戶 B 轉賬戶 A 的操作，賬戶 B.transfer(賬戶 A)，當 T1 和 T2 同時執行完①處的代碼時，T1 獲得了賬戶 A 的鎖（對于 T1，this 是賬戶 A），而 T2 獲得了賬戶 B 的鎖（對于 T2，this 是賬戶 B），之后 T1 和 T2 在執行②處的代碼時，T1 試圖獲取賬戶 B 的鎖時，發現賬戶 B 已經被鎖定（被 T2 鎖定），所以 T1 開始等待；T2 則試圖獲取賬戶 A 的鎖時，發現賬戶 A 已經被鎖定（被 T1 鎖定），所以 T2 也開始等待，于是 T1 和 T2 會無期限地等待下去，也就是我們所說的死鎖了，

二.預防死鎖

Coffman 大佬，總結發生死鎖條件

互斥，共享資源X和Y只能被一個執行緒占用；
占用且等待，執行緒T1已經取得共享資源X，在等待共享資源Y的時候，不釋放共享資源X;
不可搶占，其他執行緒不能強行搶占執行緒T1占有的資源；
回圈等待，執行緒T1等待執行緒T2占有資源，執行緒T2等待執行緒T1占有的資源，就是回圈等待，

破壞其中一個，就可以避免死鎖的發生，

解決

對應“占用且等待”這個條件，我們可以一次性申請所有的資源，這樣就不存在等待了，
對于“不可搶占”這個條件，占用部分資源的執行緒進一步申請其他資源時，如果申請不到，可以主動釋放它占有的資源，這樣不可搶占這個條件就破壞掉了，
對于“回圈等待”這個條件，可以靠按序申請資源來預防，所謂按序申請，是指資源是有線性順序的，申請的時候可以先申請資源序號小的，再申請資源序號大的，這樣線性化后自然就不存在回圈了，

2.1 破壞占用且等待條件

從理論上講，要破壞這個條件，可以一次性申請所有資源，在現實世界里，就拿前面我們提到的轉賬操作來講，它需要的資源有兩個，一個是轉出賬戶，另一個是轉入賬戶，當這兩個賬戶同時被申請時，

@Data
public class AccountClassLock4 {
    private Allocator actr = Allocator.getInstance();
    private int balance;
    public AccountClassLock4(int balance) {
        this.balance = balance;
    }
    //轉賬
    public void transfer(AccountClassLock4 target,int amt){
        //申請轉出和轉入賬號，直到成功
        while (!actr.apply(this,target)) {  }
        try {
            synchronized (this){
                synchronized (target){
                    if (this.balance > amt){
                        this.balance -= amt;
                        target.balance += amt;
                    }
                }
            }
        }finally {
            actr.free(this,target);
        }
    }
    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10000; i++) {
            AccountClassLock4 a = new AccountClassLock4(200);
            AccountClassLock4 b = new AccountClassLock4(200);
            AccountClassLock4 c = new AccountClassLock4(200);
            Thread t1 = new Thread(()->{
                a.transfer(b,100);
            });
            Thread t2 = new Thread(()->{
                b.transfer(c,100);
            });
            t1.start();
            t2.start();
            t2.join();
            System.out.println(a.getBalance());
            System.out.println(b.getBalance());
            System.out.println(c.getBalance());
            System.out.println("----------------");
        }
    }
}
class Allocator{
    private static Allocator instance = new Allocator();
    public static Allocator getInstance() {
        return instance;
    }
    private Allocator(){}
    private List<Object> als = new ArrayList<>();
    synchronized boolean apply(Object a,Object b){
        if(als.contains(a) || als.contains(b)){
            return false;
        }else{
            als.add(a);
            als.add(b);
        }
        return true;
    }
    synchronized void free(Object a,Object b){
        als.remove(a);
        als.remove(b);
    }
}

優化

// 一次性申請轉出賬戶和轉入賬戶，直到成功
while(!actr.apply(this, target))
  ；

如果 apply() 操作耗時非常短，而且并發沖突量也不大時，這個方案還挺不錯的，因為這種場景下，回圈上幾次或者幾十次就能一次性獲取轉出賬戶和轉入賬戶了，但是如果 apply() 操作耗時長，或者并發沖突量大的時候，回圈等待這種方案就不適用了，因為在這種場景下，可能要回圈上萬次才能獲取到鎖，太消耗 CPU 了，
利用等待-通知模式優化，使用執行緒阻塞方式就避免回圈等待消耗CPU的問題，

@Data
public class AccountClassLock7 {
    private Allocator actr = Allocator.getInstance();
    private int balance;

    public AccountClassLock7(int balance) {
        this.balance = balance;
    }
    public void transfer(AccountClassLock7 target,int amt){
        actr.apply(this,target);
        try {
              if (this.balance > amt){
                   this.balance -= amt;
                   target.balance += amt;
              }
        }finally {
            actr.free(this,target);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10000; i++) {
            AccountClassLock7 a = new AccountClassLock7(200);
            AccountClassLock7 b = new AccountClassLock7(200);
            AccountClassLock7 c = new AccountClassLock7(200);
            Thread t1 = new Thread(()->{
                a.transfer(b,100);
            });
            Thread t2 = new Thread(()->{
                b.transfer(c,100);
            });
            t1.start();
            t2.start();
            t2.join();
            System.out.println(a.getBalance());
            System.out.println(b.getBalance());
            System.out.println(c.getBalance());
            System.out.println("----------------");
        }

    }

    static class Allocator{
        private static Allocator instance = new Allocator();
        public static Allocator getInstance() {
            return instance;
        }
        private Allocator(){}
        private List<Object> als = new ArrayList<>();
        synchronized void apply(Object a,Object b){
            while(als.contains(a) || als.contains(b)){
                try {
                    this.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            als.add(a);
            als.add(b);
        }
        synchronized void free(Object a,Object b){
            als.remove(a);
            als.remove(b);
            this.notifyAll();
        }

    }
}

注意

因為notify()只能保證通知時間點，條件滿足，而被通知執行緒的執行時間點和通知的時間點基本上不會重合，所以當執行緒執行的時候，很可能條件已經不滿足（保不齊有其他執行緒插隊），

2.2 破壞不可搶占條件

破壞不可搶占條件看上去很簡單，核心是要能夠主動釋放它占有的資源，這一點 synchronized 是做不到的，原因是 synchronized 申請資源的時候，如果申請不到，執行緒直接進入阻塞狀態了，而執行緒進入阻塞狀態，啥都干不了，也釋放不了執行緒已經占有的資源，

@Data
public class AccountClassLock6 {
    private int balance;
    private final Lock locks = new ReentrantLock();
    public AccountClassLock6(int balance) {
        this.balance = balance;
    }
    public void transfer(AccountClassLock6 target,int amt) throws InterruptedException {
        boolean flag = true;
        Random random = new Random();
        while (flag){
            if(this.locks.tryLock(random.nextInt(1000)+1 , TimeUnit.MILLISECONDS)){
                try {
                    if(target.locks.tryLock()){
                        try {
                            if(this.balance > amt){
                                this.balance -= amt;
                                target.balance += amt;
                                flag = false;
                            }
                        }finally {
                            target.locks.unlock();
                        }
                    }
                }finally {
                    this.locks.unlock();
                }
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10000; i++) {
            AccountClassLock6 a = new AccountClassLock6(200);
            AccountClassLock6 b = new AccountClassLock6(200);
            AccountClassLock6 c = new AccountClassLock6(200);
            Thread t1 = new Thread(()->{
                try {
                    a.transfer(b,100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });

            Thread t2 = new Thread(()->{
                try {
                    b.transfer(c,100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });

            t1.start();
            t2.start();
            t2.join();
            System.out.println(a.getBalance());
            System.out.println(b.getBalance());
           System.out.println(c.getBalance());
            System.out.println("----------------");
        }
    }
}

只在外層Lock加上阻塞時間就行，如果在內層加上，內層鎖阻塞一段時間，外層鎖沒有釋放，這段時間可能形成死鎖，破壞活鎖一個隨機時間就夠了，

2.3 破壞回圈等待條件

破壞這個條件，需要對資源進行排序，然后按序申請資源，這個實作非常簡單，我們假設每個賬戶都有不同的屬性 id，這個 id 可以作為排序欄位，申請的時候，我們可以按照從小到大的順序來申請，

@Data
public class AccountClassLock5 {
    private int id;
    private int balance;
    public AccountClassLock5(int id, int balance) {
        this.id = id;
        this.balance = balance;
    }
    public void transfer(AccountClassLock5 target,int amt){
        AccountClassLock5 left = this;
        AccountClassLock5 right = target;
        if(left.id > right.id){
            left = target;
            right = this;
        }
        synchronized (left){
            synchronized (right){
                if (this.balance > amt) {
                    this.balance -= amt;
                    target.balance += amt;
                }
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10000; i++) {
            AccountClassLock5 a = new AccountClassLock5(1, 200);
            AccountClassLock5 b = new AccountClassLock5(2, 200);
            AccountClassLock5 c = new AccountClassLock5(3, 200);
            Thread t1 = new Thread(()->{
               a.transfer(b,100);
            });

            Thread t2 = new Thread(()->{
                b.transfer(c,100);
            });

            t1.start();
            t2.start();
            t2.join();
            System.out.println(a.getBalance());
            System.out.println(b.getBalance());
            System.out.println(c.getBalance());
            System.out.println("----------------");
        }
        
    }
}

2.4 小結

并發大師 Doug Lea《Java 并發編程：設計原則與模式》一書中，推薦的三個用鎖的最佳實踐

永遠只在更新物件的成員變數時加鎖；
永遠只在訪問可變的成員時加鎖；
永遠不在呼叫其他物件的方法時加鎖，

參考

《Java并發編程實戰》

公眾號

微信公眾號（bigdata_limeng）

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/218606.html

標籤：其他

上一篇：格式化字串漏洞實驗

下一篇：網路嗅探（Sniffing）與身份認證