乐观锁与悲观锁

悲观锁

总是假设最坏的情况，每次获取数据都认为别人会修改，所以拿数据时会上锁，一直到释放锁不允许其他线程修改数据。Java中如synchronized和reentrantLock就是这种实现。

乐观锁

总是假设最好的情况，每次去拿数据时都认为别人不会修改，所以不上锁，等更新数据时判断一下在此期间是否有其他人更新过这个数据，可以使用CAS算法实现。乐观锁适用于多读少写的应用类型，可以大幅度提高吞吐量。乐观锁的实现机制主要包括版本号机制（给数据加一个版本号，数据被修改版本号会加一，更新时读取版本号，若读取到的版本号和之前一致才更新，否则驳回）和CAS算法（下详）。

CAS算法

JDK5增加java.util.concurrent包，其下类通过CAS算法实现了乐观锁实现。

CAS即compare and swap，是一种有名的无锁算法，即不使用锁的情况下实现多线程之间的变量同步，也叫非阻塞同步。

CAS有三个操作数，内存值V，旧的预期内存值A，要修改的新值B，当且仅当A=V，才将内存值V修改为B，否则不会执行任何操作。一般情况下CAS是一个自旋操作，即不断重试。

CAS只能保证一个共享变量的原子操作，当操作涉及跨多个共享变量时CAS无效。但可用AtomicReference来保证引用对象之间的原子性。

CAS开销

CAS是CPU指令集的操作，只有一步的原子操作，所以非常快，但CAS的开销主要在于cache miss问题。如图

image

这是一个8核CPU系统，共有4个管芯，每个管芯中有两个CPU，每个CPU有cache，管芯内有一个互联模块，让管芯的两个核可以互相通信。图中的系统连接模块可以让四个管芯通信。例如，此时CPU0进行一个CAS操作，而该变量所在的缓存线在CPU7的高速缓存中，则流程如下：

• CPU检查本地缓存，没有找到缓存线。
• 请求被转发到CPU0和CPU1的互联模块，检查CPU1的本地高速缓存，没有找到缓存线。
• 请求被转发到系统互联模块，检查其他三个管芯，得知缓存线在CPU6和CPU7所在的管芯中。
• 请求被转发到CPU6和CPU7的互联模块，检查这两个CPU的高速缓存，在CPU7中找到缓存线。
• CPU7将缓存线发给互联模块，并刷新自己的缓存线。
• CPU6和CPU7的互联模块将缓存线发送给系统互联模块。
• 系统互联模块将缓存线发送给CPU0和CPU1的互联模块。
• CPU0对高速缓存中的变量致性CAS操作。

此外，资源竞争时，CAS会自旋（不成功就循环到成功），

ABA问题

CAS一个常见问题是ABA问题，即变量V初次读时是A值，被赋值时也是A值，但期间变量被赋值成B值,CAS会误认为他从没被修改过。JDK1.5后的AtomicStampedReference类提供了监测ABA问题的能力，其中的compareAndSet方法首先检查当前引用是否等于预期引用，并且当前标志等于预期标志，全部相等则以原子方式将该引用和该标志的值设置为给定的更新值。

CAS与synchronized

• 资源竞争少时，synchronized同步锁进行线程阻塞，唤醒切换，用户内核态间切换，浪费额外CPU资源，CAS基于硬件实现，不进入内核，不切换线程，操作自旋几率小，CAS有更高的性能。
• 资源竞争严重时，CAS自旋概率较大，从而浪费更多的CPU资源，效率低于synchronized。

java.util.concurrent.atomic

jdk1.5提供了一组原子类，由CAS对其实现。其中的类可以分为四组：

• AtomicBoolean，AtomicInteger，AtomicLong，AtomicReference
• AtomicIntegerArray，AtomicLongArray
• AtomicLongFieldUpdater，AtomicIntegerFieldUpdater，AtomicReferenceFieldUpdater
• AtomicMarkableReference，AtomicStampedReference，AtomicReferenceArray

其作用为对单一数据的操作实现原子化，无需阻塞代码，但访问两个或两个以上的atomic变量或对单个atomic变量进行2次或2次以上的操作被认为是需要同步的以便这些操作是一个原子操作。

AtomicBoolean, AtomicInteger, AtomicLong, AtomicReference

这四种类型用来处理Boolean，Integer, Long, 对象，包含以下方法：

• 构造函数，默认值分别为false, 0, 0, null。带参数则参数为初始化数据。
• set()和get()方法，常规的设置/读取值，非原子操作。
• lazySet()，设置值，原子操作。
• getAndSet()相当于先使用get再set，但是是一个原子操作。
• compareAndSet(expectedData, newData)，接受两个参数，若atomic内数据和期望数据一致，则将新数据赋值给atomic数据返回true，否则不设置并返回false。
• weakCompareAndSet(expectedData, newData)，与前者类似，但更高效，不同的是可能会返回虚假的失败，不提供排序的保证，最好用于五关于happens-before的程序。

对于AtomicInteger, AtomicLong，还实现了getAndIncrement(),increateAndGet(),getAndDecreate(),decreateAndGet(),addAndGet()，getAndAdd()方法，以实现加减法的原子操作。剩下部分代码我还在阅读中，不定期补充。

参考文献

深入理解CAS算法原理
面试必备之乐观锁与悲观锁
Java之多线程 Atomic（原子的）
对 volatile、compareAndSet、weakCompareAndSet 的一些思考