Java多线程系列--“JUC集合”09之 LinkedBlockingDeque

概要

本章介绍JUC包中的LinkedBlockingDeque。内容包括:
LinkedBlockingDeque介绍
LinkedBlockingDeque原理和数据结构
LinkedBlockingDeque函数列表
LinkedBlockingDeque源码分析(JDK1.7.0_40版本)
LinkedBlockingDeque示例

转载请注明出处:http://www.cnblogs.com/skywang12345/p/3503480.html

LinkedBlockingDeque介绍

LinkedBlockingDeque是双向链表实现的双向并发阻塞队列。该阻塞队列同时支持FIFO和FILO两种操作方式,即可以从队列的头和尾同时操作(插入/删除);并且,该阻塞队列是支持线程安全。

此外,LinkedBlockingDeque还是可选容量的(防止过度膨胀),即可以指定队列的容量。如果不指定,默认容量大小等于Integer.MAX_VALUE。

LinkedBlockingDeque原理和数据结构

LinkedBlockingDeque的数据结构,如下图所示:

Java多线程系列--“JUC集合”09之 LinkedBlockingDeque

说明
1. LinkedBlockingDeque继承于AbstractQueue,它本质上是一个支持FIFO和FILO的双向的队列。
2. LinkedBlockingDeque实现了BlockingDeque接口,它支持多线程并发。当多线程竞争同一个资源时,某线程获取到该资源之后,其它线程需要阻塞等待。
3. LinkedBlockingDeque是通过双向链表实现的。
3.1 first是双向链表的表头。
3.2 last是双向链表的表尾。
3.3 count是LinkedBlockingDeque的实际大小,即双向链表中当前节点个数。
3.4 capacity是LinkedBlockingDeque的容量,它是在创建LinkedBlockingDeque时指定的。
3.5 lock是控制对LinkedBlockingDeque的互斥锁,当多个线程竞争同时访问LinkedBlockingDeque时,某线程获取到了互斥锁lock,其它线程则需要阻塞等待,直到该线程释放lock,其它线程才有机会获取lock从而获取cpu执行权。
3.6 notEmpty和notFull分别是“非空条件”和“未满条件”。通过它们能够更加细腻进行并发控制。

     -- 若某线程(线程A)要取出数据时,队列正好为空,则该线程会执行notEmpty.await()进行等待;当其它某个线程(线程B)向队列中插入了数据之后,会调用notEmpty.signal()唤醒“notEmpty上的等待线程”。此时,线程A会被唤醒从而得以继续运行。 此外,线程A在执行取操作前,会获取takeLock,在取操作执行完毕再释放takeLock。
-- 若某线程(线程H)要插入数据时,队列已满,则该线程会它执行notFull.await()进行等待;当其它某个线程(线程I)取出数据之后,会调用notFull.signal()唤醒“notFull上的等待线程”。此时,线程H就会被唤醒从而得以继续运行。 此外,线程H在执行插入操作前,会获取putLock,在插入操作执行完毕才释放putLock。

关于ReentrantLock 和 Condition等更多的内容,可以参考:
    (01) Java多线程系列--“JUC锁”02之 互斥锁ReentrantLock
    (02) Java多线程系列--“JUC锁”03之 公平锁(一)
    (03) Java多线程系列--“JUC锁”04之 公平锁(二)
    (04) Java多线程系列--“JUC锁”05之 非公平锁
    (05) Java多线程系列--“JUC锁”06之 Condition条件

LinkedBlockingDeque函数列表

