JUC学习笔记（三）

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

文章目录

    • 八、共享模型之工具--JUC
      • 8.1 AQS 原理
        • 1. 概述
        • 2 实现不可重入锁
          • 自定义同步器
          • 自定义锁
        • 3.心得
          • 起源
          • 目标
          • 设计
            • 1) state 设计
            • 2）阻塞恢复设计
            • 3）队列设计
      • 8.2 ReentrantLock 原理
        • 1. 非公平锁实现原理
          • 加锁流程
          • 解锁流程
          • 加锁源码
          • 解锁源码
        • 2. 可重入原理
        • 3. 可打断原理
          • 不可打断模式
          • 可打断模式
        • 4. 公平锁实现原理
        • 5. 条件变量实现原理
          • await 流程
          • signal 流程
          • 源码
      • 8.3 读写锁
        • 1. ReentrantReadWriteLock
        • 2. 读写锁原理
          • 1.图解流程
            • t1 w.lock，t2 r.lock
            • t3 r.lock，t4 w.lock
            • t1 w.unlock
            • t2 r.unlock，t3 r.unlock
          • 2.源码分析
            • 写锁上锁流程
            • 写锁释放流程
            • 读锁上锁流程
            • 读锁释放流程
          • 3.StampedLock
      • 8.4 Semaphore
        • 基本使用
        • 原理
          • 1. 加锁解锁流程
          • 2. 源码分析
          • 3.为什么waitStatus要有 PROPAGATE这个类型
            • 正常流程
            • 产生 bug 的情况
            • bug 修复后
      • 8.5 CountdownLatch
        • 基本使用
        • 原理
          • countDown流程
          • await流程
      • 8.6 CyclicBarrier
        • 基本使用
        • 原理
          • await流程
      • 8.7 线程安全集合类概述
      • 8.8 ConcurrentHashMap
        • 1. JDK 7 HashMap 并发死链源码分析
        • 2. JDK 8 ConcurrentHashMap
          • 重要属性和内部类
          • 重要方法
          • 构造器分析
          • get 流程
          • put 流程
          • size 计算流程
          • 总结
        • 3. JDK 7 ConcurrentHashMap
          • 构造器分析
          • put流程
          • rehash 流程
          • get 流程
          • size 计算流程
      • 8.9 LinkedBlockingQueue 原理
        • 1. 基本的入队出队
        • 2. 加锁分析
        • 3.性能比较
      • 8.10 CopyOnWriteArrayList

