【并发知识点】CAS的实现原理及应用

深碍√TFBOYSˉ_ 2023-10-12 19:24 3阅读 0赞

## 系列文章目录 ##

[AQS的实现原理及应用][AQS]  
[CAS的实现原理及应用][CAS]

![在这里插入图片描述][18b941b697e74e0aadfe93636e5bed7c.png]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言
 *  1、CAS的概念
 *  2、CAS的实现原理
 *  3、单JVM内锁CAS实现
 *   *  3.1、效果
 *  4、模拟赛龙舟比赛

--------------------

## 前言 ##

本章节介绍CAS概念、实现原理，并通过java代码应用，最终模拟赛龙舟比赛。

## 1、CAS的概念 ##

CAS的全称为：CompareAndSwap,直译为对比和交换。  
CAS实际是普遍处理器都支持的一条指令，这条指令通过判断当前内存值V、旧的预期值A、即将更新的值B是否相等来对比并设置新值，从而实现变量的原子性。  
Synchronized会线程阻塞称为悲观锁，CAS不会使线程阻塞称为乐观锁。悲观锁其他没有获取锁的线程是不会执行代码的，而乐观锁是可以使多个线程同时访问代码，可是会判断是否有更新决定是否重新执行。

## 2、CAS的实现原理 ##

CAS的原理：通过三个参数，当前内存的变量值V、旧的预期值A、即将更新的值B。通过判断是V和A是否相等查看当前变量值是否被其他线程改变，如果相等则变量没有被其他线程更改，就把B值赋予V；如果不相等则做自旋操作。  
举例：假设i的初始值为0，现两线程分别执行i++操作，看看CAS会如何执行：

> 1线程：A = 0,B = 1  
> 2线程：A = 0,B = 1

此时两个线程的旧的期望值A、更新的B值都是一样的  
假设1线程先执行，线程1从内存中拿到i的值V,此时V等于0，刚好和旧的期望值A相等，就把更新的值B赋值到内存i值V中。  
2线程执行时，此时拿到内存的V值为1，和旧的预期值0不想等，则不做更新B的赋值操作，通过自旋把旧的预期值A=V，并再次确定CAS指令。  
![在这里插入图片描述][13eefe3456f44acc959e9af2e51ced27.png]

JDK提供的原子操作类就是基于CAS来实现原子性，比如：AtomicInteger、AtomicIntegerArray、AtomicDouble、AtomicBoolean等

## 3、单JVM内锁CAS实现 ##

import java.util.HashMap;
    import java.util.Map;
    import java.util.concurrent.ExecutorService;
    import java.util.concurrent.Executors;
    
    /***
     * @title AtomicExample
     * @desctption CAS
     * @author Kelvin
     * @create 2023/6/14 17:08
     **/
    public class AtomicExample {
        
        private static Map<String, Boolean> map = new HashMap<>();
    
        public static void main(String[] args) throws InterruptedException {
        
            ExecutorService executorService = Executors.newFixedThreadPool(10);
            //未加锁
            map.put("lock", true);
            for (int i = 0; i < 20; i++) {
        
                int finalI = i;
                executorService.submit(
                        () -> {
        
                            boolean isRotate = true;
                            while (isRotate) {
        
                                boolean vLock = map.get("lock");
                                if( vLock ) {
        
                                    boolean aLock = map.get("lock");
                                    if( vLock == aLock ) {
        
                                        //执行业务逻辑
                                        //加锁
                                        map.put("lock", false);
                                        System.out.println( "执行业务逻辑, i: " + finalI);
                                        try {
        
                                            Thread.sleep(2000);
                                        } catch (InterruptedException e) {
        
                                            throw new RuntimeException(e);
                                        }
                                        isRotate = false;
                                        //释放锁
                                        map.put("lock", true);
                                    } else {
        
                                        System.out.println("自旋，重新获取锁！");
                                        continue;
                                    }
                                }
                            }
                        }
                );
            }
    
            Thread.sleep(20 * 1000);
            System.out.println("end");
            executorService.shutdown();
            
        }
    }

### 3.1、效果 ###

