引言

为避免轮询条件为真的开销，并发编程中常用等待通知模型来优化这一点，而本文将针对等待通知模型这一知识点进行深入剖析，希望对你有所启发。

你好，我是 SharkChili ，禅与计算机程序设计艺术布道者，希望我的理念对您有所启发。

📝 我的公众号：写代码的SharkChili
在这里，我会分享技术干货、编程思考与开源项目实践。

🚀 我的开源项目：mini-redis
一个用于教学理解的 Redis 精简实现，欢迎 Star & Contribute：
https://github.com/shark-ctrl/mini-redis (opens new window)

👥 欢迎加入读者群
关注公众号，回复 【加群】 即可获取联系方式，期待与你交流技术、共同成长！

同步锁下的等待通知模型

状态依赖性的管理

在经典的生产者和消费者模式中，我们经常用到ArrayBlockingQueue作为并发安全的有界缓存，而该有界缓解进行读写操作时都必须严格按照如下两个条件谓语时机执行，即：

1. 针对阻塞队列进行元素存操作时，有界缓存必须有空闲空间，即可非满
2. 针对阻塞队列进行取操作时，有界队列必须有元素，即非空

基于上述的说法，我们基于同步锁synchronized实现了一个数组形式的环形阻塞队列的核心方法模板，大体思路为：

1. 当进行元素存操作时，互斥调用doPut函数，判断是否到达数组末端，若到达则直接将元素存到索引0，并累加count
2. 进行元素取操作时，互斥上锁执行doTake，同样执行步骤1的边界判断，完成后扣减count
3. 基于count判断非空和非满

我们的环形有界队列是用数组实现的，所以笔者也用数组直观的展现这个流程，当然读者可以在逻辑上将数组首位相接，即可构成一个环形队列：

对应的笔者也给出这个环形队列的抽象模板，核心函数思路和上述基本一致，读者可结合图文注释了解大体流程，后文将基于该模板落地一个支持阻塞等待空闲通知线程存取元素的缓存队列：

public abstract class BaseBoundedBuffer<V> {
    private final V[] items;
    private int head;
    private int tail;
    private int count;

    /**
     * 初始化环形有界队列
     *
     * @param capacity 容量
     */
    protected BaseBoundedBuffer(int capacity) {
        items = (V[]) new Object[capacity];
    }

    protected synchronized final void doPut(V v) throws InterruptedException {
        //尾节点添加元素
        items[tail] = v;
        //如果到达数组末端，则重新从0开始
        if (++tail == items.length) {
            tail = 0;
        }
        //累加元素个数
        count++;
    }

    protected synchronized final V doTake() throws InterruptedException {
        //头节点取元素
        V v = items[head];
        //头节点置空实现删除
        items[head] = null;
        if (++head == items.length) {//如果到达边界，则循环从0开始
            head = 0;
        }
        //减元素个数
        count--;
        return v;
    }

    public synchronized final boolean isFull() {
        return count == items.length;
    }

    public synchronized final boolean isEmpty() {
        return count == 0;
    }
}

基于异常式的队列模型

我们先来看看第一个有界缓存的基本实现，一旦触发如下两个条件时，该缓存就会抛出异常：

1. 获取元素时队列空
2. 插入元素时队列满

对应落地代码如下，直接继承有界队列后落地落采用异常通知方式实现元素存取的缓存队列：

public class GrumpyBoundedBuffer extends BaseBoundedBuffer<Integer> {


    protected GrumpyBoundedBuffer(int capacity) {
        super(capacity);
    }

    public synchronized void put(int value) throws Exception {
        //队列满了，直接抛出异常
        if (isFull()) {
            throw new RuntimeException("queue is full");
        }
        //队列没满，正常入队
        doPut(value);

    }


    public synchronized int take() throws Exception {
        //队列为空，直接抛出异常
        if (isEmpty()) {
            throw new RuntimeException("queue is empty");
        }
        //队列不为空，正常出队
        return doTake();
    }


   

}