八、共享模型之工具–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 {
    @Override
    protected boolean tryAcquire(int acquires) {
        if (acquires == 1) {
            if (compareAndSetState(0, 1)) {
                // 设置当前线程为锁持有者
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
        }
        return false;
    }

    @Override
    protected 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();
    }

    @Override
    protected 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 {
    // 原来的 tail
    Node 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 为 null
        if (t == null) {
            // 将 head 从 null -> dummy
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            // 将 node 的 prev 设置为原来的 tail
            node.prev = t;
            // 将 tail 从原来的 tail 设置为 node
            if (compareAndSetTail(t, node)) {
                // 原来 tail 的 next 设置为 node
                t.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

在这里插入图片描述

  1. shouldParkAfterFailedAcquire 执行完毕回到 acquireQueued ，再次 tryAcquire 尝试获取锁，当然这时 state 仍为 1，失败
  2. 当再次进入 shouldParkAfterFailedAcquire 时，这时因为其前驱 node 的 waitStatus 已经是 -1，这次返回 true
  3. 进入 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) {
        // ㈡ tryAcquire
        if (!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) // overflow
                throw 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）为 head
                    setHead(node);
                    // 上一个节点 help GC
                    p.next = null;
                    failed = false;
                    // 返回中断标记 false
                    return 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)) {
            // 队列头节点 unpark
            Node h = head;
            if (
                // 队列不为 null
                h != null &&
                // waitStatus == Node.SIGNAL 才需要 unpark
                h.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计数减去release
        setState(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) // overflow
                throw 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 被唤醒, 返回打断状态为 true
                    interrupted = true;
                }
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
        ) {
            // 如果打断状态为 true
            selfInterrupt();
        }
    }

    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 GC
                    failed = 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 时表示队列中有 Node
        return 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;
            else
                t.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 ns
                if (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();
        }
    // 等待 - 直到被唤醒或打断或超时, 逻辑类似于 awaitNanos
    public final boolean awaitUntil(Date deadline) throws InterruptedException {
            // ...
        }
    // 等待 - 直到被唤醒或打断或超时, 逻辑类似于 awaitNanos
    public 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;
    // 是否有效，如果失效，需要重新计算 data
    volatile 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 GC
                        if (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
        // 设置自己为 head
        setHead(node);

        // propagate 表示有共享资源（例如共享读锁或信号量）
        // 原 head waitStatus == Node.SIGNAL 或 Node.PROPAGATE
        // 现在 head waitStatus == Node.SIGNAL 或 Node.PROPAGATE
        if (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 changed
                break;
        }
    }
}
读锁释放流程
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.PROPAGATE
        for (;;) {
            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 cases
                    unparkSuccessor(h);
                }
                // 如果已经是 0 了，改为 -3，用来解决传播性，见后文信号量 bug 分析
                else if (ws == 0 &&
                    !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue; // loop on failed CAS
            }
            if (h == head) // loop if head changed
                break;
        }
    }
}
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，最终赋值给state
        super(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 (
                // 如果许可已经用完, 返回负数, 表示获取失败, 进入 doAcquireSharedInterruptibly
                remaining < 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 GC
                        failed = 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) // overflow
                throw new Error("Maximum permit count exceeded");
            // 将state加一，替换成功返回true
            if (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 GC
                    if (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
正常流程
t1 sync t2 t3 t4 parkAndCheckInterrupt阻塞 parkAndCheckInterrupt阻塞 head(-1)->>t1(-1)->>t2(0) releaseShared(1) unparkSuccessor(head) head(0)->>t1(-1)->>t2(0) t1恢复执行，剩余资源为1 tryAcquireShared(1) setHeadAndPropagate(t1Node, 0) head(-1)->>t2(0) releaseShared(1) unparkSuccessor(head) head(0)->>t2(0) t2恢复执行，剩余资源为1 tryAcquireShared(1) setHeadAndPropagate(t2Node, 0) head(0) t1 sync t2 t3 t4
产生 bug 的情况
t1 sync t2 t3 t4 parkAndCheckInterrupt阻塞 parkAndCheckInterrupt阻塞 head(-1)->>t1(-1)->>t2(0) releaseShared(1) unparkSuccessor(head) head(0)->>t1(-1)->>t2(0) t1恢复执行，剩余资源为1 tryAcquireShared(1) releaseShared(1) 此时头节点waitStatus为0，不满足unpark条件，返回 setHeadAndPropagate(t1Node, 0) head(-1)->>t2(0) t1 sync t2 t3 t4
  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
    // 设置自己为 head
    setHead(node);
    // propagate 表示有共享资源（例如共享读锁（始终是1）或信号量）
    // 原来的头节点：waitStatus == Node.SIGNAL 或 Node.PROPAGATE
    if (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 cases
                unparkSuccessor(h);
            } else if (ws == 0 &&
                !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                continue; // loop on failed CAS
        }
        if (h == head) // loop if head changed
            break;
    }
}
t1 sync t2 t3 t4 parkAndCheckInterrupt阻塞 parkAndCheckInterrupt阻塞 head(-1)->>t1(-1)->>t2(0) head(-1->>0), head(0->>-3) loop [doReleaseShared()不断尝试] head(0)->>t1(-1)->>t2(0) unparkSuccessor(head) t1恢复执行，剩余资源为1 tryAcquireShared(1) head(-1->>0), head(0->>-3) loop [doReleaseShared()不断尝试] head(-3)->>t1(-1)->>t2(0) setHeadAndPropagate(t1Node, 0) head(-1)->>t2(0) head(-1->>0), head(0->>-3) loop [doReleaseShared()不断尝试] 由t1或t4 head(0)->>t2(0) 由t1或t4 唤醒t2 t1 sync t2 t3 t4
  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 zero
            for (;;) {
                // 获取state
                int 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 GC
                        failed = 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 {
        // 获取 Generation
        final 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 {
                // 如果执行栅栏任务的时候失败了，就将损坏状态设置为true
                if (!ranAction)
                    breakBarrier();
            }
        }

        // loop until tripped, broken, interrupted, or timed out
        for (;;) {
            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] 作为新元素的 next
            e.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 bins
        initialCapacity = concurrencyLevel; // as estimated threads
    long 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时：

hashlength-1hash&(length)结果
4140100 & 1110 = 01004
5140101 & 1110 = 01004
6140110 & 1110 = 01106
7140111 & 1110 = 01106

当数组长度为16时：

hashlength-1hash&(length)结果
4150100 & 1111 = 01004
5150101 & 1111 = 01015
6150110 & 1111 = 01106
7150111 & 1111 = 01117

当 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;
        // 要创建 table
        if (tab == null || (n = tab.length) == 0)
        // 初始化 table 使用了 cas, 无需 synchronized 创建成功, 进入下一轮循环
            tab = initTable();
        // 要创建链表头节点
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 添加链表头使用了 cas, 无需 synchronized
            if (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;
                            // 找到相同的 key
                            if (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 是否已经在树中, 是, 则返回对应的 TreeNode
                        if ((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 (
            // 还没有 counterCells
            as == 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 = 28
    this.segmentShift = 32 - sshift;
    // segmentMask 默认是 15 即 0000 0000 0000 1111
    this.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, 是则创建该 segment
    if ((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) 创建新 node
                    node = 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 list
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                HashEntry < 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 node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;

    // 替换为新的 HashEntry table
    table = newTable;
}
get 流程

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

public V get(Object key) {
    Segment < K, V > s; // manually integrate access methods to reduce overhead
    HashEntry < K, V > [] tab;
    int h = hash(key);
    // u 为 segment 对象在数组中的偏移量
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // s 即为 segment
    if ((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 bits
    long sum; // sum of modCounts
    long last = 0 L; // previous sum
    int retries = -1; // first iteration isn't retry
    try {
        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) {
            // 倒过来读就好: 等待 notFull
            notFull.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 < capacity
    if (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（快照读，读写不互斥）都是弱一致性的表现
  • 并发高和一致性是矛盾的，需要权衡

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/881281.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Stable Diffusion不同部件拆分详解

Stable Diffusion不同部件拆分详解

看到很多文章对Stable Diffusion各种原理、详解等&#xff0c;但是么有看到有文章细拆里面各个子模块在做啥&#xff0c;怎么做的&#xff0c;所以就会遇到整体原理理解很透传&#xff0c;问到细节就卡住&#xff0c;这段时间细看了一下文章&#xff0c;对各个部分做一个拆解详…
阅读更多...
网络基础，协议，OSI分层，TCP/IP模型

网络基础，协议，OSI分层，TCP/IP模型

网络的产生是数据交流的必然趋势&#xff0c;计算机之间的独立的个体&#xff0c;想要进行数据交互&#xff0c;一开始是使用磁盘进行数据拷贝&#xff0c;可是这样的数据拷贝效率很低&#xff0c;于是网络交互便出现了&#xff1b; 1.网络是什么 网络&#xff0c;顾名思义是…
阅读更多...
【SQL Server】清除日志文件ERRORLOG、tempdb.mdf

【SQL Server】清除日志文件ERRORLOG、tempdb.mdf

数据库再使用一段时间后&#xff0c;日志文件会增大&#xff0c;特别是在磁盘容量不足的情况下&#xff0c;更是需要缩减&#xff0c;以下为缩减方法&#xff1a; 如果可以停止 SQL Server 服务&#xff0c;那么可以采取更直接的方式来缩减 ERRORLOG 和 tempdb.mdf 文件的大小…
阅读更多...
【IoTDB 线上小课 07】多类写入接口，快速易懂的“说明书”！

【IoTDB 线上小课 07】多类写入接口，快速易懂的“说明书”！

【IoTDB 视频小课】稳定更新中&#xff01;第七期来啦~ 关于 IoTDB&#xff0c;关于物联网&#xff0c;关于时序数据库&#xff0c;关于开源... 一个问题重点&#xff0c;3-5 分钟&#xff0c;我们讲给你听&#xff1a; 一条视频了解写入接口 了解我们的友友们&#xff0c;应该…
阅读更多...
centos 安装VNC，实现远程连接

centos 安装VNC，实现远程连接

centos 安装VNC&#xff0c;实现远程连接 VNC(Virtual Network Computing)是一种远程控制软件&#xff0c;可以实现通过网络远程连接计算机的图形界面。 服务器安装VNC服务 yum install -y tigervnc-server*启动VNC服务&#xff0c;过程中需要输入连接密码 vncserver :1查看…
阅读更多...
【chromedriver编译-绕过selenium机器人检测】

【chromedriver编译-绕过selenium机器人检测】

有小伙伴说使用selenium没能绕过机器人检测&#xff0c;盘他。 selenium机器人检测有2种&#xff0c;一是cdp检测&#xff0c;二是webdriver特征检测。cdp检测前面的博客已写过&#xff0c;这里就提下webdriver特征检测。一、selenium简介 Selenium 是一个强大的工具&#xff…
阅读更多...
硬件工程师笔试面试——开关

硬件工程师笔试面试——开关

目录 11、开关 11.1 基础 开关原理图 开关实物图 11.1.1 概念 11.1.2 常见的开关类型及其应用 11.2 相关问题 11.2.1 开关的工作原理是什么? 11.2.2 在设计一个电子系统时，如何选择最适合的开关类型? 11.2.3 不同类型的开关在实际应用中有哪些优势和局限性? 11.…
阅读更多...
css设置overflow:hiden行内元素会发生偏移的现象

css设置overflow:hiden行内元素会发生偏移的现象

父级元素包含几个行内元素 <div id"box"><p><span>按钮</span><span>测试文字文字文字测试文字文字文字</span><span>看这里</span></p></div>#box p{width: 800px;font-size: 30px;}#box p span{disp…
阅读更多...
Android 如何使用jdk命令给应用/APK重新签名。

Android 如何使用jdk命令给应用/APK重新签名。

写在前面&#xff1a;本篇文章介绍Windows命令行中&#xff0c;如何使用jdk命令给已经签过名的apk重新签名。 使用工具&#xff1a;jarsigner。jarsigner是jdk自带的工具&#xff0c;签名之前确保Windows电脑中已安装jdk。我的环境如下&#xff1a;   后续操作步骤如下&…
阅读更多...
【MySQL】了解并操作MySQL的缓存配置与信息

【MySQL】了解并操作MySQL的缓存配置与信息

目录 一、查看缓存配置 二、查看缓存信息 查询MySQL的缓存相关信息&#xff0c;一般我们用两个命令&#xff1a; show variables like %query_cache%; show status like %qcache%; 一、查看缓存配置 查看缓存配置的相关的系统变量变量&#xff0c;返回给我们服务器缓存的配置…
阅读更多...
Vue(13)——router-link

Vue(13)——router-link

router-link vue-router提供了一个全局组件router-link(取代a标签) 能跳转&#xff0c;配置to属性指定路径&#xff08;必须&#xff09;。本质还是a标签。默认会提供高亮类名&#xff0c;可以直接设置高亮样式 右键检查&#xff0c;发现多了两个类&#xff1a; 可以直接写样式…
阅读更多...
【React】React18.2.0核心源码解读

【React】React18.2.0核心源码解读

前言 本文使用 React18.2.0 的源码&#xff0c;如果想回退到某一版本执行git checkout tags/v18.2.0即可。如果打开源码发现js文件报ts类型错误请看本人另一篇文章&#xff1a;VsCode查看React源码全是类型报错如何解决。 阅读源码的过程&#xff1a; 下载源码 观察 package…
阅读更多...
IPD流程体系：IPD在硬件产品开发中的应用

IPD流程体系：IPD在硬件产品开发中的应用

目录 1、内容简介 2、开发各阶段介绍 3、PVT阶段 4、资源群更新 作者简介 1、内容简介 在硬件类相关产品的开发过程中&#xff0c; 每个阶段的工作都是需要按照一定的流程、规范和标准去进行的。 整体还是相对瀑布化的流程&#xff0c; 每个阶段的输入、输出、准入、准…
阅读更多...
第四天旅游线路预览——从贾登峪到喀纳斯景区入口（贾登峪游客服务中心）

第四天旅游线路预览——从贾登峪到喀纳斯景区入口（贾登峪游客服务中心）

第四天&#xff1a;从贾登峪到喀纳斯风景区入口&#xff0c;晚上住宿贾登峪&#xff1b; 从贾登峪到喀纳斯景区入口&#xff08;贾登峪游客服务中心&#xff09;&#xff1a; 搭乘贾登峪①路车&#xff0c;路过三湾到达景区换乘中心&#xff0c;路程时长约40分钟&#xff1b; …
阅读更多...
autodl连接xftp

autodl连接xftp

&#xff08;1&#xff09;首先打开xftp&#xff0c;新建会话 &#xff08;2&#xff09;给会话取个名字&#xff0c;然后填写主机和端口号 &#xff08;3&#xff09; 主机和端口号从autodl实例中找&#xff0c;登入指令那里 &#xff08;4&#xff09;点击复制&#xff0c;然…
阅读更多...
展锐平台的手机camera 系统开发过程

展锐平台的手机camera 系统开发过程

展锐公司有自己的isp 图像处理引擎&#xff0c;从2012 年底就开始在智能手机上部署应用。最初的时候就几个人做一款isp的从hal 到kernel 驱动的完整软件系统&#xff0c;分工不是很明确&#xff0c;基本是谁擅长哪些就搞哪些&#xff0c;除了架构和编码实现之外&#xff0c;另外…
阅读更多...
Kafka 基于SASL/SCRAM动态认证部署，kafka加账号密码登录部署

Kafka 基于SASL/SCRAM动态认证部署，kafka加账号密码登录部署

文章目录 前言下载 kafka安装启动zookeeper添加账号密码 启动kafka修改kafka配置文件增加jaas授权文件修改启动文件&#xff0c;启动kafka检查是否部署成功 offset explore 连接 前言 其实挺简单的几个配置文件&#xff0c;问大模型一直没说到点上&#xff0c;绕晕了。SASL/SC…
阅读更多...
【linux】4张卡，坏了1张，怎么办？

【linux】4张卡，坏了1张，怎么办？

先禁用这张卡 grub 禁用&#xff0c;防止加载驱动 禁用这张卡的 PCI # 禁用 PCI 设备 0000:b1:00.0 (NVIDIA GPU) ACTION"add", SUBSYSTEM"pci", ATTR{vendor}"0x10de", KERNELS"0000:b1:00.0", RUN"/bin/sh -c echo 0000:b1:00…
阅读更多...
数据技术进化史：从数据仓库到数据中台再到数据飞轮的旅程

数据技术进化史：从数据仓库到数据中台再到数据飞轮的旅程

随着大数据时代的到来&#xff0c;数据已经成为企业的核心资产之一。在过去几十年间&#xff0c;数据技术也随之不断演进&#xff0c;从早期的数据仓库到近年来热门的数据中台&#xff0c;再到正在快速发展的数据飞轮概念&#xff0c;每一步都是技术革新的体现。 一、数据仓库&…
阅读更多...
股价预测，非线性注意力更佳？

股价预测，非线性注意力更佳？

作者：老余捞鱼 原创不易，转载请标明出处及原作者。 写在前面的话： 本文探讨了在 transformer 模型中使用非线性注意力来预测股票价格的概念。我们讨论了黎曼空间和希尔伯特空间等非线性空间的数学基础，解释了为什么非线性建模可能是有利的，并提供了在代码中实现这种…
阅读更多...
最新文章

Copyright @ 2022~2023