彻底理解死锁和活锁 java实现

  时间:2020-07-11 11:07:12  阅读量:467  评论数:0  作者:imagine0623

彻底理解死锁和活锁 java实现主要介绍的是

以下使用转账场景来解释说明以上问题,首先认识两个基础类:抽象账户类和工具类:

参考文章:极客时间 Java并发编程实战( https://time.geekbang.org/column/article/85001)

抽象账户类

/**
 * 账户抽象类,由子类实现转账操作
 */
public abstract class AbstractAccount {
    //用户名
    public String name;
    //余额
    public int balance = 0;
    //账户锁
    public final Lock LOCK = new ReentrantLock();
    //构造方法
    public AbstractAccount(String name, int balance) {
        this.name = name;
        this.balance = balance;
    }

    /**
     * 抽象转账操作
     * @param target 目标账户
     * @param amt 转账金额
     * @return 是否成功
     */
    public abstract boolean transfer(AbstractAccount target, int amt);

}

工具类

public class CommonMethod {
    //线程睡眠 单位:毫秒
    public static void sleep(long time){
        try {
            TimeUnit.MILLISECONDS.sleep(time);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    //打印日志,打印格式是  时间 线程名 日志内容
    public static void log(String log){
        System.out.println(new SimpleDateFormat("yyyyMMdd HH:mm:ss.SSS")
                           .format(new Date())  " "
                             Thread.currentThread().getName()   " "   log);
    }

    //批量start线程
    public static void start(Collection<Thread> threads){
        threads.forEach(t->t.start());
    }

    //当前线程join目标线程
    public static void join(Thread thread){
        try {
            thread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    //批量join目标线程
    public static void join(Collection<Thread> threads){
        threads.forEach(t-> join(t));
    }

    //返回随机数字  不大于high
    public static int randomInt(int high){
        return new Random().nextInt(high);
    }

    /**
     * 转账测试程序
     *
     * 线程安全的转账在执行完成后会满足以下条件:
     * acc1 转入 1000
     * acc2 转出 1000
     * acc3 转入 1000
     * acc4 转出 1000
     */
    public static void test(AbstractAccount acc1,AbstractAccount acc2,
                            AbstractAccount acc3,AbstractAccount acc4){
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1000; i  ){
            Collection<Thread> threads = new LinkedList<>();
            threads.add(new TransferThread("thread_acc1->acc2_loop-" i, acc1, acc2,1));
            threads.add(new TransferThread("thread_acc2->acc1_loop-" i, acc2, acc1,1));
            threads.add(new TransferThread("thread_acc2->acc3_loop-" i, acc2, acc3,1));
            threads.add(new TransferThread("thread_acc4->acc1_loop-" i, acc4, acc1,1));
            start(threads);
            join(threads);
        }
        log(acc1.name " 余额: "   acc1.balance);
        log(acc2.name " 余额: "   acc2.balance);
        log(acc3.name " 余额: "   acc3.balance);
        log(acc4.name " 余额: "   acc4.balance);
        log("耗时 "   ( System.currentTimeMillis() - start));
    }
}

线程不安全的转账实现

/**
 * 线程不安全的账户实现
 */
public class UnsafeAccount extends AbstractAccount {
    public UnsafeAccount(String name, int balance) {
        super(name, balance);
    }

    @Override
    public boolean transfer(AbstractAccount target, int amt){
        //校验余额。。。如下睡眠来模拟
        CommonMethod.sleep(3);
        this.balance -= amt;
        target.balance  = amt;
        CommonMethod.log("转账成功,转出账户:" this.name  ",转入账户:"
                          target.name  ",转出金额:" amt);
        return true;
    }
    /**
     * 测试程序
     */
    public static void main(String[] args) {
        AbstractAccount acc1 = new UnsafeAccount("甲", 10000);
        AbstractAccount acc2 = new UnsafeAccount("乙", 10000);
        AbstractAccount acc3 = new UnsafeAccount("丙", 10000);
        AbstractAccount acc4 = new UnsafeAccount("丁", 10000);
        CommonMethod.test(acc1,acc2,acc3,acc4);
    }
}

执行结果如下:

20200710 12:55:07.344  main  甲 余额: 10988
20200710 12:55:07.344  main  乙 余额: 9015
20200710 12:55:07.344  main  丙 余额: 11000
20200710 12:55:07.344  main  丁 余额: 9000
20200710 12:55:07.344  main  耗时 4846

甲和乙的余额错误,说明转账出现了错误。

活锁

类比现实中的例子,有一门,路人甲靠右进,路人乙靠左出,碰在一起,两人为了避免相撞而互相谦让,路人甲改靠左进,路人乙改靠右出,又碰到一起,于是谦让碰撞再谦让再碰撞,于是就无限谦让下去了。。。

/**
 * 可能发生活锁的账户实现
 */
public class LiveLockAccount extends AbstractAccount {
    public LiveLockAccount(String name, int balance) {
        super(name, balance);
    }

    /**
     * 可能发生活锁的实现
     *
     * 比如同时有两个转账操作: 线程1执行 A->B 和 线程2执行 B-> A,为避免发生死锁,所以一旦加锁失败则释放占有的线程
     *
     * 时间:-------------------------------------------------------------->
     * 线程1: 锁A-->锁B失败-->释放A(谦让)-->锁A-->锁B失败-->释放A(谦让)-->锁A-->锁B失败-->释放A(谦让) ......
     * 线程2: 锁B-->锁A失败-->释放B(谦让)-->锁B-->锁A失败-->释放B(谦让)-->锁B-->锁A失败-->释放B(谦让) ......
     *
     * 发生活锁的原因:因为加锁顺序不同,导致一个线程占有A然后申请B,另一个线程占有B然后申请A,并陷入了无限的循环中。。。
     * 虽然因为采用非阻塞加锁然后释放已占资源的方式,破坏了占有不释放(不可剥夺)的死锁条件,避免了死锁
     */
    @Override
    public boolean transfer(AbstractAccount target, int amt){
        //自旋直到完成
        while(true){
            //尝试锁定转出账户
            if (this.LOCK.tryLock()){
                //校验余额。。。使用睡眠来模拟
                CommonMethod.sleep(3);
                try{
                    //尝试锁定转入账户
                    if (target.LOCK.tryLock()){
                        try{
                            this.balance -= amt;
                            target.balance  = amt;
                            CommonMethod.log("转账成功,转出账户:" this.name 
                                              ",转入账户:" target.name  ",转出金额:" amt);
                            return true;
                        }finally {
                            target.LOCK.unlock();
                        }
                    }else{
                        CommonMethod.log("锁定 "   target.name   " 失败");
                    }
                }finally {
                    this.LOCK.unlock();
                }
            }else{
                CommonMethod.log("锁定 "   this.name   " 失败");
            }
        }
    }
    /**
     * 测试程序
     */
    public static void main(String[] args) {
        AbstractAccount acc1 = new LiveLockAccount("甲", 1000);
        AbstractAccount acc2 = new LiveLockAccount("乙", 1000);
        AbstractAccount acc3 = new LiveLockAccount("丙", 1000);
        AbstractAccount acc4 = new LiveLockAccount("丁", 1000);
        CommonMethod.test(acc1,acc2,acc3,acc4);
    }
}

执行结果如下,任务执行十分缓慢,每次loop都会耗时很久,并循环出现大量的锁定失败,原因就是发生了活锁,导致线程加锁大多数情况都是失败的。

20200710 12:52:58.900  thread_acc4->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.902  thread_acc1->acc2_loop-0  锁定 乙 失败
20200710 12:52:58.902  thread_acc2->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.903  thread_acc4->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.905  thread_acc1->acc2_loop-0  锁定 乙 失败
20200710 12:52:58.905  thread_acc2->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.906  thread_acc4->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.908  thread_acc1->acc2_loop-0  锁定 乙 失败
20200710 12:52:58.908  thread_acc2->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.911  thread_acc4->acc1_loop-0  锁定 甲 失败
20200710 12:52:58.911  thread_acc1->acc2_loop-0  锁定 乙 失败
20200710 12:52:58.911  thread_acc2->acc1_loop-0  锁定 甲 失败
循环出现。。。。。。

死锁

在多线程环境下,如果出现两个线程互相等待对方占有的资源,而且对方还不会释放,则发生了死锁。

转账的死锁实现

以下模拟两个账户互相转账时导致死锁。

/**
 * 可能发生死锁的账户实现
 */
public class DeadLockAccount extends AbstractAccount{
    public DeadLockAccount(String name, int balance) {
        super(name, balance);
    }

    /**
     * 可能发生死锁的转账实现
     */
    @Override
    public boolean transfer(AbstractAccount target, int amt){
        //锁定转出账户
        this.LOCK.lock();
        try{
            CommonMethod.log("成功锁定账户 "   this.name   ",申请 " target.name);
            //锁定转入账户
            target.LOCK.lock();
            try{
                //校验余额。。。如下睡眠来模拟
                CommonMethod.sleep(3);
                this.balance -= amt;
                target.balance  = amt;
                CommonMethod.log("转账成功,转出账户:" this.name 
                                  ",转入账户:" target.name  ",转出金额:" amt);
                return true;
            }finally {
                target.LOCK.unlock();
            }
        }finally {
            this.LOCK.unlock();
        }
    }

    /**
     * 测试程序
     */
    public static void main(String[] args) {
       	AbstractAccount acc1 = new DeadLockAccount("甲", 1000);
        AbstractAccount acc2 = new DeadLockAccount("乙", 1000);
        AbstractAccount acc3 = new DeadLockAccount("丙", 1000);
        AbstractAccount acc4 = new DeadLockAccount("丁", 1000);
        CommonMethod.test(acc1,acc2,acc3,acc4);
    }
}

过去很久很久,程序完整输出始终如下:

20200710 12:57:20.009  thread_acc1->acc2_loop-0  成功锁定账户 甲,申请 乙
20200710 12:57:20.011  thread_acc4->acc1_loop-0  成功锁定账户 丁,申请 甲
20200710 12:57:20.009  thread_acc2->acc1_loop-0  成功锁定账户 乙,申请 甲

说明程序发生了死锁。

发生死锁的条件

当以下条件都满足时才会发生死锁:

  1. 互斥:共享资源X和Y只能被一个线程占用
  2. 占有且等待:线程T1已占有X,等待占用Y
  3. 不可抢占:其他线程不能强行抢占线程T1占有的X,或者说X无法释放
  4. 循环等待:线程T1等待线程T2占有的Y,同时线程T2等待线程T1占有的X

只要能破坏其中一个条件,就能避免死锁。其中互斥不可避免,因为用锁为的就是互斥,但其他三个条件都可以被破坏,如何做到呢?

破坏占有且等待

  1. 避免连续占用资源,换句说话就是占用一个就释放一个,不要占用后不释放就要占用其他资源。

    public class CorrectAccount1 extends AbstractAccount {
    
        public CorrectAccount1(String name, int balance) {
            super(name, balance);
        }
    
        /**
         * 通过逐一操作资源来破坏同时占有多个资源这个条件,避免死锁
         */
        @Override
        public boolean transfer(AbstractAccount target, int amt){
            //先操作转出账户,加锁
            this.LOCK.lock();
            try{
                //校验余额。。。如下睡眠来模拟
                CommonMethod.sleep(3);
                this.balance -= amt;
                CommonMethod.log("转出成功,转出账户:"   this.name  ",转出金额:" amt);
            }finally {
                //释放锁
                this.LOCK.unlock();
            }
            /*********再申请占用其他资源之前,不占用任何线程***************/
            //再操作转入账户,加锁
            target.LOCK.lock();
            try{
                target.balance  = amt;
                CommonMethod.log("转人成功,转入账户:"   target.name  ",转入金额:" amt);
            }finally {
                //释放锁
                target.LOCK.unlock();
            }
            return true;
        }
    
        /**
         * 测试程序
         */
        public static void main(String[] args) {
            AbstractAccount acc1 = new CorrectAccount1("甲", 10000);
            AbstractAccount acc2 = new CorrectAccount1("乙", 10000);
            AbstractAccount acc3 = new CorrectAccount1("丙", 10000);
            AbstractAccount acc4 = new CorrectAccount1("丁", 10000);
            CommonMethod.test(acc1,acc2,acc3,acc4);
        }
    }
    

    执行结果:

20200710 12:58:44.251 main 甲 余额: 11000
20200710 12:58:44.251 main 乙 余额: 9000
20200710 12:58:44.251 main 丙 余额: 11000
20200710 12:58:44.251 main 丁 余额: 9000
20200710 12:58:44.251 main 耗时 7146




2. 互斥的一次性占用所有资源,当程序想要同时占用多个资源时,在这些资源之上加个更粗的锁,将占用多个资源的过程互斥。

```java
public class CorrectAccount2  extends AbstractAccount {
    public CorrectAccount2(String name, int balance) {
        super(name, balance);
    }
    //静态锁
    private static final Lock STATIC_LOCK = new ReentrantLock();
    //转账不再冲突
    private static final Condition TRANSFER_NOT_CONFLICT = STATIC_LOCK.newCondition();
    //正在操作的账户集合
    private static volatile Set<AbstractAccount> accounts = new HashSet<>();

    /**
     * 通过一次性占用所有资源,来破坏占用且等待条件,避免死锁
     *
     * 实际就是加粗锁的粒度,当然直接将对象锁改为静态锁,在静态锁的临界区进行转账,
     * 但是这种方式性能差,会串行化所有转账操作,
     * 比如【账户A -> 账户B】和【账户C -> 账户D】也不能并行,假设转账操作耗时10s
     *
     * -------------------------时间线-------------------------------------->
     *
     *   时间   并发请求               临界区
     *   1s     A->B         |     A->B                         |
     *   2s     C->D         |          C->D                    |
     *   3s     E->F         |               E->F               |
     *   4s     D->G         |                     D->G         |
     *
     * 为了解决这个问题:可只在临界区中做判断:是否当前操作和正在执行的操作是否会操作同一账户,
     * 如果不冲突,则允许并发执行;如果冲突,则等待直到不冲突
     * 执行效果如下:
     *
     * -------------------------时间线-------------------------------------->
     *
     *   时间   并发请求             临界区                      并发执行
     *   1s     A->B         | wait(A,B)               |      A->B
     *   2s     C->D         |     wait(C,D)           |      C->D
     *   3s     E->F         |        wait(E,F)        |      E->F
     *   4s     D->G         |           wait(D,G)     |      D->G
     *
     * 但是上面这个判断是仍然是串行的,但相比如比较耗时的转账来说基本可以忽略不计
     */
    @Override
    public boolean transfer(AbstractAccount target, int amt){
        //一次性锁住所有账户
        lock(this, target);
        try{
            //校验余额。。。如下睡眠来模拟
            CommonMethod.sleep(3);
            this.balance -= amt;
            target.balance  = amt;
            CommonMethod.log("转账成功,转出账户:" this.name 
                              ",转入账户:" target.name  ",转出金额:" amt);
            return true;
        }finally {
            unlock(this, target);
        }
    }

     // 一次性占有所有资源
    private static void lock(AbstractAccount from, AbstractAccount to){
        STATIC_LOCK.lock();
        try{
            //等待没有冲突
            while (accounts.contains(from) || accounts.contains(to)){
                try {
                    TRANSFER_NOT_CONFLICT.await();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            accounts.add(from);
            accounts.add(to);
        }finally {
            STATIC_LOCK.unlock();
        }
    }

    // 释放所有资源
    private static void unlock(AbstractAccount from, AbstractAccount to){
        STATIC_LOCK.lock();
        try{
            accounts.remove(from);
            accounts.remove(to);
            TRANSFER_NOT_CONFLICT.signalAll();
        }finally {
            STATIC_LOCK.unlock();
        }
    }

    /**
     * 测试程序
     */
    public static void main(String[] args) {
        AbstractAccount acc1 = new CorrectAccount2("甲", 10000);
        AbstractAccount acc2 = new CorrectAccount2("乙", 10000);
        AbstractAccount acc3 = new CorrectAccount2("丙", 10000);
        AbstractAccount acc4 = new CorrectAccount2("丁", 10000);
        CommonMethod.test(acc1,acc2,acc3,acc4);
    }
}

执行结果是:

20200710 12:59:16.494  main  甲 余额: 11000
20200710 12:59:16.494  main  乙 余额: 9000
20200710 12:59:16.494  main  丙 余额: 11000
20200710 12:59:16.494  main  丁 余额: 9000
20200710 12:59:16.494  main  耗时 10431

破坏不可抢占

  1. 如果在连续占用过程中失败一次,则释放所有占用的资源

    public class CorrectAccount3  extends AbstractAccount {
        public CorrectAccount3(String name, int balance) {
            super(name, balance);
        }
    
        /**
         * 破坏不可抢占条件,如果加锁失败则释放占有资源,避免死锁
         * 释放资源后睡眠随机时间,避免活锁,即使有几次仍碰撞但是最终会执行下去
         * 当然如果同时存在大量的 A->B 和 B->A仍然会发生活锁,但是现实中基本不会有这种情况
         */
        @Override
        public boolean transfer(AbstractAccount target, int amt){
            //自旋直到转账完成
            while(true){
                //尝试锁定转出账户
                if (this.LOCK.tryLock()){
                    try{
                        //校验余额。。。使用睡眠来模拟
                        CommonMethod.sleep(3);
                        //尝试锁定转入账户
                        if (target.LOCK.tryLock()){
                            try{
                                this.balance -= amt;
                                target.balance  = amt;
                                CommonMethod.log("转账成功,转出账户:" this.name 
                                                  ",转入账户:" target.name 
                                                  ",转出金额:" amt);
                                return true;
                            }finally {
                                target.LOCK.unlock();
                            }
                        }else{
                            CommonMethod.log("锁定 "   target.name   " 失败");
                        }
                    }finally {
                        this.LOCK.unlock();
                        //******相比 LiveLockAccount 类的实现只多了下面这句*****
                        CommonMethod.sleep(CommonMethod.randomInt(20));
                    }
                }else{
                    CommonMethod.log("锁定 "   this.name   " 失败");
    
                }
            }
        }
        
        /**
         * 测试程序
         */
        public static void main(String[] args) {
            AbstractAccount acc1 = new CorrectAccount3("甲", 10000);
            AbstractAccount acc2 = new CorrectAccount3("乙", 10000);
            AbstractAccount acc3 = new CorrectAccount3("丙", 10000);
            AbstractAccount acc4 = new CorrectAccount3("丁", 10000);
            CommonMethod.test(acc1,acc2,acc3,acc4);
        }
    }
    

    执行结果:

     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc2->acc1_loop-999  锁定 甲 失败
     20200710 13:00:15.754  thread_acc4->acc1_loop-999  锁定 甲 失败
     20200710 13:00:15.754  thread_acc2->acc3_loop-999  锁定 乙 失败
     20200710 13:00:15.754  thread_acc1->acc2_loop-999  锁定 乙 失败
     20200710 13:00:15.791  main  甲 余额: 11000
     20200710 13:00:15.791  main  乙 余额: 9000
     20200710 13:00:15.791  main  丙 余额: 11000
     20200710 13:00:15.791  main  丁 余额: 9000
     20200710 13:00:15.791  main  耗时 41343
    
    

程序运行过程中虽然出现了大量的锁定失败,但是程序没有在一次loop中阻塞很久,但是程序没有假死。

破坏循环等待

  1. 对资源排序,必须按顺序占有资源,防止出现互相等待。

    public class CorrectAccount4  extends AbstractAccount {
        public CorrectAccount4(String name, int balance) {
            super(name, balance);
        }
    
        /**
         * 通过顺序加锁来破坏循环等待的死锁条件,避免死锁
         */
        @Override
        public boolean transfer(AbstractAccount target, int amt){
            //根据name的hash从小到大加锁
           AbstractAccount small = this;
           AbstractAccount big = target;
           if (this.name.hashCode() > target.name.hashCode()){
               small = target;
               big = this;
           }
            //占有小账户
            small.LOCK.lock();
            try{
                //占有大账户
                big.LOCK.lock();
                try{
                    /***************所有资源都已成功占有******************/
                    //校验余额。。。如下睡眠来模拟
                    CommonMethod.sleep(3);
                    this.balance -= amt;
                    target.balance  = amt;
                    CommonMethod.log("转账成功,转出账户:" this.name 
                                      ",转入账户:" target.name  ",转出金额:" amt);
                    return true;
                }finally {
                    big.LOCK.unlock();
                }
            }finally {
                small.LOCK.unlock();
            }
        }
        
        /**
         * 测试程序
         */
        public static void main(String[] args) {
            AbstractAccount acc1 = new CorrectAccount4("甲", 10000);
            AbstractAccount acc2 = new CorrectAccount4("乙", 10000);
            AbstractAccount acc3 = new CorrectAccount4("丙", 10000);
            AbstractAccount acc4 = new CorrectAccount4("丁", 10000);
            CommonMethod.test(acc1,acc2,acc3,acc4);
        }
    }
    

    执行结果:

     20200710 13:05:08.569  main  甲 余额: 11000
     20200710 13:05:08.569  main  乙 余额: 9000
     20200710 13:05:08.569  main  丙 余额: 11000
     20200710 13:05:08.569  main  丁 余额: 9000
     20200710 13:05:08.569  main  耗时 10558
    

总结

避免需要同时占用多个资源和顺序占有两种的策略的性能更好。

关键词:java,并发编程,多线程,彻底,理解,死锁,活锁,实现