Deadlock gossip

Previously, locks and protected resources were 1：N The relationship between , These protected resources may not be related to each other , It may also be related to each other . So what's the difference ？ How did deadlock happen ？ How to avoid deadlock ？

Protect multiple resources that are not related

Because these resources have nothing to do with each other , We can stuff them all into this It's all done in this lock , We can also add different locks to different resources and divide and rule . In general, the performance of parallel divide and conquer is much better than that of serial lock . The lock of divide and rule is also called Fine grained lock

Protect multiple resources that are related

Can associated resources be locked like unrelated resources ？

Let's take a chestnut ：

1. Yes A、B、C Three bank accounts , The account balance is 200

2.A to B Transfer accounts 100,B to C Transfer accounts 100

If we don't lock it ：

class Account {
  private int balance;
  //  Transfer accounts 
  void transfer(Account target, int amt){
    if (this.balance > amt) {
      this.balance -= amt;
      target.balance += amt;
    }
  } 
}

In this case, there is no mutual exclusion , There is no atomic operation , There will be concurrency problems .

Then we'll lock it , First, stuff all resources into one object Try it in the lock ：

class Account {
  private int balance;
  //  Transfer accounts 
  synchronized void transfer(Account target, int amt){
    if (this.balance > amt) {
      this.balance -= amt;
      target.balance += amt;
    }
  } 
}

The two associated resources are in the critical area of the current object lock , But we found that locking the current object can only lock the variables of the current object balance No locking target Object's balance. Because the concept of object lock is , To enter the code block of the object lock, you must first get the lock of the object .

Threads 1 Got it A The object lock of the account , It began to be right A Out of account , Yes B Enter in the account ; Threads 2 Get it, but B The object of the lock , It began to be right B Billing right C Enter in the account . So the two threads are aligned at the same time B The account has been operated ：

We expect that after the transfer A、B、C The balances of are 100 200 300.

But in fact B The balance value of the account 100 200 300 There will be all three results , It depends on which of the two threads put B The result of is written to memory .

since Object lock No, then add Kind of lock try ：

class Account {
  private int balance;
  //  Transfer accounts 
  void transfer(Account target, int amt){
    synchronized(Account.class) {
      if (this.balance > amt) {
        this.balance -= amt;
        target.balance += amt;
      }
    }
  } 
}

Kind of lock The advantage is that the operation of critical zone is absolutely unique , All object operations of this class use the same lock , This ensures that no matter how many threads , Can enter the critical zone right B Only .

however , Imagine if hundreds of millions of accounts are executed in such a fool's order , How slow should that be . We mentioned earlier that fine-grained locking performance will be better , Account A Transfer account B, Account C Transfer account D There is no mutual exclusion , It can be done at the same time . We are content to lock the transfer in and transfer out accounts OK, There is no need to add a global lock .

class Account {
  private int balance;
  //  Transfer accounts 
  void transfer(Account target, int amt){
    //  Lock out transfer out account 
    synchronized(this) {              
      //  Lock transfer in account 
      synchronized(target) {           
        if (this.balance > amt) {
          this.balance -= amt;
          target.balance += amt;
        }
      }
    }
  } 
}

The lock of the current object is protected this.balance ,target The lock of the object is protected target.balance Fine grained two operations to achieve parallel operations . But there are traps behind seemingly beautiful things , Programming is the same .

Take the above example , If A To give B Transfer accounts ,B Just want to give A Transfer accounts , No problem , It can be done in parallel . But the problem is , The two threads put the current object at the beginning this Lock the , That is to put each other's resources balance Home lock .A etc. B Give it balance information , meanwhile B Also waiting for A Give him balance information . Then there is no compromise , Just wait blindly . In this way, a closed loop without solution is formed , A bad relationship ： Deadlock .

How to prevent deadlock ？

The simplest and crudest solution is to restart , But in this way, we can treat the symptoms but not the root causes , In a similar situation, I'm as blind . So the best way is to avoid it , Consider its existence at the beginning of the design .

How to solve the deadlock problem , We stand on the shoulders of giants , So the giants have reached a conclusion . There's a man named Coffman The bull has long summarized the conditions for deadlock ：

1. Mutually exclusive , Shared resources X and Y Can only be occupied by one thread ;

2. To possess and wait for , Threads T1 Shared resources have been obtained X, Waiting to share resources Y When , Don't release shared resources X;

3. Do not take , Other threads cannot forcibly preempt threads T1 Resources in possession ;

4. Loop waiting for , Threads T1 Wait for thread T2 Resources in possession , Threads T2 Wait for thread T1 Resources in possession , It's a cycle of waiting .

How to solve , To sum up, break and then stand , In a stalemate, someone always wants to give in , Destroy the condition of deadlock .

I said before , Keep atomic operation , It is mutually exclusive . So the conditions 1, We can't destroy it . Then the remaining solution is ：

1. Destroy occupancy and wait for conditions

One thread applies for all resources at once . The above example , If we apply for A B Balance information of two accounts , Give it to an administrator T Manage applications , If A and B Missing one of the account balance information of indicates that the application fails . that A Transfer accounts B and B Transfer accounts A They are mutually exclusive , There will be no deadlock ;

It seems that distributed transactions can be implemented in this way

2. Destroy the non preemptive condition

Literally , If you can't preempt shared resources , Let it release the resources occupied by the thread . However synchronized It can't be done , If it cannot preempt resources, it will enter a blocking state , Resources occupied by threads will not be released .

Of course it can't , It doesn't mean that others can't , Don't you underestimate the heroes in the world . At least java.util.concurrent Provided under this package Lock This problem can be solved easily .

We often meet people who say synchronized and Lock The difference between , This is one of them .

3. Break cycle waiting condition

To break the cycle waiting condition , It's the closed loop without solution , Threads 1 occupy A Resources for , Threads 2 occupy B Resources for . Might as well give A and B Arrange the account resources in order . Then let the thread apply for resources . So if resources A At the top , Threads 1 Here it is A Resources for , Thread after locking 2 You cannot access resources A Critical area of lock , It is impossible to occupy B Of resources . Like the following code ：

class Account {
  private int id;
  private int balance;
  //  Transfer accounts 
  void transfer(Account target, int amt){
    Account left = this        ①
    Account right = target;    ②
    if (this.id > target.id) { ③
      left = target;           ④
      right = this;            ⑤
    }                          ⑥
    //  Lock the account with small number 
    synchronized(left){
      //  Lock accounts with large numbers 
      synchronized(right){ 
        if (this.balance > amt){
          this.balance -= amt;
          target.balance += amt;
        }
      }
    }
  } 
}

summary ：

There is a risk of deadlock in fine-grained locks , We should avoid it according to the situation .

Several conditions for breaking deadlock , Apply as appropriate .

The essence of atomicity is not indivisible , Instead, keep the middle state of the operation invisible . For example, the example of account transfer ：

A Transfer accounts B ,A Reduce 100 When B It hasn't changed yet , This is the intermediate state . Variables that have not yet completed the operation , Keep it invisible .