ArrayBlockingQueue
ArrayBlockingQueue是一个用数组实现的有界阻塞队列。其是线程安全的,内部通过“互斥锁”保护竞争资源。此队列按照先进先出(FIFO)的原则对元素进行排序。队列的头部是在队列中存在时间最长的元素,队列的尾部是在队列中存在时间最短的元素。
原理和数据结构
说明:
1、ArrayBlockingQueue继承于AbstractQueue,并且它实现了BlockingQueue接口。
2、ArrayBlockingQueue内部是通过Object[]数组保存数据的,即ArrayBlockingQueue本质上是通过数组实现的。ArrayBlockingQueue的大小,即数组的容量是创建ArrayBlockingQueue时指定的。
3、ArrayBlockingQueue与ReentrantLock是组合关系,ArrayBlockingQueue中包含一个ReentrantLock对象(lock)。ReentrantLock是可重入的互斥锁,ArrayBlockingQueue就是根据该互斥锁实现“多线程对竞争资源的互斥访问”。而且ReentrantLock分为公平锁和非公平锁,在创建ArrayBlockingQueue时可以指定,ArrayBlockingQueue默认使用非公平锁。
4、ArrayBlockingQueue与Condition是组合关系,ArrayBlockingQueue中包含两个Condition对象(notEmpty和notFull)。Condition依赖于ArrayBlockingQueue而存在,通过Condition可以实现对ArrayBlockingQueue的更精确的访问。
(1)若某线程(线程A)要取数据时,数据正好为空,则该线程会执行notEmpty.await()进行等待;当其它某个线程(线程B)向数组中插入数据之后,会调用notEmpty.signal()唤醒“notEmpty上的等待线程”。此时,线程A被唤醒得以继续运行。
(2)若某线程(线程H)要插入数据时,数组已满,则该线程会执行notFull.await()进行等待;当其它某个线程(线程I)取出数据之后,会调用notFull.signal()唤醒“notFull上的等待线程”,此时线程H就会被唤醒从而得以继续运行。
函数列表
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
public ArrayBlockingQueue(int capacity, boolean fair) {
}
//创建一个具有给定的(固定)容量和指定访问策略的ArrayBlockingQueue,它最初包含给定collection的元素,并以collection迭代器的遍历顺序添加元素
public ArrayBlockingQueue(int capacity, boolean fair,
Collection<? extends E> c) {
}
//将指定的元素插入此队列的尾部(如果立即可行且不会超过该队列的容量),在成功时返回true,如果此队列已满,则抛出IllegalStateException
public boolean add(E e) {
}
//将指定的元素插入此队列的尾部(如果立即可行且不会超过该队列的容量),在成功时返回true,如果此队列已满,则返回false
public boolean offer(E e) {
}
//将指定的元素插入此队列的尾部,如果该队列已满,则等待可用的空间
public void put(E e) throws InterruptedException {
}
//将指定的元素插入此队列的尾部,如果该队列已满,则在到达指定的等待时间之前等待可用的空间
public boolean offer(E e, long timeout, TimeUnit unit)
throws InterruptedException {
}
//获取并移除此队列的头,如果此队列为空,则返回null
public E poll() {
}
//获取并移除此队列的头部,在元素变得可用之前一直等待
public E take() throws InterruptedException {
}
//获取并移除此队列的头,在指定的等待时间前等待可用的元素
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
}
//获取但不移除此队列的头,如果此队列为空,则返回null
public E peek() {
}
//返回此队列中元素的数量
public int size() {
}
//返回在无阻塞的理想情况下,此队列能接受的其它元素数量
public int remainingCapacity() {
}
//从此队列中移除指定元素的单个实例
public boolean remove(Object o) {
}
//如果此队列包含指定的元素,则返回true
public boolean contains(Object o) {
}
//返回一个按适当顺序包含此队列中所有元素的数组
public Object[] toArray() {
}
//返回一个按适当顺序包含此队列中所有元素的数组,返回数组的运行时类型是指定数组的运行时类型
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
}
//返回此collection的字符串表示形式
public String toString() {
}
//自动移除此队列中的所有元素
public void clear() {
}
//移除此队列中所有可用的元素,并将它们添加到给定的collection中
public int drainTo(Collection<? super E> c) {
return drainTo(c, Integer.MAX_VALUE);
}
//最多从此队列中移除给定数量的可用元素,并将它们添加到给定的collection中
public int drainTo(Collection<? super E> c, int maxElements) {
}
//返回一个迭代器
public Iterator<E> iterator() {
return new Itr();
}
源码分析
1、创建
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();
}
2、添加。
put(E e)方法的源码如下,进行put操作之前,必须获得锁并进行加锁操作,以保证线程安全。加锁后,若发现队列已满,则调用notFull.await()方法,让当前线程陷入等待。直到其它某个线程take某个元素后,会调用notFull.signal()方法来激活该线程。激活之后,继续enqueue(e)方法插入。
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();
}
}
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)
putIndex = 0;
count++;//计数加1
//若有take()线程陷入阻塞,则该操作激活take()线程,继续进行取元素操作。
//若没有take()线程陷入阻塞,则该操作无意义。
notEmpty.signal();
}
3、取出
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
while (count == 0)
notEmpty.await();
return dequeue();
} finally {
lock.unlock();
}
}
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--;
if (itrs != null)
itrs.elementDequeued();
notFull.signal();
return x;
}
LinkedBlockingQueue
LinkedBlockingQueue是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出(FIFO)的原则对元素进行排序。LinkedBlockingQueue可以指定容量,也可以不指定,不指定即为默认长度。
LinkedBlockingQueue内部使用ReentrantLock实现插入(putLock)和取出锁(takeLock),putLock上的条件变量是notFull,即可以用notFull唤醒阻塞在putLock上的线程。takeLock上的条件变量是notEmpty,即可用notEmpty唤醒阻塞在takeLock上的线程。
需要主要的是,如果构造一个LinkedBlockingQueue对象,而没有指定其容量大小,LinkedBlockingQueue会默认一个类似无限大小的容量(Integer.MAX_VALUE),这样的话,如果生产者的速度一旦大于消费者的速度,也许还没有等到队列满阻塞产生,系统内存就有可能被消耗殆尽了。
LinkedBlockingQueue中定义的变量:
/** The capacity bound, or Integer.MAX_VALUE if none */
private final int capacity;
/** Current number of elements */
private final AtomicInteger count = new AtomicInteger();
/**
* 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;
/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();
/** Wait queue for waiting takes */
private final Condition notEmpty = takeLock.newCondition();
/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();
/** Wait queue for waiting puts */
private final Condition notFull = putLock.newCondition();
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
// Note: convention in all put/take/etc is to preset local var
// holding count negative to indicate failure unless set.
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
/*
* Note that count is used in wait guard even though it is
* not protected by lock. This works because count can
* only decrease at this point (all other puts are shut
* out by lock), and we (or some other waiting put) are
* signalled if it ever changes from capacity. Similarly
* for all other uses of count in other wait guards.
*/
/**
*当队列满时,调用notFull.await()方法释放锁,陷入等待状态
*有2种情况会激活该线程:
*1、某个put线程添加元素后,发现队列有空余,就调用notFull.signal()方法激活阻塞线程
*2、take线程取元素时,发现队列已满,则其取出元素后,也会调用notFull.signal()方法激活阻塞线程
*/
while (count.get() == capacity) {
notFull.await();
}
enqueue(node);
c = count.getAndIncrement();
//发现队列未满,调用notFull.signal()激活阻塞的put线程(可能存在)
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
//队列空,说明已经有take线程陷入阻塞,故调用signalNotEmpty激活阻塞的take线程
signalNotEmpty();
}
ArrayBlockingQueue和LinkedBlockingQueue的区别:
1.队列中锁的实现不同
ArrayBlockingQueue实现的队列中的锁是没有分离的,即生成和消费用的是同一个锁;ArrayBlockingQueue中可以指定锁的公平性,默认为非公平锁;
LinkedBlockingQueue实现的队列中的锁是分离的,即生产用的是putLock,消费用的是takeLock,LinkedBlockingQueue中的锁都是非公平锁。
2.在生产或消费时操作不同
ArrayBlockingQueue实现的队列中在生产和消费时,是直接将枚举对象插入或移除的;
LinkedBlockingQueue实现的队列中在生产和消费时,需要把枚举对象转换为Node进行插入或移除,会影响性能。
3.队列大小初始化方式不同
ArrayBlockingQueue实现的队列中必须指定队列的大小;
LinkedBlockingQueue实现的队列中科院不指定队列的大小,但默认是Integer.MAX_VALUE。