菜鸟笔记
提升您的技术认知

操作系统笔记

进程,线程,协程与并行,并发进程线程协程的区别死锁进程,线程,多线程i++的线程安全性同步和异步孤儿进程和僵尸进程/proc进程信息linux中的分段和分页互斥量 mutex线程进程间通信进程创建进程优先级进程的基础知识进程与线程的区别(面试题)线程的控制(创建,终止,等待,分离)可重入 VS 线程安全死锁的概念一级缓存和二级缓存的理解一句话解说内存屏障 Memory barrierbrk(), sbrk() 用法详解malloc/free函数的简单实现一文讲透 “进程、线程、协程”Linux进程状态线程池的陷阱linux内核学习之进程和线程进程与线程的区别和联系内存寻址linux IO子系统和文件系统读写流程Page cache和buffer cache的区别与联系漫谈linux文件IO多线程和多进程的区别内存泄漏字节、字、位、比特的概念和关系如何避免死锁ANSI是什么编码?CPU寻址范围(寻址空间)CPU 使用率低高负载的原因创建多少个线程合适操作系统下spinlock锁解析、模拟及损耗分析线程堆栈堆和栈的内存分配堆和栈的概念和区别堆和栈的区别,申请方式,程序的内存分配什么是 POD 数据类型Linux内存分配小结--malloc、brk、mmap系统调用与内存管理(sbrk、brk、mmap、munmap)进程描述和控制CPU执行程序的原理编译的基本概念Linux虚拟地址空间布局一个程序从源代码到可执行程序的过程程序的运行机制——CPU、内存、指令的那些事分页内存管理——虚拟地址到物理地址的转换深刻理解Linux进程间通信fork之后父子进程的内存关系fork之后,子进程继承了父进程哪些内容关于协程及其锁的一些认识对协程的一点理解std::thread join和detach区别CAS和ABA问题CAS算法锁和无锁无锁队列的实现Lock-Free 编程锁开销优化以及CAS

CAS和ABA问题

阅读 : 106

一、引言                                                                                                                          

我们先来看一个多线程的运行场景:
时间点1 :线程1查询值是否为A
时间点2 :线程2查询值是否为A
时间点3 :线程2比较并更新值为B
时间点4 :线程2查询值是否为B
时间点5 :线程2比较并更新值为A
时间点6 :线程1比较并更新值为C

在这个线程执行场景中,2个线程交替执行。线程1在时间点6的时候依然能够正常的进行CAS操作,尽管在时间点2到时间点6期间已经发生一些意想不到的变化, 但是线程1对这些变化却一无所知,因为对线程1来说A的确还在。通常将这类现象称为ABA问题。
ABA发生了,但线程不知道。又或者链表的头在变化了两次后恢复了原值,但是不代表链表就没有变化。

   

二、ABA问题隐患                                                                                                            

获取上面的描述ABA问题带来的隐患没有直观的认识,那我们来看下维基百科上面的形象描述:

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

     

三、ABA问题解决                                                                                                          

1 A a = ref.get();
2 
3 // 根据a的状态做一些操作
4 
5 // do something
6 
7 // CAS,这时候会出现ABA问题,a指向的对象可能已经变了
8 
9 ref.compareAndSet(a, b)

   

ABA问题我们可以使用JDK的并发包中的AtomicStampedReference和 AtomicMarkableReference来解决。

   

// 用int做时间戳

AtomicStampedReference<QNode> tail = new AtomicStampedReference<CompositeLock.QNode>(null, 0);

int[] currentStamp = new int[1];

// currentStamp中返回了时间戳信息

QNode tailNode = tail.get(currentStamp);

tail.compareAndSet(tailNode, null, currentStamp[0], currentStamp[0] + 1)

总结: AtomicStampedReference和 AtomicMarkableReference是通过版本号(时间戳)来解决ABA问题的,我们也可以使用版本号(verison)来解决ABA。

即乐观锁每次在执行数据的修改操作时,都会带上一个版本号,一旦版本号和数据的版本号一致就可以执行修改操作并对版本号执行+1操作,否则就执行失败。

   

四、java.util.concurrent.atomic.AtomicStampedReference的源代码是如何实现的   

1. 创建一个Pair类来记录对象引用和时间戳信息,采用int作为时间戳,实际使用的时候时间戳信息要做成自增的,否则时间戳如果重复,还会出现ABA的问题。这个Pair对象是不可变对象,所有的属性都是final的, of方法每次返回一个新的不可变对象。

2. 使用一个volatile类型的引用指向当前的Pair对象,一旦volatile引用发生变化,变化对所有线程可见。

3. set方法时,当要设置的对象和当前Pair对象不一样时,新建一个不可变的Pair对象。

4. compareAndSet方法中,只有期望对象的引用和版本号和目标对象的引用和版本好都一样时,才会新建一个Pair对象,然后用新建的Pair对象和原理的Pair对象做CAS操作。

5. 实际的CAS操作比较的是当前的pair对象和新建的pair对象,pair对象封装了引用和时间戳信息。

 

 1 private static class Pair<T> {
 2 
 3 final T reference;
 4 
 5 final int stamp;
 6 
 7 private Pair(T reference, int stamp) {
 8 
 9 this.reference = reference;
10 
11 this.stamp = stamp;
12 
13 }
14 
15 static <T> Pair<T> of(T reference, int stamp) {
16 
17 return new Pair<T>(reference, stamp);
18 
19 }
20 
21 }
22 
23    
24 
25 private volatile Pair<V> pair;
26 
27 public AtomicStampedReference(V initialRef, int initialStamp) {
28 
29 pair = Pair.of(initialRef, initialStamp);
30 
31 }
32 
33    
34 
35 public void set(V newReference, int newStamp) {
36 
37         Pair<V> current = pair;
38 
39         if (newReference != current.reference || newStamp != current.stamp)
40 
41             this.pair = Pair.of(newReference, newStamp);
42 
43     }
44 
45    
46 
47 public boolean compareAndSet(V   expectedReference,
48 
49                                  V   newReference,
50 
51                                  int expectedStamp,
52 
53                                  int newStamp) {
54 
55         Pair<V> current = pair;
56 
57         return
58 
59             expectedReference == current.reference &&
60 
61             expectedStamp == current.stamp &&
62 
63             ((newReference == current.reference &&
64 
65               newStamp == current.stamp) ||
66 
67              casPair(current, Pair.of(newReference, newStamp)));
68 
69     }
70 
71    
72 
73 private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
74 
75     private static final long pairOffset =
76 
77         objectFieldOffset(UNSAFE, "pair", AtomicStampedReference.class);
78 
79    
80 
81     private boolean casPair(Pair<V> cmp, Pair<V> val) {
82 
83         return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
84 
85     }