CAS

什么是CAS

CAS 全名 Compare-and-swap。 它是用来在多线程中实现同步机制的原子指令。是 CPU 的硬件同步原语。大部分的现代处理器都支持 CAS 指令。

整个 CAS 过程如下:

  • CAS 算法会先读取内存位置 V,并保存 V 的值 A,然后基于 A 计算得到 B,接着尝试更新 B 到 V 位置,更新时会先比较 A 和 V 位置的值是否相同,如果相同则将 B 写入 V 位置。
  • 如果不相同则表示该位置的值被其他线程修改过,此时更新失败,同时 CAS 会将该结果返回给调用者(通过 boolean 值或返回此时 V 位置的值),然后由调用者决定后续策略(是重试还是回退或直接放弃更新)

由于 CAS 的原子性,整个操作过程是无需加锁的,即 CAS 实现并发是无锁、无阻塞的。

CAS原理

现代的CPU提供了特殊的指令,可以自动更新共享数据,而且能够检测到其他线程的干扰,而 compareAndSet() 就用这些代替了锁定。

CAS优缺点

CAS优点

  • 无阻塞 线程间不存在阻塞操作,失败后的处理更加灵活。
  • 性能好 对 Java 而言,JVM 处理锁操作过程很复杂,可能会导致操作系统级的锁定、线程挂起以及上下文切换,开销很大。而在内部执行 CAS 是不需要执行 JVM 代码、系统调用或线程调度,开销很小。

CAS缺点

  • CAS会导致“ABA问题”。
  • 需要自行处理竞争问题。

Java中为什么要引入CAS

java 中的synchronized关键字是悲观锁,也叫独占锁。 所谓悲观锁就是某一线程独占资源,其他线程只能干等着,这种锁在高并发中性能很差。

Java是如何引入CAS的

  • JDK 1.5 中引入了对 CAS 底层的支持,JVM 将它们编译为底层硬件提供的方法。
  • java.util.concurrent.atomit 中的相关类大量使用了 CAS 操作。
  • java.util.concurrent 中的大多数类在实现时直接或间接的使用了上述的原子变量类。这也是 ConcurrentBlockingQueue 类比线程安全的 BlockingQueue 高效的原因。
  • CAS的操作对象为volatile类型。
  • volatile类型变量是:CPU直接读写变量所在的内存 而不是把变量copy到寄存器操作 这样对变量的操作所有线程都是可见的。
  • 在没有锁的机制下,需要借助volatile原语,保证线程间的数据是可见的(共享的)。这样才获取变量的值的时候才能直接读取。

ABA问题

一个线程one从内存位置V中取出A,这时候另一个线程two也从内存中取出A,并且线程two进行了一些操作变成了B,然后two又将V位置的数据变成A,这时候线程one进行CAS操作发现内存中仍然是A,然后线程one操作成功。 尽管线程one的CAS操作成功,但是不代表这个过程就是没有问题的。如果链表的头在变化了两次后恢复了原值,但是不代表链表就没有变化。

因此原子操作AtomicStampedReference/AtomicMarkableReference就很有用了。这允许一对变化的元素进行原子操作。

Java中ABA问题解决办法

由于ABA问题带来的隐患,各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记,避免并发操作带来的问题,在Java中,AtomicStampedReference也实现了这个作用,它通过包装[E,Integer]的元组来对对象标记版本戳stamp,从而避免ABA问题,例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新,AtomicInteger会成功执行CAS操作,而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package concur.lock;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABA {

private static AtomicInteger atomicInt = new AtomicInteger(100);
private static AtomicStampedReference<Integer> atomicStampedRef =
new AtomicStampedReference<Integer>(100, 0);

public static void main(String[] args) throws InterruptedException {
Thread intT1 = new Thread(new Runnable() {
@Override
public void run() {
atomicInt.compareAndSet(100, 101);
atomicInt.compareAndSet(101, 100);
}
});

Thread intT2 = new Thread(new Runnable() {
@Override
public void run() {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean c3 = atomicInt.compareAndSet(100, 101);
System.out.println(c3); //true
}
});

intT1.start();
intT2.start();
intT1.join();
intT2.join();

Thread refT1 = new Thread(new Runnable() {
@Override
public void run() {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
atomicStampedRef.compareAndSet(100, 101,
atomicStampedRef.getStamp(), atomicStampedRef.getStamp()+1);
atomicStampedRef.compareAndSet(101, 100,
atomicStampedRef.getStamp(), atomicStampedRef.getStamp()+1);
}
});

Thread refT2 = new Thread(new Runnable() {
@Override
public void run() {
int stamp = atomicStampedRef.getStamp();
System.out.println("before sleep : stamp = " + stamp); // stamp = 0
try {
TimeUnit.SECONDS.sleep(2);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("after sleep : stamp = " + atomicStampedRef.getStamp());//stamp = 1
boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp+1);
System.out.println(c3); //false
}
});

refT1.start();
refT2.start();
}

}

坚持原创技术分享,您的支持将鼓励我继续创作!
0%