14_条件队列

条件队列

一、状态依赖性管理

1.1、前提条件

类中一般有很多依赖于状态的方法，只有满足某些条件时才能正常执行。

比如说，在有界队列中的方法：

• put 方法调用前，必须满足 !isFull() 条件
• take 方法调用前，必须满足 !isEmpty() 条件

像 !isFull()、!isEmpty() 这种被操作依赖的状态条件，称为前提条件。

前提条件中可能包含一个或多个状态变量：

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

前提条件 isEmpty() 这里就包含了一个状态变量：size。

1.2 前提条件的处理

对于单线程程序而言，当前提条件不满足时，都是直接从该方法返回；

但是对于并发程序而言，前提条件不满足的情况下，可以有其他选择方案：

• 前提条件失败，可以直接返回
• 前提条件失败，可以一直等待条件变为真

并发程序中，前提条件可以等待的要求就是：线程之间共享状态变量。

• 线程在等待前提条件变为真，而变为真的情况只能是被其他线程修改了状态变量

因此，对于前提条件的要求如下：

• 前提条件中涉及的状态变量，必须由对象的锁来保护，否则会有线程安全性问题
• 等待前提条件变为真的线程，必须释放对象的锁，否则其他线程无法修改状态变量

前提条件的等待实现，有2种方式：

• 非阻塞的轮询
• 阻塞的等待

二、非阻塞的轮询

2.1 将前提条件的失败传递给调用者

前提条件失败，最简单的处理方式就是：直接返回失败。

public synchronized void put(V item) {
    if (isFull()) {
        throw new IllegalStateException("Queue full");
    }
    doPut(item);
}

当前提条件失败后，调用者将收到异常。

但是，如果调用者想要一直等待到前提条件变为真，就必须自己处理异常和重试：

while (true) {
    try {
        put(item);
        break;
    } catch (IllegalStateException e) {
        // 等待前提条件变为真
    }
}

这种方式称为忙等待或者自旋等待，会消耗大量的 CPU 时间。

不过，这种方式还可以使用休眠来进行优化：

while (true) {
    try {
        put(item);
        break;
    } catch (IllegalStateException e) {
        // 休眠一会，避免消耗大量的 CPU 时间
        Thread.sleep(SLEEP_TIME);
    }
}

但存在一个问题，休眠可能会导致系统的响应性变差。

因为在休眠期间，前提条件可能变为真了，但是线程还处于休眠状态，无法执行。

2.2 通过轮询与休眠来实现简单的阻塞

由调用者来负责处理异常和重试，调用的代码会变得非常复杂。

为了减低调用者的代码重复率和复杂度，可以将重试移入方法中：

public void put(V item) throws InterruptedException {
    while (true) {
        synchronized (this) {
            if (!isFull()) {
                doPut(item);
                return;
            }
        }
        // 休眠一会，避免消耗大量的 CPU 时间
        Thread.sleep(SLEEP_TIME);
    }
}

将代码迁入方法内后，调用者那边就变简单了，只需要调用接口即可。

不过这种方式依旧存在响应性问题。

2.3 非阻塞方式的弊端

非阻塞方式实现的前提条件等待弊端有：

• 自旋等待会消耗大量的 CPU 时间
• 定时休眠会导致系统的响应性变差

每次失败都会休眠一段时间，如果休眠期间前提条件变为真了，但还是要等休眠结束后，才会继续执行。

三、阻塞的条件队列

3.1 条件队列

条件队列是通过一种等待-通知的方式，用来解决非阻塞方式的弊端。

• 当前提条件失败时，线程进入阻塞等待状态
• 当前提条件满足后（其他线程修改状态后），通知唤醒等待线程

通过等待-通知的方式，避免了自旋等待和定时休眠的问题。

实际上，等待-通知方式的原理就是：

• 阻塞等待时，将当前线程放入锁对象的一个队列中
• 通知唤醒时，从锁对象队列中取出一个或多个线程，让它们继续执行

在等待-通知过程中用到的队列，就称为条件队列。

3.2 条件谓词（前提条件）

条件谓词，就是指的被某个操作依赖的前提条件，它是由类中各个状态变量构成的表达式。

