标签归档：ArrayBlockingQueue

JUC 并发 Queue 设计与介绍

发表于由
回复

Queue 体系

Queue 是一种先进先出的队列。

ArrayBlockingQueue 和 LinkedBlockingQueue 是带阻塞特性，基于锁来实现。ArrayBlockingQueue 采用同一把锁来控制出、入队列操作；LinkedBlockingQueue 用两把锁来分别控制出、入队列操作，提高了并发性能。

ConcurrentLinkedQueue 非阻塞，采用无锁算法、利用 CAS 操作来实现。

0.1 BlockingQueue

当生产者向队列添加元素但队列已满时，生产者会被阻塞；当消费者从队列移除元素、但队列为空时，消费者会被阻塞。

其实现类必须是线程安全，入队列 happen-before 出队列。

0.2 TransferQueue

继承自 BlockingQueue，更进一步：生产者会一直阻塞直到添加到队列的元素被某一个消费者所消费（不仅仅是添加到队列）。

特别适用于这种应用间传递消息的场景：生产者有时需要等待消费者接收消息，有时只需把消息放进队列、不需要等待消费者接收。

// 传递元素给消费者，如果需要则等待。确保一次传递完成。
void transfer(E e);

// 非阻塞
boolean tryTransfer(E e);

// 基于等待时间的。
boolean tryTransfer(E e, long timeout, TimeUnit unit);

// 返回是否有在等待接收元素的消费者
// （BlockingQueue.take()或带等待时间的 poll 方法调用）
boolean hasWaitingConsumer();

// 返回大概的在等待接收元素的消费者
//（BlockingQueue.take()或带等待时间的 poll 方法调用）
int getWaitingConsumerCount();

0.3 Deque

允许在两端进行插入、删除元素的线性集合。

实现类：

  • ArrayDeque：基于数组加头尾两个指针来实现、非线程安全的。
  • LinkedList：基于双向链表实现、非线程安全的。
  • ConcurrentLinkedDeque：基于双向链表、CAS 元语实现、无界的。

0.4 BlockingDeque

当 Deque 里没有元素时阻塞消费者，当没有空闲空间时阻塞生产者。

目前只有一个实现类 LinkedBlockingDeque，使用双向链表来存储元素，支持容量限制，用一把锁来保证线程安全性。因为允许在两端进行操作，双向链表更合适。

继续阅读 →

JUC ArrayBlockingQueue

发表于由
回复

java.util.concurrent.ArrayBlockingQueue 是一个线程安全的、基于数组、有界的、阻塞的、FIFO 队列。试图向已满队列中放入元素会导致操作受阻塞；试图从空队列中提取元素将导致类似阻塞。

此类基于 java.util.concurrent.locks.ReentrantLock 来实现线程安全，所以提供了 ReentrantLock 所能支持的公平性选择。

属性

队列的操作主要有读、写，所以用了两个 int 类型的属性作为下一个读写位置的的指针。存放元素的数组是 final 修饰的，所以数组的大小是固定的。对于并发控制，是所有的访问都必须加锁，并用两个条件对象用于协调读写操作。

// 队列存放元素的容器
final Object[] items;

// 下一次读取或移除的位置
int takeIndex;

// 存放下一个放入元素的位置
int putIndex;

// 队列里有效元素的数量
int count;


// 所有访问的保护锁
final ReentrantLock lock;

// 等待获取的条件
private final Condition notEmpty;

// 等待放入的条件
private final Condition notFull;

环绕处理

如果指针一直往前增加或一直往后减小，那么总会超出数组的有效索引范围。所以需要进行一些环绕处理。

// 指针前移
final int inc(int i) {
    return (++i == items.length) ? 0 : i;
}

// 指针后移
final int dec(int i) {
    return ((i == 0) ? items.length : i) - 1;
}

注意，上面的处理都是对指针值的直接处理，而不关心是读指针还是写指针，因为是否有可读元素、可写空间的判断是通过对 count 计数来判断的。

这也是 count 的作用，它极大地简化了指针有效性的判断。在下面的 insert 和 extract 方法中根本就不需要对读写指针之间的位置关系进行判断，非常精妙。

通过环绕处理可以把这个数组看成是圆形的缓存。
继续阅读 →