乐观锁:CAS 算法

在并发编程中,我们大多数情况下都是显式地通过加锁来保证线程安全。这里我们来介绍一种在无锁条件下多线程变量同步的方法——CAS(Compare And Swap,比较与交换)算法

abstract.jpeg

悲观锁、乐观锁

在介绍CAS算法之前,我们先了解两个概念——悲观锁、乐观锁。首先需要明确的是它们并不是指代某个具体的锁,而是指两种不同的并发控制策略

  • 悲观锁

当一个线程使用数据时,悲观锁总是认为其它线程也会过来修改这个数据。为了保证数据安全,其采用的是一种先加锁再访问的策略,其它线程要想也访问该数据则被阻塞等待、直到其获取到锁才可以访问。典型的,Java中的synchronized锁就是悲观锁

  • 乐观锁

而对于乐观锁而言,其与悲观锁的思想则恰恰相反,其认为在使用数据的过程中其它线程不会修改这个数据,故不加锁直接访问。而当该线程需要提交更新、修改时,才会判断该数据在此期间有没有被其它线程更新、修改。如果其它线程确实没有修改,则该线程直接写入完成更新;反之如果该数据已经被其它线程更新、修改,则该线程将放弃本次数据的更新提交操作以避免出现冲突,并通过报错、重试等方式进行下一步处理。而我们这里即将介绍的CAS算法就是乐观锁的一种典型实现

据此我们可以看到,悲观锁适合写操作多的场景,而乐观锁则更适合读操作多的场景

CAS 比较与交换算法

在CAS(比较与交换)算法中涉及3个操作数:变量当前内存值V、变量的预期值E、新值U。只有该变量当前的内存值V与预期值E相同时,才会将新值U写入内存完成变量修改,否则什么都不做。下面是通过CAS修改变量数据的示例,CAS通过该变量的地址即可获取该变量当前的内存值V。当本轮CAS操作失败后,会重新读取该变量内存中最新的值并重新计算新值,直到其CAS操作修改变量成功为止

1
2
3
4
do{
1. 读取变量值,记为E。用于写入修改时,判断该变量是否被修改
2. 使用读到的变量值E,计算该变量的新值,记为U
} while( !CAS(变量内存地址,E,U) )

在Java中,java.util.concurrent.atomic包的原子变量类大量使用了Unsafe类提供的CAS操作。进一步地,CAS操作通过硬件来保证了比较-更新操作的原子性。下面分别使用volatile和AtomicInteger来进行演示

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

private static AtomicInteger atomicCount = new AtomicInteger(0);
private static volatile Integer count = 0;

public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[20];
for(int i=0; i<20; i++) {
Thread thread = new Thread( ()->{
for(int j=0; j<10000; j++) {
atomicCount.incrementAndGet(); // atomicCount++
count++;
}
} );
threads[i] = thread;
thread.start();
}

for(Thread thread : threads) {
thread.join();
}

System.out.println("atomicCount: " + atomicCount);
System.out.println("count: " + count);
}
}

从测试结果中,我们可以使用了CAS的原子类具备原子性

figure 1.jpeg

实现原理

前面我们说到CAS操作的原子性是通过硬件来保证,这里作进一步的解释说明。CPU层面上,CAS的比较-写入操作上是通过cmpxchg指令去实现完成的。然而不幸的是,cmpxchg指令并不是一个原子操作。即可能会发生这样的场景,线程A在执行cmpxchg指令的过程中,发现当前内存值V与预期值E一致,正准备将新值U写入内存,这个时候另外一个线程B打断了线程A的操作,将该变量修改了。显然这个变量发生了线程安全的问题,为此为了保证cmpxchg指令的原子性,不会被打断,需要在cmpxchg指令前添加一个前缀指令lock。通过对cmpxchg指令进行加锁(总线锁或缓存锁)来保证操作的原子性。通常我们会说CAS算法是一个无锁算法,但其实我们可以看到底层依然是加了锁的,只不过这个锁的粒度是很小的

CAS缺陷

ABA问题

我们知道在CAS操作中,判断变量是否被其他线程修改,是通过比较当前内存值V和预期值E来完成的。现在考虑这样一个场景,线程1读到某变量的值为A,在其计算新值的过程中,另外一个线程2已经将该变量的值从A先修改为B、然后又将其从B修改回A。此时,当线程1通过CAS操作进行新值写入虽然可以成功,而实际上线程1执行CAS操作时 预期值的A 和 读取该变量当前值的A 已经不是”同一个”了,因为后者是线程2修改的

之所以会产生ABA问题是因为变量的值存在环形转换,而如果该变量只能朝着一个方向变化(例如一个自增的主键ID变量),就不会出现该问题。而对于ABA问题则可以通过给变量附加时间戳、版本号等信息来解决

CPU开销

虽然CAS算法是非阻塞的,但是如果CAS操作一直不成功不断循环,将会大大浪费CPU资源

只能保证一个变量的原子性

当对多个变量进行操作时,CAS算法无法保证原子性。为此Java提供了一个AtomicReference类,可以通过组合的方式将多个变量封装为一个对象再使用CAS算法

参考文献

  1. Java并发编程之美 翟陆续、薛宾田著
0%