原子类的底层实现及应用
2023-12-12 本文已影响0人
我可能是个假开发
一、CAS
1.保护共享资源
加锁方式：
public class TestAccount {
public static void main(String[] args) {
Account account = new AccountSafe(10000);
Account.demo(account);
}
}
interface Account {
// 获取余额
Integer getBalance();
// 取款
void withdraw(Integer amount);
/**
* 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
* 如果初始余额为 10000 那么正确的结果应当是 0
*/
static void demo(Account account) {
List<Thread> ts = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
ts.add(new Thread(() -> {
account.withdraw(10);
}));
}
long start = System.nanoTime();
ts.forEach(Thread::start);
ts.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
long end = System.nanoTime();
System.out.println(account.getBalance()
+ " cost: " + (end-start)/1000_000 + " ms");
}
}
class AccountSafe implements Account {
private Integer balance;
public AccountSafe(Integer balance) {
this.balance = balance;
}
@Override
public Integer getBalance() {
synchronized (this) {
return this.balance;
}
}
@Override
public void withdraw(Integer amount) {
synchronized (this) {
this.balance -= amount;
}
}
}
0 cost: 96 ms
无锁方式:
public class TestAccount {
public static void main(String[] args) {
Account account = new AccountSafe(10000);
Account.demo(account);
}
}
interface Account {
// 获取余额
Integer getBalance();
// 取款
void withdraw(Integer amount);
/**
* 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
* 如果初始余额为 10000 那么正确的结果应当是 0
*/
static void demo(Account account) {
List<Thread> ts = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
ts.add(new Thread(() -> {
account.withdraw(10);
}));
}
long start = System.nanoTime();
ts.forEach(Thread::start);
ts.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
long end = System.nanoTime();
System.out.println(account.getBalance()
+ " cost: " + (end-start)/1000_000 + " ms");
}
}
class AccountCas implements Account {
private AtomicInteger balance;
public AccountCas(int balance) {
this.balance = new AtomicInteger(balance);
}
@Override
public Integer getBalance() {
return balance.get();
}
@Override
public void withdraw(Integer amount) {
while(true) {
// 获取余额的最新值
int prev = balance.get();
// 要修改的余额
int next = prev - amount;
// 真正修改
if(balance.compareAndSet(prev, next)) {
break;
}
}
}
}
0 cost: 59 ms
2.CAS工作方式
compareAndSet：在 set 前，先比较 prev 与当前值不一致了，next 作废，返回 false 表示失败，一致，以 next 设置为新值，返回 true 表示成功。
比如，别的线程已经做了减法，当前值已经被减成了 990
那么本线程的这次 990 就作废了，进入 while 下次循环重试：
如果一致，以 next 设置为新值，返回 true 表示成功。
CAS 的底层是 lock cmpxchg 指令（X86 架构），在单核 CPU 和多核 CPU 下都能够保证【比较-交换】的原子性。
在多核状态下，某个核执行到带 lock 的指令时，CPU 会让总线锁住，当这个核把此指令执行完毕，再开启总线。这个过程中不会被线程的调度机制所打断，保证了多个线程对内存操作的准确性，是原子的。
3.CAS底层分析
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
private volatile int value;
CAS操作中的value使用了volatile来修饰，保证读取到的是共享变量的最新值。
无锁效率高:
- 无锁情况下，即使重试失败，线程始终在高速运行，没有停歇，而 synchronized 会让线程在没有获得锁的时候，发生上下文切换，进入阻塞。再次唤醒代价比较大
- 无锁情况下，因为线程要保持运行，需要额外 CPU 的支持，虽然不会进入阻塞，但由于没有分到时间片，仍然会进入可运行状态，还是会导致上下文切换
CAS 的特点：
结合 CAS 和 volatile 可以实现无锁并发，适用于线程数少、多核 CPU 的场景下。
- CAS 是基于乐观锁的思想：最乐观的估计，不怕别的线程来修改共享变量，就算改了也没关系，再重试。
- synchronized 是基于悲观锁的思想：最悲观的估计，得防着其它线程来修改共享变量，上了锁其他线程都别想改，改完了解开锁，其他线程才有机会
- CAS 体现的是无锁并发、无阻塞并发：
因为没有使用 synchronized，所以线程不会陷入阻塞，这是效率提升的因素之一
但如果竞争激烈，可以想到重试必然频繁发生，反而效率会受影响
二、原子类
1.原子整数
AtomicInteger
AtomicInteger i = new AtomicInteger(0);
// 获取并自增（i = 0, 结果 i = 1, 返回 0），类似于 i++
System.out.println(i.getAndIncrement());
// 自增并获取（i = 1, 结果 i = 2, 返回 2），类似于 ++i
System.out.println(i.incrementAndGet());
// 自减并获取（i = 2, 结果 i = 1, 返回 1），类似于 --i
System.out.println(i.decrementAndGet());
// 获取并自减（i = 1, 结果 i = 0, 返回 1），类似于 i--
System.out.println(i.getAndDecrement());
// 获取并加值（i = 0, 结果 i = 5, 返回 0）
System.out.println(i.getAndAdd(5));
// 加值并获取（i = 5, 结果 i = 0, 返回 0）
System.out.println(i.addAndGet(-5));
// 获取并更新（i = 0, p 为 i 的当前值, 结果 i = -2, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.getAndUpdate(p -> p - 2));
// 更新并获取（i = -2, p 为 i 的当前值, 结果 i = 0, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.updateAndGet(p -> p + 2));
// 获取并计算（i = 0, p 为 i 的当前值, x 为参数1, 结果 i = 10, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
// getAndUpdate 如果在 lambda 中引用了外部的局部变量，要保证该局部变量是 final 的
// getAndAccumulate 可以通过 参数1 来引用外部的局部变量，但因为其不在 lambda 中因此不必是 final
System.out.println(i.getAndAccumulate(10, (p, x) -> p + x));
// 计算并获取（i = 10, p 为 i 的当前值, x 为参数1, 结果 i = 0, 返回 0）
// 其中函数中的操作能保证原子，但函数需要无副作用
System.out.println(i.accumulateAndGet(-10, (p, x) -> p + x));
优化CAS：
优化前：
public void withdraw(Integer amount) {
while(true) {
// 获取余额的最新值
int prev = balance.get();
// 要修改的余额
int next = prev - amount;
// 真正修改
if(balance.compareAndSet(prev, next)) {
break;
}
}
}
优化后：
public void withdraw(Integer amount) {
balance.getAndAdd(-1 * amount);
}
2.原子引用
@Slf4j
public class TestDecimal {
public static void main(String[] args) {
DecimalAccount.demo(new DecimalAccountCas(new BigDecimal("10000")));
}
}
class DecimalAccountCas implements DecimalAccount {
private AtomicReference<BigDecimal> balance;
public DecimalAccountCas(BigDecimal balance) {
// this.balance = balance;
this.balance = new AtomicReference<>(balance);
}
@Override
public BigDecimal getBalance() {
return balance.get();
}
@Override
public void withdraw(BigDecimal amount) {
while(true) {
BigDecimal prev = balance.get();
BigDecimal next = prev.subtract(amount);
if (balance.compareAndSet(prev, next)) {
break;
}
}
}
}
interface DecimalAccount {
// 获取余额
BigDecimal getBalance();
// 取款
void withdraw(BigDecimal amount);
/**
* 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
* 如果初始余额为 10000 那么正确的结果应当是 0
*/
static void demo(DecimalAccount account) {
List<Thread> ts = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
ts.add(new Thread(() -> {
account.withdraw(BigDecimal.TEN);
}));
}
ts.forEach(Thread::start);
ts.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
System.out.println(account.getBalance());
}
}
ABA问题及解决
@Slf4j
public class ABA {
static AtomicReference<String> ref = new AtomicReference<>("A");
public static void main(String[] args) throws InterruptedException {
log.debug("主线程 start...");
// 获取值 A
// 这个共享变量被其它线程修改过
String prev = ref.get();
other();
Thread.sleep(100);
// 尝试改为 C
log.debug("change A->C {}", ref.compareAndSet(prev, "C"));
}
private static void other() throws InterruptedException {
new Thread(() -> {
log.debug("change A->B {}", ref.compareAndSet(ref.get(), "B"));
}, "t1").start();
Thread.sleep(500);
new Thread(() -> {
log.debug("change B->A {}", ref.compareAndSet(ref.get(), "A"));
}, "t2").start();
}
}
16:08:15.255 [main] DEBUG juc.automic.ABA - 主线程 start...
16:08:15.318 [t1] DEBUG juc.automic.ABA - change A->B true
16:08:15.822 [t2] DEBUG juc.automic.ABA - change B->A true
16:08:15.925 [main] DEBUG juc.automic.ABA - change A->C true
主线程仅能判断出共享变量的值与最初值 A 是否相同，不能感知到这种从 A 改为 B 又 改回 A 的情况，如果主线程希望：
只要有其它线程动过了共享变量，那么自己的 cas 就算失败，这时，仅比较值是不够的，需要再加一个版本号：
AtomicStampedReference
@Slf4j
public class TestABA {
static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
public static void main(String[] args) throws InterruptedException {
log.debug("main start...");
// 获取值 A
String prev = ref.getReference();
// 获取版本号
int stamp = ref.getStamp();
log.debug("版本 {}", stamp);
// 如果中间有其它线程干扰，发生了 ABA 现象
other();
Thread.sleep(1000);
// 尝试改为 C
log.debug("change A->C {}", ref.compareAndSet(prev, "C", stamp, stamp + 1));
}
private static void other() throws InterruptedException {
new Thread(() -> {
log.debug("change A->B {}", ref.compareAndSet(ref.getReference(), "B", ref.getStamp(), ref.getStamp() + 1));
log.debug("更新版本为 {}", ref.getStamp());
}, "t1").start();
Thread.sleep(500);
new Thread(() -> {
log.debug("change B->A {}", ref.compareAndSet(ref.getReference(), "A", ref.getStamp(), ref.getStamp() + 1));
log.debug("更新版本为 {}", ref.getStamp());
}, "t2").start();
}
}
18:22:38.273 [main] DEBUG juc.automic.TestABA - main start...
18:22:38.275 [main] DEBUG juc.automic.TestABA - 版本 0
18:22:38.325 [t1] DEBUG juc.automic.TestABA - change A->B true
18:22:38.325 [t1] DEBUG juc.automic.TestABA - 更新版本为 1
18:22:38.826 [t2] DEBUG juc.automic.TestABA - change B->A true
18:22:38.826 [t2] DEBUG juc.automic.TestABA - 更新版本为 2
18:22:39.829 [main] DEBUG juc.automic.TestABA - change A->C false
AtomicMarkableReference
AtomicStampedReference 可以给原子引用加上版本号，追踪原子引用整个的变化过程，如： A -> B -> A ->C ，通过AtomicStampedReference，可以知道，引用变量中途被更改了几次。
但是有时候，并不关心引用变量更改了几次，只是单纯的关心是否更改过，可以使用AtomicMarkableReference
public class TestMarked {
static AtomicMarkableReference<String> atomicStampedReference = new AtomicMarkableReference("hcx",false);
public static void main(String[] args) {
boolean oldMarked = atomicStampedReference.isMarked();
String oldReference = atomicStampedReference.getReference();
System.out.println("初始化之后的标记："+oldMarked);
System.out.println("初始化之后的值："+oldReference);
String newReference = "hcx1";
boolean b =atomicStampedReference.compareAndSet(oldReference,newReference,true,false);
if(!b){
System.out.println("Mark不一致，无法修改Reference的值");
}
b =atomicStampedReference.compareAndSet(oldReference,newReference,false,true);
if(b){
System.out.println("Mark一致，修改reference的值为hcx1");
}
System.out.println("修改成功之后的Mark："+atomicStampedReference.isMarked());
System.out.println("修改成功之后的值："+atomicStampedReference.getReference());
}
}
3.原子数组
- AtomicIntegerArray
- AtomicLongArray
- AtomicReferenceArray
package juc.automic;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicIntegerArray;
import java.util.function.BiConsumer;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Supplier;
public class AtomicArray {
public static void main(String[] args) {
demo(
()->new int[10],
(array)->array.length,
(array, index) -> array[index]++,
array-> System.out.println(Arrays.toString(array))
);
demo(
()-> new AtomicIntegerArray(10),
AtomicIntegerArray::length,
AtomicIntegerArray::getAndIncrement,
System.out::println
);
}
/**
参数1，提供数组、可以是线程不安全数组或线程安全数组
参数2，获取数组长度的方法
参数3，自增方法，回传 array, index
参数4，打印数组的方法
*/
// supplier 提供者 无中生有 ()->结果
// function 函数 一个参数一个结果 (参数)->结果 , BiFunction (参数1,参数2)->结果
// consumer 消费者 一个参数没结果 (参数)->void, BiConsumer (参数1,参数2)->
private static <T> void demo(
Supplier<T> arraySupplier,
Function<T, Integer> lengthFun,
BiConsumer<T, Integer> putConsumer,
Consumer<T> printConsumer ) {
List<Thread> ts = new ArrayList<>();
T array = arraySupplier.get();
int length = lengthFun.apply(array);
for (int i = 0; i < length; i++) {
// 每个线程对数组作 10000 次操作
ts.add(new Thread(() -> {
for (int j = 0; j < 10000; j++) {
putConsumer.accept(array, j%length);
}
}));
}
// 启动所有线程
ts.forEach(t -> t.start());
ts.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
// 等所有线程结束
printConsumer.accept(array);
}
}
[8398, 8472, 8460, 8456, 8435, 8408, 8352, 8344, 8305, 8318]
[10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000]
4.原子更新器
- AtomicReferenceFieldUpdater // 域 字段
- AtomicIntegerFieldUpdater
- AtomicLongFieldUpdater
利用字段更新器，可以针对对象的某个域（Field）进行原子操作，只能配合 volatile 修饰的字段使用，否则会出现异常
@Slf4j
public class Test {
public static void main(String[] args) {
Student stu = new Student();
AtomicReferenceFieldUpdater updater = AtomicReferenceFieldUpdater.newUpdater(Student.class, String.class, "name");
System.out.println(updater.compareAndSet(stu, null, "hcx"));
System.out.println(stu);
}
}
class Student {
volatile String name;
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
}
5.原子累加器
package juc.automic;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.LongAdder;
import java.util.function.Consumer;
import java.util.function.Supplier;
public class TestAdder {
public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
demo(
() -> new AtomicLong(0),
AtomicLong::getAndIncrement
);
}
for (int i = 0; i < 5; i++) {
demo(
LongAdder::new,
LongAdder::increment
);
}
}
/*
() -> 结果 提供累加器对象
(参数) -> 执行累加操作
*/
private static <T> void demo(Supplier<T> adderSupplier, Consumer<T> action) {
T adder = adderSupplier.get();
List<Thread> ts = new ArrayList<>();
// 4 个线程，每人累加 50 万
for (int i = 0; i < 4; i++) {
ts.add(new Thread(() -> {
for (int j = 0; j < 500000; j++) {
action.accept(adder);
}
}));
}
long start = System.nanoTime();
ts.forEach(t -> t.start());
ts.forEach(t -> {
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
long end = System.nanoTime();
System.out.println(adder + " cost:" + (end - start) / 1000_000);
}
}
2000000 cost:40
2000000 cost:36
2000000 cost:33
2000000 cost:33
2000000 cost:29
2000000 cost:12
2000000 cost:5
2000000 cost:5
2000000 cost:5
2000000 cost:5
性能提升的原因：在有竞争时，设置多个累加单元，Therad-0 累加 Cell[0]，而 Thread-1 累加Cell[1]... 最后将结果汇总。这样它们在累加时操作的不同的 Cell 变量，因此减少了 CAS 重试失败，从而提高性能。
三、LongAdder
LongAdder 类有几个关键域
// 累加单元数组, 懒惰初始化
transient volatile Cell[] cells;
// 基础值, 如果没有竞争, 则用 cas 累加这个域
transient volatile long base;
// 在 cells 创建或扩容时, 置为 1, 表示加锁
transient volatile int cellsBusy;
使用cas实现一把锁：
@Slf4j
public class CASLock {
// 0 没加锁
// 1 加锁
private AtomicInteger state = new AtomicInteger(0);
public void lock() {
while (true) {
if (state.compareAndSet(0, 1)) {
break;
}
}
}
public void unlock() {
log.debug("unlock...");
state.set(0);
}
public static void main(String[] args) {
CASLock lock = new CASLock();
new Thread(() -> {
log.debug("begin...");
lock.lock();
try {
log.debug("lock...");
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
} finally {
lock.unlock();
}
}).start();
new Thread(() -> {
log.debug("begin...");
lock.lock();
try {
log.debug("lock...");
} finally {
lock.unlock();
}
}).start();
}
}
10:20:40.732 [Thread-0] DEBUG juc.automic.CASLock - begin...
10:20:40.732 [Thread-1] DEBUG juc.automic.CASLock - begin...
10:20:40.735 [Thread-0] DEBUG juc.automic.CASLock - lock...
10:20:41.740 [Thread-0] DEBUG juc.automic.CASLock - unlock...
10:20:41.740 [Thread-1] DEBUG juc.automic.CASLock - lock...
10:20:41.740 [Thread-1] DEBUG juc.automic.CASLock - unlock...
伪共享
Cell 即为累加单元
// 防止缓存行伪共享
@sun.misc.Contended
static final class Cell {
volatile long value;
Cell(long x) { value = x; }
// 最重要的方法, 用来 cas 方式进行累加, prev 表示旧值, next 表示新值
final boolean cas(long prev, long next) {
return UNSAFE.compareAndSwapLong(this, valueOffset, prev, next);
}
...
}
image.png
| 从 cpu 到 | 大约需要的时钟周期 |
|---|---|
| 寄存器 | 1 cycle (4GHz 的 CPU 约为0.25ns) |
| L1 | 3~4 cycle |
| L2 | 10~20 cycle |
| L3 | 40~45 cycle |
| 内存 | 120~240 cycle |
因为 CPU 与 内存的速度差异很大，需要靠预读数据至缓存来提升效率。
而缓存以缓存行为单位，每个缓存行对应着一块内存，一般是 64 byte（8 个 long），缓存的加入会造成数据副本的产生，即同一份数据会缓存在不同核心的缓存行中。
CPU 要保证数据的一致性，如果某个 CPU 核心更改了数据，其它 CPU 核心对应的整个缓存行必须失效：
image.png
因为 Cell 是数组形式，在内存中是连续存储的，一个 Cell 为 24 字节（16 字节的对象头和 8 字节的 value），因此缓存行可以存下 2 个的 Cell 对象。
问题：
- Core-0 要修改 Cell[0]
- Core-1 要修改 Cell[1]
无论谁修改成功，都会导致对方 Core 的缓存行失效，比如 Core-0 中Cell[0]=6000, Cell[1]=8000 要累加Cell[0]=6001, Cell[1]=8000 ，这时会让 Core-1 的缓存行失效。
@sun.misc.Contended用来解决这个问题，它的原理是在使用此注解的对象或字段的前后各增加 128 字节大小的padding，从而让 CPU 将对象预读至缓存时占用不同的缓存行，这样，不会造成对方缓存行的失效.
四、unsafe
Unsafe 对象提供了非常底层的，操作内存、线程的方法，Unsafe 对象不能直接调用，只能通过反射获得
public class UnsafeAccessor {
private static final Unsafe unsafe;
static {
try {
Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
theUnsafe.setAccessible(true);
unsafe = (Unsafe) theUnsafe.get(null);
} catch (NoSuchFieldException | IllegalAccessException e) {
throw new Error(e);
}
}
public static Unsafe getUnsafe() {
return unsafe;
}
}
Unsafe CAS 操作:
public class TestUnsafe {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
theUnsafe.setAccessible(true);
Unsafe unsafe = (Unsafe) theUnsafe.get(null);
System.out.println(unsafe);
// 1. 获取域的偏移地址
long idOffset = unsafe.objectFieldOffset(Teacher.class.getDeclaredField("id"));
long nameOffset = unsafe.objectFieldOffset(Teacher.class.getDeclaredField("name"));
Teacher t = new Teacher();
// 2. 执行 cas 操作
unsafe.compareAndSwapInt(t, idOffset, 0, 1);
unsafe.compareAndSwapObject(t, nameOffset, null, "hcx");
// 3. 验证
System.out.println(t);
}
}
@Data
class Teacher {
volatile int id;
volatile String name;
}
使用自定义的 AtomicData 实现之前线程安全的原子整数 Account 实现:
@Slf4j
public class Test1 {
public static void main(String[] args) {
Account.demo(new MyAtomicInteger(10000));
}
}
class MyAtomicInteger implements Account {
private volatile int value;
private static final long valueOffset;
private static final Unsafe UNSAFE;
static {
UNSAFE = UnsafeAccessor.getUnsafe();
try {
valueOffset = UNSAFE.objectFieldOffset(MyAtomicInteger.class.getDeclaredField("value"));
} catch (NoSuchFieldException e) {
e.printStackTrace();
throw new RuntimeException(e);
}
}
public int getValue() {
return value;
}
public void decrement(int amount) {
while(true) {
int prev = this.value;
int next = prev - amount;
if (UNSAFE.compareAndSwapInt(this, valueOffset, prev, next)) {
break;
}
}
}
public MyAtomicInteger(int value) {
this.value = value;
}
@Override
public Integer getBalance() {
return getValue();
}
@Override
public void withdraw(Integer amount) {
decrement(amount);
}
}
