JUC学习笔记（三）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

八、共享模型之工具–JUC

8.1 AQS 原理

1. 概述

即AbstractQueuedSynchronizer（抽象类），是阻塞式锁和相关的同步器工具的框架

特点：

• 用 state 属性来表示资源的状态（分独占模式和共享模式），子类需要定义如何维护这个状态，控制如何获取 锁和释放锁
  • getState - 获取 state 状态
  • setState - 设置 state 状态
  • compareAndSetState - cas 机制设置 state 状态
  • 独占模式是只有一个线程能够访问资源，而共享模式可以允许多个线程访问资源
• 提供了基于 FIFO（先入先出） 的等待队列，类似于 Monitor 的 EntryList
• 条件变量来实现等待、唤醒机制，支持多个条件变量，类似于 Monitor 的 WaitSet

子类主要实现的方法（默认抛出 UnsupportedOperationException）

• tryAcquire
• tryRelease
• tryAcquireShared
• tryReleaseShared
• isHeldExclusivel

2 实现不可重入锁

自定义同步器

final class MySync extends AbstractQueuedSynchronizer {@Overrideprotected boolean tryAcquire(int acquires) {if (acquires == 1) {if (compareAndSetState(0, 1)) {// 设置当前线程为锁持有者setExclusiveOwnerThread(Thread.currentThread());return true;}}return false;}@Overrideprotected boolean tryRelease(int acquires) {if (acquires == 1) {if (getState() == 0) {throw new IllegalMonitorStateException();}// 释放锁setExclusiveOwnerThread(null);setState(0);return true;}return false;}protected Condition newCondition() {return new ConditionObject();}@Overrideprotected boolean isHeldExclusively() {return getState() == 1;}
}

自定义锁

有了自定义同步器，很容易复用 AQS ，实现一个功能完备的自定义锁

