devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：你好赵伟 | 2024-03-23 07:24:17

赞

踩

cas 实现原理

系列文章目录

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

在这里插入图片描述

文章目录

前言

本章节介绍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指令。
在这里插入图片描述

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();
        
    }
}


  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

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);
        }
    }
}


  • 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
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175

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

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/293867?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号