java并发编程——BlockingQueue

时间:2022-09-01 18:37:19

概述

BlockingQueue顾名思义‘阻塞的队列’,是指在:队列的读取行为被阻塞直到队列不为空时,队列的写入行为被阻塞直到队列不满时。BlockingQueue是java.util.concurrent工具包(jdk1.5版本引入,作者:Doug Lea)的重要基础工具,在ThreadPoolExcutor及tomcat等服务端容器中都有使用到。从代码层面剖析BlockingQueue的实现细节。

类图

java并发编程——BlockingQueue

 

对象存储

BlockingQueue中的对象可以存放在:数组、链表中,对应的就是ArrayBlockingQueue、LinkedBlockingQueue。

数组

ArrayBlockingQueue使用数组作为对象存储的数据结构,数组必须指定大小,故而ArrayBlockingQueue是有界队列。如下代码摘取了ArrayBlockingQueue中对象存取数据结构和核心方法的关键代码,从中可以窥见其实现原理。注意:该示例代码去掉了lock处理,故在多线程场景下,会存在并发问题。

除去类名上明显标有Linked字样的实现queue,其他queue通常都是用使用数组作为对象存储的数据结构。

 /** The queued items */
final Object[] items; //使用数组作为对象存储的数据结构,所以是有界队列

/** items index for next take, poll, peek or remove */
int takeIndex;

/** items index for next put, offer, or add */
int putIndex;

/** Number of elements in the queue */
int count;

/**
* Creates an {@code SimpleArrayQueue} with the given (fixed) capacity.
*
* @param capacity the capacity of this queue
* @throws IllegalArgumentException if {@code capacity < 1}
*/
public SimpleArrayQueue(int capacity) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
}


/**
* Inserts element at current put position, advances
*/
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x;
if (++putIndex == items.length) //在示例代码中,由于没有加上lock判定和计数器判定,如果队列已满,指针会循环寻址,队列中先入的元素可能会被后来的元素覆盖
putIndex = 0; //实际的ArrayBlockingQueue不会有该问题,这里的循环寻址配合dequeue的同样逻辑是为了保证队列的FIFO。
count++;
}

/**
* Extracts element at current take position, advances
*/
private E dequeue() {
// assert lock.getHoldCount() == 1;
// assert items[takeIndex] != null;
final Object[] items = this.items;
@SuppressWarnings("unchecked")
E x = (E) items[takeIndex];
items[takeIndex] = null;
if (++takeIndex == items.length)
takeIndex = 0;
count--;
return x;
}

  

链表

LinkedBlockingQueue使用单向链表作为对象存储的数据结构,可以指定链表的容量,如果不指定,则使用Integer.MAXVALUE,因此,通常可以将LinkedBlockingQueue作为*队列使用。

简单的使用单向链表实现queue的示例代码:

    /**
* Head of linked list. 单向链表的头节点
* Invariant: head.item == null
*/
transient Node<E> head;

/**
* Tail of linked list. 单向链表的尾节点
* Invariant: last.next == null
*/
private transient Node<E> last;

/** The capacity bound, or Integer.MAX_VALUE if none */
private final int capacity;

/** Current number of elements */
private final AtomicInteger count = new AtomicInteger();

/**
* Linked list node class 单向链表的节点定义
*/
static class Node<E> {
E item;
/**
* One of:
* - the real successor Node
* - this Node, meaning the successor is head.next
* - null, meaning there is no successor (this is the last node)
*/
Node<E> next;
Node(E x) { item = x; }
}

public SimpleLinkedQueue(int capacity) {
this.capacity = capacity;
last = head = new Node<E>(null); //将头/尾节点均初始化为空节点
}

/**
* Links node at end of queue. 入队
* @param node the node
*/
private void enqueue(Node<E> node) {
if(count.get() == capacity) {
throw new IllegalStateException("Queue full");
} else {
last = last.next = node;
count.incrementAndGet();
}
}

/**
* Removes a node from head of queue. 出队
* @return the node
*/
private E dequeue() {
if(count.get()<=0) {
throw new IllegalStateException("Queue empty");
}
Node<E> h = head;
Node<E> first = h.next;
h.next = h; // help GC
head = first;
E x = first.item;
first.item = null;
count.getAndDecrement();
return x;
}

 

双链表

LinkedBlockingDeque使用双向链表存储元素,从而可以头/尾两个方向均可出队和入队。

 /** Doubly-linked list node class */
static final class Node<E> {
/**
* The item, or null if this node has been removed.
*/
E item;

/**
* One of:
* - the real predecessor Node
* - this Node, meaning the predecessor is tail
* - null, meaning there is no predecessor
*/
Node<E> prev;

/**
* One of:
* - the real successor Node
* - this Node, meaning the successor is head
* - null, meaning there is no successor
*/
Node<E> next;

Node(E x) {
item = x;
}
}

/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;

/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;

/** Number of items in the deque */
private transient int count;

/** Maximum number of items in the deque */
private final int capacity;

/**
* Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
*
* @param capacity the capacity of this deque
* @throws IllegalArgumentException if {@code capacity} is less than 1
*/
public SimpleLinkedDeque(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
}

/**
* Links node as first element, or returns false if full.
*/
private boolean linkFirst(Node<E> node) {
// assert lock.isHeldByCurrentThread();
if (count >= capacity)
return false;
Node<E> f = first;
node.next = f;
first = node;
if (last == null)
last = node;
else
f.prev = node;
++count;
return true;
}

