之前第一个讲竞态条件
的时候有个累加器的例子屡屡被提到:
public class Test{
long count = 0;
void add10k() {
int idx = 0;
while(idx++ < 10000) {
count += 1;
}
}
}
add10k
方法存在着竞态条件
,count += 1
这个操作是一个组合操作
,需要保证其原子
性,但是这个方法没有使用同步
机制,所以在并发环境
下会出现问题。count
的可见性也会出现问题,可见性
可以使用 volatile
解决,原子性之前我们一直使用的是 互斥锁
方案。
对于只有一个变量的原子操作
我们可以使用原子类来解决,在 《JCIP Java 并发编程实战》 中第一个例子就是使用 AtomicLong
这个原子变量来替换 基础类型变量 long
,这种方案是无锁
方案,JDK
中的原子类
就是在无锁方案
的基础上提炼而来。
下面的代码中,将 long
替换为 AtomicLong
,原来的 count += 1
换成了 count.getAndIncrement
(),只需要改动这两处,就可以使 add10K
() 方法变成线程安全的:
public class Test {
AtomicLong count = new AtomicLong(0);
void add10K() {
int idx = 0;
while(idx++ < 10000) {
count.getAndIncrement();
}
}
}
无锁
方案相比于使用互斥锁
方案,最大的好处就是性能
,如果使用互斥锁
,需要执行加锁
、解锁
操作,同时无法获取到锁的线程进入阻塞
状态,线程切换
还有额外消耗,并且降低伸缩性
,将并行
方法串行化
。
相比之下,无锁方案没有任何额外的消耗,它是如何做到呢?
无锁方案的实现原理
原子性类性能高的原因很简单 —— 硬件支持。CPU
为了解决并发问题,提供了 CAS
指令(Compare And Swap
比较并交换)。
CAS
指令包含3个参数:①共享变量内存地址 A
、②用于比较的值 B
、③共享变量的新值 C
。并且只有当内存地址 A 处的值 等于 B 时,才能将内存中地址A 处的值更新为 C。作为一条 CPU
指令,CAS
指令本身是原子性的。
作者给出了一个 CAS
指令的伪代码用于说明:下面的模拟程序中有两个参数:
期望值 expect
- 需要些入的
新值
newValue
只有当 count
的值 == 期望值 expect
时,才会将 count
更新为 newValue
。
class SimulatedCAS {
int count;
synchronized int cas(int expect int newValue) {
// 读取目前count的值
int curValue = count;
// 比较count的值是否和期望值相等
if(curValue == expect) {
// 如果相等,更新count值
count = newValue;
}
// 返回写入前的值
return curValue;
}
}
继续思考上面那句:只有当 count
的值 == 期望值 expect
时,才会将 count
更新为 newValue
。
对于之前累加器的例子, count += 1
的核心问题是内存中 count
的当前值 A
计算出来的 count +=1
的结果是 A+1
,当将 A+1
写入内存时,很可能此时内存中的 count
已经被其他线程更新
了,这样就会导致错误地覆盖
其他线程写入的值。
只有当内存中的 count
的值 等于
期望值 A
时,才能将内存中的 count
更新为 A+1
,这就是 CAS
的语义。
使用 CAS
解决并发问题,一般都伴随着自旋
。所谓自旋,指的就是循环尝试。
例如 需求是「实现一个线程安全的 count += 1
操作」,使用 CAS + 自旋
的实现方案如下所示:
计算
newValue = count+1
,如果cas(count,newValue) 返回的值 != count
,则意味着线程在执行完①
处代码之后
,执行②
处代码之前
,count
的值被其他线程更新
过。此时需要采用自旋方案:重新读
count
最新的值然后来计算newValue
,并尝试再次更新
,直到更新成功。
public class SimulatedCAS {
volatile int count;
// 实现count+=1
void addOne() {
int newValue;
do {
newValue = count + 1; // ①
} while (count != cas(count, newValue)); // ②
}
synchronized int cas(int expect, int newValue) {
// 读取当前count的值
int curValue = count;
// 比较当前count是否和期望值相等
if (curValue == expect) {
count = newValue;
}
// 返回写入前的值
return curValue;
}
}
通过上面的代码可以看到,CAS
这种方案完全没有加锁
、解锁
操作。即使两个线程同时执行 addOne
方法,也不会有线程被阻塞,所以相对于使用互斥锁
,这种方案的性能好了很多。
但是 CAS
方案中存在一个 ABA
问题,什么是 ABA
问题呢?我自制了一个简单的示意图:
之前提到了,如果 cas(count,newValue)
的返回值不等于
之前内存中的 count
也就是 示意图中的 99
,那么意味着线程在执行完 ①处代码之后,执行 ②处代码之前
,count
的值被其他线程更新过。
但是 cas(count,newValue)
的返回值
与当前内存中的 count
值一致
,也并不能一定保证
这个值没有被其他线程更新过,可能是被更新过之后又被更新为了之前的值,count
被线程 T2
更新为了 100
,又被 T3
更新回 99
,这样虽然线程 T1
看到的 count
一直是 99
,但是其实count
的值已经被更新过了一次
,这就是 ABA
问题。
虽然大多数情况
下我们并不关心 ABA
问题,例如数值的原子递增,但是当 ABA
问题发生时,虽然 count
的值相等,但是可能有其他的属性发生了变化,所以在使用 CAS
方案时,一定要进行 check
。【这里的check 指的是什么?关键属性的验证吗?】
Java 如何实现原子化的 count += 1
下面分析Java 中的 AtomicLong
类 的 getAndIncrement
方法怎样使用 CAS
实现原子化的 count += 1
。
JDK8
中,getAndIncrement
会调用 unsafe.getAndAddLong
方法,这里使用 this
和 valueOffSet
两个参数可以唯一确定共享变量
的内存地址
。
/**
* Atomically increments by one the current value.
*
* @return the previous value
*/
public final long getAndIncrement() {
return unsafe.getAndAddLong(this, valueOffset, 1L);
}
下面是 unsafe.getAndAddLong
的源码:该方法首先在**内存
**中读取共享变量的值,之后循环调用 compareAndSwapLong
尝试给共享变量赋值,直到成功为止。
compareAndSwapLong
是一个 native
方法,只有当内存
中共享变量的值等于 expected
时,才会将共享变量值更新为 x 并返回true
,否则返回 false
。
compareAndSwapLong
的语义和 CAS
指令的语义区别只是返回值不同。
public final long getAndAddLong(Object o, long offset, long delta) {
long v;
do {
// 读取内存中的值
v = this.getLongVolatile(o, offset);
} while(!this.compareAndSwapLong(o, offset, v, v + delta));
return v;
}
// 原子性地将变量更新为 x ,条件是内存中的值等于 expect,更新成功返回 true
public final native boolean compareAndSwapLong(Object o, long offset, long expect, long x);
另外需要注意的是,getAndAddLong
方法的实现,基本就是 CAS
使用的经典范例,所以将这个例子抽象提取后,就是无锁方法的使用范式,它在很多无锁程序中都会出现。
Java
提供的原子类中的 CAS
一般被实现为 compareAndSet
(),compareAndSet
的语义 和 CAS
的语义之间的差别仅仅是返回值的不同
,compareAndSet
中如果变量更新成功返回 ture
, 失败返回 false
,CAS
返回的则是写入前的值。
do {
// 获取当前值
oldValue = xxx;
// 根据当前值计算新值
newValue = oldValue ...;
} while(!compareAndSet(oldValue,newValue));
原子类概览
JDK 并发包中提供的原子类内容很丰富,可以将其分为五类:
- 原子化的基本数据类型
- 原子化的引用数据类型
- 原子化数组
- 原子化对象属性更新器
- 原子化累加器
1. 原子化的基本数据
相关实现包括:AtomicBoolean
、AtomicLong
、AtomicInteger
,主要方法如下:
getAndIncrement() //原子化i++
getAndDecrement() //原子化的i--
incrementAndGet() //原子化的++i
decrementAndGet() //原子化的--i
//当前值+=delta,返回+=前的值
getAndAdd(delta)
//当前值+=delta,返回+=后的值
addAndGet(delta)
//CAS操作,返回是否成功
compareAndSet(expect, update)
//以下四个方法
//新值可以通过传入func函数来计算
getAndUpdate(func)
updateAndGet(func)
getAndAccumulate(x,func)
accumulateAndGet(x,func)
原子化的对象引用类型
相关实现:AtomicReference
、AtomicStampedReference
、AtomicMarkableReference
,利用它们可以实现对象引用的原子化更新。
AtomicReference
提供的方法和原子化基本数据类型差不多,需要注意的是,对象引用更新需要重点关注 ABA 问题,AtomicStampedReference
和 AtomicMarkableReference
这两个原子类可以解决 ABA 问题。
解决 ABA 问题的思路很简单:给对象增加一个版本号字段就可以,这和之前介绍的乐观锁机制很类似,每次执行 CAS
操作,附加再更新一个版本号,只要保证版本号
是递增的,即便 A变成B之后再变回A,版本号也是会发生改变的。
AtomicStampedReference
实现的 CAS
方法就增加了版本号
参数:
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
AtomicMarkableReference
实现机制更简单,将版本号
简化成了一个 Boolean
值:
public boolean compareAndSet(V expectedReference,
V newReference,
boolean expectedMark,
boolean newMark) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedMark == current.mark &&
((newReference == current.reference &&
newMark == current.mark) ||
casPair(current, Pair.of(newReference, newMark)));
}
3.原子化数组
相关实现:AtomicIntegerArray
、AtomicLongArrray
、AtomicReferenceArray
,利用这些原子类,可以原子化地更新数组里的每一个元素
。
这些类提供的方法和原子化基本数据类型的区别是:每个方法多了一个数组索引
参数。
4.原子化对象属性更新器
相关实现:AtomicIntegerFieldUpdater
、AtomicLongFieldUpdater
、AtomicReferenceFieldUpdater
,利用它们可以原子化地更新对象属性,这三个方法都是利用反射机制实现的
,创建更新器的方法如下:
@CallerSensitive
public static <U> AtomicLongFieldUpdater<U> newUpdater(Class<U> tclass,
String fieldName) {
Class<?> caller = Reflection.getCallerClass();
if (AtomicLong.VM_SUPPORTS_LONG_CAS)
return new CASUpdater<U>(tclass, fieldName, caller);
else
return new LockedUpdater<U>(tclass, fieldName, caller);
}
需要注意的是,更新的对象属性必须是 volatile
类型,这样才能保证可见性,如果对象属性不是 volatile
类型,则 newUpdater
() 方法抛出 IllegalArgumentException
异常。
newUpdate
() 方法参数值有类信息,没有对象引用,但是更新对象的属性是一定要获取对象引用的,这个参数是怎也传入的呢?是在原子操作的方法中传入的。
例如 compareAndSet
() 这个原子操作,相比原子化的基本数据类型多了一个对象引用 obj。原子化对象属性更新器的相关方法,相比原子化基本数据类型仅仅多了对象引用参数。
public abstract boolean compareAndSet(T obj, long expect, long update);
5.原子化累加器
DoubleAccumulator
、DoubleAdder
、LongAccumulator
、LongAdder
这4个类仅仅用来执行计数累加操作,相比原子化的基本数据类型,优势是速度更快
,但是不支持 compareAndSet() 方法
,如果仅需要做计数器功能,使用原子化累加器性能更好。
总结
无锁方案相对于互斥锁,优点很多:
- 性能好
- 不会出现死锁问题(但是可能出现活锁和饥饿,因为自旋会反复重试)
Java
提供的原子类大部分都实现了 compareAndSet
() 方法,基于 compareAndSet
,你可以构建自己的无锁数据结构
,但是不建议这样做,因为无锁算法没有想象的那么简单,还是交给大佬去做,我们使用就好。
Java 提供的原子类可以解决一些简单的原子性问题,但是只能针对一个变量
,如果是多个变量,哪怕是多个原子变量,也不能保证一组操作是原子性的。
Q.E.D.
Comments | 0 条评论