Java的死锁及解决思路(延伸: 活锁,饥饿,无锁)

死锁：

A线程持有锁1，接下来要获取锁2；与此同时，B线程持有锁2，要获取锁1。两个线程都在等对方释放自己需要的锁，这时两方会永远等待下去，就形成了死锁。

死锁的四个必要条件：

1.互斥：资源(锁)同时只能被一个线程占用。

2.占有且等待：线程已经占用资源A，同时等待资源B时，不释放资源A。

3.不可抢占：其他线程不能强行获取当前线程占有的资源

4.循环等待：存在一个等待链，即T1等待T2占有的资源，T2等待T3占有的资源，T3等待T1占有的资源。

如果要解决死锁，则需要破坏任意一死锁的必要条件。

一.破坏占有且等待条件

解决方法：只要限定所有资源锁同时获取，同时释放。就可以预防掉死锁。其实就是破坏掉占有且等待条件。

下面以银行转账的代码为例子

/**
 * 锁分配类(单例)
 *
 * @author Liumz
 * @since 2019-04-02  15:57:32
 */
@Component
public class Allocator {
    /**
     * 已被申请锁的集合
     */
    private List<Object> locks = new ArrayList<>();
    /**
     * 申请锁
     *
     * @param timeOut   过期时间(秒)
     * @param lockArray 要申请的锁集合
     */
    public synchronized void apply(int timeOut, Object... lockArray) throws Exception {
        //如果当前不满足申请条件，则等待。直到资源被释放时进行notifyAll唤醒当前线程
        //while(condition){wait()} 是一个标准范式，线程如果被唤醒，执行时会再判断一次条件。
        LocalDateTime dtStart = LocalDateTime.now();
        while (Arrays.stream(lockArray).anyMatch(i -> this.locks.contains(i))) {
            //时间间隔达到5秒还未获取到条件锁，则抛出异常
            if (Duration.between(dtStart, LocalDateTime.now()).toMillis() > timeOut * 1000) {
                throw new Exception("放弃任务");
            }
            //释放当前对象锁，并等待
            try {
                this.wait(1000);
            } catch (InterruptedException ignore) {
            }
        }
        //如果已被申请锁的集合中没有要申请的锁，表示申请成功，并把申请成功的锁加入集合
        this.locks.addAll(Arrays.asList(lockArray));
    }
    /**
     * 释放锁
     *
     * @param lockArray 要释放的锁集合
     */
    public synchronized void free(Object... lockArray) {
        for (Object o : lockArray) {
            this.locks.remove(o);
        }
        //唤醒所有wait的线程，正在等待locks被移除释放的线程。尽量使用notifyAll，避免有的线程会不被唤醒，一直wait
        this.notifyAll();
    }
}

View Code

/**
 * 银行账户类
 *
 * @author Liumz
 * @since 2019-04-02  15:36:15
 */
@Component
@Scope("prototype")
public class BankAccount {
    /**
     * 余额
     */
    private int balance;
    /**
     * 锁分配对象
     */
    @Autowired
    private Allocator allocator;
    /**
     * 转账
     *
     * @param target 目标账户
     * @param amount 转账金额
     */
    public void transfer(BankAccount target, int amount) {
        //申请锁,如果申请不到会一直等待。除非超时时抛出异常
        try {
            this.allocator.apply(5, target, this);
        } catch (Exception e) {
            return;
        }
        try {
            //同时锁定目标和当前账户,避免出现死锁情况.并且进行账户余额加减操作
            synchronized (this) {
                synchronized (target) {
                    this.balance -= amount;
                    target.balance += amount;
                }
            }
        } finally {
            //同时释放加的两个锁
            this.allocator.free(target, this);
        }
    }
}

View Code

二.破坏循环等待条件

解决方法:对锁进行排序，每次申请锁需要按从小到大顺序申请。这样就不存在循环等待了

/**
 * 银行账户类
 *
 * @author Liumz
 * @since 2019-04-02  15:36:15
 */
@Component
@Scope("prototype")
public class BankAccount {
    /**
     * 余额
     */
    private int balance;
    /**
     * 序号id
     */
    private int id;

    /**
     * 转账
     *
     * @param target 目标账户
     * @param amount 转账金额
     */
    public void transfer(BankAccount target, int amount) {
        //对账户序号排序
        BankAccount firstLock = target;
        BankAccount secondLock = this;
        if (firstLock.id > secondLock.id) {
            firstLock = this;
            secondLock = target;
        }
        //先锁定序号小的账户，再锁定序号大的账户
        synchronized (firstLock){
            synchronized (secondLock){
                this.balance -= amount;
                target.balance += amount;
            }
        }
    }
}

View Code

三.破坏不可抢占条件

解决方法: 使用 Lock 和UnLock，在finally里执行unlock，主动释放资源。此时别人就可以抢占了。

活锁：

多个线程获取不到资源，就放开已获得的资源，重试。相当于系统空转，一直在做无用功。

例如，行人走路相向而行，互相谦让，一直重复谦让的过程。

如以下一直死循环：

start:
p1 lock A
p2 lock B
p1 lock B failed
p2 lock A failed 
p1 release A
p2 release B
goto start

解决方法：引入一些随机性，比如暂停随机时间重试。

饥饿：

1：优先级高的线程总是抢占到资源，而优先级低的线程可能会一直等待，从而无法获取资源无法执行；

2：一个线程一直不释放资源，别的线程也会出现饥饿的情况。

3：wait()等待情况下的线程一直都不被notify，而其他的线程总是能被唤醒

解决方法:引入公平锁

无锁：

CAS(campare and swap):内存值V、旧的预期值A、要修改的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做并返回false。CAS是原子操作，只有一条cpu指令

无锁即不对资源锁定，所有的线程都能访问并修改同一个资源，但同时只有一个线程能修改成功。一个修改操作在一个循环内进行，线程会不断的尝试修改共享资源，如果没有冲突（CAS判断）就修改成功并退出否则就会继续下一次循环尝试。

如jdk的基于CAS实现的原子操作类，就是对无锁的实现。还有无锁队列，也是循环线程对变量进行CAS操作的数据结构。

CAS的缺点:

1.ABA问题：V值为A，T1，T2从内存取出V值为A.。然后T2 CAS修改变量V为B , 接着T2 又CAS修改变量V为A。这时T1 CAS 变量V时发现内存中V还是A ，CAS操作成功。

2.循环消耗大

3.只能保证一个共享变量的原子操作