执行业务逻辑, i: 1  
执行业务逻辑, i: 5  
自旋，重新获取锁！  
自旋，重新获取锁！  
自旋，重新获取锁！  
自旋，重新获取锁！  
自旋，重新获取锁！  
自旋，重新获取锁！  
执行业务逻辑, i: 4  
自旋，重新获取锁！  
自旋，重新获取锁！  
执行业务逻辑, i: 10  
自旋，重新获取锁！  
自旋，重新获取锁！  
执行业务逻辑, i: 9  
执行业务逻辑, i: 2  
自旋，重新获取锁！  
执行业务逻辑, i: 3  
自旋，重新获取锁！  
执行业务逻辑, i: 0  
执行业务逻辑, i: 12  
执行业务逻辑, i: 11  
执行业务逻辑, i: 8  
执行业务逻辑, i: 6  
执行业务逻辑, i: 7  
执行业务逻辑, i: 14  
自旋，重新获取锁！  
执行业务逻辑, i: 15  
执行业务逻辑, i: 16  
执行业务逻辑, i: 18  
自旋，重新获取锁！  
自旋，重新获取锁！  
执行业务逻辑, i: 17  
执行业务逻辑, i: 19  
执行业务逻辑, i: 13  
end

## 4、模拟赛龙舟比赛 ##

在这个程序中，我们将使用Java的AtomicInteger来实现一个裁判的计时器，模拟一个赛龙舟比赛中多支队伍竞争的场景。每个队伍都会在启动时创建一个独立的线程，并在程序中使用LockFreeQueue来模拟龙舟的运动。同时，程序中还会使用CountDownLatch来控制所有龙舟同时开始比赛，并使用CyclicBarrier来模拟所有队伍完成比赛后的庆祝活动。

