并发总结2--volatile、CAS、HB

1. 原子性CAS(比较并交换)

回想一下，之前使用syn块可以保证只有一个线程能够得到锁（互斥性），但是使用syn的成本可能会大。因为线程会阻塞，挂起，上下文切换等

 

几乎每个现代处理器都有通过检测或阻止其他处理器的并发访问的方式来让共享变量安全的更新。最常用的指令是CAS

 

1.1. CAS 原理

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)

 

我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。他是非阻塞的。

 

从某种意义上来看，简单的复合操作，不管是getAndInc和getAndDec还有IncAndGet、DecAndGet等等，其实都可以归结为一个CAS操作，比如getAndInc，在for循环内取原值，并且+1，并且和原值比较设置结果，如果成功的话返回，否则继续！

 

1.2. 无锁定（乐观非阻塞算法）

基于 CAS 的并发算法称为 无锁定算法，因为线程不必再等待锁。无论 CAS 操作成功还是失败，在任何一种情况中，它都在可预知的时间内完成。如果 CAS 失败，调用者可以重试 CAS 操作或采取其他适合的操作。

 

这是一个乐观锁，多线程调用时，一个会胜出，其他都失败，失败的不会挂起（和锁不同），可以再次尝试完成，这类算法称之为非阻塞(nonblocking)算法。

使用非阻塞算法比同步更好，要实现非阻塞，关键就是把原子的范围缩小到一个变量！

1.3. ABA问题

假设, 第一次读取V地址的A值, 然后通过CAS来判断V地址的值是否仍旧为A, 如果是, 就将B的值写入V地址,覆盖A值.

但是, 语义上, 有一个漏洞, 当第一次读取V的A值, 此时, 内存V的值变为B值, 然后在未执行CAS前, 又变回了A值.
此时, CAS再执行时, 会判断其正确的, 并进行赋值.

这种判断值的方式来断定内存是否被修改过, 针对某些问题, 是不适用的.

为了解决这种问题, jdk 1.5并发包提供了AtomicStampedReference(有标记的原子引用)类, 通过控制变量值的版本来保证CAS正确性.其实, 大部分通过值的变化来CAS, 已经够用了.

 

1.4. 性能考量

在轻度到中度的争用情况下，非阻塞算法的性能会超越阻塞算法，因为 CAS 的多数时间都在第一次尝试时就成功，而发生争用时的开销也不涉及线程挂起和上下文切换，只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多（这句话肯定是真的，因为没有争用的锁涉及 CAS 加上额外的处理，加锁至少需要一个CAS，在有竞争的情况下，需要操作队列，线程挂起，上下文切换），而争用的 CAS 比争用的锁获取涉及更短的延迟。

 

在高度争用的情况下（即有多个线程不断争用一个内存位置的时候），基于锁的算法开始提供比非阻塞算法更好的吞吐率，因为当线程阻塞时，它就会停止争用，耐心地等候轮到自己，从而避免了进一步争用。但是，这么高的争用程度并不常见，因为多数时候，线程会把线程本地的计算与争用共享数据的操作分开，从而给其他线程使用共享数据的机会。（这么高的争用程度也表明需要重新检查算法，朝着更少共享数据的方向努力。）“流行的原子” 中的图在这方面就有点儿让人困惑，因为被测量的程序中发生的争用极其密集，看起来即使对数量很少的线程，锁定也是更好的解决方案。

在java5之前，除非写本机代码通过jni，否则不能在java代码里实现CAS，Java5引入了底层的支持：

unsafe.compareAndSwapInt(this, valueOffset, expect, update);

 

因此出现了一系列原子类！

 

 

2. 可见性和顺序

指令重排序与happens-before法则

2.1. happens-before

之前觉得hb很简单，没仔细看，结果看代码的时候遇到了问题，理解不了，所以还是重点讲一下吧

 

（1）同一个线程中的每个Action都happens-before于出现在其后的任何一个Action。

（2）对一个监视器的解锁happens-before于每一个后续对同一个监视器的加锁。

（3）对volatile字段的写入操作happens-before于每一个后续的同一个字段的读操作。

（4）Thread.start()的调用会happens-before于启动线程里面的动作。

（5）Thread中的所有动作都happens-before于其他线程检查到此线程结束或者Thread.join（）中返回或者Thread.isAlive()==false。