虽然这种方式使得缓存在实现非常的简单，但是这种方案对于使用者来说非常的不友好，在业务正常的情况下，即使存取消费的缓存在单位时间满即直接抛出异常告知线程不可存取，让使用者手动捕获异常进行重试：

public static void main(String[] args) {
        GrumpyBoundedBuffer grumpyBoundedBuffer = new GrumpyBoundedBuffer(1);
        ThreadUtil.execAsync(() -> {
            while (true) {
                try {
                    grumpyBoundedBuffer.put(1);
                } catch (Exception e) {
                    Console.error("队列已满，1s后重试");
                    ThreadUtil.sleep(1000);
                }
            }
        });
    }

输出结果如下所示，非常的不方便：

轮询检测式的等待唤醒

于是我们就考虑在队列存储上在一个重试的的机制，即当队列存取失败时，进行休眠重试，直到成功后返回。

但是对于程序的性能表现而言，也是一种灾难，这种做法设计释放锁之后的休眠和循环重试，这就使得设计者需要在CPU使用率和响应性之间做好权衡：

1. 如果设置休眠时间相对短，那么重试就会尽可能快，响应性就会越高，但是循环带来的CPU资源的开销却急剧增加。
2. 如果休眠时间设置过长，有概率完成任务处理，但是却来响应的延迟。

public class SleepyBoundedBuffer extends BaseBoundedBuffer<Integer> {


    protected SleepyBoundedBuffer(int capacity) {
        super(capacity);
    }

    /**
     * 轮询重试，直到成功
     *
     * @param value
     * @throws InterruptedException
     */
    public synchronized void put(int value) throws InterruptedException {
        while (true) {
            synchronized (this) {
                if (!isFull()) {
                    doPut(value);
                }

            }
            Console.log("队列已满，500ms后重试");
            ThreadUtil.sleep(500);
        }

    }


    public synchronized int take() throws InterruptedException {

        while (true) {
            synchronized (this) {
                if (!isEmpty()) {
                    return doTake();
                }
            }
            Console.log("队列已空，500ms后重试");
            ThreadUtil.sleep(500);
        }
    }

   

}

这种方案一定程度解决用户手动捕获异常重试的繁琐，但也存在着如下缺点：

1. 重试时休眠间隔500ms可能太长也可能太短，固定值等待非常不合理
2. 频繁循环重试使得线程大量时间得到CPU时间片做一些无用功
3. 重试多次无果后无法中断

基于条件等待的有界缓存

所以我们需要进行进一步的优化即通过如下两个列条件谓语避免线程无用的轮询开销：

1. 当队列满的时候，当前存线程阻塞等待，直到队列非空时被唤醒
2. 当队列空的时候，取线程阻塞等待，知道队列有元素时将其唤醒

总结起来就是一句话，非满的时候唤醒存线程尝试存元素，非空的时候通知取线程取元素，由此得出如下两个条件谓语isNotFull和isNotEmpty:

所以我们需要以object中对应的wait、notify和notifyAll构成内部条件队列的交互通知，当然要调用这些通知方法的前提也就是需要获取当前这个对象的锁。

以我们有界缓存存元素操作为例，我们执行添加操作时执行步骤为：

1. 获得这个对象的锁
2. 当发现缓存空间已满即不符合检测条件时，则调用当前对象(有界缓存)的wait方法将当前线程挂起
3. 与此同时，线程也会释放这把锁，等待队列非满时通过notify或者notifyAll尝试将当前线程唤醒。

对应我们给出代码示例，这种方式相比于休眠的方案，改进了响应的效率和CPU使用率的开销，避免了非必要的检测步骤:

public class BoundedBuffer extends BaseBoundedBuffer<Integer> {
    protected BoundedBuffer(int capacity) {
        super(capacity);
    }


    public synchronized void put(int value) throws InterruptedException {
        if (isFull()) {
            Console.log("队列已满，等待");
            wait();
        }
        Console.log("队列非满，开始写入");
        doPut(value);

        //通知阻塞线程消费
        notifyAll();

    }