// 创建一个容量为 Integer.MAX_VALUE 的 LinkedBlockingDeque。
LinkedBlockingDeque()
// 创建一个容量为 Integer.MAX_VALUE 的 LinkedBlockingDeque,最初包含给定 collection 的元素,以该 collection 迭代器的遍历顺序添加。
LinkedBlockingDeque(Collection<? extends E> c)
// 创建一个具有给定(固定)容量的 LinkedBlockingDeque。
LinkedBlockingDeque(int capacity) // 在不违反容量限制的情况下,将指定的元素插入此双端队列的末尾。
boolean add(E e)
// 如果立即可行且不违反容量限制,则将指定的元素插入此双端队列的开头;如果当前没有空间可用,则抛出 IllegalStateException。
void addFirst(E e)
// 如果立即可行且不违反容量限制,则将指定的元素插入此双端队列的末尾;如果当前没有空间可用,则抛出 IllegalStateException。
void addLast(E e)
// 以原子方式 (atomically) 从此双端队列移除所有元素。
void clear()
// 如果此双端队列包含指定的元素,则返回 true。
boolean contains(Object o)
// 返回在此双端队列的元素上以逆向连续顺序进行迭代的迭代器。
Iterator<E> descendingIterator()
// 移除此队列中所有可用的元素,并将它们添加到给定 collection 中。
int drainTo(Collection<? super E> c)
// 最多从此队列中移除给定数量的可用元素,并将这些元素添加到给定 collection 中。
int drainTo(Collection<? super E> c, int maxElements)
// 获取但不移除此双端队列表示的队列的头部。
E element()
// 获取,但不移除此双端队列的第一个元素。
E getFirst()
// 获取,但不移除此双端队列的最后一个元素。
E getLast()
// 返回在此双端队列元素上以恰当顺序进行迭代的迭代器。
Iterator<E> iterator()
// 如果立即可行且不违反容量限制,则将指定的元素插入此双端队列表示的队列中(即此双端队列的尾部),并在成功时返回 true;如果当前没有空间可用,则返回 false。
boolean offer(E e)
// 将指定的元素插入此双端队列表示的队列中(即此双端队列的尾部),必要时将在指定的等待时间内一直等待可用空间。
boolean offer(E e, long timeout, TimeUnit unit)
// 如果立即可行且不违反容量限制,则将指定的元素插入此双端队列的开头,并在成功时返回 true;如果当前没有空间可用,则返回 false。
boolean offerFirst(E e)
// 将指定的元素插入此双端队列的开头,必要时将在指定的等待时间内等待可用空间。
boolean offerFirst(E e, long timeout, TimeUnit unit)
// 如果立即可行且不违反容量限制,则将指定的元素插入此双端队列的末尾,并在成功时返回 true;如果当前没有空间可用,则返回 false。
boolean offerLast(E e)
// 将指定的元素插入此双端队列的末尾,必要时将在指定的等待时间内等待可用空间。
boolean offerLast(E e, long timeout, TimeUnit unit)
// 获取但不移除此双端队列表示的队列的头部(即此双端队列的第一个元素);如果此双端队列为空,则返回 null。
E peek()
// 获取,但不移除此双端队列的第一个元素;如果此双端队列为空,则返回 null。
E peekFirst()
// 获取,但不移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null。
E peekLast()
// 获取并移除此双端队列表示的队列的头部(即此双端队列的第一个元素);如果此双端队列为空,则返回 null。
E poll()
// 获取并移除此双端队列表示的队列的头部(即此双端队列的第一个元素),如有必要将在指定的等待时间内等待可用元素。
E poll(long timeout, TimeUnit unit)
// 获取并移除此双端队列的第一个元素;如果此双端队列为空,则返回 null。
E pollFirst()
// 获取并移除此双端队列的第一个元素,必要时将在指定的等待时间等待可用元素。
E pollFirst(long timeout, TimeUnit unit)
// 获取并移除此双端队列的最后一个元素;如果此双端队列为空,则返回 null。
E pollLast()
// 获取并移除此双端队列的最后一个元素,必要时将在指定的等待时间内等待可用元素。
E pollLast(long timeout, TimeUnit unit)
// 从此双端队列所表示的堆栈中弹出一个元素。
E pop()
// 将元素推入此双端队列表示的栈。
void push(E e)
// 将指定的元素插入此双端队列表示的队列中(即此双端队列的尾部),必要时将一直等待可用空间。
void put(E e)
// 将指定的元素插入此双端队列的开头,必要时将一直等待可用空间。
void putFirst(E e)
// 将指定的元素插入此双端队列的末尾,必要时将一直等待可用空间。
void putLast(E e)
// 返回理想情况下(没有内存和资源约束)此双端队列可不受阻塞地接受的额外元素数。
int remainingCapacity()
// 获取并移除此双端队列表示的队列的头部。
E remove()
// 从此双端队列移除第一次出现的指定元素。
boolean remove(Object o)
// 获取并移除此双端队列第一个元素。
E removeFirst()
// 从此双端队列移除第一次出现的指定元素。
boolean removeFirstOccurrence(Object o)
// 获取并移除此双端队列的最后一个元素。
E removeLast()
// 从此双端队列移除最后一次出现的指定元素。
boolean removeLastOccurrence(Object o)
// 返回此双端队列中的元素数。
int size()
// 获取并移除此双端队列表示的队列的头部(即此双端队列的第一个元素),必要时将一直等待可用元素。
E take()
// 获取并移除此双端队列的第一个元素,必要时将一直等待可用元素。
E takeFirst()
// 获取并移除此双端队列的最后一个元素,必要时将一直等待可用元素。
E takeLast()
// 返回以恰当顺序(从第一个元素到最后一个元素)包含此双端队列所有元素的数组。
Object[] toArray()
// 返回以恰当顺序包含此双端队列所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。
<T> T[] toArray(T[] a)
// 返回此 collection 的字符串表示形式。
String toString()

LinkedBlockingDeque源码分析(JDK1.7.0_40版本)