比如条件谓词（前提条件） isEmpty()：

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

用到的状态变量就是 size。

在设计一个依赖于状态的类时，必须找出类中的条件谓词和依赖于条件谓词的操作。

比如之前提到的：

• 依赖操作：put()、take()
• 条件谓词：isEmpty()、isFull()
• 状态变量：size

统计完后，这些操作中涉及到的条件谓词、变量代码都需要加锁处理。

3.3 内置条件队列

在 Java 中，每个对象都内置有一个条件队列。

操作内置条件队列，需要执行特定的方法。比如说：

public void put(V item) throws InterruptedException {
    synchronized (this) {
        while (isFull()) {
            wait(); // 进入内置条件队列阻塞等待
        }
        doPut(item);
        notifyAll(); // 通知唤醒内置条件队列中的线程
    }
}

当执行 wait() 方法之后，实际上就会进入 this 对象的内置条件队列。

而执行 notifyAll() 方法之后，就会唤醒所有在内置条件队列中的线程。

内置条件队列，底层是由 JVM 来实现和维护的，所以无需写 Java 代码去管理。

3.4 显式条件队列

除了内置锁，Java 中还提供了显式锁 Lock，它的作用和内置锁是一样的。

显式锁也有自己的条件队列：

final Lock lock = new ReentrantLock();

public void put(V item) throws InterruptedException {
    lock.lock();
    try {
        while (isFull()) {
            lock.await(); // 进入显式条件队列阻塞等待
        }
        doPut(item);
        lock.signalAll(); // 通知唤醒显式条件队列中的线程
    } finally {
        lock.unlock();
    }
}

显式条件队列和内置条件队列的区别是：

• 内置条件队列，是由 JVM 来实现和维护的；而显式锁的条件队列是由锁类自己实现的
• 内置条件队列，只能有一个；而显式锁的条件队列可以有多个
• 内置锁的条件等待是不可中断的；而显示锁的条件等待是可以中断的
• 内置的条件队列是非公平的；而显式的条件队列提供了公平和非公平两种方式

比如说，显示锁支持多个条件队列：

final Lock lock = new ReentrantLock();
final Condition notFull = lock.newCondition();
final Condition notEmpty = lock.newCondition();

public void put(V item) throws InterruptedException {
    lock.lock();
    try {
        while (isFull()) {
            notFull.await(); // notFull 条件队列
        }
        doPut(item);
        notEmpty.signalAll(); // notEmpty 条件队列
    } finally {
        lock.unlock();
    }
}

这里就用了 2 个显式条件队列，分别是 notFull 和 notEmpty。

3.5 条件队列和轮询

阻塞的条件队列和非阻塞的轮询，在本质上还是一样的：

• 条件队列并没有改变轮询的语义
• 条件队列只是对轮询进行了优化：CPU 效率、上下文切换开销和响应性

条件队列只是使得前提条件的等待方式变得更高效了。

四、条件队列的使用

4.1 加锁后操作

条件队列，是绑定在等待对象上的，所以对条件队列的操作，都必须先拿到对象的锁。

public void put(V item) throws InterruptedException {
    // 先拿到对象的锁
    synchronized (lock) {
        while (isFull()) {
            // 在锁对象的条件队列上阻塞等待
            lock.wait();
        }
        doPut(item);
        lock.notifyAll();
    }
}

操作条件队列，不管是出队还是入队，都需要先获取对象的锁。

对于内置条件队列而言，wait()、notifyAll() 方法就是入队和出队的操作。

所以 wait() 方法和 notifyAll() 方法必须在获取对象锁之后才能执行。

4.2 循环等待条件

线程被唤醒后，必须重新校验条件谓词，避免是伪唤醒：

• 条件队列可以被多个条件谓词使用，比如 isEmpty() 和 isFull() 可以共用同一个条件队列
• 线程从开始唤醒到真正执行这段时间内，条件谓词有可能从真变为了假

基于各种情况，线程唤醒后，应该再重新验证一下条件谓词，否则可能会出现线程安全问题。

不要使用这种非循环等待的方式：