/**
* Links node as last element, or returns false if full.
*/
private boolean linkLast(Node<E> node) {
// assert lock.isHeldByCurrentThread();
if (count >= capacity)
return false;
Node<E> l = last;
node.prev = l;
last = node;
if (first == null)
first = node;
else
l.next = node;
++count;
return true;
}

/**
* Removes and returns first element, or null if empty.
*/
private E unlinkFirst() {
// assert lock.isHeldByCurrentThread();
Node<E> f = first;
if (f == null)
return null;
Node<E> n = f.next;
E item = f.item;
f.item = null;
f.next = f; // help GC
first = n;
if (n == null)
last = null;
else
n.prev = null;
--count;
return item;
}

/**
* Removes and returns last element, or null if empty.
*/
private E unlinkLast() {
// assert lock.isHeldByCurrentThread();
Node<E> l = last;
if (l == null)
return null;
Node<E> p = l.prev;
E item = l.item;
l.item = null;
l.prev = l; // help GC
last = p;
if (p == null)
first = null;
else
p.next = null;
--count;
return item;
}

对象存取

BlockingQueue提供了几种通用的对象存取方法,由其子类实现。注意:LinkedBlockingDeque是双向队列,故会提供头/尾两种方式的存/取方法,这里不做讲述。

 java并发编程——BlockingQueue

以ArrayBlockingQueue的实现代码加以说明:

ArrayBlockingQueue.offer():

    public boolean offer(E e) {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
if (count == items.length)
return false; //如果队列已满,则返回false,不抛出异常
else {
enqueue(e); //向队列尾部插入元素e
return true;
}
} finally {
lock.unlock();
}
}

ArrayBlockingQueue.offer(timeout),带超时的offer:

    public boolean offer(E e, long timeout, TimeUnit unit)
throws InterruptedException {

checkNotNull(e);
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly(); //在lock锁定期间,该生产者线程可以被中断,好处是什么呢?
try {
while (count == items.length) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos); //和offer(e)不一样,该方法会等待队列的notFull信号量,但等待时长不会超过设定的timeout时长。
}
enqueue(e);
return true;
} finally {
lock.unlock();
}
}

ArrayBlockingQueue.add(): 

    public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full"); //队列满,抛出异常
}

ArrayBlockingQueue.put():

    public void put(E e) throws InterruptedException {
checkNotNull(e);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == items.length)
notFull.await(); //队列满时,生产者线程阻塞等待,直到该队列被消费者线程take后,notFull condition被signal触发
enqueue(e);
} finally {
lock.unlock();
}
}

 读取对象的的操作方法原理和上面写入对象的类似,不再赘述。  

ArrayBlockingQueue只有一个锁,对应两个Condition,count计数器也不是Atomic的;

LinkedBlockQueue有两个锁,一个put,一个take,也有两个Condition,所以put和take之间是不互斥的,但是在遍历和remov、clear操作时需要同时加两把锁;

理论上,LinkedBlockQueue的put / take性能要好于ArrayBlockingQueue。

 

一个问题:是否可以考虑也用两把锁实现ArrayBlockingQueue呢?

特殊队列

SynchronousQueue

SynchronousQueue是一种特殊的队列,其内部实现的Node,不是存储任务对象,而是存放生产者或者消费者线程,或者说这个队列的容量永远是零,因为他规定:一个生产线程,当它生产产品(即put的时候),如果当前没有人想要消费产品(即当前没有线程执行take),此生产线程必须阻塞,等待一个消费线程调用take操作,take操作将会唤醒该生产线程,同时消费线程会获取生产线程的产品(即数据传递),这样的一个过程称为一次配对过程(当然也可以先take后put,原理是一样的)。

其模型参考:java并发之SynchronousQueue实现原理 

源码分析-SynchronousQueue 这篇文章讲的特别好。

DelayQueue

DelayQueue 对元素进行持有直到一个特定的延迟到期。

能放入DelayQueue的元素都需要实现Delayed接口,Delayed接口实现了Comparable接口,用处在于在入队时,会根据放入元素的getDelay()返回的延迟时间进行排序,决定元素的排序,以便根据延迟时间从近及远有序出队。

DelayQueue队列内部实际直接持有了一个PriorityQueue队列,将按照元素的延迟时间长短作为优先级,到期时间最近的元素先出队。

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E> {

private final PriorityQueue<E> q = new PriorityQueue<E>();

PriorityBlockingQueue

具有优先级的*队列,元素存放在数组中,队列元素必须实现Comparable接口,入队时需要根据元素的compareTo()决定优先级。其他操作同ArrayBlockingQueue。

    private static <T> void siftUpComparable(int k, T x, Object[] array) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = array[parent];
if (key.compareTo((T) e) >= 0)
break;
array[k] = e;
k = parent;
}
array[k] = key;
}

 ConcurrentLinkedQueue vs BlockingQueue

ConcurrentLinkedQueue是非阻塞的,借助CAS操作实现线程安全,其实性能最高的并发队列;

BlockingQueue是阻塞的队列,提供了阻塞式的put/take api,是天然的实现 consumer/producer模式的队列。当然他也提供了非阻塞式的api,如offer/poll,add/remove。

参考:linkedblockingqueue-vs-concurrentlinkedqueue