LinkedBlockingQueue出入队实现原理

2023-04-28,,

类图概述

由类图可以看出,L是单向链表实现的,有两个ReentrantLock实例用来控制元素入队和出队的原子性,takeLock用来控制只有一个线程可以从队头获取元素,putLock控制只有一个线程可以从队尾添加元素。notEmpty和notFull是条件变量,内部有条件队列用来存放进队和出队被阻塞的线程。

阻塞入队

put操作:在队尾插入元素,如果队列已满则阻塞当前线程,直到队列有空闲插入成功后返回。如果在阻塞时被其他线程设置中断标志,线程会抛出异常而返回。(中断是一种线程协作的方式)

public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
final int c;
final 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.
*/
while (count.get() == capacity) { (3)
notFull.await();
}
enqueue(node); (4)
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
if (c == 0)
signalNotEmpty();
}

代码(3)如果队列满了,调用await放入条件队列,当前线程被阻塞挂起后会释放获取到的putLock锁,所以其他线程就有机会获取到putLock锁了。

另外,在判断队列是否为空时为何使用while而不是if?这是考虑当前线程被虚假唤醒的问题,如果使用if语句,那么虚假唤醒后会执行(4)的入队操作,并且递增计数器,而这时候队列已经满了,从而导致队列元素溢出。而使用while循环时,假如await被虚假唤醒了,那么在此循环检查当前队列是否已满,如果是则在此进行等待。

虚假唤醒:多个等待线程在满足if条件时都会被唤醒(虚假的),但实际上条件并不满足,生产者生产出来的消费品已经被第一个线程消费了。

结论:对条件变量的状态进行不断检查直到其满足条件。

https://www.cnblogs.com/tqyysm/articles/9765667.html

阻塞出队

take操作:当线程获取到锁,其他调用take or poll的线程会被阻塞挂起(ReentrantLock内部的AQS)。如果队列为空,将当前线程放入条件队列中。

Reference

《Java并发编程之美》

LinkedBlockingQueue出入队实现原理的相关教程结束。

《LinkedBlockingQueue出入队实现原理.doc》

下载本文的Word格式文档,以方便收藏与打印。