import java.util.Random;
    import java.util.concurrent.*;
    import java.util.concurrent.atomic.AtomicInteger;
    
    public class DragonBoatRace {
        
        private static final int TEAM_NUM = 4; // 参赛队伍数
        private static final int BOAT_NUM = 1; // 龙舟数量
        private static final Random random = new Random();
        private static final AtomicInteger time = new AtomicInteger(0);
        private static final CountDownLatch startLatch = new CountDownLatch(TEAM_NUM);
        private static final CyclicBarrier finishBarrier = new CyclicBarrier(TEAM_NUM + 1);
        private static final LockFreeQueue<Integer> queue = new LockFreeQueue<>();
    
        public static void main(String[] args) throws InterruptedException {
        
            ExecutorService executorService = Executors.newFixedThreadPool(TEAM_NUM);
            for (int i = 0; i < TEAM_NUM; i++) {
        
                executorService.submit(new Team(i + 1));
            }
            startLatch.await(); // 等待所有队伍准备就绪
            System.out.println("比赛开始！");
            for (int i = 0; i < BOAT_NUM; i++) {
        
                new Thread(new Boat(i + 1)).start();
            }
            System.out.println("龙舟已经准备好！");
            finishBarrier.await(); // 等待所有队伍完成比赛
            System.out.println("所有队伍完成比赛，开始庆祝！");
            executorService.shutdown(); // 关闭线程池
        }
    
        static class Team implements Runnable {
        
            private final int teamId;
    
            public Team(int teamId) {
        
                this.teamId = teamId;
            }
    
            @Override
            public void run() {
        
                try {
        
                    Thread.sleep(1000 * teamId); // 模拟队伍准备时间
                    System.out.println("队伍" + teamId + "已准备就绪！");
                    startLatch.countDown(); // 准备就绪，计数器减一
                    queue.add(1); // 龙舟前进一步
                    while (time.get() < 2000) {
         // 等待龙舟到达终点
                        Thread.yield();
                    }
                    System.out.println("队伍" + teamId + "已完成比赛，用时" + time.get() + "ms！");
                } catch (InterruptedException e) {
        
                    e.printStackTrace();
                } finally {
        
                    try {
        
                        finishBarrier.await(); // 等待其他队伍完成比赛
                        System.out.println("队伍" + teamId + "正在庆祝！");
                    } catch (InterruptedException | BrokenBarrierException e) {
        
                        e.printStackTrace();
                    }
                }
            }
        }
    
        static class Boat implements Runnable {
        
            private final int boatId;
    
            public Boat(int boatId) {
        
                this.boatId = boatId;
            }
    
            @Override
            public void run() {
        
                while (!queue.isEmpty()) {
         // 龙舟前进，直到到达终点
                    if (queue.poll() != null) {
        
                        time.addAndGet(random.nextInt(10) + 1); // 龙舟前进一步，用时1~10ms
                    }
                }
                try {
        
                    finishBarrier.await(); // 等待所有队伍完成比赛
                } catch (InterruptedException | BrokenBarrierException e) {
        
                    e.printStackTrace();
                }
            }
        }
    
        static class LockFreeQueue<E> {
        
            private static class Node<E> {
        
                final E item;
                volatile Node<E> next;
    
                Node(E item) {
        
                    this.item = item;
                }
            }
    
            private volatile Node<E> head;
            private volatile Node<E> tail;
    
            public boolean isEmpty() {
        
                return head == null;
            }
    
            public void add(E item) {
        
                Node<E> node = new Node<>(item);
                while (true) {
        
                    Node<E> last = tail;
                    Node<E> next = last == null ? head : last.next;
                    if (last == tail) {
        
                        if (next == null) {
        
                            if (compareAndSetNext(last, null, node)) {
        
                                compareAndSetTail(last, node);
                                return;
                            }
                        } else {
        
                            compareAndSetTail(last, next);
                        }
                    }
                }
            }
    
            public E poll() {
        
                while (true) {
        
                    Node<E> first = head;
                    Node<E> last = tail;
                    Node<E> next = first == null ? null : first.next;
                    if (first == head) {
        
                        if (first == last) {
        
                            if (next == null) {
        
                                return null;
                            }
                            compareAndSetTail(last, next);
                        } else {
        
                            E item = next.item;
                            if (compareAndSetHead(first, next)) {
        
                                return item;
                            }
                        }
                    }
                }
            }
    
            private boolean compareAndSetHead(Node<E> expect, Node<E> update) {
        
                return unsafe.compareAndSwapObject(this, headOffset, expect, update);
            }
    
            private boolean compareAndSetTail(Node<E> expect, Node<E> update) {
        
                return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
            }
    
            private boolean compareAndSetNext(Node<E> node, Node<E> expect, Node<E> update) {
        
                return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
            }
    
            private static final sun.misc.Unsafe unsafe;
            private static final long headOffset;
            private static final long tailOffset;
            private static final long nextOffset;
    
            static {
        
                try {
        
                    unsafe = getUnsafe();
                    Class<?> k = LockFreeQueue.class;
                    headOffset = unsafe.objectFieldOffset(k.getDeclaredField("head"));
                    tailOffset = unsafe.objectFieldOffset(k.getDeclaredField("tail"));
                    nextOffset = unsafe.objectFieldOffset(Node.class.getDeclaredField("next"));
                } catch (Exception e) {
        
                    throw new Error(e);
                }
            }
    
            private static sun.misc.Unsafe getUnsafe() throws Exception {
        
                Field field = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
                field.setAccessible(true);
                return (sun.misc.Unsafe) field.get(null);
            }
        }
    }

在这个程序中，我们模拟了4个队伍参加赛龙舟比赛。每个队伍都在启动时创建一个独立的线程，并在比赛前等待1-4s的准备时间。当所有队伍都准备就绪后，裁判发出比赛开始信号，龙舟开始前进。程序中使用LockFreeQueue来模拟龙舟的运动，每次龙舟前进一步，用时1~10ms。当某个队伍完成比赛后，程序会使用CyclicBarrier来等待其他队伍完成比赛，并且进行庆祝活动。

总之，基于CAS的Java多线程程序可以很好地模拟赛龙舟比赛中的多支队伍竞争的场景。通过使用Java的AtomicInteger和LockFreeQueue等基于CAS的同步机制，我们可以实现高效的线程协作和同步操作。

[AQS]: https://blog.csdn.net/s445320/article/details/131339215
[CAS]: https://blog.csdn.net/s445320/article/details/131339468
[18b941b697e74e0aadfe93636e5bed7c.png]: https://img-blog.csdnimg.cn/18b941b697e74e0aadfe93636e5bed7c.png
[13eefe3456f44acc959e9af2e51ced27.png]: https://img-blog.csdnimg.cn/13eefe3456f44acc959e9af2e51ced27.png