    public synchronized int take() throws InterruptedException {
        if (isEmpty()) {
            Console.log("队列已空，等待");
            wait();
        }

        int value = doTake();
        //通知阻塞线程写入    
        notifyAll();

        return value;
    }
}

对应的笔者以线程调试模式给出下面这段代码，在首先让线程1执行两次写操作,查看是否在第二次阻塞是否会在消费者线程消费后存入，所以笔者也会在两个线程执行完毕后，判断队列非空来查看是否实现这一点：

 //创建一个容量为1的缓冲区
        BoundedBuffer boundedBuffer = new BoundedBuffer(1);

        CountDownLatch countDownLatch = new CountDownLatch(2);

        //启动写入线程第一次写入成功，第二次写入阻塞，直到消费者线程完成消费
        new Thread(() -> {
            try {
                boundedBuffer.put(1);
                boundedBuffer.put(2);
                countDownLatch.countDown();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }).start();

        new Thread(() -> {
            try {
                ThreadUtil.sleep(1000);
                Console.log("take:{}", boundedBuffer.take());
                countDownLatch.countDown();
            } catch (InterruptedException e) {
                throw new RuntimeException();
            }
        }).start();

        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        //通过非空函数判断线程1第二个元素是否存成功
        Console.log("main线程结束：{}", boundedBuffer.isEmpty());

对应输出结果如下，可以看到第二次写入因为队列满而阻塞，一旦消费者完成消费后，生产者就立刻被唤醒写入：

关于条件谓词的一些探讨

条件谓词的使用方式

要想正确的使用条件队列，就需要正确的抓住线程与条件谓语之间的关联，保证合适的条件下当线程添加至条件队列，并在合适的时机将其唤醒，以我们的本文一直在强调的有界队列：

1. 对于put方法来说：只有条件非满的情况下，才能添加元素至队列
2. 对于take方法来说，只有条件非空的情况下，才能取出元素

同时，每一次wait的调用都会将调用者隐式的和条件队列加以关联，例如:

1. 调用有界缓存的take方法时，若没有元素，当前线程调用wait阻塞存入监视锁底层的waitSet
2. 调用有界缓存put方法时，若空间已满，当前线程调用wait存入监视锁底层的waitset

当然这一切的都有一个前提，即调用者已经获取到的当前wait方法对应的对象的监视锁，这是并发互斥中等待通知模型有序协调的一个必要条件：

过早的唤醒或错误唤醒

对条件队列有了基本的概念之后，我们再来更进一步的探讨这套设计理念，实际上按照目前的设计来看，这套等待唤醒模型还是存在一定的缺陷，即多条件关联单监视锁导致的错误唤醒问题。

举个例子，假设基于我们要上述的有界缓存队列，我们打算增加一个关闭有界缓存的操作，即直接起一个线程查看shutdownFlag如果为false则挂起等待，当其他线程将shutdownFlag设置为true的时候将其唤醒,对应的我们也给出下面这样一段代码：

public synchronized void shutdown() {
        isShuttingDown = true;
        notifyAll();
    }

    private volatile boolean isShuttingDown = false;
    public synchronized void shutdownIfInNeed() throws InterruptedException {
        if (isShuttingDown == false) {
            wait();
            Console.log("关闭线程被唤醒");
        }

        //执行阻塞队列中断和关闭所有线程的操作
        //......
    }

对此我们试想这样一个情况，我们现在有一个上界为1的有界队列，对应3个线程按如下顺序执行：

1. 消费者线程尝试从有界缓存获取元素，阻塞等待唤醒
2. 停止线程发现停止标识为false，阻塞等待唤醒
3. 生产者线程存入元素，队列有新元素，调用notifyall通知消费者消费

重点来了，停止线程和消费者线程都处于当前监视锁的等待队列中，所以notifyall操作可能会误唤醒停止线程将队列消费和所有线程中断造成系统崩溃。

除此之外处于wait的线程还可能会被错误的唤醒即没有任何征兆的情况下苏醒被CPU时间片执行，引用《java并发编程实战中》的说法：

以 “早餐” 烤面包机烤面包完成后通知人们食用为例 ， 这就好⽐烤⾯包机的线 路 连 接 有 问 题 ， 有时候当⾯包还未烤 时 ， 铃声 就 响起来了

对应的我们也给出这个案例的代码：

public static void main(String[] args) {
        //创建一个容量为1的缓冲区
        BoundedBuffer boundedBuffer = new BoundedBuffer(1);

        CountDownLatch countDownLatch = new CountDownLatch(2);

        new Thread(() -> {
            try {
                //线程0取元素阻塞
                Console.log("take:{}", boundedBuffer.take());
                countDownLatch.countDown();
            } catch (InterruptedException e) {
                throw new RuntimeException();
            }
        }, "t0").start();


        new Thread(() -> {
            try {
                //线程1查看停止信号为false阻塞
                boundedBuffer.shutdownIfInNeed();
                countDownLatch.countDown();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }, "t1").start();


        new Thread(() -> {
            try {
                //线程2put操作队列非空执行通知操作，导致停止线程被错误的唤醒
                boundedBuffer.put(1);
                countDownLatch.countDown();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
        }, "t2").start();

        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
        
        Console.log("main线程结束：{}", boundedBuffer.size());

    }

输出结果如下，可以看到在生产者生产元素后的通知动作，把关闭线程给唤醒了，这就是经典的错误唤醒：

队列已空，take线程:t0等待
队列非满，开始写入
关闭线程被唤醒
take线程 t0被唤醒
take:-1
main线程结束：1

本质原因就是一个监视锁中的队列关联多个条件，使得在多条件的等待通知场景下存在错误通知的情况，考虑到这一点，无论是对于put、take还是shutdown方法，我们都需要进行改进，确保：

1. 生产者被唤醒后，进行必要的非满检查，且只有将空队列存入元素后通知消费者
2. 消费者被唤醒后，进行必要的非空检查，只有将非空队列消费空之后，通知生产者
3. shutdown线程被唤醒后，进行必要的状态标识检查，只有状态标识为true才能停止线程

改进后的代码如下所示，可以看到笔者将if条件判断后wait的操作改为while+wait操作确保唤醒后的再确认：

public synchronized void put(int value) throws InterruptedException {
        while (isFull()) {//条件触发时循环检测一下
            wait();
        }
        //空变为非空
        boolean wasEmpty = isEmpty();
        doPut(value);

        if (wasEmpty) {//仅当空变为非空时才通知
            notifyAll();
        }
    }

    public synchronized int take() throws InterruptedException {
        while (isEmpty()) {
            wait();
        }
        //满变为非满才通知
        boolean wasFull = isFull();
        int value = doTake();
        if (wasFull) {
            notifyAll();
        }
        return value;
    }


    public synchronized void shutdownIfInNeed() throws InterruptedException {
        while (isShuttingDown == false) {
            wait();
            Console.log("关闭线程被唤醒");
        }

        //执行阻塞队列中断和关闭所有线程的操作
        //......
    }

notify下的信号丢失问题

我们再来说说通知的哲学，刚接触java这门语言的时候，都会了解到notify和notifyAll的区别，这一点我们也可以直接从源码的注释上了解这一点，即前者仅仅通知监视锁下的单个线程而后者则是所有线程：

1. notify:Wakes up a single thread that is waiting on this object's monitor.
2. notifyAll:Wakes up all threads that are waiting on this object's monitor. A thread waits on an object's monitor by calling one of the wait methods.

所以这也就是为什么笔者在实现上述通知这个动作的时候，使用的是notifyAll而非notify,即notify存在信号丢失问题，还是用我上述的生产者-消费者和异步关闭线程的例子，试想下述场景：

1. 有界队列元素空间为1
2. 线程1取元素为空，阻塞
3. 线程2查看停止标识为false，阻塞
4. 线程0添加元素，元素非空，notify选中了线程2
5. 本该处理元素的线程1因为没收到通知，造成了一种信号丢失的情况

这本质就是同步锁和wait以及条件谓语上一种设计缺陷，即一个同步锁只能关联一组条件队列，而条件队列无法做区分。

所以基于上述条件队列的案例，我们通过条件通知的方式进行比对保证更高效的准确的通知，避免每次操作之后都非常激进的通知所有线程造成非必要的上下文切换开销，当然读者在进行这样的优化时务必记得，只有保证程序可以使用的情况下，在进行优化的哲学：

基于条件变量下的等待通知模型

内置队列存在一个内置锁关联多个条件队列的情况，这使得很多线程被错误的唤醒，导致非必要的CPU时钟消耗和上下文切换和并发竞争锁的开销。针对上述的问题，我们必须到借由一种工具保证同一把锁下的各个条件的线程都放置到不同的队列中，从而保证正确的唤醒，即：

1. 等待队列非满的生产者线程存到一个队列，待消费者完成元素消费后通知这个队列
2. 等待队列非空的消费者线程存到一个等待队列，待生产者完成元素投递后通知这个队列

所以，通过juc包下的锁即可实现将条件放到不同的条件队列中，同时它还能可以实现队列内部公平的唤醒，以保证等待唤醒模型调度的有序性，以及减小非必要的上下文切换的开销：

public class ConditionBoundedBuffer<V> {


    private final V[] items;
    private int head;
    private int tail;
    private int count;
    //下述两个条件队列关联同一把锁，线程按照各自条件与队列关联
    private final ReentrantLock lock = new ReentrantLock();
    //生产者等待队列非满的等待队列
    private final Condition notFull = lock.newCondition();
    //消费者等待队列非空的等待队列
    private final Condition notEmpty = lock.newCondition();

    public ConditionBoundedBuffer(int capacity) {
        this.items = (V[]) new Object[capacity];
    }


    public boolean isFull() {
        return count == items.length;
    }

    public boolean isEmpty() {
        return count == 0;
    }


    public void put(V v) throws InterruptedException {
        lock.lock();
        try {

            while (isFull()) {//轮询检测非满
                notFull.await();
            }
            //添加元素
            items[tail++] = v;
            count++;
            if (tail == items.length) {
                tail = 0;
            }
            notEmpty.signal();


        } finally {
            lock.unlock();
        }
    }


    public V take() throws InterruptedException {

        lock.lock();
        try {
            while (isEmpty()) {//轮询检测非空
                notEmpty.await();
            }
            //消费元素
            V v = items[head];
            items[head] = null;
            head++;
            count--;
            if (head == items.length) {
                head = 0;
            }
            notFull.signal();
            return v;
        } finally {
            lock.unlock();
        }
    }


  

}

对应的我们也给出压测代码，最终断言也是正确的：

ConditionBoundedBuffer<Integer> conditionBoundedBuffer = new ConditionBoundedBuffer<>(1);

        ExecutorService threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors() + 1);


        for (int i = 0; i < 100_0000; i++) {
            //提交1一个元素
            threadPool.execute(() -> {
                try {
                    conditionBoundedBuffer.put(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            //消费一个元素
            threadPool.execute(() -> {
                try {
                    conditionBoundedBuffer.take();

                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
        }

        threadPool.shutdown();
        while (!threadPool.isTerminated()) {
        }
        //判断并发下线程是否正确的对等生产和消费
        Assert.equals(conditionBoundedBuffer.count, 0);

小结

自此我们针对并发编程中的等待通知模型中的状态管理，等待通知原则和技巧进行了深入的分析和演示，希望对你有帮助。

你好，我是 SharkChili ，禅与计算机程序设计艺术布道者，希望我的理念对您有所启发。

📝 我的公众号：写代码的SharkChili
在这里，我会分享技术干货、编程思考与开源项目实践。

🚀 我的开源项目：mini-redis
一个用于教学理解的 Redis 精简实现，欢迎 Star & Contribute：
https://github.com/shark-ctrl/mini-redis (opens new window)

👥 欢迎加入读者群
关注公众号，回复 【加群】 即可获取联系方式，期待与你交流技术、共同成长！

参考

《java并发编程实战》