Commit 3909cc8

悲观锁：总是认为每次访问共享变量资源时会发生冲突。

乐观锁：又称为"无锁"，当线程发生冲突时，乐观锁通常是使用一种称为 CAS 的技术来保证线程执行的安全性。**由于无锁操作中没有锁的存在，因此乐观锁天生免疫死锁。**

CAS 的全称是：比较并交换(Compare And Swap)，在 CAS 中，有这样三个值：

- V：要更新的变量(var)

- E：预期值(expected)

- N：新值(new)

比较并交换的过程：判断 V 是否等于 E，如果等于，将 V 的值设置为 N；如果不等，则当前线程放弃更新，什么都不做，**所以这里的预期值 E 本质上指的是"旧值"。**

**当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。**

public native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);

public native boolean compareAndSwapInt(Object o, long offset,int expected,int x);

public native boolean compareAndSwapLong(Object o, long offset,long expected,long x);

Linux 的 X86 下主要是通过 cmpxchgl 这个指令在 CPU 级完成 CAS 操作的，但在多处理器情况下必须使用 lock 指令加锁来完成。

public final int getAndAddInt(Object o, long offset, int delta) {

int v;

do {

v = getIntVolatile(o, offset);

} while (!weakCompareAndSetInt(o, offset, v, v + delta));

return v;

}

这里使用的是 do-while 循环,它的目的是保证循环体内的语句至少会被执行一遍。这样才能保证 return 的值 v 是我们期望的值。

public final boolean weakCompareAndSetInt(Object o, long offset,

int expected,

int x) {

return compareAndSetInt(o, offset, expected, x);

}

public final native boolean compareAndSetInt(Object o, long offset,

int expected,

int x);

这里可以看到，其实最终调用的就是 Unsafe 类中的 native 方法。

所谓ABA问题，就是一个值原来是A，变成了B，又变回了A。这个时候使用CAS是检查不出变化的，但实际上却被更新了两次。

ABA 问题的解决思路是在变量前面追加上版本号或者时间戳。从 JDK 1.5 开始，JDK 的 atomic 包里提供了一个类 AtomicStampedReference 类来解决 ABA 问题。

这个类的 compareAndSet 方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果二者都相等，才使用CAS设置为新的值和标志。

public boolean compareAndSet(V expectedReference,

V newReference,

int expectedStamp,

int newStamp) {

Pair<V> current = pair;

return

expectedReference == current.reference &&

expectedStamp == current.stamp &&

((newReference == current.reference &&

newStamp == current.stamp) ||

casPair(current, Pair.of(newReference, newStamp)));

}

解决思路是让 JVM 支持处理器提供的 pause 指令。pause 指令能让自旋失败时 CPU 睡眠一小段时间再继续自旋。

这个问题有两种解决方案：

1. 使用 JDK 1.5 提供的 AtomicReference 类保证对象之间的原子性，把多个变量放到一个对象里面进行 CAS 操作；

2. 使用锁。

AQS 是 AbstractQueuedSynchronizer 的简称，即**抽象队列同步器**。AQS 是一个用来构建锁和同步器的框架，使用 AQS 能简单且高效地构造出应用广泛的同步器，比如我们提到的 ReentrantLock，Semaphore，ReentrantReadWriteLock，SynchronousQueue，FutureTask等等皆是基于 AQS 的。

AQS 内部使用了一个 volatile 的变量 state 来作为资源的标识。同时定义了几个获取和改变 state 的 protected 方法，子类可以覆盖这些方法来实现自己的逻辑：

getState()

setState()

compareAndSetState()

这三种均是原子操作，其中 compareAndSetState 的实现依赖于 Unsafe 的 compareAndSwapInt() 方法。

AQS 内部使用了一个先进先出的双端队列，并使用了两个指针 head 和 tail 用于标识队列的头部和尾部。但它并不是直接存储线程，而是存储拥有线程的 Node 节点。

资源有两种同步模式：

1. 独占模式(Exclusive)：资源是独占的，一次只能一个线程获取。

2. 共享模式(Share)：同时可以被多个线程获取，具体的资源个数可以通过参数指定。

