◉◡◉ 您好,欢迎到访伊成个人站!

浅谈多线程之CAS原理

本文于1843天之前发表,文中内容可能已经过时。

'浅谈多线程之CAS原理'

前言

在Java并发包中有这样一个包,java.util.concurrent.atomic,该包是对Java部分数据类型的原子封装,在原有数据类型的基础上,
提供了原子性的操作方法,保证了线程安全。
下面以AtomicInteger为例,来看一下是如何实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}


public final int decrementAndGet() {
for (;;) {
int current = get();
int next = current - 1;
if (compareAndSet(current, next))
return next;
}
}

以这两个方法为例,incrementAndGet方法相当于原子性的i,decrementAndGet方法相当于原子性的–i(根据第一章和第二章我们知道i或–i不是一个原子性的操作),
这两个方法中都没有使用阻塞式的方式来保证原子性(如Synchronized),那它们是如何保证原子性的呢,下面引出CAS。

Compare And Swap

CAS 指的是现代 CPU 广泛支持的一种对内存中的共享数据进行操作的一种特殊指令。这个指令会对内存中的共享数据做原子的读写操作。
简单介绍一下这个指令的操作过程:首先,CPU 会将内存中将要被更改的数据与期望的值做比较。

然后,当这两个值相等时,CPU 才会将内存中的数值替换为新的值。否则便不做操作。
最后,CPU 会将旧的数值返回。这一系列的操作是原子的。它们虽然看似复杂,但却是 Java 5 并发机制优于原有锁机制的根本。

简单来说,CAS 的含义是“我认为原有的值应该是什么,如果是,则将原有的值更新为新值,否则不做修改,并告诉我原来的值是多少”。
(这段描述引自《Java并发编程实践》) 简单的来说,CAS有3个操作数,内存值V,旧的预期值A,要修改的新值B。

当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则返回V。这是一种乐观锁的思路,它相信在它修改之前,
没有其它线程去修改它;而Synchronized是一种悲观锁,它认为在它修改之前,一定会有其它线程去修改它,悲观锁效率很低。
下面来看一下AtomicInteger是如何利用CAS实现原子性操作的。

CAS的ABA问题

所谓 ,问题基本是这个样子:

进程P1在共享变量中读到值为A P1被抢占了,进程P2执行 P2把共享变量里的值从A改成了B,再改回到A,此时被P1抢占。

P1回来看到共享变量里的值没有被改变,于是继续执行。 虽然P1以为变量值没有改变,继续执行了,但是这个会引发一些潜在的问题。
ABA问题最容易发生在lock free 的算法中的,CAS首当其冲,因为CAS判断的是指针的地址。如果这个地址被重用了呢,问题就很大了。(地址被重用是很经常发生的,一个内存分配后释放了,再分配,很有可能还是原来的地址)

比如上述的DeQueue()函数,因为我们要让head和tail分开,所以我们引入了一个dummy指针给head,当我们做CAS的之前,
如果head的那块内存被回收并被重用了,而重用的内存又被EnQueue()进来了,这会有很大的问题。(内存管理中重用内存基本上是一种很常见的行为)

这个例子你可能没有看懂,维基百科上给了一个活生生的例子——

你拿着一个装满钱的手提箱在飞机场,此时过来了一个火辣性感的美女,然后她很暖昧地挑逗着你,并趁你不注意的时候,
把用一个一模一样的手提箱和你那装满钱的箱子调了个包,然后就离开了,你看到你的手提箱还在那,于是就提着手提箱去赶飞机去了。

这就是ABA的问题。

支付宝打赏 微信打赏