    class MyLock implements Lock {MySync sync = new MySync();@Override// 尝试，不成功，进入等待队列public void lock() {sync.acquire(1);}@Override// 尝试，不成功，进入等待队列，可打断public void lockInterruptibly() throws InterruptedException {sync.acquireInterruptibly(1);}@Override// 尝试一次，不成功返回，不进入队列public boolean tryLock() {return sync.tryAcquire(1);}@Override// 尝试，不成功，进入等待队列，有时限public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {return sync.tryAcquireNanos(1, unit.toNanos(time));}@Override// 释放锁public void unlock() {sync.release(1);}@Override// 生成条件变量public Condition newCondition() {return sync.newCondition();}}

测试

public static void main(String[] args) {MyLock lock = new MyLock();new Thread(() -> {lock.lock();try {log.debug("locking...");try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}} finally {log.debug("unlocking...");lock.unlock();}}, "t1").start();new Thread(() -> {lock.lock();try {log.debug("locking...");} finally {log.debug("unlocking...");lock.unlock();}}, "t2").start();}

输出

12:34:24.822 [t1] DEBUG com.zhou.aqs.MySync - locking...
12:34:25.831 [t1] DEBUG com.zhou.aqs.MySync - unlocking...
12:34:25.831 [t2] DEBUG com.zhou.aqs.MySync - locking...
12:34:25.831 [t2] DEBUG com.zhou.aqs.MySync - unlocking...

不可重入测试

如果改为下面代码，会发现自己也会被挡住（只会打印一次 locking）,因为第二次lock时候获取不到锁，当前线程加入阻塞队列阻塞，却没人唤醒

lock.lock();
log.debug("locking...");
lock.lock();
log.debug("locking...");

3.心得

起源

早期程序员会自己通过一种同步器去实现另一种相近的同步器，例如用可重入锁去实现信号量，或反之。这显然不 够优雅，于是在 JSR166（java 规范提案）中创建了 AQS，提供了这种通用的同步器机制。

目标

AQS 要实现的功能目标

• 阻塞版本获取锁 acquire 和非阻塞的版本尝试获取锁 tryAcquire
• 获取锁超时机制
• 通过打断取消机制
• 独占机制及共享机制
• 条件不满足时的等待机制

设计

获取锁的逻辑

while(state 状态不允许获取) {if(队列中还没有此线程) {入队并阻塞}
}
当前线程出队

释放锁的逻辑

if(state 状态允许了) {恢复阻塞的线程(s)
}

1) state 设计

• state 使用 volatile 配合 cas 保证其修改时的原子性 state
• 使用了 32bit int 来维护同步状态，因为当时使用 long 在很多平台下测试的结果并不理想

2）阻塞恢复设计

• 早期的控制线程暂停和恢复的 api 有 suspend 和 resume，但它们是不可用的，因为如果先调用的 resume 那么 suspend 将感知不到
• 解决方法是使用 park & unpark 来实现线程的暂停和恢复，先 unpark 再 park 也没 问题
• park & unpark 是针对线程的，而不是针对同步器的，因此控制粒度更为精细
• park 线程还可以通过 interrupt 打断

3）队列设计

• 使用了 FIFO 先入先出队列，并不支持优先级队列
• 设计时借鉴了 CLH 队列，它是一种单向无锁队列

队列中有 head 和 tail 两个指针节点，都用 volatile 修饰配合 cas 使用，每个节点有 state 维护节点状态

入队伪代码，只需要考虑 tail 赋值的原子性

do {// 原来的 tailNode prev = tail;// 用 cas 在原来 tail 的基础上改为 node
} while (tail.compareAndSet(prev, node))

出队伪代码

// prev 是上一个节点
while ((Node prev = node.prev).state != 唤醒状态) {}
// 设置头节点
head = node;

CLH 好处：

• 无锁，使用自旋
• 快速，无阻塞

AQS 在一些方面改进了 CLH

private Node enq(final Node node) {for (;;) {Node t = tail;// 队列中还没有元素 tail 为 nullif (t == null) {// 将 head 从 null -> dummyif (compareAndSetHead(new Node()))tail = head;} else {// 将 node 的 prev 设置为原来的 tailnode.prev = t;// 将 tail 从原来的 tail 设置为 nodeif (compareAndSetTail(t, node)) {// 原来 tail 的 next 设置为 nodet.next = node;return t;}}}
}

主要用到 AQS 的并发工具类

8.2 ReentrantLock 原理

1. 非公平锁实现原理

加锁流程

// 默认为非公平锁实现
public ReentrantLock() {sync = new NonfairSync();
}

NonfairSync 继承自 AQS

没有竞争时

第一个竞争出现时

Thread-1 执行了

1. CAS 尝试将 state 由 0 改为 1，结果失败
2. 进入 tryAcquire 逻辑，这时 state 已经是1，结果仍然失败
3. 接下来进入 addWaiter 逻辑，构造 Node 队列
   • 图中黄色三角表示该 Node 的 waitStatus 状态，其中 0 为默认正常状态
   • Node 的创建是懒惰的
   • 其中第一个 Node 称为 Dummy（哑元）或哨兵，用来占位，并不关联线程

当前线程进入 acquireQueued 逻辑

1. acquireQueued 会在一个死循环中不断尝试获得锁，失败后进入 park 阻塞
2. 如果自己是紧邻着 head（排第二位），那么再次 tryAcquire 尝试获取锁，当然这时 state 仍为 1，失败
3. 进入 shouldParkAfterFailedAcquire 逻辑，将前驱 node，即 head 的 waitStatus 改为 -1，这次返回 false

4. shouldParkAfterFailedAcquire 执行完毕回到 acquireQueued ，再次 tryAcquire 尝试获取锁，当然这时 state 仍为 1，失败
5. 当再次进入 shouldParkAfterFailedAcquire 时，这时因为其前驱 node 的 waitStatus 已经是 -1，这次返回 true
6. 进入 parkAndCheckInterrupt， Thread-1 park阻塞（灰色表示）

再次有多个线程经历上述过程竞争失败，变成这个样子

解锁流程

Thread-0 释放锁，进入 tryRelease 流程，如果成功

• 设置 exclusiveOwnerThread 为 null
• state = 0

当前队列不为 null，并且 head 的 waitStatus = -1，进入 unparkSuccessor 流程

找到队列中离 head 最近的一个 Node（没取消的），unpark 恢复其运行，本例中即为 Thread-1

回到 Thread-1 的 acquireQueued 流程

如果加锁成功（没有竞争），会设置

• exclusiveOwnerThread 为 Thread-1，state = 1
• head 指向刚刚 Thread-1 所在的 Node，该 Node 清空 Thread
• 原本的 head 因为从链表断开，而可被垃圾回收

如果这时候有其它线程来竞争（非公平的体现），例如这时有 Thread-4 来了

如果不巧又被 Thread-4 占了先

• Thread-4 被设置为 exclusiveOwnerThread，state = 1
• Thread-1 再次进入 acquireQueued 流程，获取锁失败，重新进入 park 阻塞

加锁源码

// Sync 继承自 AQS
static final class NonfairSync extends Sync {private static final long serialVersionUID = 7316153563782823691 L;// 加锁实现final void lock() {// 首先用 cas 尝试（仅尝试一次）将 state 从 0 改为 1, 如果成功表示获得了独占锁if (compareAndSetState(0, 1))setExclusiveOwnerThread(Thread.currentThread());else// 如果尝试失败，进入 ㈠acquire(1);}// ㈠ AQS 继承过来的方法, 方便阅读, 放在此处public final void acquire(int arg) {// ㈡ tryAcquireif (!tryAcquire(arg) &&// 当 tryAcquire 返回为 false 时, 先调用 addWaiter ㈣, 接着 acquireQueued ㈤acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {selfInterrupt();}}// ㈡ 进入 ㈢protected final boolean tryAcquire(int acquires) {return nonfairTryAcquire(acquires);}// ㈢ Sync 继承过来的方法, 方便阅读, 放在此处final boolean nonfairTryAcquire(int acquires) {final Thread current = Thread.currentThread();int c = getState();// 如果还没有获得锁if (c == 0) {// 尝试用 cas 获得, 这里体现了非公平性: 不去检查 AQS 队列if (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);return true;}}// 如果已经获得了锁, 线程还是当前线程, 表示发生了锁重入else if (current == getExclusiveOwnerThread()) {// state++int nextc = c + acquires;if (nextc < 0) // overflowthrow new Error("Maximum lock count exceeded");setState(nextc);return true;}// 获取失败, 回到调用处return false;}// ㈣ AQS 继承过来的方法, 方便阅读, 放在此处private Node addWaiter(Node mode) {// 将当前线程关联到一个 Node 对象上, 模式为独占模式Node node = new Node(Thread.currentThread(), mode);// 如果 tail 不为 null, cas 尝试将 Node 对象加入 AQS 队列尾部Node pred = tail;if (pred != null) {node.prev = pred;if (compareAndSetTail(pred, node)) {// 双向链表pred.next = node;return node;}}// 多线程情况下，上面替换可能失败，所以再次尝试将 Node 加入 AQS, 进入 ㈥enq(node);return node;}// ㈥ AQS 继承过来的方法, 方便阅读, 放在此处private Node enq(final Node node) {for (;;) {Node t = tail;if (t == null) {// 还没有, 设置 head 为哨兵节点（不对应线程，状态为 0）if (compareAndSetHead(new Node())) {tail = head;}} else {// cas 尝试将 Node 对象加入 AQS 队列尾部node.prev = t;if (compareAndSetTail(t, node)) {t.next = node;return t;}}}}// ㈤ AQS 继承过来的方法, 方便阅读, 放在此处final boolean acquireQueued(final Node node, int arg) {boolean failed = true;try {boolean interrupted = false;for (;;) {final Node p = node.predecessor();// 上一个节点是 head, 表示轮到自己（当前线程对应的 node）了, 尝试获取if (p == head && tryAcquire(arg)) {// 获取成功, 设置自己（当前线程对应的 node）为 headsetHead(node);// 上一个节点 help GCp.next = null;failed = false;// 返回中断标记 falsereturn interrupted;}if (// 获取锁失败，判断是否应当 park, 进入 ㈦shouldParkAfterFailedAcquire(p, node) &&// park 等待, 此时 Node 的状态被置为 Node.SIGNAL ㈧parkAndCheckInterrupt()) {interrupted = true;}}} finally {if (failed)cancelAcquire(node);}}// ㈦ AQS 继承过来的方法, 方便阅读, 放在此处private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {// 获取上一个节点的状态int ws = pred.waitStatus;if (ws == Node.SIGNAL) {// 上一个节点都在阻塞, 那么自己也阻塞好了return true;}// > 0 表示取消状态if (ws > 0) {// 上一个节点取消, 那么重构删除前面所有取消的节点, 返回到外层循环重试do {node.prev = pred = pred.prev;} while (pred.waitStatus > 0);pred.next = node;} else {// 这次还没有阻塞// 但下次如果重试不成功, 则需要阻塞，这时需要设置上一个节点状态为 Node.SIGNAL(值为-1)compareAndSetWaitStatus(pred, ws, Node.SIGNAL);}return false;}// ㈧ 阻塞当前线程private final boolean parkAndCheckInterrupt() {LockSupport.park(this);return Thread.interrupted();}
}

注意

• 是否需要 unpark 是由当前节点的前驱节点的 waitStatus == Node.SIGNAL 来决定，而不是本节点的 waitStatus 决定

解锁源码

// Sync 继承自 AQS
static final class NonfairSync extends Sync {// 解锁实现public void unlock() {sync.release(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final boolean release(int arg) {// 尝试释放锁, 进入 ㈠if (tryRelease(arg)) {// 队列头节点 unparkNode h = head;if (// 队列不为 nullh != null &&// waitStatus == Node.SIGNAL 才需要 unparkh.waitStatus != 0) {// unpark AQS 中等待的线程, 进入 ㈡unparkSuccessor(h);}return true;}return false;}// ㈠ Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryRelease(int releases) {// state--int c = getState() - releases;if (Thread.currentThread() != getExclusiveOwnerThread())throw new IllegalMonitorStateException();boolean free = false;// 支持锁重入, 只有 state 减为 0, 才释放成功if (c == 0) {free = true;setExclusiveOwnerThread(null);}// 否则state计数减去releasesetState(c);return free;}// ㈡ AQS 继承过来的方法, 方便阅读, 放在此处private void unparkSuccessor(Node node) {// 如果状态为 Node.SIGNAL 尝试重置状态为 0// 不成功也可以int ws = node.waitStatus;if (ws < 0) {// 防止多线程情况下，重复唤醒compareAndSetWaitStatus(node, ws, 0);}// 找到需要 unpark 的节点, 但本节点从 AQS 队列中脱离, 是由唤醒节点完成的Node s = node.next;// 不考虑已取消的节点, 从 AQS 队列从后至前找到队列最前面需要 unpark 的节点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);}
}

2. 可重入原理

static final class NonfairSync extends Sync {// ...// Sync 继承过来的方法, 方便阅读, 放在此处final boolean nonfairTryAcquire(int acquires) {final Thread current = Thread.currentThread();int c = getState();if (c == 0) {if (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);return true;}}// 如果已经获得了锁, 线程还是当前线程, 表示发生了锁重入else if (current == getExclusiveOwnerThread()) {// state++int nextc = c + acquires;if (nextc < 0) // overflowthrow new Error("Maximum lock count exceeded");setState(nextc);return true;}return false;}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryRelease(int releases) {// state--int c = getState() - releases;if (Thread.currentThread() != getExclusiveOwnerThread())throw new IllegalMonitorStateException();boolean free = false;// 支持锁重入, 只有 state 减为 0, 才释放成功if (c == 0) {free = true;setExclusiveOwnerThread(null);}setState(c);return free;}
}

3. 可打断原理

不可打断模式

在此模式下，即使它被打断，仍会驻留在 AQS 队列中阻塞等待获取锁，一直要等到获得锁后方能得知自己被打断了

// Sync 继承自 AQS
static final class NonfairSync extends Sync {// ...private final boolean parkAndCheckInterrupt() {// 如果打断标记已经是 true, 则 park 会失效，失效就会接着往下走LockSupport.park(this);// interrupted 会清除打断标记return Thread.interrupted();}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()) {// 如果是因为 interrupt 被唤醒, 返回打断状态为 trueinterrupted = true;}}} finally {if (failed)cancelAcquire(node);}}public final void acquire(int arg) {if (!tryAcquire(arg) &&acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {// 如果打断状态为 trueselfInterrupt();}}static void selfInterrupt() {// 重新产生一次中断，打上打断标记，调用者可以判断该线程是否被打断过Thread.currentThread().interrupt();}
}

可打断模式

通过抛出异常来进行中断处理，无需等待锁获取才告知中断

static final class NonfairSync extends Sync {public final void acquireInterruptibly(int arg) throws InterruptedException {if (Thread.interrupted())throw new InterruptedException();// 如果没有获得到锁, 进入 ㈠if (!tryAcquire(arg))doAcquireInterruptibly(arg);}// ㈠ 可打断的获取锁流程private void doAcquireInterruptibly(int arg) throws InterruptedException {final Node node = addWaiter(Node.EXCLUSIVE);boolean failed = true;try {for (;;) {final Node p = node.predecessor();if (p == head && tryAcquire(arg)) {setHead(node);p.next = null; // help GCfailed = false;return;}if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()) {// 在 park 过程中如果被 interrupt 会进入此// 这时候抛出异常, 而不会再次进入 for (;;)throw new InterruptedException();}}} finally {if (failed)cancelAcquire(node);}}
}

例如前面ReentrantLock的例子

当t调用t1.interrupt()时，t1线程唤醒，然后lockInterruptibly里面会抛出异常不会再次进入阻塞

ReentrantLock lock = new ReentrantLock();
Thread t1 = new Thread(() - > {log.debug("启动...");try {lock.lockInterruptibly();} catch (InterruptedException e) {e.printStackTrace();log.debug("等锁的过程中被打断");return;}try {log.debug("获得了锁");} finally {lock.unlock();}
}, "t1");
lock.lock();// 主线程获取锁
log.debug("获得了锁");
t1.start();
try {sleep(1);t1.interrupt();log.debug("执行打断");
} finally {lock.unlock();
}

4. 公平锁实现原理

tatic final class FairSync extends Sync {private static final long serialVersionUID = -3000897897090466540 L;final void lock() {acquire(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final void acquire(int arg) {if (!tryAcquire(arg) &&acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {selfInterrupt();}}// 与非公平锁主要区别在于 tryAcquire 方法的实现protected final boolean tryAcquire(int acquires) {final Thread current = Thread.currentThread();int c = getState();if (c == 0) {// 先检查 AQS 队列中是否有前驱节点, 没有才去竞争, 有的话返回false执行acquireQueued流程if (!hasQueuedPredecessors() &&compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current);return true;}} else if (current == getExclusiveOwnerThread()) {int nextc = c + acquires;if (nextc < 0)throw new Error("Maximum lock count exceeded");setState(nextc);return true;}return false;}// ㈠ AQS 继承过来的方法, 方便阅读, 放在此处public final boolean hasQueuedPredecessors() {Node t = tail;Node h = head;Node s;// h != t 时表示队列中有 Nodereturn h != t &&(// (s = h.next) == null 表示队列中还有没有老二(s = h.next) == null ||// 或者队列中老二线程不是此线程s.thread != Thread.currentThread());}
}

5. 条件变量实现原理

每个条件变量其实就对应着一个等待队列，其实现类是 ConditionObject

await 流程

开始 Thread-0 持有锁，调用 await，进入 ConditionObject 的 addConditionWaiter 流程

创建新的 Node 状态为 -2（Node.CONDITION），关联 Thread-0，加入等待队列尾部

接下来进入 AQS 的 fullyRelease 流程，释放同步器上的锁

unpark AQS 队列中的下一个节点，竞争锁，假设没有其他竞争线程，那么 Thread-1 竞争成功

park 阻塞 Thread-0

signal 流程

假设 Thread-1 要来唤醒 Thread-0

进入 ConditionObject 的 doSignal 流程，取得等待队列中第一个 Node，即 Thread-0 所在 Node

执行 transferForSignal 流程，将该 Node 加入 AQS 队列尾部，将 Thread-0 的 waitStatus 改为 0，Thread-3 的 waitStatus 改为 -1

Thread-1 释放锁，进入 unlock 流程，略

总结：

• await方法只是将当前线程移到等待队列中，并且释放自己的锁（重置state为0），然后唤醒AQS阻塞队列的老二节点去竞争锁，然后自己park阻塞
• signal方法只是将等待队列的头节点的waitstatus改为0，然后转移到AQS队列的尾部，并将AQS原来的尾节点的waitstatus，由0改成-1；然后等待唤醒（只是转移节点）

源码

public class ConditionObject implements Condition, java.io.Serializable {private static final long serialVersionUID = 1173984872572414699 L;// 第一个等待节点private transient Node firstWaiter;// 最后一个等待节点private transient Node lastWaiter;public ConditionObject() {}// ㈠ 添加一个 Node 至等待队列private Node addConditionWaiter() {Node t = lastWaiter;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (t != null && t.waitStatus != Node.CONDITION) {unlinkCancelledWaiters();t = lastWaiter;}// 创建一个关联当前线程的新 Node, 添加至队列尾部Node node = new Node(Thread.currentThread(), Node.CONDITION);if (t == null)firstWaiter = node;elset.nextWaiter = node;lastWaiter = node;return node;}// 唤醒 - 将没取消的第一个节点转移至 AQS 队列private void doSignal(Node first) {do {// 已经是尾节点了if ((firstWaiter = first.nextWaiter) == null) {lastWaiter = null;}first.nextWaiter = null;} while (// 将等待队列中的 Node 转移至 AQS 队列, 不成功且还有节点则继续循环 ㈢!transferForSignal(first) &&// 队列还有节点(first = firstWaiter) != null);}// 外部类方法, 方便阅读, 放在此处// ㈢ 如果节点状态是取消, 返回 false 表示转移失败, 否则转移成功final boolean transferForSignal(Node node) {// 如果状态已经不是 Node.CONDITION, 说明被取消了if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))return false;// 加入 AQS 队列尾部Node p = enq(node);int ws = p.waitStatus;if (// 上一个节点被取消ws > 0 ||// 上一个节点不能设置状态为 Node.SIGNAL!compareAndSetWaitStatus(p, ws, Node.SIGNAL)) {// unpark 取消阻塞, 让线程重新同步状态LockSupport.unpark(node.thread);}return true;}// 全部唤醒 - 等待队列的所有节点转移至 AQS 队列private void doSignalAll(Node first) {lastWaiter = firstWaiter = null;do {Node next = first.nextWaiter;first.nextWaiter = null;transferForSignal(first);first = next;} while (first != null);}// ㈡private void unlinkCancelledWaiters() {// ...}// 唤醒 - 必须持有锁才能唤醒, 因此 doSignal 内无需考虑加锁public final void signal() {if (!isHeldExclusively())throw new IllegalMonitorStateException();Node first = firstWaiter;if (first != null)doSignal(first);}// 全部唤醒 - 必须持有锁才能唤醒, 因此 doSignalAll 内无需考虑加锁public final void signalAll() {if (!isHeldExclusively())throw new IllegalMonitorStateException();Node first = firstWaiter;if (first != null)doSignalAll(first);}// 不可打断等待 - 直到被唤醒public final void awaitUninterruptibly() {// 添加一个 Node 至等待队列, 见 ㈠Node node = addConditionWaiter();// 释放节点持有的锁, 见 ㈣int savedState = fullyRelease(node);boolean interrupted = false;// 如果该节点还没有转移至 AQS 队列, 阻塞while (!isOnSyncQueue(node)) {// park 阻塞LockSupport.park(this);// 如果被打断, 仅设置打断状态if (Thread.interrupted())interrupted = true;}// 唤醒后, 尝试竞争锁, 如果失败进入 AQS 队列if (acquireQueued(node, savedState) || interrupted)selfInterrupt();}// 外部类方法, 方便阅读, 放在此处// ㈣ 因为某线程可能重入，需要将 state 全部释放final int fullyRelease(Node node) {boolean failed = true;try {int savedState = getState();if (release(savedState)) {failed = false;return savedState;} else {throw new IllegalMonitorStateException();}} finally {if (failed)node.waitStatus = Node.CANCELLED;}}// 打断模式 - 在退出等待时重新设置打断状态private static final int REINTERRUPT = 1;// 打断模式 - 在退出等待时抛出异常private static final int THROW_IE = -1;// 判断打断模式private int checkInterruptWhileWaiting(Node node) {return Thread.interrupted() ?(transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :0;}// ㈤ 应用打断模式private void reportInterruptAfterWait(int interruptMode)throws InterruptedException {if (interruptMode == THROW_IE)throw new InterruptedException();else if (interruptMode == REINTERRUPT)selfInterrupt();}// 等待 - 直到被唤醒或打断public final void await() throws InterruptedException {if (Thread.interrupted()) {throw new InterruptedException();}// 添加一个 Node 至等待队列, 见 ㈠Node node = addConditionWaiter();// 释放节点持有的锁int savedState = fullyRelease(node);int interruptMode = 0;// 如果该节点还没有转移至 AQS 队列则阻塞；在被unlock唤醒之前会调用singnal方法转移至AQS队			// 列，然后调用unlock唤醒该线程，条件不成立退出循环while (!isOnSyncQueue(node)) {// park 阻塞LockSupport.park(this);// 如果被打断, 退出等待队列，不在阻塞if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)break;}// 退出等待队列后, 被唤醒的线程还需要获得 AQS 队列的锁，执行后续代码if (acquireQueued(node, savedState) && interruptMode != THROW_IE)interruptMode = REINTERRUPT;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (node.nextWaiter != null)unlinkCancelledWaiters();// 应用打断模式, 见 ㈤if (interruptMode != 0)reportInterruptAfterWait(interruptMode);}// 等待 - 直到被唤醒或打断或超时public final long awaitNanos(long nanosTimeout) throws InterruptedException {if (Thread.interrupted()) {throw new InterruptedException();}// 添加一个 Node 至等待队列, 见 ㈠Node node = addConditionWaiter();// 释放节点持有的锁int savedState = fullyRelease(node);// 获得最后期限final long deadline = System.nanoTime() + nanosTimeout;int interruptMode = 0;// 如果该节点还没有转移至 AQS 队列, 阻塞while (!isOnSyncQueue(node)) {// 已超时, 退出等待队列if (nanosTimeout <= 0 L) {transferAfterCancelledWait(node);break;}// park 阻塞一定时间, spinForTimeoutThreshold 为 1000 nsif (nanosTimeout >= spinForTimeoutThreshold)LockSupport.parkNanos(this, nanosTimeout);// 如果被打断, 退出等待队列if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)break;nanosTimeout = deadline - System.nanoTime();}// 退出等待队列后, 还需要获得 AQS 队列的锁(打断的也需要)if (acquireQueued(node, savedState) && interruptMode != THROW_IE)interruptMode = REINTERRUPT;// 所有已取消的 Node 从队列链表删除, 见 ㈡if (node.nextWaiter != null)unlinkCancelledWaiters();// 应用打断模式, 见 ㈤if (interruptMode != 0)reportInterruptAfterWait(interruptMode);return deadline - System.nanoTime();}// 等待 - 直到被唤醒或打断或超时, 逻辑类似于 awaitNanospublic final boolean awaitUntil(Date deadline) throws InterruptedException {// ...}// 等待 - 直到被唤醒或打断或超时, 逻辑类似于 awaitNanospublic final boolean await(long time, TimeUnit unit) throws InterruptedException {// ...}// 工具方法 省略 ...
}

8.3 读写锁

1. ReentrantReadWriteLock

当读操作远远高于写操作时，这时候使用 读写锁 让 读-读 可以并发，提高性能。 类似于数据库中的 select ... from ... lock in share mode

提供一个 数据容器类 内部分别使用读锁保护数据的 read() 方法，写锁保护数据的 write() 方法

class DataContainer {private Object data;private ReentrantReadWriteLock rw = new ReentrantReadWriteLock();private ReentrantReadWriteLock.ReadLock r = rw.readLock();private ReentrantReadWriteLock.WriteLock w = rw.writeLock();public Object read() {log.debug("获取读锁...");r.lock();try {log.debug("读取");sleep(1);return data;} finally {log.debug("释放读锁...");r.unlock();}}public void write() {log.debug("获取写锁...");w.lock();try {log.debug("写入");sleep(1);} finally {log.debug("释放写锁...");w.unlock();}}
}

测试

DataContainer dataContainer = new DataContainer();
new Thread(() -> {dataContainer.read();
}, "t1").start();
new Thread(() -> {dataContainer.read();
}, "t2").start();

输出结果，从这里可以看到 Thread-0 锁定期间，Thread-1 的读操作不受影响

14:05:14.341 c.DataContainer [t2] - 获取读锁...
14:05:14.341 c.DataContainer [t1] - 获取读锁...
14:05:14.345 c.DataContainer [t1] - 读取
14:05:14.345 c.DataContainer [t2] - 读取
14:05:15.365 c.DataContainer [t2] - 释放读锁...
14:05:15.386 c.DataContainer [t1] - 释放读锁... 

测试 读锁-写锁 相互阻塞，写锁和写锁也是互斥的就不测试了

DataContainer dataContainer = new DataContainer();
new Thread(() -> {dataContainer.read();
}, "t1").start();
Thread.sleep(100);
new Thread(() -> {dataContainer.write();
}, "t2").start();

输出结果

14:04:21.838 c.DataContainer [t1] - 获取读锁...
14:04:21.838 c.DataContainer [t2] - 获取写锁...
14:04:21.841 c.DataContainer [t2] - 写入
14:04:22.843 c.DataContainer [t2] - 释放写锁...
14:04:22.843 c.DataContainer [t1] - 读取
14:04:23.843 c.DataContainer [t1] - 释放读锁...

注意事项

• 读锁不支持条件变量，读锁共享不存在互斥情况
• 重入时升级不支持：即持有读锁的情况下去获取写锁，会导致获取写锁永久等待

r.lock();
try {// ...w.lock();try {// ...} finally {w.unlock();}
} finally {r.unlock();
}

• 重入时降级支持：即持有写锁的情况下去获取读锁

class CachedData {Object data;// 是否有效，如果失效，需要重新计算 datavolatile boolean cacheValid;final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();void processCachedData() {rwl.readLock().lock();if (!cacheValid) {// 获取写锁前必须释放读锁rwl.readLock().unlock();rwl.writeLock().lock();try {// 判断是否有其它线程已经获取了写锁、更新了缓存, 避免重复更新if (!cacheValid) {data = ...cacheValid = true;}// 降级为读锁, 释放写锁, 这样能够让其它线程读取缓存rwl.readLock().lock();} finally {rwl.writeLock().unlock();}}// 自己用完数据, 释放读锁try {use(data);} finally {rwl.readLock().unlock();}}
}

2. 读写锁原理

1.图解流程

读写锁用的是同一个 Sycn 同步器，因此等待队列、state 等也是同一个

t1 w.lock，t2 r.lock

1） t1 成功上锁，流程与 ReentrantLock 加锁相比没有特殊之处，不同是写锁状态占了 state 的低 16 位，而读锁 使用的是 state 的高 16 位

2）t2 执行 r.lock，这时进入读锁的 sync.acquireShared(1) 流程，首先会进入 tryAcquireShared 流程。如果有写 锁占据，那么 tryAcquireShared 返回 -1 表示失败

tryAcquireShared 返回值表示

• -1 表示失败
• 0 表示成功，但后继节点不会继续唤醒
• 正数表示成功，而且数值是还有几个后继节点需要唤醒，读写锁返回 1

3）这时会进入 sync.doAcquireShared(1) 流程，首先也是调用 addWaiter 添加节点，不同之处在于节点被设置为 Node.SHARED 模式而非 Node.EXCLUSIVE 模式，注意此时 t2 仍处于活跃状态

4）t2 会看看自己的节点是不是老二，如果是，还会再次调用 tryAcquireShared(1) 来尝试获取锁

5）如果没有成功，在 doAcquireShared 内 for (;😉 循环一次，把前驱节点的 waitStatus 改为 -1，再 for (;😉 循环一 次尝试 tryAcquireShared(1) 如果还不成功，那么在 parkAndCheckInterrupt() 处 park

t3 r.lock，t4 w.lock

这种状态下，假设又有 t3 加读锁和 t4 加写锁，这期间 t1 仍然持有锁，就变成了下面的样子

t1 w.unlock

这时会走到写锁的 sync.release(1) 流程，调用 sync.tryRelease(1) 成功，变成下面的样子

接下来执行唤醒流程 sync.unparkSuccessor，即让老二恢复运行，这时 t2 在 doAcquireShared 内 parkAndCheckInterrupt() 处恢复运行

这回再来一次 for (;😉 执行 tryAcquireShared 成功则让读锁计数加一

这时 t2 已经恢复运行，接下来 t2 调用 setHeadAndPropagate(node, 1)，它原本所在节点被置为头节点

事情还没完，在 setHeadAndPropagate 方法内还会检查下一个节点是否是 shared，如果是则调用 doReleaseShared() 将 head 的状态从 -1 改为 0 并唤醒老二，这时 t3 在 doAcquireShared 内 parkAndCheckInterrupt() 处恢复运行

这回再来一次 for (;；) 执行 tryAcquireShared 成功则让读锁计数加一

这时 t3 已经恢复运行，接下来 t3 调用 setHeadAndPropagate(node, 1)，它原本所在节点被置为头节点

下一个节点不是 shared 了，因此不会继续唤醒 t4 所在节点

t2 r.unlock，t3 r.unlock

t2 进入 sync.releaseShared(1) 中，调用 tryReleaseShared(1) 让计数减一，但由于计数还不为零

t3 进入 sync.releaseShared(1) 中，调用 tryReleaseShared(1) 让计数减一，这回计数为零了，进入 doReleaseShared() 将头节点从 -1 改为 0 并唤醒老二，即

之后 t4 在 acquireQueued 中 parkAndCheckInterrupt 处恢复运行，再次 for (;😉 这次自己是老二，并且没有其他 竞争，tryAcquire(1) 成功，修改头结点，流程结束

2.源码分析

写锁上锁流程

static final class NonfairSync extends Sync {// ... 省略无关代码// 外部类 WriteLock 方法, 方便阅读, 放在此处public void lock() {sync.acquire(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final void acquire(int arg) {if (// 尝试获得写锁失败!tryAcquire(arg) &&// 将当前线程关联到一个 Node 对象上, 模式为独占模式// 进入 AQS 队列阻塞acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) {selfInterrupt();}}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryAcquire(int acquires) {// 获得低 16 位, 代表写锁的 state 计数Thread current = Thread.currentThread();int c = getState();// c会和(1 << 16) - 1做与运算，其中1 << 16表示1向左移16位等于0001 0000 0000 0000 0000// 减一就变成了0000 1111 1111 1111 1111，这样c和它做与运算结果不为0说明低16位有1，有写锁int w = exclusiveCount(c);if (c != 0) {if (// c != 0 and w == 0 表示有读锁, 或者w == 0 ||// 有写锁但exclusiveOwnerThread 不是自己current != getExclusiveOwnerThread()) {// 获得锁失败return false;}// 写锁计数超过低 16 位, 报异常if (w + exclusiveCount(acquires) > MAX_COUNT)throw new Error("Maximum lock count exceeded");// 写锁重入, 获得锁成功setState(c + acquires);return true;}if (// 判断写锁是否该阻塞（公平锁会判断是否有AQS队列，有的话会返回true）, 或者writerShouldBlock() ||// 尝试更改计数失败!compareAndSetState(c, c + acquires)) {// 获得锁失败return false;}// 获得锁成功setExclusiveOwnerThread(current);return true;}// 非公平锁 writerShouldBlock 总是返回 false, 无需阻塞final boolean writerShouldBlock() {return false;}
}

写锁释放流程

static final class NonfairSync extends Sync {// ... 省略无关代码// WriteLock 方法, 方便阅读, 放在此处public void unlock() {sync.release(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final boolean release(int arg) {// 尝试释放写锁成功if (tryRelease(arg)) {// unpark AQS 中等待的线程Node h = head;if (h != null && h.waitStatus != 0)unparkSuccessor(h);return true;}return false;}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryRelease(int releases) {if (!isHeldExclusively())throw new IllegalMonitorStateException();int nextc = getState() - releases;// 因为可重入的原因, 写锁计数为 0, 才算释放成功boolean free = exclusiveCount(nextc) == 0;if (free) {setExclusiveOwnerThread(null);}setState(nextc);return free;}
}

读锁上锁流程

static final class NonfairSync extends Sync {// ReadLock 方法, 方便阅读, 放在此处public void lock() {sync.acquireShared(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final void acquireShared(int arg) {// tryAcquireShared 返回负数, 表示获取读锁失败if (tryAcquireShared(arg) < 0) {doAcquireShared(arg);}}// Sync 继承过来的方法, 方便阅读, 放在此处protected final int tryAcquireShared(int unused) {Thread current = Thread.currentThread();int c = getState();// 如果是其它线程持有写锁, 获取读锁失败if (exclusiveCount(c) != 0 &&getExclusiveOwnerThread() != current) {return -1;}// c向右移16位，这样就得到高16位了int r = sharedCount(c);if (// 读锁不该阻塞(如果老二是写锁，读锁该阻塞), 并且!readerShouldBlock() &&// 小于读锁计数, 并且r < MAX_COUNT &&// 尝试增加计数成功compareAndSetState(c, c + SHARED_UNIT)) {// ... 省略不重要的代码return 1;}return fullTryAcquireShared(current);}// 非公平锁 readerShouldBlock 看 AQS 队列中第一个节点是否是写锁// true 则该阻塞, false 则不阻塞final boolean readerShouldBlock() {return apparentlyFirstQueuedIsExclusive();}// AQS 继承过来的方法, 方便阅读, 放在此处// 与 tryAcquireShared 功能类似, 但会不断尝试 for (;;) 获取读锁, 执行过程中无阻塞final int fullTryAcquireShared(Thread current) {HoldCounter rh = null;for (;;) {int c = getState();if (exclusiveCount(c) != 0) {if (getExclusiveOwnerThread() != current)return -1;} else if (readerShouldBlock()) {// ... 省略不重要的代码}if (sharedCount(c) == MAX_COUNT)throw new Error("Maximum lock count exceeded");if (compareAndSetState(c, c + SHARED_UNIT)) {// ... 省略不重要的代码return 1;}}}// AQS 继承过来的方法, 方便阅读, 放在此处private void doAcquireShared(int arg) {// 将当前线程关联到一个 Node 对象上, 模式为共享模式final Node 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) {// ㈠// r 表示可用资源数, 在这里总是 1 允许传播//（唤醒 AQS 中下一个 Share 节点）setHeadAndPropagate(node, r);p.next = null; // help GCif (interrupted)selfInterrupt();failed = false;return;}}if (// 是否在获取读锁失败时阻塞（前一个阶段 waitStatus == Node.SIGNAL）shouldParkAfterFailedAcquire(p, node) &&// park 当前线程parkAndCheckInterrupt()) {interrupted = true;}}} finally {if (failed)cancelAcquire(node);}}// ㈠ AQS 继承过来的方法, 方便阅读, 放在此处private void setHeadAndPropagate(Node node, int propagate) {Node h = head; // Record old head for check below// 设置自己为 headsetHead(node);// propagate 表示有共享资源（例如共享读锁或信号量）// 原 head waitStatus == Node.SIGNAL 或 Node.PROPAGATE// 现在 head waitStatus == Node.SIGNAL 或 Node.PROPAGATEif (propagate > 0 || h == null || h.waitStatus < 0 ||(h = head) == null || h.waitStatus < 0) {Node s = node.next;// 如果是最后一个节点或者是等待共享读锁的节点if (s == null || s.isShared()) {// 进入 ㈡doReleaseShared();}}}// ㈡ AQS 继承过来的方法, 方便阅读, 放在此处private void doReleaseShared() {// 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark// 如果 head.waitStatus == 0 ==> Node.PROPAGATE, 为了解决 bug, 见后面分析for (;;) {Node h = head;// 队列还有节点if (h != null && h != tail) {int ws = h.waitStatus;if (ws == Node.SIGNAL) {if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))continue; // loop to recheck cases/** 下一个节点 unpark，并接着从阻塞位置的代码开始执行，如果成功获取读锁，再走一遍*	 setHeadAndPropagate方法流程*	并且下下个节点还是 shared节点唤醒, 继续doReleaseShared，直到把全部shared* 节点唤醒，这样就可以提高读的并发，因为前面获取了读锁，说明肯定没有写锁了*/unparkSuccessor(h);} else if (ws == 0 &&!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))continue; // loop on failed CAS}if (h == head) // loop if head changedbreak;}}
}

读锁释放流程

static final class NonfairSync extends Sync {// ReadLock 方法, 方便阅读, 放在此处public void unlock() {sync.releaseShared(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final boolean releaseShared(int arg) {if (tryReleaseShared(arg)) {doReleaseShared();return true;}return false;}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryReleaseShared(int unused) {// ... 省略不重要的代码for (;;) {int c = getState();int nextc = c - SHARED_UNIT;if (compareAndSetState(c, nextc)) {// 读锁的计数不会影响其它获取读锁线程, 但会影响其它获取写锁线程// 计数为 0 才是真正释放return nextc == 0;}}}// AQS 继承过来的方法, 方便阅读, 放在此处private void doReleaseShared() {// 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark// 如果 head.waitStatus == 0 ==> Node.PROPAGATEfor (;;) {Node h = head;if (h != null && h != tail) {int ws = h.waitStatus;// 如果有其它线程也在释放读锁，那么需要将 waitStatus 先改为 0// 防止 unparkSuccessor 被多次执行if (ws == Node.SIGNAL) {if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))continue; // loop to recheck casesunparkSuccessor(h);}// 如果已经是 0 了，改为 -3，用来解决传播性，见后文信号量 bug 分析else if (ws == 0 &&!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))continue; // loop on failed CAS}if (h == head) // loop if head changedbreak;}}
}

3.StampedLock

该类自 JDK 8 加入，是为了进一步优化读性能，它的特点是在使用读锁、写锁时都必须配合【戳】使用

加解读锁

long stamp = lock.readLock();
lock.unlockRead(stamp);

加解写锁

long stamp = lock.writeLock();
lock.unlockWrite(stamp);

乐观读，StampedLock 支持 tryOptimisticRead() 方法（乐观读），读取完毕后需要做一次 戳校验 如果校验通 过，表示这期间确实没有写操作，数据可以安全使用，如果校验没通过，需要重新获取读锁，保证数据安全。

ong stamp = lock.tryOptimisticRead();
// 验戳
if (!lock.validate(stamp)) {// 锁升级
}

提供一个 数据容器类 内部分别使用读锁保护数据的 read() 方法，写锁保护数据的 write() 方法

class DataContainerStamped {private int data;private final StampedLock lock = new StampedLock();public DataContainerStamped(int data) {this.data = data;}public int read(int readTime) {// 获取戳long stamp = lock.tryOptimisticRead();log.debug("optimistic read locking...{}", stamp);sleep(readTime);// 验戳if (lock.validate(stamp)) {log.debug("read finish...{}, data:{}", stamp, data);return data;}// 验戳失败，期间有线程修改数据，需要加读锁// 锁升级 - 读锁log.debug("updating to read lock... {}", stamp);try {stamp = lock.readLock();log.debug("read lock {}", stamp);sleep(readTime);log.debug("read finish...{}, data:{}", stamp, data);return data;} finally {log.debug("read unlock {}", stamp);lock.unlockRead(stamp);}}public void write(int newData) {long stamp = lock.writeLock();log.debug("write lock {}", stamp);try {sleep(2);this.data = newData;} finally {log.debug("write unlock {}", stamp);lock.unlockWrite(stamp);}}
}

测试 读-读 可以优化

public static void main(String[] args) {DataContainerStamped dataContainer = new DataContainerStamped(1);new Thread(() -> {dataContainer.read(1);}, "t1").start();sleep(0.5);new Thread(() -> {dataContainer.read(0);}, "t2").start();
}

输出结果，可以看到实际没有加读锁

15:58:50.217 c.DataContainerStamped [t1] - optimistic read locking...256
15:58:50.717 c.DataContainerStamped [t2] - optimistic read locking...256
15:58:50.717 c.DataContainerStamped [t2] - read finish...256, data:1
15:58:51.220 c.DataContainerStamped [t1] - read finish...256, data:1

测试 读-写 时优化读补加读锁

public static void main(String[] args) {DataContainerStamped dataContainer = new DataContainerStamped(1);new Thread(() -> {dataContainer.read(1);}, "t1").start();sleep(0.5);new Thread(() -> {dataContainer.write(100);}, "t2").start();
}

输出结果

15:57:00.219 c.DataContainerStamped [t1] - optimistic read locking...256
15:57:00.717 c.DataContainerStamped [t2] - write lock 384
15:57:01.225 c.DataContainerStamped [t1] - updating to read lock... 256
15:57:02.719 c.DataContainerStamped [t2] - write unlock 384
15:57:02.719 c.DataContainerStamped [t1] - read lock 513
15:57:03.719 c.DataContainerStamped [t1] - read finish...513, data:1000
15:57:03.719 c.DataContainerStamped [t1] - read unlock 513

注意

那所有的地方都用StampedLock 替代读写锁吗？答案肯定不是，它有以下缺点

• StampedLock 不支持条件变量
• StampedLock 不支持可重入

8.4 Semaphore

基本使用

信号量，用来限制能同时访问共享资源的线程上限。

public static void main(String[] args) {// 1. 创建 semaphore 对象Semaphore semaphore = new Semaphore(3);// 2. 10个线程同时运行for (int i = 0; i < 10; i++) {new Thread(() - > {// 3. 获取许可try {semaphore.acquire();} catch (InterruptedException e) {e.printStackTrace();}try {log.debug("running...");sleep(1);log.debug("end...");} finally {// 4. 释放许可semaphore.release();}}).start();}
}

输出：三个三个任务的执行

07:35:15.485 c.TestSemaphore [Thread-2] - running...
07:35:15.485 c.TestSemaphore [Thread-1] - running...
07:35:15.485 c.TestSemaphore [Thread-0] - running...
07:35:16.490 c.TestSemaphore [Thread-2] - end...
07:35:16.490 c.TestSemaphore [Thread-0] - end...
07:35:16.490 c.TestSemaphore [Thread-1] - end...
07:35:16.490 c.TestSemaphore [Thread-3] - running...
07:35:16.490 c.TestSemaphore [Thread-5] - running...
07:35:16.490 c.TestSemaphore [Thread-4] - running...
07:35:17.490 c.TestSemaphore [Thread-5] - end...
07:35:17.490 c.TestSemaphore [Thread-4] - end...
07:35:17.490 c.TestSemaphore [Thread-3] - end...
07:35:17.490 c.TestSemaphore [Thread-6] - running...
07:35:17.490 c.TestSemaphore [Thread-7] - running...
07:35:17.490 c.TestSemaphore [Thread-9] - running...
07:35:18.491 c.TestSemaphore [Thread-6] - end...
07:35:18.491 c.TestSemaphore [Thread-7] - end...
07:35:18.491 c.TestSemaphore [Thread-9] - end...
07:35:18.491 c.TestSemaphore [Thread-8] - running...
07:35:19.492 c.TestSemaphore [Thread-8] - end... 

原理

1. 加锁解锁流程

Semaphore 有点像一个停车场，permits 就好像停车位数量，当线程获得了 permits 就像是获得了停车位，然后 停车场显示空余车位减一

刚开始，permits（state）为 3，这时 5 个线程来获取资源

假设其中 Thread-1，Thread-2，Thread-4 cas 竞争成功，而 Thread-0 和 Thread-3 竞争失败，进入 AQS 队列 park 阻塞

这时 Thread-4 释放了 permits，并且回去唤醒阻塞队列中的Thread0线程，状态如下

接下来 Thread-0 竞争成功，permits 再次设置为 0，设置自己为 head 节点，断开原来的 head 节点，unpark 接 下来的 Thread-3 节点，但由于 permits 是 0，因此 Thread-3 在尝试不成功后再次进入 park 状态

2. 源码分析

static final class NonfairSync extends Sync {private static final long serialVersionUID = -2694183684443567898 L;NonfairSync(int permits) {// permits 即 state，最终赋值给statesuper(permits);}// Semaphore 方法, 方便阅读, 放在此处public void acquire() throws InterruptedException {sync.acquireSharedInterruptibly(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final void acquireSharedInterruptibly(int arg)throws InterruptedException {if (Thread.interrupted())throw new InterruptedException();if (tryAcquireShared(arg) < 0)// 获取锁失败才执行doAcquireSharedInterruptibly(arg);}// 尝试获得共享锁protected int tryAcquireShared(int acquires) {return nonfairTryAcquireShared(acquires);}// Sync 继承过来的方法, 方便阅读, 放在此处final int nonfairTryAcquireShared(int acquires) {for (;;) {int available = getState();int remaining = available - acquires;if (// 如果许可已经用完, 返回负数, 表示获取失败, 进入 doAcquireSharedInterruptiblyremaining < 0 ||// 如果 cas 重试成功, 返回正数, 表示获取成功compareAndSetState(available, remaining)) {return remaining;}}}// AQS 继承过来的方法, 方便阅读, 放在此处private void doAcquireSharedInterruptibly(int arg) throws InterruptedException {final Node node = addWaiter(Node.SHARED);boolean failed = true;try {for (;;) {final Node p = node.predecessor();if (p == head) {// 如果当前节点的前驱节点是头节点，则再次尝试获取许可int r = tryAcquireShared(arg);if (r >= 0) {// 成功后本线程出队（AQS）, 所在 Node设置为 head// 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark// 如果 head.waitStatus == 0 ==> Node.PROPAGATE// r 表示可用资源数, 为 0 则不会继续传播setHeadAndPropagate(node, r);p.next = null; // help GCfailed = false;return;}}// 不成功, 设置上一个节点 waitStatus = Node.SIGNAL, 下轮进入 park 阻塞if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())throw new InterruptedException();}} finally {if (failed)cancelAcquire(node);}}// Semaphore 方法, 方便阅读, 放在此处public void release() {sync.releaseShared(1);}// AQS 继承过来的方法, 方便阅读, 放在此处public final boolean releaseShared(int arg) {if (tryReleaseShared(arg)) {// 唤醒阻塞的线程doReleaseShared();return true;}return false;}// Sync 继承过来的方法, 方便阅读, 放在此处protected final boolean tryReleaseShared(int releases) {for (;;) {int current = getState();int next = current + releases;if (next < current) // overflowthrow new Error("Maximum permit count exceeded");// 将state加一，替换成功返回trueif (compareAndSetState(current, next))return true;}}
}

3.为什么waitStatus要有 PROPAGATE这个类型

早期的方法实现有bug

• releaseShared 方法

public final boolean releaseShared(int arg) {if (tryReleaseShared(arg)) {Node h = head;if (h != null && h.waitStatus != 0)unparkSuccessor(h);return true;}return false;
}

• doAcquireShared 方法

private void doAcquireShared(int arg) {final Node node = addWaiter(Node.SHARED);boolean failed = true;try {boolean interrupted = false;for (;;) {final Node p = node.predecessor();if (p == head) {// 读写锁始终返回1，信号量返回剩余资源数int r = tryAcquireShared(arg);if (r >= 0) {// 这里会有空档setHeadAndPropagate(node, r);p.next = null; // help GCif (interrupted)selfInterrupt();failed = false;return;}}if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())interrupted = true;}} finally {if (failed)cancelAcquire(node);}
}

• setHeadAndPropagate 方法

private void setHeadAndPropagate(Node node, int propagate) {setHead(node);// 有空闲资源if (propagate > 0 && node.waitStatus != 0) {Node s = node.next;// 下一个if (s == null || s.isShared())unparkSuccessor(node);}
}

• 假设存在某次循环中队列里排队的结点情况为 head(-1)->t1(-1)->t2(-1)
• 假设存在将要信号量释放的 T3 和 T4，释放顺序为先 T3 后 T4

正常流程

产生 bug 的情况

1. T3 调用 releaseShared(1)，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0
2. T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源 量）
3. T4 调用 releaseShared(1)，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个head），不满足 条件，因此不调用 unparkSuccessor(head)
4. T1 获取信号量成功，调用 setHeadAndPropagate 时，因为不满足 propagate > 0（2 的返回值也就是 propagate（剩余资源量） == 0），从而不会唤醒后继结点， T2 线程得不到唤醒

bug 修复后

private void setHeadAndPropagate(Node node, int propagate) {Node h = head; // Record old head for check below// 设置自己为 headsetHead(node);// propagate 表示有共享资源（例如共享读锁（始终是1）或信号量）// 原来的头节点：waitStatus == Node.SIGNAL 或 Node.PROPAGATEif (propagate > 0 || h == null || h.waitStatus < 0 ||// 重新获取头节点，即自己所在节点，现在的头节点：waitStatus == Node.SIGNAL 或 Node.PROPAGATE(h = head) == null || h.waitStatus < 0) {Node s = node.next;// 如果是最后一个节点或者是等待共享读锁的节点if (s == null || s.isShared()) {doReleaseShared();}}
}
private void doReleaseShared() {// 如果 head.waitStatus == Node.SIGNAL ==> 0 成功, 下一个节点 unpark// 如果 head.waitStatus == 0，说明当前有节点唤醒但还没执行setHead操作，重新设置头节点的	   	   	   // waitStatus为Node.PROPAGATE(-3)for (;;) {Node h = head;if (h != null && h != tail) {int ws = h.waitStatus;if (ws == Node.SIGNAL) {if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))continue; // loop to recheck casesunparkSuccessor(h);} else if (ws == 0 &&!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))continue; // loop on failed CAS}if (h == head) // loop if head changedbreak;}
}

1. T3 调用 releaseShared()，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0
2. T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源 量）
3. T4 调用 releaseShared()，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个 head），调用 doReleaseShared() 将等待状态置为 PROPAGATE（-3）
4. T1 获取信号量成功，调用 setHeadAndPropagate 时，读到原来的头节点h.waitStatus < 0，从而调用 doReleaseShared() ，然后里面获取到最新的头节点的状态为-1，从而唤醒 T2
5. 也有可能是T1线程设置头节点还没执行**doReleaseShared()**的时候，T4线程刚好执行了if(h==head)代码，此时头节点已经被T1重新赋值了，所以条件不成立不用退出循环，再次执行一遍循环，而当前头节点的waitStatus已经为-1了，所以T4线程也会有唤醒T2线程的可能，将头节点设置为0，此时T1线程执行doReleaseShared方法也不会重复唤醒线程

所以PROPAGATE的存在就是为了解决上面出现的线程不可被唤醒的问题

8.5 CountdownLatch

基本使用

用来进行线程同步协作，等待所有线程完成倒计时。

其中构造参数用来初始化等待计数值，await() 用来等待计数归零，countDown() 用来让计数减一

例如：

• 通常用于主线程等待其他线程执行完任务之后，再执行后续操作
• 那为什么不用join方法呢，因为它可以用在线程池上，而join不行，因为核心线程不会结束，用了join，主线程就会一直阻塞了

public static void main(String[] args) throws InterruptedException {CountDownLatch latch = new CountDownLatch(2);new Thread(() - > {log.debug("begin...");sleep(1);latch.countDown();log.debug("end...{}", latch.getCount());}).start();new Thread(() - > {log.debug("begin...");sleep(2);latch.countDown();log.debug("end...{}", latch.getCount());}).start();log.debug("waiting...");latch.await();log.debug("wait end...");
}

输出

18:44:00.778 c.TestCountDownLatch [main] - waiting...
18:44:00.778 c.TestCountDownLatch [Thread-0] - begin...
18:44:00.778 c.TestCountDownLatch [Thread-1] - begin...
18:44:01.782 c.TestCountDownLatch [Thread-0] - end...2
18:44:02.782 c.TestCountDownLatch [Thread-1] - end...0
18:44:02.782 c.TestCountDownLatch [main] - wait end... 

原理

countDown流程

public void countDown() {sync.releaseShared(1);
}// AQS 继承过来的方法, 方便阅读, 放在此处
public final boolean releaseShared(int arg) {if (tryReleaseShared(arg)) {doReleaseShared();return true;}return false;
}protected boolean tryReleaseShared(int releases) {// Decrement count; signal when transition to zerofor (;;) {// 获取stateint c = getState();if (c == 0)return false;// state减一int nextc = c-1;if (compareAndSetState(c, nextc))// 如果state等于0了就返回true，执行doReleaseShared方法唤醒阻塞线程return nextc == 0;}}

await流程

public void await() throws InterruptedException {sync.acquireSharedInterruptibly(1);
}
// AQS 继承过来的方法, 方便阅读, 放在此处
public final void acquireSharedInterruptibly(int arg)throws InterruptedException {if (Thread.interrupted())throw new InterruptedException();if (tryAcquireShared(arg) < 0)doAcquireSharedInterruptibly(arg);
}protected int tryAcquireShared(int acquires) {//state等于0（countDown减为0）才获取锁成功，否则执行doAcquireSharedInterruptibly方法return (getState() == 0) ? 1 : -1;
}
// AQS 继承过来的方法, 方便阅读, 放在此处
private void doAcquireSharedInterruptibly(int arg)throws InterruptedException {// 添加节点到AQS队列尾部，head(0)-main(0)final Node node = addWaiter(Node.SHARED);boolean failed = true;try {for (;;) {final Node p = node.predecessor();if (p == head) {// 第二次尝试获取锁失败int r = tryAcquireShared(arg);if (r >= 0) {setHeadAndPropagate(node, r);p.next = null; // help GCfailed = false;return;}}// 设置头节点waitStatus(-1)，此时head(-1)-main(0)if (shouldParkAfterFailedAcquire(p, node) &&// 第三次尝试获取锁失败进入阻塞，等待被唤醒parkAndCheckInterrupt())throw new InterruptedException();}} finally {if (failed)cancelAcquire(node);}}

8.6 CyclicBarrier

基本使用

循环栅栏，用来进行线程协作，等待线程满足某个计数。

构造时设置计数个数，每个线程执行到某个需要“同步”的时刻调用 await() 方法进行等待，当等待的线程数满足计数个数时，继续执行（可以设置额外任务执行）

CyclicBarrier cb = new CyclicBarrier(2); // 个数为2时才会继续执行
new Thread(() - > {System.out.println("线程1开始.." + new Date());try {cb.await(); // 当个数不足时，等待} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}System.out.println("线程1继续向下运行..." + new Date());
}).start();
new Thread(() - > {System.out.println("线程2开始.." + new Date());try {Thread.sleep(2000);} catch (InterruptedException e) {}try {cb.await(); // 2 秒后，线程个数够2，继续运行} catch (InterruptedException | BrokenBarrierException e) {e.printStackTrace();}System.out.println("线程2继续向下运行..." + new Date());
}).start();

注意

• CyclicBarrier 与 CountDownLatch 的主要区别在于 CyclicBarrier 是可以重用的

原理

提供两个有参构造方法

// 
private final int parties;
// 计数个数
private int count;
// 计数到达时要执行的任务
private final Runnable barrierCommand;
// 锁
private final ReentrantLock lock = new ReentrantLock();
// 条件变量
private final Condition trip = lock.newCondition();
// 栅栏代数
private Generation generation = new Generation();public CyclicBarrier(int parties) {this(parties, null);
}public CyclicBarrier(int parties, Runnable barrierAction) {if (parties <= 0) throw new IllegalArgumentException();this.parties = parties;this.count = parties;this.barrierCommand = barrierAction;
}

await流程

public int await() throws InterruptedException, BrokenBarrierException {try {return dowait(false, 0L);} catch (TimeoutException toe) {throw new Error(toe); // cannot happen}}private int dowait(boolean timed, long nanos) throws InterruptedException, BrokenBarrierException, TimeoutException {final ReentrantLock lock = this.lock;// 抢锁lock.lock();try {// 获取 Generationfinal Generation g = generation;// 如果这代损坏了，抛出异常if (g.broken)throw new BrokenBarrierException();// 当前线程被中断过if (Thread.interrupted()) {// 将损坏状态设置为true// 并通知其他阻塞在此栅栏上的线程breakBarrier();throw new InterruptedException();}// 计数个数减一int index = --count;// 如果等于0，满足计数个数，继续往下执行if (index == 0) {boolean ranAction = false;try {// 执行栅栏任务final Runnable command = barrierCommand;if (command != null)command.run();ranAction = true;// 唤醒之前等待的线程nextGeneration();return 0;} finally {// 如果执行栅栏任务的时候失败了，就将损坏状态设置为trueif (!ranAction)breakBarrier();}}// loop until tripped, broken, interrupted, or timed outfor (;;) {try {// 没有时间限制，则无期限等待if (!timed)trip.await();// 有时间限制，则等待一定时间else if (nanos > 0L)nanos = trip.awaitNanos(nanos);} catch (InterruptedException ie) {// 当前代没有损坏if (g == generation && ! g.broken) {// 让栅栏失效breakBarrier();throw ie;} else {// 上面条件不满足，说明这个线程不是这代的// 就不会影响当前这代栅栏的执行，所以，就打个中断标记 										  Thread.currentThread().interrupt();}}// 当有任何一个线程中断了，就会调用breakBarrier方法// 就会唤醒其他的线程，其他线程醒来后，也要抛出异常if (g.broken)throw new BrokenBarrierException();// g != generation表示正常换代了，返回当前线程所在栅栏的下标// 如果 g == generation，说明还没有换代，那为什么会醒了？// 因为一个线程可以使用多个栅栏，当别的栅栏唤醒了这个线程，就会走到这里，所以需要判断是否是当前代。// 正是因为这个原因，才需要generation来保证正确。if (g != generation)return index;// 如果有时间限制，且时间小于等于0，销毁栅栏并抛出异常if (timed && nanos <= 0L) {breakBarrier();throw new TimeoutException();}}} finally {lock.unlock();}
}private void breakBarrier() {// 让当前代栅栏失效generation.broken = true;// 重新赋值计数个数count = parties;// 唤醒其他线程trip.signalAll();
}private void nextGeneration() {// 唤醒其他线程trip.signalAll();// 重新赋值计数个数，能够重复执行的关键count = parties;// 开始新一代栅栏generation = new Generation();
}

8.7 线程安全集合类概述

线程安全集合类可以分为三大类：

• 遗留的线程安全集合如 Hashtable ， Vector （底层使用synchronized）

• 使用 Collections 装饰的线程安全集合，如： （底层使用synchronized）

  • Collections.synchronizedCollection
  • Collections.synchronizedList
  • Collections.synchronizedMap
  • Collections.synchronizedSet
  • Collections.synchronizedNavigableMap
  • Collections.synchronizedNavigableSet
  • Collections.synchronizedSortedMap
  • Collections.synchronizedSortedSet

• java.util.concurrent.* 包下的集合类：Blocking、CopyOnWrite、Concurrent等等

  • Blocking 大部分实现基于锁，并提供用来阻塞的方法
  • CopyOnWrite 之类容器修改开销相对较重 ，增删改时会加锁
  • Concurrent 类型的容器，内部很多操作使用 cas 优化，一般可以提供较高吞吐量

因为获取数据的方法是不加锁的，所以Concurrent类型的容器存在弱一致性问题：

• 遍历时弱一致性，例如，当利用迭代器遍历时，如果容器发生修改，迭代器仍然可以继续进行遍历，这时内容是旧的
• 求大小弱一致性，size 操作未必是 100% 准确，比如在获取大小还没返回时，此时容器又新增或删除了数据
• 读取弱一致性

遍历时如果发生了修改，对于非安全容器来讲，使用 fail-fast 机制也就是让遍历立刻失败，抛出 ConcurrentModificationException，不再继续遍历，这是强一致性的体现

非安全容器的并发修改异常：

增强for循环底层还是使用集合的迭代器进行遍历，当迭代器迭代的时候，在当前线程A中，会单独创建一个新的线程B。

• A线程负责继续迭代, B线程负责去删除.

• B线程每次都会去检查和A线程中的元素是否个数相同.如果不是报错ConcurrentModificationException.

在迭代集合的时候,边迭代边删除是非常常用的操作，如何解决并发修改异常呢?

• 不要使用集合对象的删除方法，该方法只能从集合中删除元素,不能把迭代器中指定的元素也删除

• 使用Iterator中的remove方法，该方法会从两个线程中同时移除被删除的元素，保证了两个线程的同步

8.8 ConcurrentHashMap

1. JDK 7 HashMap 并发死链源码分析

死链图文说明

JDK8 HashMap源码分析

// 将 table 迁移至 newTable
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry < K, V > e: table) {while (null != e) {Entry < K, V > next = e.next;// 1 处if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);// 2 处// 将新元素加入 newTable[i], 原 newTable[i] 作为新元素的 nexte.next = newTable[i];newTable[i] = e;e = next;}}
}

假设 map 中初始元素是

原始链表，格式：[下标] (key,next)
[1] (1,35)->(35,16)->(16,null)线程 a 执行到 1 处 ，此时局部变量 e 为 (1,35)，而局部变量 next 为 (35,16) 线程 a 挂起线程 b 开始执行
第一次循环
[1] (1,null)第二次循环
[1] (35,1)->(1,null)第三次循环
[1] (35,1)->(1,null)
[17] (16,null)切换回线程 a，此时局部变量 e 和 next 被恢复，引用没变但内容变了：e 的内容被改为 (1,null)，而 next 的内
容被改为 (35,1) 并链向 (1,null)
第一次循环
[1] (1,null)第二次循环，注意这时 e 是 (35,1) 并链向 (1,null) 所以 next 又是 (1,null)
[1] (35,1)->(1,null)第三次循环，e 是 (1,null)，而 next 是 null，但 e 被放入链表头，这样 e.next 变成了 35 （2 处）
[1] (1,35)->(35,1)->(1,35)已经是死链了

• JDK 8扩容采用尾插法，不再将元素加入链表头（而是保持与扩容前一样的顺序），但在多线程环境下扩容，还会出现其它问题（如扩容丢数据）

2. JDK 8 ConcurrentHashMap

重要属性和内部类

// 默认为 0
// 当初始化时, 为 -1
// 当扩容时, 为 -(1 + 扩容线程数)
// 当初始化或扩容完成后，为 下一次的扩容的阈值大小
private transient volatile int sizeCtl;// 整个 ConcurrentHashMap 就是一个 Node[]
static class Node<K,V> implements Map.Entry<K,V> {}// hash 表
transient volatile Node<K,V>[] table;// 扩容时的 新 hash 表
private transient volatile Node<K,V>[] nextTable;// 扩容时如果某个 bin 迁移完毕, 用 ForwardingNode 作为旧 table bin 的头结点
static final class ForwardingNode<K,V> extends Node<K,V> {}// 用在 compute 以及 computeIfAbsent 时, 用来占位, 计算完成后替换为普通 Node
static final class ReservationNode<K,V> extends Node<K,V> {}// 作为 treebin 的头节点, 存储 root 和 first
static final class TreeBin<K,V> extends Node<K,V> {}// 作为 treebin 的节点, 存储 parent, left, right
static final class TreeNode<K,V> extends Node<K,V> {}

重要方法

// 获取 Node[] 中第 i 个 Node
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i)// cas 修改 Node[] 中第 i 个 Node 的值, c 为旧值, v 为新值
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v)// 直接修改 Node[] 中第 i 个 Node 的值, v 为新值
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v)

构造器分析

实现了懒惰初始化，在构造方法中仅仅计算了 table 的大小，以后在第一次使用时才会真正创建

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0 f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (initialCapacity < concurrencyLevel) // Use at least as many binsinitialCapacity = concurrencyLevel; // as estimated threadslong size = (long)(1.0 + (long) initialCapacity / loadFactor);//tableSizeFor保证计算的大小是 2^n, 即 16,32,64 ...int cap = (size >= (long) MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int) size);this.sizeCtl = cap;
}

为什么要保证数组长度是2的n次方，主要是为了保证key可以均匀的散落到不同的桶中，因为计算桶的逻辑为

tab[(n-1) & hash]，它等价于tab[n % hash]，但是它比取余操作快，来看个例子，如果数组长度不是2的n次方会怎么样?

当数组长度为15时：

hash	length-1	hash&(length)	结果
4	14	0100 & 1110 = 0100	4
5	14	0101 & 1110 = 0100	4
6	14	0110 & 1110 = 0110	6
7	14	0111 & 1110 = 0110	6

当数组长度为16时：

hash	length-1	hash&(length)	结果
4	15	0100 & 1111 = 0100	4
5	15	0101 & 1111 = 0101	5
6	15	0110 & 1111 = 0110	6
7	15	0111 & 1111 = 0111	7

当 length =15时，6 和 7 的结果一样，也就是产生了碰撞，6、7就会在一个位置形成链表，4和5的结果也是一样，这样就会导致查询速度降低。所以要保证数组长度为2的n次方。

get 流程

public V get(Object key) {Node < K, V > [] tab;Node < K, V > e, p;int n, eh;K ek;// spread 方法能确保返回结果是正数int h = spread(key.hashCode());if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {// 如果头结点已经是要查找的 key，返回值if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// hash为负数表示该 bin 在扩容中或是 treebin, 这时调用 find 方法来查找else if (eh < 0)return (p = e.find(h, key)) != null ? p.val : null;// 正常遍历链表, 用 equals 比较while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;
}

put 流程

以下数组简称（table），链表简称（bin）

public V put(K key, V value) {return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();// 其中 spread 方法会综合高位低位, 具有更好的 hash 性int hash = spread(key.hashCode());int binCount = 0;for (Node < K, V > [] tab = table;;) {// f 是链表头节点// fh 是链表头结点的 hash// i 是链表在 table 中的下标Node < K, V > f;int n, i, fh;// 要创建 tableif (tab == null || (n = tab.length) == 0)// 初始化 table 使用了 cas, 无需 synchronized 创建成功, 进入下一轮循环tab = initTable();// 要创建链表头节点else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 添加链表头使用了 cas, 无需 synchronizedif (casTabAt(tab, i, null,new Node < K, V > (hash, key, value, null)))break;}// ForwardingNode节点的hash为-1，说明正在扩容，需要帮忙扩容else if ((fh = f.hash) == MOVED)// 帮忙之后, 进入下一轮循环tab = helpTransfer(tab, f);else {V oldVal = null;// 锁住链表头节点synchronized(f) {// 再次确认链表头节点没有被移动if (tabAt(tab, i) == f) {// 链表if (fh >= 0) {binCount = 1;// 遍历链表for (Node < K, V > e = f;; ++binCount) {K ek;// 找到相同的 keyif (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;// 更新if (!onlyIfAbsent)e.val = value;break;}Node < K, V > pred = e;// 已经是最后的节点了, 新增 Node, 追加至链表尾if ((e = e.next) == null) {pred.next = new Node < K, V > (hash, key,value, null);break;}}}// 红黑树else if (f instanceof TreeBin) {Node < K, V > p;binCount = 2;// putTreeVal 会看 key 是否已经在树中, 是, 则返回对应的 TreeNodeif ((p = ((TreeBin < K, V > ) f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}// 释放链表头节点的锁}if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)// 如果链表长度 >= 树化阈值(8),并且数组的长度 >= 64 进行链表转为红黑树treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}// 增加 size 计数addCount(1 L, binCount);return null;
}// 初始化一个table
private final Node < K, V > [] initTable() {Node < K, V > [] tab;int sc;while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0)/**让当前线程从运行进入就绪状态, 让出CPU的执行权，只是一种暗示，并不能保证一定会发生让					* 出CPU执行权的效果。因为线程调度器可能会忽略这个暗示，导致调用yield()的线程再次获得                  * 执行权。*/Thread.yield();// 尝试将 sizeCtl 设置为 -1（表示初始化 table）else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// 获得锁, 创建 table, 这时其它线程会在 while() 循环中 yield 直至 table 创建try {if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;Node < K, V > [] nt = (Node < K, V > []) new Node <? , ?> [n];table = tab = nt;sc = n - (n >>> 2);}} finally {sizeCtl = sc;}break;}}return tab;}// check 是之前 binCount(列表长度) 的个数
private final void addCount(long x, int check) {CounterCell[] as;long b, s;if (// 已经有了 counterCells, 向 cell 累加(as = counterCells) != null ||// 还没有, 向 baseCount 累加!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {CounterCell a;long v;int m;boolean uncontended = true;if (// 还没有 counterCellsas == null || (m = as.length - 1) < 0 ||// 还没有 cell(a = as[ThreadLocalRandom.getProbe() & m]) == null ||// cell cas 增加计数失败!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {// 创建累加单元数组和cell, 累加重试，和LongAdder累加逻辑差不多，不再介绍fullAddCount(x, uncontended);return;}if (check <= 1)return;// 获取元素个数s = sumCount();}// 如果列表长度大于1，可能需要扩容if (check >= 0) {Node < K, V > [] tab, nt;int n, sc;// 当前元素个数是否大于阈值sizeCtl，需要扩容while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {int rs = resizeStamp(n);if (sc < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;// newtable 已经创建了，帮忙扩容if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt);}// 需要扩容，这时 newtable 未创建，把阈值cas替换成负数，后续线程判断阈值为负数会帮忙扩容else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null);s = sumCount();}}
}

size 计算流程

size 计算实际发生在 put，remove 改变集合元素的操作之中

• 没有竞争发生，向 baseCount 累加计数
• 有竞争发生，新建 counterCells，向其中的一个 cell 累加计数
  • counterCells 初始有两个 cell
  • 如果计数竞争比较激烈，会创建新的 cell 来累加计数

public int size() {long n = sumCount();return ((n < 0 L) ? 0 :(n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int) n);
}
final long sumCount() {CounterCell[] as = counterCells;CounterCell a;// 将 baseCount 计数与所有 cell 计数累加long sum = baseCount;if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)sum += a.value;}}return sum;
}

总结

Java 8的结构为数组（Node） +（ 链表 Node | 红黑树 TreeNode ），以下数组简称（table），链表简称（bin）

• 初始化，使用 cas 来保证并发安全，懒惰初始化 table
• 树化，当bin.length > 8时且 table.length < 64 时，先尝试扩容，大于等于64 时，才将链表树化，树化过程 会用 synchronized 锁住链表头
• put，如果该 bin 尚未创建，只需要使用 cas 创建 bin；如果已经有了，锁住链表头进行后续 put 操作，元素 添加至 bin 的尾部，如果链表头节点为ForwardingNode，还会帮助扩容
• get，无锁操作仅需要保证可见性，扩容过程中 get 操作拿到的是 ForwardingNode，说明table正在执行扩容，它会让 get 操作在新 table 进行搜索
• 扩容，扩容时以 bin 为单位进行，需要对 bin 进行 synchronized，但这时其它竞争线程会帮助把其它 bin 进行扩容，扩容时平均只有 1/6 的节点会把复制到新 table 中
• size，元素个数保存在 baseCount 中，并发时的个数变动保存在 CounterCell[] 当中。最后统计数量时累加 即可

发现和创建相关的都采用cas进行创建，和修改相关的都采用synchronized 锁住链表头操作

3. JDK 7 ConcurrentHashMap

它维护了一个 segment 数组，每个 segment 对应一把锁

• 优点：如果多个线程访问不同的 segment，实际是没有冲突的，这与 jdk8 中是类似的
• 缺点：Segments 数组默认大小为16，这个容量初始化指定后就不能改变了，并且不是懒惰初始化，并且锁的粒度比JDK1.8的粗，一次锁好几个链表头（HashEntry数组）

构造器分析

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (concurrencyLevel > MAX_SEGMENTS)concurrencyLevel = MAX_SEGMENTS;// ssize 必须是 2^n, 即 2, 4, 8, 16 ... 表示了 segments 数组的大小int sshift = 0;int ssize = 1;while (ssize < concurrencyLevel) {++sshift;ssize <<= 1;}// segmentShift 默认是 32 - 4 = 28this.segmentShift = 32 - sshift;// segmentMask 默认是 15 即 0000 0000 0000 1111this.segmentMask = ssize - 1;if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;int c = initialCapacity / ssize;if (c * ssize < initialCapacity)++c;int cap = MIN_SEGMENT_TABLE_CAPACITY;while (cap < c)cap <<= 1;// 创建 segments and segments[0]Segment < K, V > s0 =new Segment < K, V > (loadFactor, (int)(cap * loadFactor), (HashEntry < K, V > []) new HashEntry[cap]);Segment < K, V > [] ss = (Segment < K, V > []) new Segment[ssize];UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]this.segments = ss;
}

构造完成，如下图所示

可以看到 ConcurrentHashMap 没有实现懒惰初始化，空间占用不友好

其中 this.segmentShift 和 this.segmentMask 的作用是决定将 key 的 hash 结果匹配到哪个 segment

例如，根据某一 hash 值求 segment 位置，先将高位向低位移动 this.segmentShift 位

put流程

public V put(K key, V value) {Segment < K, V > s;if (value == null)throw new NullPointerException();int hash = hash(key);// 计算出 segment 下标int j = (hash >>> segmentShift) & segmentMask;// 获得 segment 对象, 判断是否为 null, 是则创建该 segmentif ((s = (Segment < K, V > ) UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null) {// 这时不能确定是否真的为 null, 因为其它线程也发现该 segment 为 null,// 因此在 ensureSegment 里用 cas 方式保证该 segment 安全性s = ensureSegment(j);}// 进入 segment 的put 流程return s.put(key, hash, value, false);
}

segment 继承了可重入锁（ReentrantLock），它的 put 方法为

final V put(K key, int hash, V value, boolean onlyIfAbsent) {// 尝试加锁HashEntry < K, V > node = tryLock() ? null :// 如果不成功, 进入 scanAndLockForPut 流程// 如果是多核 cpu 最多 tryLock 64 次, 进入 lock 流程// 在尝试期间, 还可以顺便看该节点在链表中有没有, 如果没有顺便创建出来scanAndLockForPut(key, hash, value);// 执行到这里 segment 已经被成功加锁, 可以安全执行V oldValue;try {HashEntry < K, V > [] tab = table;int index = (tab.length - 1) & hash;HashEntry < K, V > first = entryAt(tab, index);for (HashEntry < K, V > e = first;;) {if (e != null) {// 更新K k;if ((k = e.key) == key ||(e.hash == hash && key.equals(k))) {oldValue = e.value;if (!onlyIfAbsent) {e.value = value;++modCount;}break;}e = e.next;} else {// 新增// 1) 之前等待锁时, node 已经被创建, next 指向链表头if (node != null)node.setNext(first);else// 2) 创建新 nodenode = new HashEntry < K, V > (hash, key, value, first);int c = count + 1;// 3) 扩容if (c > threshold && tab.length < MAXIMUM_CAPACITY)rehash(node);else// 将 node 作为链表头setEntryAt(tab, index, node);++modCount;count = c;oldValue = null;break;}}} finally {unlock();}return oldValue;
}

rehash 流程

发生在 put 中，因为此时已经获得了锁，因此 rehash 时不需要考虑线程安全

private void rehash(HashEntry < K, V > node) {HashEntry < K, V > [] oldTable = table;int oldCapacity = oldTable.length;int newCapacity = oldCapacity << 1;threshold = (int)(newCapacity * loadFactor);HashEntry < K, V > [] newTable =(HashEntry < K, V > []) new HashEntry[newCapacity];int sizeMask = newCapacity - 1;for (int i = 0; i < oldCapacity; i++) {HashEntry < K, V > e = oldTable[i];if (e != null) {HashEntry < K, V > next = e.next;int idx = e.hash & sizeMask;if (next == null) // Single node on listnewTable[idx] = e;else { // Reuse consecutive sequence at same slotHashEntry < K, V > lastRun = e;int lastIdx = idx;// 过一遍链表, 尽可能把 rehash 后 idx 不变的节点重用for (HashEntry < K, V > last = next; last != null; last = last.next) {int k = last.hash & sizeMask;if (k != lastIdx) {lastIdx = k;lastRun = last;}}newTable[lastIdx] = lastRun;// 剩余节点需要新建for (HashEntry < K, V > p = e; p != lastRun; p = p.next) {V v = p.value;int h = p.hash;int k = h & sizeMask;HashEntry < K, V > n = newTable[k];newTable[k] = new HashEntry < K, V > (h, p.key, v, n);}}}}// 扩容完成, 才加入新的节点int nodeIndex = node.hash & sizeMask; // add the new nodenode.setNext(newTable[nodeIndex]);newTable[nodeIndex] = node;// 替换为新的 HashEntry tabletable = newTable;
}

get 流程

get 时并未加锁，用了 UNSAFE 方法保证了可见性，扩容过程中，get 先发生就从旧表取内容，get 后发生就从新 表取内容

public V get(Object key) {Segment < K, V > s; // manually integrate access methods to reduce overheadHashEntry < K, V > [] tab;int h = hash(key);// u 为 segment 对象在数组中的偏移量long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;// s 即为 segmentif ((s = (Segment < K, V > ) UNSAFE.getObjectVolatile(segments, u)) != null &&(tab = s.table) != null) {for (HashEntry < K, V > e = (HashEntry < K, V > ) UNSAFE.getObjectVolatile(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e != null; e = e.next) {K k;if ((k = e.key) == key || (e.hash == h && key.equals(k)))return e.value;}}return null;
}

size 计算流程

• 计算元素个数前，先不加锁计算两次，如果前后两次结果如一样，认为个数正确返回
• 如果不一样，进行重试，重试次数超过 3，将所有 segment 锁住，重新计算个数返回

public int size() {// Try a few times to get accurate count. On failure due to// continuous async changes in table, resort to locking.final Segment < K, V > [] segments = this.segments;int size;boolean overflow; // true if size overflows 32 bitslong sum; // sum of modCountslong last = 0 L; // previous sumint retries = -1; // first iteration isn't retrytry {for (;;) {if (retries++ == RETRIES_BEFORE_LOCK) {// 超过重试次数, 需要创建所有 segment 并加锁for (int j = 0; j < segments.length; ++j)ensureSegment(j).lock(); // force creation}sum = 0 L;size = 0;overflow = false;for (int j = 0; j < segments.length; ++j) {Segment < K, V > seg = segmentAt(segments, j);if (seg != null) {sum += seg.modCount;int c = seg.count;if (c < 0 || (size += c) < 0)overflow = true;}}if (sum == last)break;last = sum;}} finally {if (retries > RETRIES_BEFORE_LOCK) {for (int j = 0; j < segments.length; ++j)segmentAt(segments, j).unlock();}}return overflow ? Integer.MAX_VALUE : size;
}

8.9 LinkedBlockingQueue 原理

1. 基本的入队出队

public class LinkedBlockingQueue < E > extends AbstractQueue < E >implements BlockingQueue < E > , java.io.Serializable {static class Node < E > {E item;/*** 下列三种情况之一* - 真正的后继节点* - 自己, 发生在出队时* - null, 表示是没有后继节点, 是最后了*/Node < E > next;Node(E x) {item = x;}}}

初始化链表 last = head = new Node(null); Dummy 节点用来占位，item 为 null

出队

// 原头节点
Node<E> h = head;
Node<E> first = h.next;
// 原头节点的下一节点指向自己，断开链接
h.next = h; // help GC
// 重新设置头节点
head = first;
E x = first.item;
first.item = null;
return x;

2. 加锁分析

高明之处在于用了两把锁和 dummy 节点

• 用一把锁，同一时刻，最多只允许有一个线程（生产者或消费者，二选一）执行
• 用两把锁，同一时刻，可以允许两个线程同时（一个生产者与一个消费者）执行
  • 消费者与消费者线程仍然串行
  • 生产者与生产者线程仍然串行

线程安全分析

• 当节点总数大于 2 时（包括 dummy 节点），putLock 保证的是 last 节点的线程安全，takeLock 保证的是 head 节点的线程安全。两把锁保证了入队和出队没有竞争
• 当节点总数等于 2 时（即一个 dummy 节点，一个正常节点）这时候，仍然是两把锁锁两个对象，不会竞争
• 当节点总数等于 1 时（就一个 dummy 节点）这时 take 线程会被 notEmpty 条件阻塞，有竞争，会阻塞

// 用于 put(阻塞) offer(非阻塞)
private final ReentrantLock putLock = new ReentrantLock();// 用户 take(阻塞) poll(非阻塞)
private final ReentrantLock takeLock = new ReentrantLock();

put 操作

public void put(E e) throws InterruptedException {if (e == null) throw new NullPointerException();int c = -1;Node < E > node = new Node < E > (e);final ReentrantLock putLock = this.putLock;// count 用来维护元素计数final AtomicInteger count = this.count;putLock.lockInterruptibly();try {// 满了等待while (count.get() == capacity) {// 倒过来读就好: 等待 notFullnotFull.await();}// 有空位, 入队且计数加一enqueue(node);c = count.getAndIncrement();// 除了自己 put 以外, 队列还有空位, 由自己叫醒其他 put 线程if (c + 1 < capacity)notFull.signal();} finally {putLock.unlock();}// 如果队列中有一个元素, 叫醒 take 线程if (c == 0)// 这里调用的是 notEmpty.signal() 而不是 notEmpty.signalAll() 是为了减少竞争signalNotEmpty();
}

take操作

public E take() throws InterruptedException {E x;int c = -1;final AtomicInteger count = this.count;final ReentrantLock takeLock = this.takeLock;takeLock.lockInterruptibly();try {while (count.get() == 0) {notEmpty.await();}x = dequeue();c = count.getAndDecrement();if (c > 1)notEmpty.signal();} finally {takeLock.unlock();}// 如果队列中只有一个空位时, 叫醒 put 线程// 如果有多个线程进行出队, 第一个线程满足 c == capacity, 但后续线程 c < capacityif (c == capacity)// 这里调用的是 notFull.signal() 而不是 notFull.signalAll() 是为了减少竞争signalNotFull()return x;
}

由 put 唤醒 put 是为了避免信号不足

3.性能比较

主要列举 LinkedBlockingQueue 与 ArrayBlockingQueue 的性能比较

• Linked 支持有界，Array 强制有界
• Linked 实现是链表，Array 实现是数组
• Linked 是懒惰的，而 Array 需要提前初始化 Node 数组
• Linked 每次入队会生成新 Node，而 Array 的 Node 是提前创建好的
• Linked 两把锁，Array 一把锁

8.10 CopyOnWriteArrayList

采用了 写入时拷贝 的思想，增删改操作会将旧数组拷贝一份，更改操作在新数组上执行，不影响其它线程的并发读（读旧数组），读写分离。 以新增为例：

private transient volatile Object[] array;public boolean add(E e) {synchronized(lock) {// 获取旧的数组Object[] es = getArray();int len = es.length;// 拷贝新的数组（这里是比较耗时的操作，但不影响其它读线程）es = Arrays.copyOf(es, len + 1);// 添加新元素es[len] = e;// 替换旧的数组setArray(es);return true;}
}

这里的源码版本是 Java 11，在 Java 1.8 中使用的是可重入锁而不是 synchronized

    public boolean add(E e) {final ReentrantLock lock = this.lock;lock.lock();try {Object[] elements = getArray();int len = elements.length;Object[] newElements = Arrays.copyOf(elements, len + 1);newElements[len] = e;setArray(newElements);return true;} finally {lock.unlock();}}

其它读操作并未加锁，例如：

public void forEach(Consumer <? super E > action) {Objects.requireNonNull(action);for (Object x: getArray()) {@SuppressWarnings("unchecked") E e = (E) x;action.accept(e);}
}

适合『读多写少』的应用场景，get操作存在弱一致性问题

此时线程0读取的是旧数据，无法读取到线程1期间改的数据

不要觉得弱一致性就不好

• 数据库的 MVCC（快照读，读写不互斥）都是弱一致性的表现
• 并发高和一致性是矛盾的，需要权衡