static final class Node {

// 标记一个结点（对应的线程）在共享模式下等待

static final Node SHARED = new Node();

// 标记一个结点（对应的线程）在独占模式下等待

static final Node EXCLUSIVE = null;

// waitStatus的值，表示该结点（对应的线程）已被取消

static final int CANCELLED = 1;

// waitStatus的值，表示后继结点（对应的线程）需要被唤醒

static final int SIGNAL = -1;

// waitStatus的值，表示该结点（对应的线程）在等待某一条件

static final int CONDITION = -2;

/*waitStatus的值，表示有资源可用，新head结点需要继续唤醒后继结点（共享模式下，多线程并发释放资源，而head唤醒其后继结点后，需要把多出来的资源留给后面的结点；设置新的head结点时，会继续唤醒其后继结点）*/

static final int PROPAGATE = -3;

// 等待状态，取值范围，-3，-2，-1，0，1

volatile int waitStatus;

volatile Node prev; // 前驱结点

volatile Node next; // 后继结点

volatile Thread thread; // 结点对应的线程

Node nextWaiter; // 等待队列里下一个等待条件的结点

// 判断共享模式的方法

final boolean isShared() {

return nextWaiter == SHARED;

}

Node(Thread thread, Node mode) { // Used by addWaiter

this.nextWaiter = mode;

this.thread = thread;

}

// 其它方法忽略，可以参考具体的源码

}

private Node addWaiter(Node mode) {

// 使用了Node的这个构造函数

Node node = new Node(Thread.currentThread(), mode);

// 其它代码省略

}

- isHeldExclusively()：该线程是否正在独占资源。只有用到 condition 才需要去实现它；

- tryAcquire(int)：独占方式。尝试获取资源，成功则返回 true，失败则返回 false；

- tryRelease(int)：独占方式。尝试释放资源，成功则返回 true，失败则返回 false；

- tryAcquireShared(int)：共享方式。尝试获取资源。负数表示失败；0表示成功，但没有剩余可用资源；正数表示成功，且有剩余资源；

- tryReleaseShared(int)：共享方式。尝试释放资源，如果释放后允许唤醒后续等待结点返回 true，否则返回 false。

上述方法都是 protected 方法，之所以不使用抽象方法的目的是可以灵活的让子类根据需要选择实现某些方法而不是强迫子类实现所有的抽象方法。

public final void acquire(int arg) {

if (!tryAcquire(arg) &&

acquireQueued(addWaiter(Node.EXCLUSIVE), arg))

selfInterrupt();

}

private Node addWaiter(Node mode) {

// 生成该线程对应的Node节点

Node node = new Node(Thread.currentThread(), mode);

// 将Node插入队列中

Node pred = tail;

if (pred != null) {

node.prev = pred;

// 使用CAS尝试，如果成功就返回

if (compareAndSetTail(pred, node)) {

pred.next = node;

return node;

}

}

// 如果等待队列为空或者上述CAS失败，再自旋CAS插入

enq(node);

return node;

}

private Node enq(final Node node) {

for (;;) {

Node t = tail;

if (t == null) { // Must initialize

if (compareAndSetHead(new Node()))

tail = head;

} else {

node.prev = t;

if (compareAndSetTail(t, node)) {

t.next = node;

return t;

}

}

}

}

final boolean acquireQueued(final Node node, int arg) {

boolean failed = true;

try {

boolean interrupted = false;

// 自旋

for (;;) {

final Node p = node.predecessor();

// 如果node的前驱结点p是head，表示node是第二个结点，就可以尝试去获取资源了

if (p == head && tryAcquire(arg)) {

// 拿到资源后，将head指向该结点。

// 所以head所指的结点，就是当前获取到资源的那个结点或null。

setHead(node);

p.next = null; // help GC

failed = false;

return interrupted;

}

// 如果自己可以休息了，就进入waiting状态，直到被unpark()

if (shouldParkAfterFailedAcquire(p, node) &&

parkAndCheckInterrupt())

interrupted = true;

}

} finally {

if (failed)

cancelAcquire(node);

}

}

1. park(boolean isAbsolute, long time)：阻塞当前线程；

2.unpark(Thread jthread)：使给定的线程停止阻塞。

**所以结点进入等待队列后，是调用park使它进入阻塞状态的。只有头结点的线程是处于活跃状态的。**

获取资源的方法除了 acquire 外，还有以下三个：

- acquireInterruptibly：申请可中断的资源(独占模式)；

- acquireShared：申请共享模式的资源；

- acquireSharedInterruptibly：申请可中断的资源(共享模式)

public final boolean release(int arg) {

if (tryRelease(arg)) {

Node h = head;

if (h != null && h.waitStatus != 0)

unparkSuccessor(h);

return true;

}

return false;

}

private void unparkSuccessor(Node node) {

// 如果状态是负数，尝试把它设置为0

int ws = node.waitStatus;

if (ws < 0)

compareAndSetWaitStatus(node, ws, 0);

// 得到头结点的后继结点head.next

Node s = node.next;

// 如果这个后继结点为空或者状态大于0

// 通过前面的定义我们知道，大于0只有一种可能，就是这个结点已被取消

if (s == null || s.waitStatus > 0) {

s = null;

// 等待队列中所有还有用的结点，都向前移动

for (Node t = tail; t != null && t != node; t = t.prev)

if (t.waitStatus <= 0)

s = t;

}

// 如果后继结点不为空，

if (s != null)

LockSupport.unpark(s.thread);

}