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

Dear 丶 2023-02-25 02:24 10阅读 0赞

以下使用转账场景来解释说明活锁和死锁，以及4种正确的实现方法。

首先认识两个基础类：抽象账户类和工具类：

参考文章：极客时间 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.  互斥的一次性占用所有资源，当程序想要同时占用多个资源时，在这些资源之上加个更粗的锁，将占用多个资源的过程互斥。
    
        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->D | E->D | * 4s F->G | F->G | * * 为了解决这个问题：可只在临界区中做判断：是否当前操作和正在执行的操作是否会操作同一账户， * 如果不冲突，则允许并发执行；如果冲突，则等待直到不冲突 * 执行效果如下： * * -------------------------时间线--------------------------------------> * * 时间 并发请求 临界区 并发执行 * 1s A->B | 无冲突 | A->B * 2s C->D | 无冲突 | C->D * 3s E->D | 有冲突(阻塞) E->D * 4s F->G | 无冲突 | F->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

**总结**

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