LinkedBlockingDeque.java的完整源码如下:

 /*
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/ /*
*
*
*
*
*
* Written by Doug Lea with assistance from members of JCP JSR-166
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/publicdomain/zero/1.0/
*/ package java.util.concurrent; import java.util.AbstractQueue;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock; /**
* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
* linked nodes.
*
* <p> The optional capacity bound constructor argument serves as a
* way to prevent excessive expansion. The capacity, if unspecified,
* is equal to {@link Integer#MAX_VALUE}. Linked nodes are
* dynamically created upon each insertion unless this would bring the
* deque above capacity.
*
* <p>Most operations run in constant time (ignoring time spent
* blocking). Exceptions include {@link #remove(Object) remove},
* {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
* #removeLastOccurrence removeLastOccurrence}, {@link #contains
* contains}, {@link #iterator iterator.remove()}, and the bulk
* operations, all of which run in linear time.
*
* <p>This class and its iterator implement all of the
* <em>optional</em> methods of the {@link Collection} and {@link
* Iterator} interfaces.
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @since 1.6
* @author Doug Lea
* @param <E> the type of elements held in this collection
*/
public class LinkedBlockingDeque<E>
extends AbstractQueue<E>
implements BlockingDeque<E>, java.io.Serializable { /*
* Implemented as a simple doubly-linked list protected by a
* single lock and using conditions to manage blocking.
*
* To implement weakly consistent iterators, it appears we need to
* keep all Nodes GC-reachable from a predecessor dequeued Node.
* That would cause two problems:
* - allow a rogue Iterator to cause unbounded memory retention
* - cause cross-generational linking of old Nodes to new Nodes if
* a Node was tenured while live, which generational GCs have a
* hard time dealing with, causing repeated major collections.
* However, only non-deleted Nodes need to be reachable from
* dequeued Nodes, and reachability does not necessarily have to
* be of the kind understood by the GC. We use the trick of
* linking a Node that has just been dequeued to itself. Such a
* self-link implicitly means to jump to "first" (for next links)
* or "last" (for prev links).
*/ /*
* We have "diamond" multiple interface/abstract class inheritance
* here, and that introduces ambiguities. Often we want the
* BlockingDeque javadoc combined with the AbstractQueue
* implementation, so a lot of method specs are duplicated here.
*/ private static final long serialVersionUID = -387911632671998426L; /** 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; /** Main lock guarding all access */
final ReentrantLock lock = new ReentrantLock(); /** Condition for waiting takes */
private final Condition notEmpty = lock.newCondition(); /** Condition for waiting puts */
private final Condition notFull = lock.newCondition(); /**
* Creates a {@code LinkedBlockingDeque} with a capacity of
* {@link Integer#MAX_VALUE}.
*/
public LinkedBlockingDeque() {
this(Integer.MAX_VALUE);
} /**
* 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 LinkedBlockingDeque(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
} /**
* Creates a {@code LinkedBlockingDeque} with a capacity of
* {@link Integer#MAX_VALUE}, initially containing the elements of
* the given collection, added in traversal order of the
* collection's iterator.
*
* @param c the collection of elements to initially contain
* @throws NullPointerException if the specified collection or any
* of its elements are null
*/
public LinkedBlockingDeque(Collection<? extends E> c) {
this(Integer.MAX_VALUE);
final ReentrantLock lock = this.lock;
lock.lock(); // Never contended, but necessary for visibility
try {
for (E e : c) {
if (e == null)
throw new NullPointerException();
if (!linkLast(new Node<E>(e)))
throw new IllegalStateException("Deque full");
}
} finally {
lock.unlock();
}
} // Basic linking and unlinking operations, called only while holding lock /**
* 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;
notEmpty.signal();
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;
notEmpty.signal();
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;
notFull.signal();
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;
notFull.signal();
return item;
} /**
* Unlinks x.
*/
void unlink(Node<E> x) {
// assert lock.isHeldByCurrentThread();
Node<E> p = x.prev;
Node<E> n = x.next;
if (p == null) {
unlinkFirst();
} else if (n == null) {
unlinkLast();
} else {
p.next = n;
n.prev = p;
x.item = null;
// Don't mess with x's links. They may still be in use by
// an iterator.
--count;
notFull.signal();
}
} // BlockingDeque methods /**
* @throws IllegalStateException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void addFirst(E e) {
if (!offerFirst(e))
throw new IllegalStateException("Deque full");
} /**
* @throws IllegalStateException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void addLast(E e) {
if (!offerLast(e))
throw new IllegalStateException("Deque full");
} /**
* @throws NullPointerException {@inheritDoc}
*/
public boolean offerFirst(E e) {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
return linkFirst(node);
} finally {
lock.unlock();
}
} /**
* @throws NullPointerException {@inheritDoc}
*/
public boolean offerLast(E e) {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
return linkLast(node);
} finally {
lock.unlock();
}
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public void putFirst(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
while (!linkFirst(node))
notFull.await();
} finally {
lock.unlock();
}
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public void putLast(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
lock.lock();
try {
while (!linkLast(node))
notFull.await();
} finally {
lock.unlock();
}
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public boolean offerFirst(E e, long timeout, TimeUnit unit)
throws InterruptedException {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (!linkFirst(node)) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos);
}
return true;
} finally {
lock.unlock();
}
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public boolean offerLast(E e, long timeout, TimeUnit unit)
throws InterruptedException {
if (e == null) throw new NullPointerException();
Node<E> node = new Node<E>(e);
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (!linkLast(node)) {
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos);
}
return true;
} finally {
lock.unlock();
}
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
E x = pollFirst();
if (x == null) throw new NoSuchElementException();
return x;
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeLast() {
E x = pollLast();
if (x == null) throw new NoSuchElementException();
return x;
} public E pollFirst() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return unlinkFirst();
} finally {
lock.unlock();
}
} public E pollLast() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return unlinkLast();
} finally {
lock.unlock();
}
} public E takeFirst() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lock();
try {
E x;
while ( (x = unlinkFirst()) == null)
notEmpty.await();
return x;
} finally {
lock.unlock();
}
} public E takeLast() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lock();
try {
E x;
while ( (x = unlinkLast()) == null)
notEmpty.await();
return x;
} finally {
lock.unlock();
}
} public E pollFirst(long timeout, TimeUnit unit)
throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
E x;
while ( (x = unlinkFirst()) == null) {
if (nanos <= 0)
return null;
nanos = notEmpty.awaitNanos(nanos);
}
return x;
} finally {
lock.unlock();
}
} public E pollLast(long timeout, TimeUnit unit)
throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
E x;
while ( (x = unlinkLast()) == null) {
if (nanos <= 0)
return null;
nanos = notEmpty.awaitNanos(nanos);
}
return x;
} finally {
lock.unlock();
}
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getFirst() {
E x = peekFirst();
if (x == null) throw new NoSuchElementException();
return x;
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
E x = peekLast();
if (x == null) throw new NoSuchElementException();
return x;
} public E peekFirst() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (first == null) ? null : first.item;
} finally {
lock.unlock();
}
} public E peekLast() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return (last == null) ? null : last.item;
} finally {
lock.unlock();
}
} public boolean removeFirstOccurrence(Object o) {
if (o == null) return false;
final ReentrantLock lock = this.lock;
lock.lock();
try {
for (Node<E> p = first; p != null; p = p.next) {
if (o.equals(p.item)) {
unlink(p);
return true;
}
}
return false;
} finally {
lock.unlock();
}
} public boolean removeLastOccurrence(Object o) {
if (o == null) return false;
final ReentrantLock lock = this.lock;
lock.lock();
try {
for (Node<E> p = last; p != null; p = p.prev) {
if (o.equals(p.item)) {
unlink(p);
return true;
}
}
return false;
} finally {
lock.unlock();
}
} // BlockingQueue methods /**
* Inserts the specified element at the end of this deque unless it would
* violate capacity restrictions. When using a capacity-restricted deque,
* it is generally preferable to use method {@link #offer(Object) offer}.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
addLast(e);
return true;
} /**
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
return offerLast(e);
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public void put(E e) throws InterruptedException {
putLast(e);
} /**
* @throws NullPointerException {@inheritDoc}
* @throws InterruptedException {@inheritDoc}
*/
public boolean offer(E e, long timeout, TimeUnit unit)
throws InterruptedException {
return offerLast(e, timeout, unit);
} /**
* Retrieves and removes the head of the queue represented by this deque.
* This method differs from {@link #poll poll} only in that it throws an
* exception if this deque is empty.
*
* <p>This method is equivalent to {@link #removeFirst() removeFirst}.
*
* @return the head of the queue represented by this deque
* @throws NoSuchElementException if this deque is empty
*/
public E remove() {
return removeFirst();
} public E poll() {
return pollFirst();
} public E take() throws InterruptedException {
return takeFirst();
} public E poll(long timeout, TimeUnit unit) throws InterruptedException {
return pollFirst(timeout, unit);
} /**
* Retrieves, but does not remove, the head of the queue represented by
* this deque. This method differs from {@link #peek peek} only in that
* it throws an exception if this deque is empty.
*
* <p>This method is equivalent to {@link #getFirst() getFirst}.
*
* @return the head of the queue represented by this deque
* @throws NoSuchElementException if this deque is empty
*/
public E element() {
return getFirst();
} public E peek() {
return peekFirst();
} /**
* Returns the number of additional elements that this deque can ideally
* (in the absence of memory or resource constraints) accept without
* blocking. This is always equal to the initial capacity of this deque
* less the current {@code size} of this deque.
*
* <p>Note that you <em>cannot</em> always tell if an attempt to insert
* an element will succeed by inspecting {@code remainingCapacity}
* because it may be the case that another thread is about to
* insert or remove an element.
*/
public int remainingCapacity() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return capacity - count;
} finally {
lock.unlock();
}
} /**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public int drainTo(Collection<? super E> c) {
return drainTo(c, Integer.MAX_VALUE);
} /**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public int drainTo(Collection<? super E> c, int maxElements) {
if (c == null)
throw new NullPointerException();
if (c == this)
throw new IllegalArgumentException();
final ReentrantLock lock = this.lock;
lock.lock();
try {
int n = Math.min(maxElements, count);
for (int i = 0; i < n; i++) {
c.add(first.item); // In this order, in case add() throws.
unlinkFirst();
}
return n;
} finally {
lock.unlock();
}
} // Stack methods /**
* @throws IllegalStateException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
public void push(E e) {
addFirst(e);
} /**
* @throws NoSuchElementException {@inheritDoc}
*/
public E pop() {
return removeFirst();
} // Collection methods /**
* Removes the first occurrence of the specified element from this deque.
* If the deque does not contain the element, it is unchanged.
* More formally, removes the first element {@code e} such that
* {@code o.equals(e)} (if such an element exists).
* Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* <p>This method is equivalent to
* {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
*
* @param o element to be removed from this deque, if present
* @return {@code true} if this deque changed as a result of the call
*/
public boolean remove(Object o) {
return removeFirstOccurrence(o);
} /**
* Returns the number of elements in this deque.
*
* @return the number of elements in this deque
*/
public int size() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
return count;
} finally {
lock.unlock();
}
} /**
* Returns {@code true} if this deque contains the specified element.
* More formally, returns {@code true} if and only if this deque contains
* at least one element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this deque
* @return {@code true} if this deque contains the specified element
*/
public boolean contains(Object o) {
if (o == null) return false;
final ReentrantLock lock = this.lock;
lock.lock();
try {
for (Node<E> p = first; p != null; p = p.next)
if (o.equals(p.item))
return true;
return false;
} finally {
lock.unlock();
}
} /*
* TODO: Add support for more efficient bulk operations.
*
* We don't want to acquire the lock for every iteration, but we
* also want other threads a chance to interact with the
* collection, especially when count is close to capacity.
*/ // /**
// * Adds all of the elements in the specified collection to this
// * queue. Attempts to addAll of a queue to itself result in
// * {@code IllegalArgumentException}. Further, the behavior of
// * this operation is undefined if the specified collection is
// * modified while the operation is in progress.
// *
// * @param c collection containing elements to be added to this queue
// * @return {@code true} if this queue changed as a result of the call
// * @throws ClassCastException {@inheritDoc}
// * @throws NullPointerException {@inheritDoc}
// * @throws IllegalArgumentException {@inheritDoc}
// * @throws IllegalStateException {@inheritDoc}
// * @see #add(Object)
// */
// public boolean addAll(Collection<? extends E> c) {
// if (c == null)
// throw new NullPointerException();
// if (c == this)
// throw new IllegalArgumentException();
// final ReentrantLock lock = this.lock;
// lock.lock();
// try {
// boolean modified = false;
// for (E e : c)
// if (linkLast(e))
// modified = true;
// return modified;
// } finally {
// lock.unlock();
// }
// } /**
* Returns an array containing all of the elements in this deque, in
* proper sequence (from first to last element).
*
* <p>The returned array will be "safe" in that no references to it are
* maintained by this deque. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
*
* <p>This method acts as bridge between array-based and collection-based
* APIs.
*
* @return an array containing all of the elements in this deque
*/
@SuppressWarnings("unchecked")
public Object[] toArray() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] a = new Object[count];
int k = 0;
for (Node<E> p = first; p != null; p = p.next)
a[k++] = p.item;
return a;
} finally {
lock.unlock();
}
} /**
* Returns an array containing all of the elements in this deque, in
* proper sequence; the runtime type of the returned array is that of
* the specified array. If the deque fits in the specified array, it
* is returned therein. Otherwise, a new array is allocated with the
* runtime type of the specified array and the size of this deque.
*
* <p>If this deque fits in the specified array with room to spare
* (i.e., the array has more elements than this deque), the element in
* the array immediately following the end of the deque is set to
* {@code null}.
*
* <p>Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
* <p>Suppose {@code x} is a deque known to contain only strings.
* The following code can be used to dump the deque into a newly
* allocated array of {@code String}:
*
* <pre>
* String[] y = x.toArray(new String[0]);</pre>
*
* Note that {@code toArray(new Object[0])} is identical in function to
* {@code toArray()}.
*
* @param a the array into which the elements of the deque are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose
* @return an array containing all of the elements in this deque
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this deque
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
if (a.length < count)
a = (T[])java.lang.reflect.Array.newInstance
(a.getClass().getComponentType(), count); int k = 0;
for (Node<E> p = first; p != null; p = p.next)
a[k++] = (T)p.item;
if (a.length > k)
a[k] = null;
return a;
} finally {
lock.unlock();
}
} public String toString() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Node<E> p = first;
if (p == null)
return "[]"; StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = p.item;
sb.append(e == this ? "(this Collection)" : e);
p = p.next;
if (p == null)
return sb.append(']').toString();
sb.append(',').append(' ');
}
} finally {
lock.unlock();
}
} /**
* Atomically removes all of the elements from this deque.
* The deque will be empty after this call returns.
*/
public void clear() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
for (Node<E> f = first; f != null; ) {
f.item = null;
Node<E> n = f.next;
f.prev = null;
f.next = null;
f = n;
}
first = last = null;
count = 0;
notFull.signalAll();
} finally {
lock.unlock();
}
} /**
* Returns an iterator over the elements in this deque in proper sequence.
* The elements will be returned in order from first (head) to last (tail).
*
* <p>The returned iterator is a "weakly consistent" iterator that
* will never throw {@link java.util.ConcurrentModificationException
* ConcurrentModificationException}, and guarantees to traverse
* elements as they existed upon construction of the iterator, and
* may (but is not guaranteed to) reflect any modifications
* subsequent to construction.
*
* @return an iterator over the elements in this deque in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
} /**
* Returns an iterator over the elements in this deque in reverse
* sequential order. The elements will be returned in order from
* last (tail) to first (head).
*
* <p>The returned iterator is a "weakly consistent" iterator that
* will never throw {@link java.util.ConcurrentModificationException
* ConcurrentModificationException}, and guarantees to traverse
* elements as they existed upon construction of the iterator, and
* may (but is not guaranteed to) reflect any modifications
* subsequent to construction.
*
* @return an iterator over the elements in this deque in reverse order
*/
public Iterator<E> descendingIterator() {
return new DescendingItr();
} /**
* Base class for Iterators for LinkedBlockingDeque
*/
private abstract class AbstractItr implements Iterator<E> {
/**
* The next node to return in next()
*/
Node<E> next; /**
* nextItem holds on to item fields because once we claim that
* an element exists in hasNext(), we must return item read
* under lock (in advance()) even if it was in the process of
* being removed when hasNext() was called.
*/
E nextItem; /**
* Node returned by most recent call to next. Needed by remove.
* Reset to null if this element is deleted by a call to remove.
*/
private Node<E> lastRet; abstract Node<E> firstNode();
abstract Node<E> nextNode(Node<E> n); AbstractItr() {
// set to initial position
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
next = firstNode();
nextItem = (next == null) ? null : next.item;
} finally {
lock.unlock();
}
} /**
* Returns the successor node of the given non-null, but
* possibly previously deleted, node.
*/
private Node<E> succ(Node<E> n) {
// Chains of deleted nodes ending in null or self-links
// are possible if multiple interior nodes are removed.
for (;;) {
Node<E> s = nextNode(n);
if (s == null)
return null;
else if (s.item != null)
return s;
else if (s == n)
return firstNode();
else
n = s;
}
} /**
* Advances next.
*/
void advance() {
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
// assert next != null;
next = succ(next);
nextItem = (next == null) ? null : next.item;
} finally {
lock.unlock();
}
} public boolean hasNext() {
return next != null;
} public E next() {
if (next == null)
throw new NoSuchElementException();
lastRet = next;
E x = nextItem;
advance();
return x;
} public void remove() {
Node<E> n = lastRet;
if (n == null)
throw new IllegalStateException();
lastRet = null;
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
if (n.item != null)
unlink(n);
} finally {
lock.unlock();
}
}
} /** Forward iterator */
private class Itr extends AbstractItr {
Node<E> firstNode() { return first; }
Node<E> nextNode(Node<E> n) { return n.next; }
} /** Descending iterator */
private class DescendingItr extends AbstractItr {
Node<E> firstNode() { return last; }
Node<E> nextNode(Node<E> n) { return n.prev; }
} /**
* Save the state of this deque to a stream (that is, serialize it).
*
* @serialData The capacity (int), followed by elements (each an
* {@code Object}) in the proper order, followed by a null
* @param s the stream
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
final ReentrantLock lock = this.lock;
lock.lock();
try {
// Write out capacity and any hidden stuff
s.defaultWriteObject();
// Write out all elements in the proper order.
for (Node<E> p = first; p != null; p = p.next)
s.writeObject(p.item);
// Use trailing null as sentinel
s.writeObject(null);
} finally {
lock.unlock();
}
} /**
* Reconstitute this deque from a stream (that is,
* deserialize it).
* @param s the stream
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
count = 0;
first = null;
last = null;
// Read in all elements and place in queue
for (;;) {
@SuppressWarnings("unchecked")
E item = (E)s.readObject();
if (item == null)
break;
add(item);
}
} }

下面从ArrayBlockingQueue的创建,添加,取出,遍历这几个方面对LinkedBlockingDeque进行分析

1. 创建

下面以LinkedBlockingDeque(int capacity)来进行说明。

public LinkedBlockingDeque(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
}

说明:capacity是“链式阻塞队列”的容量。

LinkedBlockingDeque中相关的数据结果定义如下:

// “双向队列”的表头
transient Node<E> first;
// “双向队列”的表尾
transient Node<E> last;
// 节点数量
private transient int count;
// 容量
private final int capacity;
// 互斥锁 , 互斥锁对应的“非空条件notEmpty”, 互斥锁对应的“未满条件notFull”
final ReentrantLock lock = new ReentrantLock();
private final Condition notEmpty = lock.newCondition();
private final Condition notFull = lock.newCondition();

说明:lock是互斥锁,用于控制多线程对LinkedBlockingDeque中元素的互斥访问;而notEmpty和notFull是与lock绑定的条件,它们用于实现对多线程更精确的控制。

双向链表的节点Node的定义如下:

static final class Node<E> {
E item; // 数据
Node<E> prev; // 前一节点
Node<E> next; // 后一节点 Node(E x) { item = x; }
}

2. 添加

下面以offer(E e)为例,对LinkedBlockingDeque的添加方法进行说明。

public boolean offer(E e) {
return offerLast(e);
}

offer()实际上是调用offerLast()将元素添加到队列的末尾。

offerLast()的源码如下:

public boolean offerLast(E e) {
if (e == null) throw new NullPointerException();
// 新建节点
Node<E> node = new Node<E>(e);
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
try {
// 将“新节点”添加到双向链表的末尾
return linkLast(node);
} finally {
// 释放锁
lock.unlock();
}
}

说明:offerLast()的作用,是新建节点并将该节点插入到双向链表的末尾。它在插入节点前,会获取锁;操作完毕,再释放锁。

linkLast()的源码如下:

private boolean linkLast(Node<E> node) {
// 如果“双向链表的节点数量” > “容量”,则返回false,表示插入失败。
if (count >= capacity)
return false;
// 将“node添加到链表末尾”,并设置node为新的尾节点
Node<E> l = last;
node.prev = l;
last = node;
if (first == null)
first = node;
else
l.next = node;
// 将“节点数量”+1
++count;
// 插入节点之后,唤醒notEmpty上的等待线程。
notEmpty.signal();
return true;
}

说明:linkLast()的作用,是将节点插入到双向队列的末尾;插入节点之后,唤醒notEmpty上的等待线程。

3. 删除

下面以take()为例,对LinkedBlockingDeque的取出方法进行说明。

public E take() throws InterruptedException {
return takeFirst();
}

take()实际上是调用takeFirst()队列的第一个元素。

takeFirst()的源码如下:

public E takeFirst() throws InterruptedException {
final ReentrantLock lock = this.lock;
// 获取锁
lock.lock();
try {
E x;
// 若“队列为空”,则一直等待。否则,通过unlinkFirst()删除第一个节点。
while ( (x = unlinkFirst()) == null)
notEmpty.await();
return x;
} finally {
// 释放锁
lock.unlock();
}
}

说明:takeFirst()的作用,是删除双向链表的第一个节点,并返回节点对应的值。它在插入节点前,会获取锁;操作完毕,再释放锁。

unlinkFirst()的源码如下:

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;
// 将“节点数量”-1
--count;
// 删除节点之后,唤醒notFull上的等待线程。
notFull.signal();
return item;
}

说明:unlinkFirst()的作用,是将双向队列的第一个节点删除;删除节点之后,唤醒notFull上的等待线程。

4. 遍历

下面对LinkedBlockingDeque的遍历方法进行说明。

public Iterator<E> iterator() {
return new Itr();
}

iterator()实际上是返回一个Iter对象。

Itr类的定义如下:

private class Itr extends AbstractItr {
// “双向队列”的表头
Node<E> firstNode() { return first; }
// 获取“节点n的下一个节点”
Node<E> nextNode(Node<E> n) { return n.next; }
}

Itr继承于AbstractItr,而AbstractItr的定义如下:

private abstract class AbstractItr implements Iterator<E> {
// next是下一次调用next()会返回的节点。
Node<E> next;
// nextItem是next()返回节点对应的数据。
E nextItem;
// 上一次next()返回的节点。
private Node<E> lastRet;
// 返回第一个节点
abstract Node<E> firstNode();
// 返回下一个节点
abstract Node<E> nextNode(Node<E> n); AbstractItr() {
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
// 获取“LinkedBlockingDeque的互斥锁”
lock.lock();
try {
// 获取“双向队列”的表头
next = firstNode();
// 获取表头对应的数据
nextItem = (next == null) ? null : next.item;
} finally {
// 释放“LinkedBlockingDeque的互斥锁”
lock.unlock();
}
} // 获取n的后继节点
private Node<E> succ(Node<E> n) {
// Chains of deleted nodes ending in null or self-links
// are possible if multiple interior nodes are removed.
for (;;) {
Node<E> s = nextNode(n);
if (s == null)
return null;
else if (s.item != null)
return s;
else if (s == n)
return firstNode();
else
n = s;
}
} // 更新next和nextItem。
void advance() {
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
// assert next != null;
next = succ(next);
nextItem = (next == null) ? null : next.item;
} finally {
lock.unlock();
}
} // 返回“下一个节点是否为null”
public boolean hasNext() {
return next != null;
} // 返回下一个节点
public E next() {
if (next == null)
throw new NoSuchElementException();
lastRet = next;
E x = nextItem;
advance();
return x;
} // 删除下一个节点
public void remove() {
Node<E> n = lastRet;
if (n == null)
throw new IllegalStateException();
lastRet = null;
final ReentrantLock lock = LinkedBlockingDeque.this.lock;
lock.lock();
try {
if (n.item != null)
unlink(n);
} finally {
lock.unlock();
}
}
}

LinkedBlockingDeque示例

 import java.util.*;
import java.util.concurrent.*; /*
* LinkedBlockingDeque是“线程安全”的队列,而LinkedList是非线程安全的。
*
* 下面是“多个线程同时操作并且遍历queue”的示例
* (01) 当queue是LinkedBlockingDeque对象时,程序能正常运行。
* (02) 当queue是LinkedList对象时,程序会产生ConcurrentModificationException异常。
*
* @author skywang
*/
public class LinkedBlockingDequeDemo1 { // TODO: queue是LinkedList对象时,程序会出错。
//private static Queue<String> queue = new LinkedList<String>();
private static Queue<String> queue = new LinkedBlockingDeque<String>();
public static void main(String[] args) { // 同时启动两个线程对queue进行操作!
new MyThread("ta").start();
new MyThread("tb").start();
} private static void printAll() {
String value;
Iterator iter = queue.iterator();
while(iter.hasNext()) {
value = (String)iter.next();
System.out.print(value+", ");
}
System.out.println();
} private static class MyThread extends Thread {
MyThread(String name) {
super(name);
}
@Override
public void run() {
int i = 0;
while (i++ < 6) {
// “线程名” + "-" + "序号"
String val = Thread.currentThread().getName()+i;
queue.add(val);
// 通过“Iterator”遍历queue。
printAll();
}
}
}
}

