java并发编程的艺术——第五章总结（Lock锁与队列同步器）
Lock锁
锁是用来控制多个线程访问共享资源的方式。
一般来说一个锁可以防止多个线程同时访问共享资源（但有些锁可以允许多个线程访问共享资源，如读写锁）。
在Lock接口出现前，java使用synchronized关键字实现锁的功能，但是在javaSE5之后，并发包中提供了Lock接口（以及其实现类）用来实现锁的功能。
Lock提供了与synchronized相似的功能，但必须显示的获取锁与释放锁，虽然不及隐式操作方便，但是拥有了锁获取与释放的可操作性、可中断的锁获取与超时获取锁等多重功能。
提供场景：先获取锁A，在获取锁B，当获取锁B后，释放锁A的同时获取锁C，当获取锁C后，释放锁B的同时获取锁D，以此类推，可以通过Lock实现。
Lock的使用：
注：在finally中释放锁，目的保证获取锁之后能够最终释放锁。
不要把获取锁的过程写在try中，因为这样出现异常时，锁将会因为异常的抛出而被释放掉。
队列同步器
队列同步器AbstractQueuedSynchronizer（以下简称同步器），是构建锁或者其他同步组件的基本框架。
使用了一个int成员变量表示同步状态，通过内置的FIFO队列来完成资源的获取线程的排队工作。
同步器的主要使用方法是继承，子类通过继承同步器并实现它的抽象方法来管理同步状态。
在抽象方法的实现过程中对同步状态进行更改，需要使用到同步器提供的三个方法：getState()、setState(int newState)和compareAndSetState(int expect,int update)来进行操作，这三个方法可以保证状态的改变是安全的。
子类被推荐定义为自定义同步组件的静态内部类，同步器自身没有实现任何同步接口，它仅仅是定义了若干同步状态获取和释放方法来供自定义同步组件使用，同步器即可以支持独占式获取同步状态，也可以支持共享式地获取同步状态，这样方便实现不同类型的同步组件（ReentrantLock、ReentrantReadWriteLock、CountDownLatch等）。
同步器是实现锁（也可以是任何同步组件）的关键：在锁中聚合同步器，利用同步器实现锁的语义。
两者的关系：锁是面向使用者的，他定义了使用者与锁交互的接口（比如允许两个线程并行访问），隐藏了实现细节；
同步器是面向锁的实现者，它简化了锁的实现方式，屏蔽了同步管理状态、线程的排队、等待与唤醒等底层操作。
锁让使用者仅仅是调用其方法既可以实现同步效果、同步器让实现者通过重写抽象方法进行了队列的底层操作。他们两个是使用者和实现者关注不同的领域实现了相同的效果。
队列同步器的接口与示例
同步器基于模板设计模式实现的，使用者需要继承同步器并重写指定的方法，随后将同步器组合在自定义的同步组件的实现中，并调用同步器提供的模板方法，而这些模板方法会调用使用者重写的方法。
注：实现同步组件是要依赖于同步器，而实现同步器需要重写一些方法，然后同步组件调用同步器中的模板方法实现同步效果，而这些模板方法又调用我们重写的方法来实现功能。
同步器的原理可以使我们只关注于自己需要实现的方法而不需要关注其他的地方
（实际上你想要对流程有一个清晰的认识还是要把所有的都熟悉的，但是在实现同步器时，可以把主要的精力都放在同步器重写方法上，而不是别的地方）
重写同步器指定方法时需要使用同步器提供的如下三个方法来访问或修改同步状态：
getState（）：获取当前同步状态
setState（int new State）：设置当前同步状态
compareAndState（int expect，int update）：使用CAS设置当前状态，该方法能够保证状态设置的原子性。
同步器可重写的方法：
实现自定义同步组件时，将会调用同步器提供的模板方法，这些模板方法与描述：
注：模板方法基本分为三类：独占式同步状态获取与释放、共享式同步状态获取与释放和查询同步队列中等待线程情况。
以独占锁的示例来深入了解一下同步器的工作原理（以便能够更加深入的理解其他同步组件）。
独占锁：同一时刻只有一个线程能够获取锁，而其他获取锁的线程只能处于同步队列中等待，只有获取锁的线程释放了锁，后续的线程才能够获取锁。
public class Metux implements Lock {
//静态内部类，自定义同步器
private static class Sync extends AbstractQueuedSynchronizer{
//是否处于占用状态
@Override
protected boolean isHeldExclusively() {
return getState() == 1;
}
//当状态为0的时候获取锁
@Override
protected boolean tryAcquire(int arg) {
if (compareAndSetState(0,1)) {
setExclusiveOwnerThread(Thread.currentThread());
return true;
}
return false;
}
//释放锁，将状态设置为0
@Override
protected boolean tryRelease(int arg) {
if (getState() == 0) throw new
IllegalMonitorStateException();
setExclusiveOwnerThread(null);
setState(0);
return true;
}
//返回一个condition，每个condition都包含了一个condition队列
Condition newCondition() {
return new ConditionObject();
}
}
//仅需要将操作代理到Sync上即可
private final Sync sync = new Sync();
@Override
public void lock() {
sync.tryAcquire(1);
}
@Override
public boolean tryLock() {
return sync.tryAcquire(1);
}
@Override
public void unlock() {
sync.tryRelease(1);
}
@Override
public Condition newCondition() {
return sync.newCondition();
}
public boolean isLocked() {
return sync.isHeldExclusively();
}
public boolean hasQueuedThreads() {
return sync.hasQueuedThreads();
}
@Override
public void lockInterruptibly() throws InterruptedException {
sync.acquireInterruptibly(1);
}
@Override
public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
return sync.tryAcquireNanos(1,unit.toNanos(time));
}
}独占锁Mutex是一个自定义同步组件，它在同一时刻只允许一条线程占有锁。
Mutex定义了一个静态内部类，该内部类继承了同步器并实现了独占式获取和释放同步状态。
在tryAcquire(int acquire)方法中，如果经过CAS设置成功（同步状态设置为1），则代表获取了同步状态，
而在tryRelease(int release)方法中只是将同步状态重置为0。
用户使用Mutex时，并不会直接和内部同步器实现打交道。而是调用Mutex提供的方法，在Mutex的实现中，以获取锁的lock()犯法为例：只需要在方法实现中调用同步器的模板方法acquire(int args)即可。
当前线程调用该方法获取同步状态失败后会被加入到同步队列中等待，这样就大大降低了实现一个可靠自定义组件的门槛。
队列同步器的实现分析
同步器完成线程同步的方式：同步队列、独占式同步状态获取与释放、共享式同步状态获取与释放以及超时获取同步状态等同步器的核心数据结构和模板方法。
1.同步队列
原理：同步器依赖于内部的同步队列（一个FIFO双向队列）来完成同步状态的管理，当前线程获取同步状态失败时，同步器会将当前线程以及等待状态等信息构成一个节点（Node）并将其加入同步队列，同时阻塞当前线程，当同步状态释放时，会将首节点中的线程唤醒，使其再次尝试获取同步状态。
FIFO：first in first output，先入先出。
节点（Node）：用来保存获取同步状态失败的线程引用、等待状态以及前驱和后继节点信息。
节点是构成同步队列的基础，同步器拥有首节点（head）和尾节点（tail），没有成功获取同步状态的线程将会称为节点加入队列的尾部。
同步队列的结构：
注：同步器包含两个节点类型的引用，一个指向头节点，一个指向尾节点。
线程加入队列的过程必须保证线程安全，同步器提供了一个基于CAS的设置尾节点的方法：compareAndSetTail（Node expect，Node update），保证线程安全。
为什么必须保证线程安全：同时有多条线程没有获取同步状态要加入同步队列，这时如果不是线程安全的，请问谁先谁后呢？所以在此处的这个操作必须是线程安全的
它需要传递当前线程“认为”的尾节点和当前节点，只有设置成功后，当前节点才正式与之前的尾节点建立关联。
同步器将节点加入同步队列的过程：
注：同步队列遵循FIFO，首节点是获取同步状态成功的节点，首节点的线程在释放同步状态时，将会唤醒后继节点，而后继节点将会在获取同步状态成功时将自己设置为首节点：
在5-3的过程中，设置首节点是通过获取同步状态成功的线程完成的，由于只有一个线程能够获取到同步状态，因此设置头节点的方法并不需要CAS来保障，它只需要将首节点设置成为原首节点的后继节点并断开原首节点的next引用即可。
2.独占式同步状态获取与释放
通过同步器的acquire(int arg)方法可以获取同步状态，该方法对中断不敏感，也就是说由于线程获取同步状态失败后进入同步队列中，后继对线程进行中断操作时，线程不会从同步队列移除。acquire方法：
上述代码中完成了同步状态的获取、节点构造、加入同步队列以及同步队列中自旋等待的相关工作。
主要逻辑：
首先调用自定义同步器实现的tryAcquire(int arg)方法，该方法保证线程安全的获取同步状态，如果同步状态获取失败，则构造同步节点（独占式Node.EXCLUSIVE，同一时刻只能有一个线程成功获取同步状态）并通过addWaiter(Node node)方法将该节点加入到同步队列的尾部，最后调用acquireQueued(Node node,int arg)方法，使得该节点以“死循环”的方式获取同步状态。如果获取不到阻塞节点中的线程，而被阻塞线程的唤醒主要依靠前驱节点的出队或阻塞线程被中断来实现。
节点的构造以及加入同步队列依靠于addWaiter和enq方法：
addwaiter:
enq:
注：上述代码通过compareAndSetTail(Node expect, Node update)方法来确保节点能够被线程安全添加。
在enq(final Node node)中，同步器通过死循环的方式来确保节点的添加，在死循环中只有通过CAS将当前节点设置为尾节点之后，当前线程才能从该方法返回，否则的话当前线程不断地尝试设置。
可以看出，enq(final Node node)方法将并发添加节点的请求通过CAS变得“串行化”了。（个人认为这里指的是将节点通过入队的方式，暂时保存了它的一系列状态。）
节点进入队列后，就进入了一个自旋状态，每个节点（或者说每个线程），都在自省观察，当条件满足，获取到同步状态，就可以从这个自旋过程中退出，否则依旧留在自旋过程中（见代码）：
注：在acquireQueued(final Node node, int arg)方法中，当前线程在“死循环”中尝试获取同步状态，而只有前驱节点是头节点才能够尝试获取同步状态，原因如下：
1）头节点是成功获取到同步状态的节点，而头节点线程获取到同步状态后，将会唤醒其后继节点，后继节点的线程被唤醒后需要检查自己的前驱节点是否是头节点。
2）维护同步队列的FIFO原则，该方法中节点自旋获取同步状态的行为如下图：
注：由于非首节点线程前驱节点出队或被中断而从等待状态返回，随后检查自己的前驱是否是头节点，如果是则尝试获取同步状态。
可以看到节点与及节点之间在循环检查的过程中基本上不相互通信，而是简单地判断自己的前驱是否为头节点，这样就使得节点的释放符合FIFO，并且对于方便对过早通知进行处理（过早通知指的是前驱节点不是头节点的线程由于中断被唤醒）。
独占式同步状态获取流程，也就是acquire(int arg)方法调用流程：
注：在上图中前驱节点为头节点且能够获取同步状态与线程进入等待状态是获取同步状态的自旋过程（acquireQueued方法的死循环），当同步状态获取成功，当前线程从acquire(int arg)方法返回，这也就代表着当前线程获得了锁。
当前线程获取同步状态完成相应逻辑后，需要释放同步状态，通过调用同步器的release(int arg)方法可以释放同步状态，该方法在释放了同步状态后，会唤醒其后继节点（进而使后继节点重新尝试获取同步状态）。代码如下：
该方法执行时，会唤醒头节点的后继节点线程，unparkSuccerssor(Node node)方法使用LcokSupport（后面讲）来唤醒处理等待状态的线程。
独占式同步状态获取和释放：
在获取同步状态时，同步器会维持一个同步队列，获取失败的线程都会被加入到同步队列中，并在同步队列中自旋（判断自己前驱节点为头节点）。
移出队列（停止自旋）的条件是前驱节点为头节点且成功获取了同步状态。在释放同步状态时，同步器调用tryRelease(int arg)方法释放同步状态，然后唤醒头节点的后继节点。
3.共享式同步状态获取与释放
共享式获取与独占式获取最主要的区别在于同一时刻能否有多个线程同时获取到同步状态。
以读写为例：
如果一个程序对文件进行读操作时，那么这一时刻对于该文件的写操作均被堵塞，而读操作能够同时访问。
写操作要求对资源的独占，而读操作是可以共享式的访问。
注：从图可以看到，共享是可以在同一时刻所有共享线程对资源进行访问的，而独占的话是在同一时刻只有一个线程能够访问。
通过调用同步器的acquireShared(int arg)方法可以共享式地获取同步状态：
注：在acquireShared(int arg)方法中，同步器调用tryAcquireShared(int arg)方法尝试获取同步状态，tryAcquireShared(int arg)方法返回值为int型，当返回值大于等于0时，表示能够获取到同步状态。
在共享式获取自选状态过程中，成功获取到同步状态并退出自旋的条件就是tryAcquireShared(int arg)方法的返回值大于等于0。
可以看到在doAcquireShared(int arg)方法的自旋过程中，如果当前节点的前驱为头节点时，尝试获取同步状态，如果返回值大于等于0，表示该次获取同步状态成功，并从自旋过程中退出。
与独占式相同，共享式获取也需要释放同步状态，通过调用releaseShared(int arg)方法可以释放同步状态：
注：该方法释放同步状态之后，将会唤醒后续处于等待状态的节点。对于能够支持多个线程同时访问的并发组件，它和独占式主要区别在于tryReleaseShared(int arg)方法必须确保同步状态（或者资源数）线程安全释放，一般都是通过CAS和循环来保证的，因为释放同步状态的操作会同时来自多个线程。
4.独占式超时获取同步状态
通过调用同步器的tryAcquireNanos(int arg,long nanosTimeout)方法可以超时获取同步状态，即在指定的时间内获取同步状态，如果获取到同步状态则返回true，否则，返回false。
在java5之后，同步器提供了acquireInterruptibly(int arg)方法，这个方法在等待获取同步状态时，如果当前线程被中断，会立刻返回，并抛出InterruptException异常。（1.5之前并不会）。
超时获取同步状态的过程可以被视作响应中断获取同步状态过程的“增强版”。
doAcquireNanos(int arg,long nanosTimeout)方法在支持响应中断的基础上，增加了超时获取的特性。
为了针对超时获取，主要需要计算出需要睡眠的时间间隔nanosTimeout，为了防止过早通知，nanosTimeout计算公式为：nanosTimeout=now-lastTime，其中now为当前唤醒时间，lastTime为上次唤醒时间，如果nanosTimeout大于0表示超时时间未到，需要继续睡眠nanosTimeout纳秒，反之，表示已经超时。
注：该方法在自旋过程中，当节点的前驱节点为头节点时尝试获取同步状态，如果获取成功则从该方法返回，这个过程和独占式同步获取的过程类似，但是在同步状态获取失败的处理上不同。
如果当前线程获取同步状态失败，则判断是否超时（nanosTimeout小于0表示超时），如果没有超时，重新计算超时间隔nanosTimeout，然后使线程等待nanosTimeout纳秒（当已到设置的超时时间，该线程会从LockSupport.parkNanos(Object blocker, long nanos)方法返回）。
如果nanosTimeout小于等于spinForTimeoutThreshold(1000纳秒)时，将不会使该线程进行超时等待，而是进入快速的自旋过程。原因：非常短的超时等待无法做到十分精确，如果这时再进行超时等待，相反会让nanosTimeout的超时从整体上表现的不精确。
因此在超时非常短的场景下，同步器会进入无条件的快速自旋。
独占式超时获取同步状态doAcquireNanos(int arg, long nanosTimeout)与独占式获取同步状态acquire(int args)的主要区别：
未获取到同步状态的逻辑。
acquire(int args)在未获取到同步状态时，将会使当前线程一直处于等待状态，
doAcquireNanos(int arg, long nanosTimeout)会使当前线程等待nanosTimeout纳秒，如果当前线程在nanosTimeout纳秒内没有获取到同步状态，将会从等待逻辑中自动返回。
5.自定义同步组件——TwinsLock
通过自定义自己的同步组件提高对同步器的理解。
同步组件功能：该组件同一时刻最多只允许两个线程访问，超过两个线程的访问将被阻塞，我们将这个同步工具命名为TwinsLock。
1）确定访问模式：
TwinsLock能够在同一时刻支持多个线程的访问，这是共享式访问。
同步器应该提供acquireShared(int args)方法与Shared相关的方法。
这就要求TwinsLock必须重写tryAcquireShared(int args)方法和tryReleaseShared(int args)方法，这样才能保证同步器的共享式同步状态的获取与释放方法的执行。
2）定义资源数：
TwinsLock在同一时刻允许至多两个线程的同时访问，同步资源数为2。设置初始状态status为2，当一个线程进行获取时，status减1，该线程释放，则status加1，状态的合法范围0、1、2。
其中0代表两个线程已经获取了同步资源，此时再有其他线程对同步状态进行获取，该线程只能被阻塞。在同步状态变更时，需要使用compareAndSet（int expect， int update）方法做原子性保障
3）定义同步器：
自定义同步组件通过组合自定义同步器来完成同步功能，一般情况下自定义同步器会被定义为自定义同步组件的内部类。
public class TwinsLock implements Lock {
private final Sync sync = new Sync(2);
private static final class Sync extends AbstractQueuedSynchronizer {
Sync(int count) {
if(count < 0) {
throw new IllegalArgumentException("count must large than zero");
}
setState(count);
}
@Override
public int tryAcquireShared(int reducecount) {
for (;;) {
int current = getState();
int newCount = current - reducecount;
if (newCount < 0 || compareAndSetState(current,newCount)) {
return newCount;
}
}
}
@Override
protected boolean tryReleaseShared(int returnCount) {
for(;;) {
int current = getState();
int newCount = current + returnCount;
if (compareAndSetState(current,newCount)) {
return true;
}
}
}
}
@Override
public void lock() {
sync.acquireShared(1);
}
@Override
public void unlock() {
sync.releaseShared(1);
}
//其他接口略
}注：在上例中TwinsLock实现了Lock接口，提供了面向使用者的接口，使用者调用lock()方法获取锁，使用unlock()释放锁，而且同一时刻只能有两个线程获取到锁。
TwinsLock同时还包含了一个自定义同步器sync，而该同步器面向线程访问和同步状态控制。
以共享式获取同步状态为例：同步器会先计算出获取后的同步状态，然后通过CAS确保状态的正确设置，当tryAcquireShared(int reduceCount)方法返回值大于等于0时，当前线程才能获取同步状态，对于上层的TwinsLock而言，则表示当前线程获取锁。
同步器作为一个桥梁，连接了线程访问以及同步状态控制等底层技术与不同并发组件（Lock、CountDownLatch等）的接口语义。