死锁

发表于 | 分类于

死锁是常见的线程活性问题。多个线程互相等待对方而导致永远暂停称为死锁。常见的死锁q情况是线程A持有锁L1的情况下申请锁L2,线程B持有锁L2申请锁L1。线程A等待锁L2释放，线程B等待锁L1释放，从而互相等待永远暂停。

死锁的必要条件

  1. 资源互斥,资源同时只能被一个线程占用。
  2. 资源不可抢夺，资源被一个线程占用时，其他线程无法抢夺。
  3. 占用并等待资源，线程持有资源，并申请另外的资源而进入等待时。不会释放现有资源。
  4. 循环等待资源，线程A持有锁L1的情况下申请锁L2,线程B持有锁L2申请锁L1。线程A等待锁L2释放，线程B等待锁L1释放。A持有L1等L2,B持有L2等L1 这就是循环等待。

哲学家用餐问题

哲学家用餐问题是经典的死锁问题。一群哲学家围着一个大圆桌坐下，每个哲学家面前都有一个碗和一根筷子。哲学家要么思考要么吃饭。哲学家吃饭时总是先拿起左手边的筷子再拿起右手边的筷子。只有拿到2根筷子的哲学家可以吃饭。哲学家吃饭吃着会放下筷子，再次思考。

将问题简化，假设只有2个哲学家。哲学家p1想吃饭，先拿起他左边的筷子c1。这时哲学家p2也想吃饭,拿起他左边的筷子c2。哲学家相当于线程，筷子相当于锁。这样就进入死锁状态。
image

代码模拟

哲学家抽象类

定义哲学家的吃饭，思考动作和 身份标识id，左右筷子属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public abstract class AbstractPhilosopher  extends Thread {
    protected int id;
    protected Chopsticks left;
    protected Chopsticks right;
    public AbstractPhilosopher(int id,Chopsticks left,Chopsticks right){
        this.id=id;
        this.left=left;
        this.right=right;
    }

    @Override
    public void run() {
       //哲学家不是在思考，就是在吃饭
       while (true){
            think();
            eat();
        }
    }
    public  abstract  void  eat();
    public void think(){
        try {
            System.out.println(String.format("%s  thinking",this.toString()));
            Thread.sleep(new Random().nextInt(2)*1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public void doEat(){
        try {
            System.out.println(String.format("%s eating",this.toString()));
            Thread.sleep(new Random().nextInt(2)*1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

      @Override
    public String toString() {
          return String.format("Philosopher%d",this.id);
    }
}

筷子类

筷子类充当锁对象，获取锁相当于拿起筷子，释放锁相当于放下筷子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Chopsticks {
    private int id;
    public Chopsticks(int id){
        this.id=id;
    }

    public int getId() {
        return id;
    }
     @Override
    public String toString() {
        return String.format("Chopsticks%d",id);
    }
}

哲学家实现类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class DeadLockPhilosopher extends AbstractPhilosopher {
    public DeadLockPhilosopher(int id, Chopsticks left, Chopsticks right) {
        super(id, left, right);
    }
    @Override
    public void eat() {
         //拿起左边筷子
        synchronized (this.left){
            System.out.println(String.format("%s拿起%s",this.toString(),this.left.toString()));

            //为了使死锁发生频率高点，在这里等下哲学家2获取锁
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            synchronized (this.right){
                //拿起右边筷子
                System.out.println(String.format("%s拿起%s",this.toString(),this.right.toString()));
                this.doEat();
            }
        }
    }
}

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
 public static void main(String[] args) throws InterruptedException {

         Chopsticks c1 = new Chopsticks(1);
         Chopsticks c2 = new Chopsticks(2);
         //筷子c1是哲学家p1的左筷子，c2是p1的右筷子
         DeadLockPhilosopher p1 = new DeadLockPhilosopher(1,c1,c2);
          //筷子c2是哲学家p2的左筷子，c1是p2的右筷子
         DeadLockPhilosopher p2 = new DeadLockPhilosopher(2,c2,c1);
         p1.start();
         p2.start();

         p1.join();
}

运行结果

1
2
3
4
Philosopher1  thinking
Philosopher2  thinking
Philosopher2拿起Chopsticks2
Philosopher1拿起Chopsticks1

哲学家p2拿起了筷子c2,哲学家p1拿起了筷子c1。产生死锁。

避免死锁的解决方法

死锁的解决方法可以从死锁的产生条件入手。只要消除死锁四个必要条件之一就可以避免死锁。

粗粒锁法

通过一个大的锁来替代多个细粒度的锁。由于只有一个锁，死锁的必要条件占用并等待资源和循环等待资源都不成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class BigLogPhilosopher extends AbstractPhilosopher {
    private  final  static Object GLOBAL_LOCK=new Object();
    public BigLogPhilosopher(int id, Chopsticks left, Chopsticks right) {
        super(id, left, right);
    }

    @Override
    public void eat() {
        synchronized (GLOBAL_LOCK){
            //拿起左边
            System.out.println(String.format("%s拿起%s",this.toString(),this.left.toString()));
            //拿起右边筷子
            System.out.println(String.format("%s拿起%s",this.toString(),this.right.toString()));
            this.doEat();
        }
    }
}

粗粒锁的缺点是降低了并发，浪费资源。如果有4个哲学家的情况下，一个哲学家吃饭，还剩下2根筷子可以给一个哲学家同时用餐。
但是用粗粒锁的方法同时只能一个哲学家吃饭。

锁排序法

锁排序是给锁进行排序，所有线程申请锁都按排好的顺序。从而消除循环等待条件。

如哲学家问题中，给筷子排序，每次哲学家不按照左右顺序来拿筷子。而是都拿id小的筷子再拿大的。
所以哲学家p1,p2都会先拿筷子c1。当哲学家p1拿到筷子c1后，哲学家p2获取不到锁进入阻塞。死锁不会发送。

1
2
3
4
5
6
7
8
9
10
public class SortLockPhilosopher extends DeadLockPhilosopher {
    public SortLockPhilosopher(int id, Chopsticks left, Chopsticks right) {
        super(id, left, right);
        if(left.getId()>right.getId()){
            this.left=right;
            this.right=left;
        }
    }
    
}

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) throws InterruptedException {
    Chopsticks c1 = new Chopsticks(1);
    Chopsticks c2 = new Chopsticks(2);
    DeadLockPhilosopher p1 = new SortLockPhilosopher(1,c1,c2);
    DeadLockPhilosopher p2 = new SortLockPhilosopher(2,c2,c1);
    p1.start();
    p2.start();

    p1.join();
}

用tryLock(long,TimeUnit)

第三种方法是通过tryLock(long,TimeUnit),固定时间内获取不了锁就获取失败返回false。哲学家问题中，可以在超时获取不到锁的情况下，将本来就持有的锁放下，即可消除占有并等待资源条件，避免死锁。