(某一次)运行结果

ta1, ta1, tb1, tb1,

ta1, ta1, tb1, tb1, tb2, tb2, ta2,
ta2,
ta1, ta1, tb1, tb1, tb2, tb2, ta2, ta2, tb3, tb3, ta3,
ta3, ta1,
tb1, ta1, tb2, tb1, ta2, tb2, tb3, ta2, ta3, tb3, tb4, ta3, ta4,
tb4, ta1, ta4, tb1, tb5,
tb2, ta1, ta2, tb1, tb3, tb2, ta3, ta2, tb4, tb3, ta4, ta3, tb5, tb4, ta5,
ta4, ta1, tb5, tb1, ta5, tb2, tb6,
ta2, ta1, tb3, tb1, ta3, tb2, tb4, ta2, ta4, tb3, tb5, ta3, ta5, tb4, tb6, ta4, ta6,
tb5, ta5, tb6, ta6,

结果说明:示例程序中,启动两个线程(线程ta和线程tb)分别对LinkedBlockingDeque进行操作。以线程ta而言,它会先获取“线程名”+“序号”,然后将该字符串添加到LinkedBlockingDeque中;接着,遍历并输出LinkedBlockingDeque中的全部元素。 线程tb的操作和线程ta一样,只不过线程tb的名字和线程ta的名字不同。
当queue是LinkedBlockingDeque对象时,程序能正常运行。如果将queue改为LinkedList时,程序会产生ConcurrentModificationException异常。


更多内容

1. Java多线程系列--“JUC集合”01之 框架

2. Java多线程系列目录(共xx篇)

上一篇:Spring_Task初探(注解,XML配置)


下一篇:django中migration文件是干啥的