Java常见的阻塞队列总结
作者：盼兮猫 发布时间：2022-10-03 10:12:06
Java阻塞队列
阻塞队列和普通队列主要区别在阻塞二字：
阻塞添加：队列已满时，添加元素线程会阻塞，直到队列不满时才唤醒线程执行添加操作
阻塞删除：队列元素为空时，删除元素线程会阻塞，直到队列不为空再执行删除操作
常见的阻塞队列有 LinkedBlockingQueue 和 ArrayBlockingQueue，其中它们都实现 BlockingQueue 接口，该接口定义了阻塞队列需实现的核心方法：
public interface BlockingQueue<E> extends Queue<E> {
// 添加元素到队尾，成功返回true，队列满抛出异常 IllegalStateException
boolean add(E e);
// 添加元素到队尾，成功返回 true，队列满返回 false
boolean offer(E e);
// 阻塞添加
void put(E e) throws InterruptedException;
// 阻塞添加，包含最大等待时长
boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
// 阻塞移除队顶元素
E take() throws InterruptedException;
// 阻塞移除队顶元素，包含最大等待时长
E poll(long timeout, TimeUnit unit) throws InterruptedException;
// 返回可以添加到队列不阻塞的最大数量
int remainingCapacity();
// 如果存在元素则删除，成功返回 true，失败返回 false
boolean remove(Object o);
// 是否包含某元素
public boolean contains(Object o);
// 批量移除元素并添加入指定集合
int drainTo(Collection<? super E> c);
// 批量移除包含最大数量
int drainTo(Collection<? super E> c, int maxElements);
}
除了上面的方法，还有三个继承自 Queue 接口的方法常常被用到：
// 获取队列头元素，不删除，没有抛出异常 NoSuchElementException
E element();
// 获取队列头元素，不删除，没有返回 null
E peek();
// 获取并移除队列头元素，没有返回 nul
E poll();
根据具体作用，方法可以被分为以下三类：
添加元素类：add() 成功返回 true，失败抛异常、offer() 成功返回 true，失败返回 false，可以定义最大等待时长、put() 阻塞方法
删除元素类：remove() 成功返回 true，失败返回 false、poll() 成功返回被移除元素，为空返回 null、take() 阻塞方法
查询元素类：element() 成功返回元素，否则抛出异常、peek() 返回对应元素或 null
根据方法类型又可以分为阻塞和非阻塞，其中 put()、take() 是阻塞方法，带最大等待时长的 offer() 和 poll() 也是阻塞方法，其余都是非阻塞方法，阻塞队列基于上述方法实现
ArrayBlockingQueue 基于数组实现，满足队列先进先出特性，下面我们通过一段代码初步认识：
public class ArrayBlockingQueueTest {
ArrayBlockingQueue<TestProduct> queue = new ArrayBlockingQueue<TestProduct>(1);
public static void main(String[] args) {
ArrayBlockingQueueTest test = new ArrayBlockingQueueTest();
new Thread(test.new Product()).start();
new Thread(test.new Customer()).start();
}
class Product implements Runnable {
@Override
public void run() {
while (true) {
try {
queue.put(new TestProduct());
System.out.println("生产者创建产品等待消费者消费");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Customer implements Runnable {
@Override
public void run() {
while (true) {
try {
Thread.sleep(1000);
queue.take();
System.out.println("消费者消费产品等待生产者创建");
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class TestProduct {
}
}
上述代码比较简单，在一个容量为1的阻塞队列中，生产者和消费者由于容量限制依次阻塞运行。
ArrayBlockingQueue 基于 ReentrantLock 锁和 Condition 等待队列实现，因此存在公平和非公平的两种模式。公平场景下所有被阻塞的线程按照阻塞顺序执行，非公平场景下，队列中的线程和恰好准备进入队列的线程竞争，谁抢到就是谁的。默认使用非公平锁，因为效率更高：
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();
}
从代码可以看出，ArrayBlockingQueue 通过一个 ReentrantLock 锁以及两个 Condition 等待队列实现，它的属性如下：
public class ArrayBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable {
// 保存数据的数组
final Object[] items;
// 移除元素的索引
int takeIndex;
// 添加元素的索引
int putIndex;
// 元素数量
int count;
// 用于并发控制的锁
final ReentrantLock lock;
// 不为空，用于take()操作
private final Condition notEmpty;
// 不满，用于put()操作
private final Condition notFull;
// 迭代器
transient Itrs itrs = null;
}
从代码可以看出，ArrayBlockingQueue 使用同一个锁、移除元素和添加元素通过数组下标的方式记录，分表表示队列头和队列尾。通过两个等待队列分别阻塞 take() 和 put() 方法，下面我们直接看源码：
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
public boolean offer(E e) {
// 检查是否为空
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 判断队列是否已满
if (count == items.length)
return false;
else {
enqueue(e);
return true;
}
} finally {
lock.unlock();
}
}
private void enqueue(E x) {
final Object[] items = this.items;
// 赋值保存数据
items[putIndex] = x;
// 循环复用空间
if (++putIndex == items.length)
putIndex = 0;
count++;
// 唤醒take线程
notEmpty.signal();
}
从代码可以看出：add() 方法基于 offer() 方法实现，offer() 方法添加失败返回 false 后，add() 方法抛出异常。offer() 方法会加锁，保证线程安全，队列没满时执行入队操作，入队操作通过操作数组实现，并且通过循环复用数组空间。元素添加成功后队列不为空，调用 signal() 方法唤醒移除元素的阻塞线程，最后我们看 put() 方法：
public void put(E e) throws InterruptedException {
// 判断不为空
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
// 队列满就挂起在等待队列
while (count == items.length)
notFull.await();
enqueue(e);
} finally {
lock.unlock();
}
}
从代码可以看出，当队列满时，当前线程会被挂起到等待队列中，直到队列不满时被唤醒执行添加操作。下面我们看删除操作：
public boolean remove(Object o) {
// 判断是否为 NULL
if (o == null) return false;
final Object[] items = this.items;
final ReentrantLock lock = this.lock;
lock.lock();
try {
if (count > 0) {
final int putIndex = this.putIndex;
int i = takeIndex;
// 从移除下标开始遍历到添加新元素的下标
do {
if (o.equals(items[i])) {
removeAt(i);
return true;
}
// 循环判断，移除下标可能大于添加下标（添加下标二次遍历时）
if (++i == items.length)
i = 0;
} while (i != putIndex);
}
return false;
} finally {
lock.unlock();
}
}
void removeAt(final int removeIndex) {
final Object[] items = this.items;
// 要删除的元素正好是移除下标
if (removeIndex == takeIndex) {
items[takeIndex] = null;
// 循环删除
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
} else {
final int putIndex = this.putIndex;
// 如果不是移除下标，从该下标开始到添加下标，所有元素左移一位
for (int i = removeIndex;;) {
int next = i + 1;
if (next == items.length)
next = 0;
if (next != putIndex) {
// 向左移除
items[i] = items[next];
i = next;
} else {
// 最后put下标置为null
items[i] = null;
this.putIndex = i;
break;
}
}
count--;
// 更新迭代器
if (itrs != null)
itrs.removedAt(removeIndex);
}
notFull.signal();
}
remove() 和 poll()、take() 不同，它可以删除指定的元素。这里需要考虑删除的元素不是移除索引指向的情况，从代码可以看出，当要删除的元素不是移除索引指向的元素时，将所有从被删除元素下标开始到添加元素下标所有元素左移一位。
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (count == 0) ? null : dequeue();
} finally {
lock.unlock();
}
}
private E dequeue() {
final Object[] items = this.items;
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
if (itrs != null)
itrs.elementDequeued();
// 移除元素后唤醒put()添加线程
notFull.signal();
return x;
}
相比 remove() 方法，poll() 方法简单了很多，这里不做赘述，下面我们看 take()：
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
// 队列为空就挂起
while (count == 0)
notEmpty.await();
return dequeue();
} finally {
lock.unlock();
}
}
take() 方法和 put() 方法可以说基本一致，相对也比较简单，最后我们来看看两个查询方法：
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E peek() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 直接返回移除元素下标对应的元素，也就是队列头
return itemAt(takeIndex);
} finally {
lock.unlock();
}
}
final E itemAt(int i) {
return (E) items[i];
}
element() 基于 peek() 方法实现实现、当队列为空时，peek() 方法返回 null，element() 抛出异常。关于 ArrayBlockingQueue 就介绍到这里
LinkedBlockingQueue 基于链表实现，它的属性如下：
public class LinkedBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable {
// 链表节点，存储元素
static class Node<E> {
E item;
Node<E> next;
Node(E x) { item = x; }
}
// 链表容量
private final int capacity;
// 当前元素数量
private final AtomicInteger count = new AtomicInteger();
// 头节点
transient Node<E> head;
// 尾节点
private transient Node<E> last;
// 删除锁
private final ReentrantLock takeLock = new ReentrantLock();
// 不为空等待队列
private final Condition notEmpty = takeLock.newCondition();
// 添加锁
private final ReentrantLock putLock = new ReentrantLock();
// 不满等待队列
private final Condition notFull = putLock.newCondition();
}
从代码可以看出，元素被封装为 Node 节点保存在单向链表中，其中链表默认长度为 Integer.MAX_VALUE，因此在使用时需注意内存溢出：当添加元素速度大于删除元素速度时，队列最终会记录到大量不会用到并且无法回收的对象，导致内存溢出。
ArrayBlockingQueue 和 LinkedBlockingQueue 的主要区别在于 ReentrantLock 锁的数量和等待队列，LinkedBlockingQueue 用到两个锁和两个等待队列，也就是说添加和删除操作可以并发执行，整体效率更高。下面我们直接看代码：
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
public boolean offer(E e) {
// 元素为空抛出异常
if (e == null) throw new NullPointerException();
// 获取当前队列容量
final AtomicInteger count = this.count;
// 队列已满时直接返回false
if (count.get() == capacity)
return false;
int c = -1;
Node<E> node = new Node<E>(e);
// 获取添加锁
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
// 二次判断，因为上面判断时未加锁，数据可能已更新
if (count.get() < capacity) {
// 入队操作
enqueue(node);
// 获取还未添加元素前，队列的容量
c = count.getAndIncrement();
if (c + 1 < capacity)
// 唤醒其它添加元素的线程
notFull.signal();
}
} finally {
putLock.unlock();
}
// 如果添加前队列没有数据，也就是说现在有一条数据时
if (c == 0)
// 唤醒take线程
signalNotEmpty();
return c >= 0;
}
private void enqueue(Node<E> node) {
last = last.next = node;
}
private void signalNotEmpty() {
// 唤醒take线程前必须获取对应take锁
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
notEmpty.signal();
} finally {
takeLock.unlock();
}
}
这里有以下几点需要我们注意：
1.LinkedBlockingQueue count 属性必须通过并发类封装，因为可能存在添加、删除两个线程并发执行，需考虑同步
2.这里需要判断两次的主要原因在于方法开始时并没有加锁，数值可能改变，因此在获取到锁后需要二次判断
3.和 ArrayBlockingQueue 不同，LinkedBlockingQueue 在队列不满时会唤醒添加线程，这样做的原因是 LinkedBlockingQueue 中添加和删除操作使用不同的锁，各自只需管好自己，还可以提高吞吐量。而 ArrayBlockingQueue 使用唯一锁，这样做会导致移除线程永远不被唤醒或添加线程永远不被唤醒，吞吐量较低
4.添加元素前队列长度为0才唤醒移除线程，因为队列长度为0时，移除线程肯定已经挂起，此时唤醒一个移除线程即可。因为移除线程和添加线程类似，都会自己唤醒自己。而 c>0 时只会有两种情况：存在移除线程在运行，如果有会递归唤醒，无须我们参与、不存在移除线程运行，此时也无须我们参与，等待调用 take()、poll() 方法即可
5.唤醒只针对 put()、take() 方法阻塞的线程，offer() 方法直接返回（不包含最大等待时长），不参与唤醒场景
下面我们来看 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;
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
// 队列满时阻塞
while (count.get() == capacity) {
notFull.await();
}
// 入队
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}
从代码可以看出，put() 方法和 offer() 方法唯一区别在于自身通过 condition 阻塞挂起到等待队列，其余基本相同。至此关于添加操作介绍完毕，下面我们看移除方法：
public boolean remove(Object o) {
if (o == null) return false;
// 同时加两个锁
fullyLock();
try {
// 循环查找
for (Node<E> trail = head, p = trail.next; p != null; trail = p, p = p.next) {
if (o.equals(p.item)) {
unlink(p, trail);
return true;
}
}
return false;
} finally {
fullyUnlock();
}
}
void unlink(Node<E> p, Node<E> trail) {
// p是要溢出的节点，trail是它的前驱节点
// 方便gc
p.item = null;
// 引用取消
trail.next = p.next;
if (last == p)
last = trail;
if (count.getAndDecrement() == capacity)
notFull.signal();
}
void fullyLock() {
putLock.lock();
takeLock.lock();
}
void fullyUnlock() {
takeLock.unlock();
putLock.unlock();
}
从代码可以看出，remove() 方法只会在操作前容量不满时唤醒创建线程，并不会唤醒移除线程。并且由于我们不确定要删除元素的位置，因此此时需要加两个锁，确保数据安全。
public E poll() {
final AtomicInteger count = this.count;
if (count.get() == 0)
return null;
E x = null;
int c = -1;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
if (count.get() > 0) {
x = dequeue();
// 获取移除前队列的元素数量
c = count.getAndDecrement();
if (c > 1)
notEmpty.signal();
}
} finally {
takeLock.unlock();
}
// 移除前如果队列是满的，唤醒添加线程
if (c == capacity)
signalNotFull();
return x;
}
private E dequeue() {
Node<E> h = head;
// 获取要删除的节点
Node<E> first = h.next;
// 清除原来的头结点(方便gc)
h.next = h;
// 设置新的头结点
head = first;
// 获取返回值
E x = first.item;
// 新头结点置为空
first.item = null;
return x;
}
需要注意的一点，每次出队时更换 head 节点，head 节点本身不保存数据，head.next 记录下次需要出队的元素，每次出队后 head.next 变为新的 head 节点返回并置为 null
poll() 方法和上面提到的 offer() 方法基本镜像相同，这里我再不做过多赘述
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();
}
if (c == capacity)
signalNotFull();
return x;
}
take() 方法和 poll() 方法类似，区别在于新增了阻塞逻辑。至此关于溢出元素方法介绍完毕，最后我们看看查询方法源码：
public LinkedBlockingQueue(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
last = head = new Node<E>(null);
}
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E peek() {
if (count.get() == 0)
return null;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
Node<E> first = head.next;
if (first == null)
return null;
else
return first.item;
} finally {
takeLock.unlock();
}
}
从代码可以看出，默认 head 和 last 头尾节点都为 null，入队时直接从 next 开始操作，也就是说 head 节点不保存数据。
最后我们来看看有最大等待时长的 offer() 方法：
public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException {
if (e == null) throw new NullPointerException();
// 将时间转换成纳秒
long nanos = unit.toNanos(timeout);
int c = -1;
// 获取锁
final ReentrantLock putLock = this.putLock;
// 获取当前队列大小
final AtomicInteger count = this.count;
// 可中断锁
putLock.lockInterruptibly();
try {
while (count.get() == capacity) {
// 小于0说明已到达最大等待时长
if (nanos <= 0)
return false;
// 如果队列已满，根据等待队列阻塞等待
nanos = notFull.awaitNanos(nanos);
}
// 队列没满直接入队
enqueue(new Node<E>(e));
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
return true;
}
public final long awaitNanos(long nanosTimeout) throws InterruptedException {
if (Thread.interrupted()) throw new InterruptedException();
// 将当前线程封装为 AQS Node 类加入等待队列
Node node = addConditionWaiter();
// 释放锁
int savedState = fullyRelease(node);
//计算过期时间
final long deadline = System.nanoTime() + nanosTimeout;
int interruptMode = 0;
// 当前线程没有唤醒进入同步队列时
while (!isOnSyncQueue(node)) {
// 已经等待相应时间，删除当前节点，将状态设置为已关闭从队列删除
if (nanosTimeout <= 0L) {
transferAfterCancelledWait(node);
break;
}
// 判断是否超时
if (nanosTimeout >= spinForTimeoutThreshold)
// 挂起线程
LockSupport.parkNanos(this, nanosTimeout);
// 判断线程状态是否被中断
if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
break;
// 重新计算剩余等待时间
nanosTimeout = deadline - System.nanoTime();
}
// 被唤醒后执行自旋操作争取获得锁，同时判断线程是否被中断
if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
interruptMode = REINTERRUPT;
if (node.nextWaiter != null)
// 清理等待队列中不为Condition状态的线程
unlinkCancelledWaiters();
// 判断是否被中断
if (interruptMode != 0)
// 抛出异常或中断线程，独占模式抛出异常，共享模式中断线程
reportInterruptAfterWait(interruptMode);
// 返回时差,如果成功当前时间小于最大等待时长，返回值大于0，否则返回值小于0
return deadline - System.nanoTime();
}
从代码可以看出，包含最大等待时长的 offer()、poll() 方法通过循环判断时间是否超时的方式挂起在等待队列，达到最大等待时长还未被唤醒或没被执行就返回
ArrayBlockingQueue 和 LinkedBlockingQueue 对比：
大小不同，一个有界，一个 * 。ArrayBlockingQueue 必须指定初始大小，LinkedBlockingQueue * 时可能内存溢出
一个采用数组，一个采用链表，数组保存无须创建新对象，链表需创建 Node 对象
锁机制不同，ArrayBlockingQueue 添加删除操作使用同一个锁，两者操作不能并发执行。LinkedBlockingQueue 添加和删除使用不同锁，添加和删除操作可并发执行，整体效率 LinkedBlockingQueue 更高
来源：https://blog.csdn.net/m0_57015193/article/details/117459806
0
投稿猜你喜欢
什么是进程？电脑中时会有很多单独运行的程序，每个程序有一个独立的进程，而进程之间是相互独立存在的。比如下图中的QQ、酷狗播放器、电脑管家等等- 前言泛型，一个孤独的守门者。大家可能会有疑问，我为什么叫做泛型是一个守门者。这其实是我个人的看法而已，我的意思是说泛型没有其看起来那么深不可
- 相关方法：wait():一旦执行此方法，当前线程就进入阻塞状态，并释放同步监视器。notify():一旦执行此方法，就会唤醒被wait的一个
- 我计划在后续的一段时间内，写一系列关于java 9的文章，虽然java 9 不像Java 8或者Java 11那样的核心java版本，但是还
- 产生90-100的重复的随机数：public class RandomTest { public static void main(Str
- 前言之前实现过《Android可签到的日历控件》的功能，跟这篇一样都是实现签到打卡功能，这篇实现的是按月进行打卡做标识，本篇内容实现的按周进
- 要求:用DateTimeFormatter实现: 用扫描器获取输入的时间(年月日时分),这个时间的格式是常用的格式,然后格式化这个时间,把格
- 一、 WillPopScope用法WillPopScope本质是一个widget用于拦截物理按键返回事件(Android的物理返回键和iOS
- POM<dependency> <groupId>org.springframework.boot<
- 一、反射概述反射机制指的是Java在运行时候有一种自观的能力，能够了解自身的情况为下一步做准备，其想表达的意思就是：在运行状态中，对于任意一
- Android application捕获崩溃异常怎么办？通用 application1、收集所有 avtivity 用于彻底退出应用2、捕
- 跨域问题，其实百度上面有一堆的解决方案针对普通的情况其实百度上面的方案都是可行的。我这里主要介绍2种情况。当然我这里的配置都是基于网关的，而
- 本文实例为大家分享了Android实现拼图游戏的具体代码，供大家参考，具体内容如下本人是用 android studio 完成的源码pack
- import java.io.File; public class ShowAllXML { public static void main
- 废话不多说，直接上代码import java.text.SimpleDateFormat; import java.util.Date;/*
- 1.面对对象的初步认识1.1什么是面向对象用面向对象的思想来涉及程序，更符合人们对事物的认知，对于大型程序的设计、扩展以及维护都非常友好。1
- 在Word文档中，超链接是指在特定文本或者图片中插入的能跳转到其他位置或网页的链接，它也是我们在编辑制作Word文档时广泛使用到的功能之一。
- 本文实例为大家分享了java实现Dijkstra算法的具体代码，供大家参考，具体内容如下1 问题描述何为Dijkstra算法？Dijkstr
- 本文实例讲述了Spring的组合注解和元注解原理与用法。分享给大家供大家参考，具体如下：一 点睛从Spring 2开始，为了相应JDK 1.
- 中午没事，把去年刚毕业那会画的几张图翻出来了，大概介绍Winform应用程序运行的过程，以及TCP协议在Winform中的应用。如果有Win
