系列文章目录
AQS的实现原理及应用
CAS的实现原理及应用
文章目录
- 系列文章目录
- 前言
- 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指令。
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的同步机制，我们可以实现高效的线程协作和同步操作。
