CAS自旋锁——Atomic原子类算法实现

cover.jpg

乐观者的人生观则相反,凡事不管最终结果如何,他都会先尝试去做,大不了最后不成功。

1. 前言

如果你阅读过AQS源码或者AtomicInteger等原子自增类源码,你会发现很多地方有CAS自旋锁应用。

例如在AQS中,通过自旋锁的方式将结点加入到队尾,如果compareAndSetHeadcompareAndSetTail返回false意味着存在并发修改,将重新进入循环重复之前的操作。如果返回true则意味着修改成功:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) {
// 队列为空,创建一个空结点作为head结点,并将tail也指向它
if (compareAndSetHead(new Node()))
tail = head;
} else { // 正常流程,放入队尾
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}

private final boolean compareAndSetHead(Node update) {
return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

private final boolean compareAndSetTail(Node expect, Node update) {
return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}

2. 原理剖析

CAS(compare and swap),即比较并交换,是提供交换值原子操作的乐观实现算法。即对于内存中的某一个值V,提供一个旧值A和一个新值B。如果提供的旧值V和A相等就把B写入V;如果不相等则说明被修改过,返回失败状态。这个过程是原子性的。

例如下图示例,线程二在获取到内存中的值后对该值进行了操作,并试图将新值设置到内存中。但是在此之前线程一对该内存块成功进行了更新的操作,所以线程二通过CAS算法检测到当前内存块中的值与之前获取的不一致,所以导致更新失败:

TIM截图20190418180224.png

我们借助CAS锁来实现一个简单的原子自增类AtomicInt:我们仿造AQS的写法,通过Unsafe类获取到value值的地址偏移量,用于compareAndSwapInt方法的入参。

仔细观察你会发现这里获取Unsafe对象的方法和JDK中的不同,这是因为getUnsafe方法会判断当前调用这个方法的对象的类型,如果并非java.util.concurrent.atomic内的原子类、AbstractQueuedSynchronizer等类型,则会抛出SecurityException不安全异常。因此需要反射来调用这个方法从而获得Unsafe对象实例:

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
public class AtomicInt {

private volatile int value;

private static final long valueOffset;

private static final Unsafe unsafe;

static {
try {
Class<?> clazz = Unsafe.class;
Field f = clazz.getDeclaredField("theUnsafe");
f.setAccessible(true);
unsafe = (Unsafe) f.get(clazz);

// 获取到value变量的地址偏移量
valueOffset = unsafe.objectFieldOffset(AtomicInt.class.getDeclaredField("value"));
} catch (Exception e) {
throw new Error(e);
}
}

public int get() {
return value;
}

public final int getAndIncrement() {
for (;;) {
int oldValue = get(); // value变量的旧值
int expect = current + 1; // 操作之后的期望值
if (compareAndSet(oldValue, expect)) {
return oldValue; // 更新成功,返回旧值
}
// 更新失败,意味有并发修改,重新循环修改
}
}

private boolean compareAndSet(int current, int expect) {
// 由底层CPU硬件指针保证原子性的实现
return unsafe.compareAndSwapInt(this, valueOffset, current, expect);
}
}

getAndIncrement方法中为CAS算法的具体实现,首先我们计算出更新后的期望值,调用底层的compareAndSwapInt方法,如果当前value地址指向的值与期望值expect不一致将丢弃更改,返回false,重新进入循环修改。

我们用100个线程来进行自增的操作,CAS锁的实现可以不使用同步锁,也能保证AtomicInt能原子性的自增,消除线程的竞争条件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class AtomicIntExample {

private static AtomicInt atomic = new AtomicInt();

public static void main(String[] args) throws InterruptedException {
List<Thread> threads = new ArrayList<>();
for (int i = 0; i < 100; i++) {
Thread t = new Thread(atomic::getAndIncrement);
threads.add(t);
}
for (Thread thread : threads) {
thread.start();
thread.join();
}
System.out.println("Value: " + atomic.get());
}
}

// Value: 100

3. ABA问题

考虑一种使用CAS的情况:即线程1修改V值,读取出内存旧值为A。此时,线程1被挂起(时间片耗尽等)。线程2开始执行,将V修改为B,然后又修改为A。线程1被唤醒,比较旧值与当前内存值相等,完成更新。这就是所谓的ABA问题,乍一看好像不会发生什么错误的结果。但是!对于复杂的情况来说就不一样了。

引用一个维基百科的例子

对于P1来说,数值A未发生过改变,但实际上A已经被变化过了,继续使用可能会出现问题。在CAS操作中,由于比较的多是指针,这个问题将会变得更加严重。试想如下情况:

1
2
3
4
5
   top
|
V
0x0014
| Node A | --> | Node X | --> ……

有一个堆(先入后出)中有top和节点A,节点A目前位于堆顶top指针指向A。现在有一个进程P1想要pop一个节点,因此按照如下无锁操作进行

1
2
3
4
5
6
7
8
pop()
{
do{
ptr = top; // ptr = top = NodeA
next_prt = top->next; // next_ptr = NodeX
} while(CAS(top, ptr, next_ptr) != true);
return ptr;
}

而进程P2在执行CAS操作之前打断了P1,并对堆进行了一系列的pop和push操作,使堆变为如下结构:

1
2
3
4
5
   top
|
V
0x0014
| Node C | --> | Node B | --> | Node X | --> ……

进程P2首先pop出NodeA,之后又Push了两个NodeB和C,由于内存管理机制中广泛使用的内存重用机制,导致NodeC的地址与之前的NodeA一致。

这时P1又开始继续运行,在执行CAS操作时,由于top依旧指向的是NodeA的地址(实际上已经变为NodeC),因此将top的值修改为了NodeX,这时堆结构如下:

1
2
3
4
                                  top
|
0x0014 V
| Node C | --> | Node B | --> | Node X | --> ……

经过CAS操作后,top指针错误的指向了NodeX而不是NodeB。

update

在知乎上看到一个生动的例子,可以参考一下:

小明账户上有100元。现在小明取钱,小强汇钱,诈骗分子盗刷三个动作同时进行。
1,小明取50元。
2,诈骗分子盗刷50元。
3,小强给小明汇款50元。

此时,银行交易系统出问题,每笔交易无法通过短信告知小明。ABA问题就是:
1,小明验证账户上有100元后,取出50元。——账上有50元。
2,小强不会验证小明账户的余额,直接汇款50元。——账上有100元。
3,诈骗分子验证账户有100元后,取出50元。——账上有50元。

小强没有告诉小明自己汇钱,小明也没收到短信,那么小明就一直以为只有自己取款操作,最后损失了50元。

作者:zmx
链接:https://www.zhihu.com/question/23281499/answer/729694164
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Pushy wechat
欢迎订阅我的微信公众号