public void put(V item) {
    synchronized (this) {
        if (isFull()) { // 应该用 while 循环
            wait();
        }
        doPut(item);
        notifyAll();
    }
}

因为你永远不知道，为什么线程会被唤醒，比如这种无条件唤醒：

// 假设此时阻塞了
queue.put(item);

// 没有条件，直接唤醒所有线程
synchronized (queue) {
    queue.notifyAll();
}

线程完全不知道，是在什么情况下被唤醒的，它只知道被唤醒了而已。

如果唤醒后直接执行后续代码，有可能条件是不满足的，所以应该采用循环等待的方式。

4.3 锁对象必须是同一个

不同的对象，拥有各自不同的条件队列。

前提条件用到的锁对象，必须和条件队列绑定的锁对象是同一个。

比如说：

public void put(V item) {
    synchronized (lock1) {
        if (isFull()) {
            lock2.wait();
        }
        doPut(item);
        lock3.notifyAll();
    }
}

假如执行了 lock2.wait() 方法，那么线程就会被阻塞，并进入 lock2 的条件队列中。

线程进入了阻塞，而此时线程还拿着 lock1 的锁没有释放，因为线程阻塞后释放的是 lock2 的锁。

这就导致，其他线程完全没有办法执行 put() 方法了。

除此以外，状态变量不是由同一个锁保护，还可能出现死锁、并发安全等问题。

4.4 避免信号丢失

信号丢失，是指线程在等待一个已经发生过的信号。

唤醒可以分为 2 种方式：

• notify：随机唤醒条件队列中的一个线程
• notifyAll：唤醒条件队列中的所有线程

其中，使用 notify 唤醒1个线程时，有可能导致信号丢失。

• 一个条件队列可以绑定多个条件谓词
• 唤醒随机时，就不知道是唤醒的是哪个条件谓词相关的线程
• 可能通知信号被其他条件谓词的线程劫持了，从而导致真正需要的线程无法唤醒

举个栗子：

1. 线程 A 在等待条件 PA；线程 B 在等待条件 PB
2. 此时条件 PA 满足了，然后调用 notify() 方法唤醒，结果唤醒的是线程 B
3. 线程 B 一看，自己的 PB 条件还未满足，又阻塞去了
4. 结果导致线程 A 没有收到唤醒信号

所以，如果想使用 notify() 方法，必须满足以下条件：

• 条件队列关联的条件谓词是一样的
• 所有等待线程的类型都相同
• 单进单出，每次只有1个线程来执行

建议，优先使用 notifyAll() 方法，除非使用 notifyAll() 方法出现了性能问题。

notifyAll() 方法会唤醒所有等待线程，因此会带来一些性能问题：

• 可能会出现大量的上下文切换
• 可能会出现大量的锁竞争

比如说，n 个等待线程，使用 notifyAll() 可能会导致 O(n^2) 次唤醒操作，但实际只需要 n 次而已。

不过，可以使用条件通知来稍微优化一下 notifyAll()：

public void put(V item) {
    synchronized (this) {
        if (isFull()) {
            wait();
        }
        boolean wasEmpty = isEmpty();
        doPut(item);
        if (wasEmpty) {
            notifyAll();
        }
    }
}

实际上，单次通知 notify() 和条件通知，都是对 notifyAll() 的优化。

但是这 2 种优化在使用时很容易写错，所以应该考虑清楚后再使用。

4.5 子类继承

当父类使用单次通知或条件通知时，子类可能会变得比较复杂。

• 子类可能会违背单次通知和条件通知的原则

也就是说，单次通知和条件通知都是限制了特定情况下触发的，如果子类变更了这类需求，就有可能导致信号丢失等问题。

• 子类如果破坏了单次通知和条件通知，那么子类需要自己增加合适的通知机制，比如使用 notifyAll

对于状态依赖且使用条件队列的类，其设计原则应该满足：

• 要么等待-通知等协议完全向子类公开，协议需写入正式文档
• 要么完全阻止子类参与等待-通知等过程

因为等待-通知机制是很容易出错的，所以设计时需谨慎。