（6）一个线程A调用另一个另一个线程B的interrupt（）都happens-before于线程A发现B被A中断（B抛出异常或者A检测到B的isInterrupted（）或者interrupted()）。

（7）一个对象构造函数的结束happens-before与该对象的finalizer的开始

（8）如果A动作happens-before于B动作，而B动作happens-before与C动作，那么A动作happens-before于C动作。 

 

 

仔细理解1，2，8三条，再去理解下ConcurrentHashMap里的代码实现，就会发现确实是非常精巧。

 

要实现HB（比如volatile关键字），在多线程环境下，首先要确保不能参与重排序，另外，也要解决内存缓存同步的问题

 

2.2. 内存屏障

参考：内存屏障

2.3. 定义

内存屏障的作用是让屏障指令前面的指令不会被重排序到屏障指令之后，屏障指令之后的指令也不会被重排序到屏障指令之前，相当于一道屏障挡在了指令之间，前面和后面的指令都不能跨过屏障。

 

2.4. 屏障的分类

内存屏障主要有：读屏障、写屏障、通用屏障、优化屏障、几种。

 

以读屏障为例，它用于保证读操作有序。屏障之前的读操作一定会先于屏障之后的读操作完成，写操作不受影响，同属于屏障的某一侧的读操作也不受影响。

 

类似的，写屏障用于限制写操作。

 

而通用屏障则对读写操作都有作用。

 

而优化屏障则用于限制编译器的指令重排，不区分读写。前三种屏障都隐含了优化屏障的功能。比如：

tmp = ttt; *addr = 5; mb(); val = *data;

有了内存屏障就了确保先设置地址端口，再读数据端口。而至于设置地址端口与tmp的赋值孰先孰后，屏障则不做干预。

 

有了内存屏障，就可以在隐式因果关系的场景中，保证因果关系逻辑正确。

 

-----------------------------------------------------------------------------

 

另外按编译器和CPU角度来看：

· 编译器级别的：防止编译器对指令进行重排序，例如GCC的asm volatile("" ::: "memory")等等。

· 处理器级别的：防止处理器对指令进行重排序，例如X86的lock，lfence()，sfenec()等等(关于处理器级别的内存屏障如何实现，可以参考这篇文章)。

 

2.5. Volatile

 

Volatile声明的变量不会和其他内存槽组一起被重排序，也不会缓存在寄存器之类的地方可以理解为线程A向volatile变量写入值，随后线程B读取该变量，所有A执行写操作之前可见的变量，在B线程读取了volatile变量之后，成为对B也是可见的，就像是写入volatile变量就像退出锁，读取volatile就像进入同步块

 

能保证可见性和顺序性，在Hotspot JVM中，

a) 在JVM层次，对volatile变量在线程本地工作区中不做缓存，对volatile的读写总是指向堆中的引用。可以视作在一个assign指令后总是跟着一个store指令[5]。

b) 在机器码执行层次，通过内存屏障指令等迫使CPU不重排序，清除缓存，详细请参考《Memory Barriers and JVM Concurrency》的分析。

 

这与synchronized是有明显不同的，synchronized通常需要原子锁定，在SMP上要通过锁定总线等方式来实现，其代价在大多数平台上通常要比volatile高得多。

 

在这里Java中的Volatile关键字 有一段性能测试：

 

2.6. volatile的实现

下文提到了volatile的实现，

【并发编程】深入分析Volatile的实现原理

 

Java代码：	instance = new Singleton();//instance是volatile变量
汇编代码：	0x01a3de1d: movb $0x0,0x1104800(%esi); 0x01a3de24: lock addl $0x0,(%esp);

 

对应到指令上会多出lock指令，有两个作用：

 

1.Lock前缀指令会引起处理器缓存回写到内存，它会锁定这块内存区域的缓存并回写到内存，并使用缓存一致性机制来确保修改的原子性，此操作被称为“缓存锁定”，缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据。

 

2.缓存回写导致其他处理器的缓存失效。IA-32 和Intel 64处理器能嗅探其他处理器访问系统内存和它们的内部缓存。它们使用嗅探技术保证它的内部缓存，系统内存和其他处理器的缓存的数据在总线上保持一致

 

不过里面关于PaddedAtomicReference的优化还没怎么看明白，以后再看吧

 

http://www.360doc.com/content/15/0803/11/18167315_489198658.shtml