决战圣地玛丽乔亚Day15 CAS和分布式锁

volatile的问题：

volatile只能保证读/写操作的原子性，没有办法保证变量的其他操作的原子性，例如 ++  等非单独读/写操作。

相对于Synchronized的悲观锁方式，还有一种方式来保证并发的同步，那就是乐观锁，乐观锁其中的一种实现方式就是CAS。

CAS:（compare and swap 比较并交换）　　

CAS(内存位置，预期数值，新值)  首先把内存位置的值进行比较，如果相等说明没有被写入新值，替换为新值；若不相等，不做改变，重试。

CAS在底层的处理会根据CPU是多核还是单核进行分别的处理，如果是多核CPU 就为 cmpxchg 指令加上 lock 前缀，单核不加lock（单核处理器自己维护顺序唯一，不需要lock提供的内存屏障效果）

对于lock前缀的说明：

• 确保对内存的读 - 改 - 写操作原子执行。在 Pentium 及 Pentium 之前的处理器中，带有 lock 前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。很显然，这会带来昂贵的开销。从 Pentium 4，Intel Xeon 及 P6 处理器开始，intel 在原有总线锁的基础上做了一个很有意义的优化：如果要访问的内存区域（area of memory）在 lock 前缀指令执行期间已经在处理器内部的缓存中被锁定（即包含该内存区域的缓存行当前处于独占或以修改状态），并且该内存区域被完全包含在单个缓存行（cache line）中，那么处理器将直接执行该指令。由于在指令执行期间该缓存行会一直被锁定，其它处理器无法读 / 写该指令要访问的内存区域，因此能保证指令执行的原子性。这个操作过程叫做缓存锁定（cache locking），缓存锁定将大大降低 lock 前缀指令的执行开销，但是当多处理器之间的竞争程度很高或者指令访问的内存地址未对齐时，仍然会锁住总线。   （也就是说，如果缓存行是单独的，不会锁整个内存，锁单独的缓存行，其他的进程可以用缓存的其他部分不会被阻塞）

• 禁止该指令与之前和之后的读和写指令重排序。

• 把写缓冲区中的所有数据刷新到内存中。

 concurrent 包就是利用Volatile+CAS的模式来实现同步：

• 首先，声明共享变量为 volatile；

• 然后，使用 CAS 的原子条件更新来实现线程之间的同步；

• 同时，配合以 volatile 的读 / 写和 CAS 所具有的 volatile 读和写的内存语义来实现线程之间的通信。

AQS，非阻塞数据结构和原子变量类（java.util.concurrent.atomic 包中的类），这些 concurrent 包中的基础类都是使用这种模式来实现的，而 concurrent 包中的高层类又是依赖于这些基础类来实现的。从整体来看，concurrent 包的实现示意图如下：

JVM中的CAS（堆中对象的分配）：　

Java 调用 new object() 会创建一个对象，这个对象会被分配到 JVM 的堆中。那么这个对象到底是怎么在堆中保存的呢？

首先，new object() 执行的时候，这个对象需要多大的空间，其实是已经确定的，因为 java 中的各种数据类型，占用多大的空间都是固定的（对其原理不清楚的请自行Google）。那么接下来的工作就是在堆中找出那么一块空间用于存放这个对象。

在单线程的情况下，一般有两种分配策略：

1. 指针碰撞：这种一般适用于内存是绝对规整的（内存是否规整取决于内存回收策略），分配空间的工作只是将指针像空闲内存一侧移动对象大小的距离即可。

2. 空闲列表：这种适用于内存非规整的情况，这种情况下JVM会维护一个内存列表，记录哪些内存区域是空闲的，大小是多少。给对象分配空间的时候去空闲列表里查询到合适的区域然后进行分配即可。

但是JVM不可能一直在单线程状态下运行，那样效率太差了。由于再给一个对象分配内存的时候不是原子性的操作，至少需要以下几步：查找空闲列表、分配内存、修改空闲列表等等，这是不安全的。解决并发时的安全问题也有两种策略：

1. CAS：实际上虚拟机采用CAS配合上失败重试的方式保证更新操作的原子性，原理和上面讲的一样。

2. TLAB：如果使用CAS其实对性能还是会有影响的，所以 JVM 又提出了一种更高级的优化策略：每个线程在 Java 堆中预先分配一小块内存，称为本地线程分配缓冲区（TLAB），线程内部需要分配内存时直接在 TLAB 上分配就行，避免了线程冲突。只有当缓冲区的内存用光需要重新分配内存的时候才会进行CAS操作分配更大的内存空间。

CAS存在的问题：

1.ABA： 

两个线程轮流占用CPU， 线程2在线程1不知情的情况下把数值进行2次修改    a->b   b->a   。  这种问题可以通过加版本号'/时间戳来解决

2.循环时间过长：

自旋CAS（不成功，就一直循环执行，直到成功） 如果长时间不成功，会给 CPU 带来非常大的执行开销。如果JVM能支持处理器提供的 pause 指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline），使 CPU 不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起 CPU 流水线被清空（CPU pipeline flush），从而提高 CPU 的执行效率。 

3.只能保证一个共享变量的原子操作：

把多个变量放入一个对象，原子类也有提供对象的原子操作类AtomicReference

CAS 与 Synchronized 的使用情景：　　　

1. 对于资源竞争较少（线程冲突较轻）的情况，使用synchronized同步锁进行线程阻塞和唤醒切换以及用户态内核态间的切换操作额外浪费消耗cpu资源；而CAS基于硬件实现，不需要进入内核，不需要切换线程，操作自旋几率较少，因此可以获得更高的性能。

2. 对于资源竞争严重（线程冲突严重）的情况，CAS自旋的概率会比较大，从而浪费更多的CPU资源，效率低于synchronized。

补充： synchronized 在 jdk1.6 之后，已经改进优化。synchronized 的底层实现主要依靠 Lock-Free 的队列，基本思路是自旋后阻塞，竞争切换后继续竞争锁，稍微牺牲了公平性，但获得了高吞吐量。在线程冲突较少的情况下，可以获得和 CAS 类似的性能；而线程冲突严重的情况下，性能远高于 CAS。