|
本文参考了：
Java并发之AQS详解
黑马JUC并发编程
Java并发编程的艺术
深入理解java虚拟机
synchronized
在讲锁之前，先回顾一下synchronized的知识
在java中，最基本的互斥同步就是synchronized关键字。这是一种块结构（Block Structured）的同步语法。其经过Javac编译后，会分别形成monitorenter和monitorexit两个字节码指令。两者都需要一个reference类型的参数来指明锁定和解锁的对象；如果不指定，则根据其修饰的方法类型（实例方法或类方法）来决定对象作为锁，还是类型对应的Class对象作为锁。
每个monitorenter都需要有与之对应的monitorexit配对。
当第一个线程获取锁时，即执行到monitorenter时，会为对象关联Monitor，此时对象头存放Monitor的地址，monitor的所有者就是这个线程。此时，锁的计数器+1，而在执行monitorexit时，计数器-1。当值为0，锁就被释放。
我们说的可重入，也指的是：被synchronized修饰的同步块（同一个锁）对同一线程来说是可重复进入的，不会引起阻塞。
观察字节码指令时，我们会发现存在两个monitorexit指令
0 aload_0
1 dup
2 astore_1
3 monitorenter
4 aload_1
5 monitorexit
6 goto 14 (+8)
9 astore_2
10 aload_1
11 monitorexit
12 aload_2
13 athrow
14 return
这两个指令保证了无论是正常退出同步代码块，还是发生了异常，都能释放锁。
我们发现在使用synchronized代码块时，会先将引用复制一份
如果没有异常，正常释放锁，并goto跳过异常处理指令
如果发生异常，则将异常对象放入slot下标为2的位置，再释放锁对象，然后再抛出异常。
也就是说只要退出同步代码块，JVM就一定能保证锁的释放（前提是计数器为0，代表此时线程已经退出所有的同步代码块）。
不可中断性：被synchronized修饰的同步块在持有锁的线程执行完毕并释放锁之前，会无条件地阻塞后面线程的进入。意味着无法强制已获得锁的线程释放锁；也无法使正在等待锁的线程中断等待或超时退出。
这意味着持有锁是一个重量级操作。由于Java线程映射到操作系统原生内核线程之上，每次阻塞、唤醒线程，都需要用户态到核心态的转换，需要耗费大量处理器时间。
（此处我们说的是重量级锁，关于synchronized的优化，详见线程安全与锁优化（2）——锁优化）
从JDK5起，Java类库中提供了concurrent包。其中的Lock接口成为Java全新的互斥同步手段。用户可以通过非块结构实现同步，从而摆脱了语言特性的束缚，而改为在类库层面去实现同步。从而为日后的扩展提供了空间。
Lock接口
synchronized是语法特性层面上的，而Lock则是类层面上的。这两者都提供了类似的同步功能，只是Lock类需要在使用时显示获取和释放锁，而synchronized的释放是由JVM管理的。
使用Lock的好处是：具备可中断性、可扩展性和超时时间等。
使用syncrhonized好处是：使用简洁，方便，不用自己管理锁的释放，且由于是语法层面的特性，JVM更容易针对其进行优化。
语法格式
Lock l = new ReentrantLock();
l.lock();
try{
......
}finally {
l.unlock();
}
注意：不要将获取锁的过程写在try中，因为如果获取锁（自定锁的情况）发生异常，异常抛出的同时，也会导致锁无故释放，因为线程本来就没有锁，导致在释放锁的时候又会抛出IllegalMonitorStateException异常，使得原本的异常信息被覆盖。
Lock具有的特性：
- 能够响应中断，当获取到锁的线程被中断时，中断异常会被抛出，锁被释放
- 超时获取锁，在指定的截止时间之前获取锁，如果截止时间到了仍旧无法获取锁，则返回。
Lock的API：
- V lock() 调用该方法的线程获取锁，成功获取后返回
- V lockInterruptibly() throws IE 可中断地获取锁，阻塞的过程中可以被中断。
- boolean tryLock() 尝试非阻塞地获取锁，调用该方法后立刻返回，如果获取成功则为true，失败为false
- boolean tryLock(long time, TimeUnit unit) thows IE 返回的情况：
- 当前线程在超时时间内获得了锁
- 超时时间内被中断
- 超时时间结束，返回false
- V unlock() 释放锁
- Condition newCondition() 获取一个条件，并与当前锁绑定。当前线程只有获得了锁才能调用wait()方法。
队列同步器
AbstractQueuedSynchronizer(同步器)，是用来构建锁或其它同步组件的基础框架。要想了解锁的知识，必须要了解AQS。
锁的内部中聚合了同步器，同步器实现了锁的功能。
锁面向使用者，隐藏了实现细节
同步器面向实现者，简化了锁的实现方式，屏蔽了同步状态管理、线程唤醒等等底层操作
为什么锁的核心是同步器？
不用细看这段代码，看一看结构就行了。
public class Mutex implements Lock {
private static class Sync extends AbstractQueuedSynchronizer {
protected boolean isHeldExclusively() { return getState() == 1; }
public boolean tryAcquire(int acquires) {
if (compareAndSetState(0, 1)) {
setExclusiveOwnerThread(Thread.currentThread());
return true;
}
return false;
}
protected boolean tryRelease(int releases) {
if (getState() == 0)
throw new IllegalMonitorStateException();
setExclusiveOwnerThread(null); setState(0);
return true; }
Condition newCondition() { return new ConditionObject(); } }
private final Sync sync = new Sync();
public void lock() { sync.acquire(1); }
public boolean tryLock() { return sync.tryAcquire(1); }
public void unlock() { sync.release(1); }
public Condition newCondition() { return sync.newCondition(); }
public boolean isLocked() { return sync.isHeldExclusively(); }
public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
public void lockInterruptibly() throws InterruptedException { sync.acquireInterruptibly(1); }
public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException { return sync.tryAcquireNanos(1, unit.toNanos(timeout)); }
}
从这段代码中可以看出，Mutex内部锁的功能，基本上都是由Sync类实现的，而Sync类又继承于AQS。
State同步状态
AQS定义了三种方法以访问state，并且无法被重写:
getState()
setState()
compareAndSetState()
以ReentrantLock为例：
如果state为0，代表锁未被线程持有；
如果state>=1，代表已经被持有，争取锁时，如果占有锁的就是当前线程，则state+1，否则被阻塞，直到持有锁的线程释放锁。
独占与共享
AQS定义了两种资源共享方式：独占式获取与释放，即同一时间只能有一个线程获取锁（如：ReentrantLock）、共享式获取与释放（如：CountDownLatch）
其中最核心且需要被重写的（实现者需要关心的部分）是以下四个方法：
以try开头的方法的基本原则是：如果能做就做，不能做就返回，不会阻塞等待
boolean tryAcquire(int)
boolean tryRelease(int)
int tryAcquireShared(int) //负数失败；0成功但没有剩余可用资源；正数表示成功，且有剩余资源
boolean tryReleaseShared(int) //尝试释放资源，如果释放后允许唤醒后续等待结点返回true，否则返回false。
需要注意的是，一般来说，一种锁只需要实现独占或者共享的其中一种，所以前两者和后两者只需选择其中一对来进行实现。
同步队列
同步器依赖内部的同步队列（FIFO双向队列）来管理同步状态，如果当前线程获取同步状态失败，同步器会把当前线程及等待状态等信息构造为一个节点，并加入同步队列，同时阻塞当前线程；同步状态释放时，会把首节点中的线程唤醒，使其再次尝试获取同步状态。（这一段基本上就是acquire，release的整体流程）
其中节点Node是一个重要的概念，它包含以下属性:
waitStatus int
- CACELLED，值为1，表示该节点已经不需要再获取锁了（timeout，或被中断，前提是能响应中断）。进入此状态后，节点状态不会再变化。
- SIGNAL，值为-1，表示此节点的后继节点处于等待状态，如果当前节点释放或被取消，则会通知后继节点。
- CONDITION，值为-2，节点在等待队列中，表示节点等待在Condition上，当其他线程对此Condition调用了signal方法，该节点将会从等待队列转移到同步队列中。
- PROPAGAT，值为-3，表示下一次共享式同步状态将会无条件传播
- INITIAL，值为0，初始默认状态
prev Node
前驱节点，当节点加入同步队列时，会放到尾部，并设置prev为前一个节点
next Node
后继节点
thread Thread
被包装的线程
独占式
独占式获取
通过调用acquire(int arg)方法，可以实现：获取资源，成功则返回；否则进入同步队列。
注意：此方法对中断是不敏感的，即一旦进入同步队列中，后续中断时，线程不会从同步队列中移出
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
别看仅有这一小段代码，但基本就是独占模式下，线程获取锁的全部逻辑了。
简单解释一下其中的逻辑：
tryAcquire
这个方法是需要被重写的，尝试去获取锁，如果成功则返回true，失败返回false。具体逻辑可以等到后面锁的实现再叙述。
addWaiter(Node mode)
如果tryAcquire没有成功获取到锁则先进入此方法
这个方法将当前线程和传进来的mode作为参数，包装成一个节点，我们称其为当前节点。
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;
if (pred != null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
如果当前队列中，有尾部节点的话，则直接将此节点附在尾部节点的后面，并通过compareAndSetTail重新设置尾部节点。
注意，此处的CAS操作是必要的，如果有多个线程并发获取锁失败，并试图加入同步队列的尾部，没有同步保护很容易出现错误。由于CAS是原子操作，一旦有一个线程设置成功（返回node），其它线程都会察觉到进而退出竞争。此时就直接进入enq()方法。
总结功能：将当前线程打包为node，并设为tail
enq
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) {
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
如果tail为null，说明此时没有任何节点，故新创建一个node，设置为头节点，并且tail，head都指向这个节点
否则，使这个节点依附在上一个节点的后面，和addWaiter不同的是，此方法使用死循环，保证能成功加入。
总结功能：将当前节点设为tail，不成功不返回
aquiredQueue
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null;
failed = false;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
如果发现当前节点的前驱就是头节点，说明已经可以尝试去获取锁了，为什么？
第一：头节点就是获取到锁的节点，头节点线程释放同步状态后，将会唤醒后继节点。也就是说，释放状态时并不代表头节点被移除了，而仅是发出一个唤醒的信号，释放头节点是交给下一个要获取锁的线程执行的。这也说明，只要前面的节点是头节点，就表示可以尝试去获取锁了(tryAcquire)，但最终是否能获取到锁却是不一定的，因为头节点表示的线程可能还持有锁呢。
第二：维护FIFO的原则，只有前驱是头节点才能尝试获取。
如果尝试成功，则当前节点成为新头节点，原头节点被释放，由于没有其它引用，它会被垃圾回收器回收，返回。
如果尝试失败，则先判断是否可以停下，即shouldParkAfterFailedAcquire()
总结功能：尝试获取锁，不成功则停下
shouldParkAfterFailedAcquire
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
从方法名就可以看出来，这个方法就是用来判断：当获取失败时，是否需要停下来。
获取前驱节点的waitStatus，注意：此时的pred我们称为前驱节点，node是当前节点
- 如果为SIGNAL，说明前驱节点已经被通知过了，回顾一下之前我们对SIGNAL的定义就知道了，此时，我们直接返回true，说明可以park，只需要等到前驱节点被release后唤醒当前节点就行了，
- ws大于0只有一种情况，即CANCELLED。此时我们需要从node处一直向前取前驱，并重新赋值，直到前驱的ws<=0。此时，node前面的ws为1的节点虽然还有next指针指向node，但没有next指针指向它，故也会被回收。
- 如果处于其它状态，那就尝试去通知前驱，告诉它有个线程正在等着你释放。
后两者都返回false，说明前驱还没有做好准备。
总结功能：查看前驱的状态，如果已经被通知了则可以停下，否则通知一个可用的前驱，且需要再去尝试一下能否获取锁。
独占式释放
讲清楚了获取，释放就非常简单了。
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h);
return true;
}
return false;
}
tryRelease依旧是留给实现者，但需要注意的是，返回值如果为true，才能代表这个锁已经free了，所以如果有重入的情况，还不能进行后续操作。
获取到头节点，并唤醒后继节点，此时后继节点继续aquiredQueued循环–>检查前驱是否为头节点–>尝试获取–>成功返回，失败继续park。
unparkSuccessor
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
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);
}
重点在后半段代码，虽然要唤醒的是后继节点，可要是后继节点为null或已经CANCEL了呢？
那就从tail开始，一直往前找，直到找到最后一个合法的节点状态（即<=0），然后把这个节点唤醒。
注意：此处不像前面那样将CANCELLED节点移出了，因为移除是交给aquire的一系列方法
总结
- 为什么说不会响应中断呢？明明
LockSupport.park()是可以响应interrupt的？
LS一旦遇到interrupt()就会跳出等待状态，这是肯定的，原理详见interrupt()中断对LockSupport.park()的影响。
但不像sleep方法，LS并非以抛出异常的形式跳出，而是正常从方法返回。 private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
从这个地方可以看出，返回的是中断状态（注意，这个静态方法会使得中断状态变为false）
所以，发出interrupt信号可以使得Node短暂被唤醒，但注意aquiredQueue原方法是一个死循环，被中断的线程发现自己还处于队列的后面，于是又挂起了。 - 那为什么要专门设置一个interrupted变量？
还是从acquiredQueue方法来看，如果中途被中断过，就会将interrupted变量设为true，返回后，调用selfInterrupt()方法，设置中断状态为true。为什么返回的时候要再设置一次？因为前面的parkAndCheckInterrupt方法已经将标记清除了。
为什么要清除这个标记？如果不清除，那么之后使用LockSupport.park方法就中断不了了，原理详见interrupt()中断对LockSupport.park()的影响。 - finally后的cancelAcquire是什么意思？
如果遭遇异常，或者timeout等等，就会取消掉这个节点在同步队列的等待，这里就不细讲了，感兴趣的同学可以去看看 - 需要注意的是，当一个锁第一次被线程获取时，一般不会创建属于这个线程的节点。注意aquire方法先调用的是tryAcquire，一旦获取成功，就不需要再创建节点了，这也是为什么当第二个节点加入时，需要新创建一个节点以充当头节点的原因。
- 最后要说明的是：AQS的实现是遵循的公平锁原则，因为遵守的是FIFO的原则
模拟
假如按时间先后顺序有三个线程A, B, C争抢一个锁：
-
A首先抢到了锁，tryAcquire()返回true直接退出acquire()方法 -
B加入同步队列，由于tail，head都为null，故创建了一个空节点作为头节点，并指代A，然后将B作为尾结点；
加入以后，由于前驱是头节点，故尝试获取，但A还占有着锁，获取失败；将前驱状态改为SIGNAL后，再次尝试失败，陷入park状态等待。 -
C加入同步队列，前驱是B，直接放在B的后面作为尾结点；将前驱状态改为SIGNAL，再循环一次后，陷入等待状态。 -
A释放锁，调用unparkSuccessor()把后继节点唤醒 -
B被唤醒，尝试获取锁成功，把自己设置为头节点（A节点被抛弃），完成事务逻辑后，释放锁 -
C被唤醒，同B。
特殊情况
1. 如果B 进入enq方法还没有创建头节点时，A就已经释放了会怎样？
在A的release中，由于h为null，方法直接返回true；B创建头节点后，尝试获取锁成功，这个头节点就直接被抛弃，没有效果。
2. 会不会有线程同时获取锁成功的情况？
不会，注意：虽然这些方法看起来没有使用任何同步手段，但每个关键节点都使用了CAS操作，这样保证了：仅有一个线程获取到锁；入队一定会有先后顺序；设置头节点、尾结点一定不会被其它线程覆盖等等。
3. 最后一个线程释放锁后，队列中好像还存在一个节点啊？
确实是这样，但并没有什么影响。下一个线程可以直接获取锁，再下一个线程会将这个头节点当做是占有锁的线程。很妙的是，release方法中，并非取到的是当前线程所在的节点（因为当前线程可能没有节点），而是头节点，这样就保证了操作的正确性。
共享式
共享与独占的主要区别在于同一时刻能否有多个线程同时获取到同步状态。
共享式访问资源时，其它共享式访问均被允许（资源足够的情况下），独占式被阻塞
独占式访问资源时，所有其它访问都被阻塞
共享式获取
public final void acquireShared(int arg) {
if(tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}
tryAcquireShared
同样是需要自己去实现的功能，但必须遵守约定的规则，即返回值满足：负数失败；0成功但没有剩余可用资源；正数表示成功，且有剩余资源。
如果成功了，那就不用再进行下一步了。
doAcquireShared
private void doAcquireShared(int arg) {
finalNode node = addWaiter(Node.SHARED);
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head) {
int r = tryAcquireShared(arg);
if (r >= 0) {
setHeadAndPropagate(node, r);
p.next = null;
if (interrupted)
selfInterrupt();
failed = false;
return;
}
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
这个方法其实大致与acquireQueue差不多，抛开重复的不符，就只有一段代码是这个方法独有的：
if (r >= 0) {
setHeadAndPropagate(node, r);
}
这个方法也很简单，就是将当前节点设置为头节点，并尝试释放下一个节点
setHeadAndPropagate
private void setHeadAndPropagate(Node node, int propagate) {
Node h = head;
setHead(node);
if (propagate > 0 || h == null || h.waitStatus < 0 ||
(h = head) == null || h.waitStatus < 0) {
Node s = node.next;
if (s == null || s.isShared())
doReleaseShared();
}
}
将当前节点设为头节点，并尝试释放资源。
doReleaseShared
private void doReleaseShared() {
for (;;) {
Node h = head;
if (h != null && h != tail) {
int ws = h.waitStatus;
if (ws == Node.SIGNAL) {
if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
continue;
unparkSuccessor(h);
}
else if (ws == 0 &&
!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
continue;
}
if (h == head)
break;
}
}
如果头节点的ws为SIGNAL，说明后面有节点在等着呢，此时就唤醒后继节点，并重置ws为0。注意，当前线程并没有失去锁。
如果头节点ws为0，则将其改变为传播ws。
此时，被唤醒的线程也去尝试获取资源，因为前驱节点一定是头节点，由setHeadAndPropagate保证，这样就会一直循环向后去唤醒。
什么情况下，h会不等于head？
纵观全局，只有setHeadAndPropagate会调用setHead方法，也就是说，有可能下一个线程已经被设置为head了，此时，循环可以加速对后续线程的释放。
这样会不会导致在没有资源的情况下，线程获取到锁？
注意，只有在成功获取到资源以后，才会发生setHead。
共享式释放
public final boolean releaseShared(int arg) {
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}
释放资源成功后，唤醒后继
总结
我们会发现，共享式与独占式的主要区别在于：
独占式，线程一旦占有锁，就返回了；失败就加入同步队列，它与后面节点是没有关联的。
共享式，线程一旦占有锁，还要去通知后面的节点，直到没有资源为止。
结语
本来想一次性把锁讲完的，结果AQS就占了很大的篇幅。所以把ReentrantLock等锁放到下一篇来讲。
|