基于链表阻塞队列LinkedBlockingQueue

基于链表的无边界阻塞队列，常用与线程池创建中作为任务缓冲队列使用

I. 底层数据结构

先看一下内部定义，与ArrayBlockingQueue做一下对比，顺带看下这两者的区别及不同的应用场景

说明

1. 底层结构为单向链表，其中队列头不包含有效数据；

2. 队列长度有界，为初始化时指定的容量大小；没指定时，默认为int最大值

3. count实时表示队列中元素的个数，采用原子进行+/-1

4. 进队和出队是两个锁，也就是说出队和进队可以并发进行

对比下ArrayBlockingQueue,主要区别为两个地方

1. LinkedBlockingQueue底层为链表；ArrayBlockingQueue底层为数组（貌似有点多余，命名上就可以看出）

2. LinkedBlockingQueue出队和入队是两个锁，而ArrayBlockingQueue是一个锁进行控制；即前者出队和入队可以并发执行；而后者会出现锁的竞争

II. 阻塞实现原理

0. Prefer

分析阻塞原理之前，先通过注释解释下LinkedBlockingQueue的使用场景

• 先进先出队列（队列头的是最先进队的元素；队列尾的是最后进队的元素）

• 有界队列（即初始化时指定的容量，就是队列最大的容量，不会出现扩容，容量满，则阻塞进队操作；容量空，则阻塞出队操作）

• 队列不支持空元素

1. 进队

进队逻辑:

1. null不允许入队

2. 加入队锁

3. 判断队列是否已满，若是，则阻塞线程

4. 待其他线程出队时被唤醒，将元素挂在队列尾

5. 如果队列之前为空，此时入队成功之后，需要执行notEmpty.singal()，唤醒因为队列空被阻塞的出队线程

2. 出队

出队逻辑

1. 出队锁

2. 判断队列是否非空，为空时阻塞出队线程

3. 其他线程入队成功，唤醒因队列为空被阻塞的线程

4. 若出队之前，队列为满的，则唤醒因为队列满无法入队而阻塞的线程

查看上面的源码时，还发现一个非常有意思的地方，出队成功之后，会判断如果之前的队列中元素的个数大于1（即出队之后，还有元素），会执行notEmpty.signal();,唤醒被阻塞的出队线程，为什么要这么干？

假设一种场景，一个空队列，两个线程（A,B）都执行出队，被阻塞；

此时线程C执行入队，入队完成，因为队列由空到非空，会唤醒一个被阻塞的出队线程（假设为A）；


因为出队和入队是可以并发的，现在在线程A执行`c = count.getAndDecrement();`之前，若线程D又入队成功一个，因为此时队列非空，所以不会调用`signalNotEmpty` 现在如果线程A执行出队之后，获取到的c应该为2，如果不执行`notEmpty.signal();`，就会导致线程B一直被阻塞，显然不符合我们的预期

3. 其他方法

除了出队和入队的方法之外，还有几个有意思的方法，如队列中元素以数组形式输出，判断队列是否有元素，这两个操作，都会竞争出队和入队锁，确保在执行这个方法时，队列不会被其他线程修改

III. 经典case

链表阻塞队列的经典使用case，基本上用过线程池就会用到这个了，如jdk中自带的

IV. 对比小结

1. 底层结构

ArrayBlockingQueue: 底层存储结构为数组，直接将数据存入数组中

LinkedBlockingQueue: 底层存储结构为单向链表，会将数据封装到Node对象作为链表的节点，且链表头中不包含实际的元素信息

2. 锁的分离

ArrayBlockingQueue: 出队入队公用一把锁，即两者无法并发

LinkedBlockingQueue: 出队和入队各一把锁，因此出队和入队可并发执行

因此在线程池的创建中，一般是使用LinkedBlockingQueue,至少线程在进入等待队列中时，出队和进队不会相互阻塞，但是两者之间有关联

• 出队时，若队列之前为满队列时，会唤醒因为队列满被阻塞的入队线程

• 进队时，若队列之前为空队列时，会唤醒因为队列空被阻塞的出队线程

3. 出队和进队的操作不同

ArrayBlockingQueue: 是直接将对象插入或移除

LinkedBlockingQueue: 需要把枚举对象转换为Node<E>进行插入或移除，其中会将出队的Node节点作为新的队列头，返回并置空Node的item元素

4. 队列大小初始化

ArrayBlockingQueue: 必须指定队列的容量

LinkedBlockingQueue: 可以指定队列的容量，不指定时，容量为 Integer.MAX_VALUE

V. 相关博文

1. JDK容器学习之Queue: ArrayBlockingQueue

2. Java并发学习之ReentrantLock及Condition工作原理及使用姿势