• 公开给子类实现：将父类的协议规定写入文档，让子类按文档要求实现
• 禁止子类参与等待-通知过程：将条件队列、锁、状态变量等隐藏起来，使得子类看不见

实际上就是，要么完全由子类自己实现等待-通知，要么完全由父类实现等待-通知。

4.6 入口协议和出口协议

对于依赖状态或影响状态的操作，都应该定义好入口协议和出口协议：

• 入口协议：即该操作的条件谓词（前提条件）
• 出口协议：即该操作修改的状态所影响到的条件谓词

比如说，操作 put 的出入口协议：

入口协议：isEmpty()
出口协议：isFull()

在实际使用时，应该这样：

• 入口协议不满足时，进入条件队列等待阻塞
• 出口协议满足时，通知条件队列唤醒线程

用代码来表示，大概就是这样：

public void put(V item) {
    lock.lock();
    try {
        // 入口协议，不满足时进入条件队列等待
        while (isFull()) {
            notFull.await();
        }

        doPut(item);

        // 出口协议，满足后通知条件队列唤醒线程
        notEmpty.signalAll();
    } finally {
        lock.unlock();
    }
}

另外，应该将入口协议和出口协议写入正式文档。

总结

前提条件：

• 前提条件：被操作方法依赖的状态条件，可能包含一个或多个状态变量
• 对于并发程序而言，在前提条件不满足的情况下，可以有不同的处理方案
  • 前提条件失败，可以直接返回
  • 前提条件失败，可以一直等待条件变为真
• 线程在等待前提条件变为真，而变为真的情况只能是被其他线程修改了状态变量
• 前提条件中涉及的状态变量，必须由对象的锁来保护，否则会有线程安全性问题
• 等待前提条件变为真的线程，必须释放对象的锁，否则其他线程无法修改状态变量
• 前提条件的等待实现，有2种方式：
  • 非阻塞的轮询
  • 阻塞的等待

轮询等待（忙等待、自旋等待）：

• 轮询等待直到前提条件变为真，就必须自己处理异常和重试
• 轮询等待的弊端：
  • 自旋等待会消耗大量的 CPU 时间
  • 定时休眠会导致系统的响应性变差

条件队列：

• 条件队列是通过一种等待-通知的方式，用来解决非阻塞方式的弊端

  • 当前提条件失败时，线程进入阻塞等待状态
  • 当前提条件满足后（其他线程修改状态后），通知唤醒等待线程

• 条件队列：在等待-通知过程中用到的队列

• 条件谓词：就是指的被某个操作依赖的前提条件

内置条件队列：

• 在 Java 中，每个对象都内置有一个条件队列
• 执行 wait()、notify()、notifyAll() 方法，实际就是内置条件队列的出入队操作
• 内置的条件队列，底层是由 JVM 来实现和维护的，所以无需写 Java 代码去管理

显式条件队列：

• 除了内置锁，Java 中还提供了显式锁 Lock，它的作用和内置锁是一样的
• 内置条件队列，是由 JVM 来实现和维护的；而显式锁的条件队列是由类自己实现的
• 内置条件队列，只能有一个；而显式锁的条件队列可以有多个
• 内置锁的条件等待是不可中断的；而显示锁的条件等待是可以中断的
• 内置的条件队列是非公平的；而显式的条件队列提供了公平和非公平两种方式

条件队列和轮询的区别：

• 条件队列并没有改变轮询的语义
• 条件队列只是对轮询进行了优化：CPU 效率、上下文切换开销和响应性
• 条件队列只是使得前提条件的等待方式变得更高效了

条件队列的使用：

• 加锁后操作：操作条件队列，不管是出队还是入队，都必须要先获取对象的锁
• 循环等待条件：线程被唤醒后，必须重新校验条件谓词，避免是伪唤醒
• 锁对象必须是同一个：前提条件用到的锁对象，必须和条件队列绑定的锁对象是同一个
• 避免信号丢失：优先使用 notifyAll() 方法
• 子类继承：要么完全由子类自己实现等待-通知，要么完全由父类实现等待-通知
• 入口协议和出口协议：
  • 入口协议：即该操作的条件谓词（前提条件）
  • 出口协议：即该操作修改的状态所影响的条件谓词