BlockingQueue阻塞队列

BlockingQueue

有界阻塞队列，先进先出，存取相互排斥

容量固定必须指定长度，没有扩容机制

没有元素的位置也占用空间，被 null 占位

数据结构：静态数组

存取是同一把锁，操作的是同一个数组对象，存取互相排斥

锁：ReentrantLock

出队：队列count=0，无元素可取时，阻塞在该对象上

notEmpty

入队：队列count=length，放不进去元素时，阻塞在该对象上

notFull

阻塞对象

唤醒notEmpty

从队首开始添加元素，记录putIndex（到队尾时设置为0）

入队

唤醒notFull

从队首开始取出元素，记录takeIndex（到队尾时设置为0）

出队

两个指针都是从队首向队尾移动，保证队列的先进先出原则

ArrayBlockingQueue

无界阻塞队列，可以指定容量，默认为 Integer.MAX_VALUE，先进先出，存取互不干扰

可以指定容量，默认为Integer.MAX_VALUE，内部类 Node 存储元素

数据结构：链表

取Node节点保证前驱后继不会乱

takeLock

存Node节点保证前驱后继不会乱

putLock

锁分离：存取互不干扰，存取操作的是不同的Node对象

入队：队列count=capacity，放不进去元素时，阻塞在该对象上

队尾入队，由last指针记录

队首出队，由head指针记录

先进先出

锁分离

线程池中为什么使用LinkedBlockingQueue而不用ArrayBlockingQueue？

LinkedBlockingQueue

一个链表阻塞双端队列，无界可以指定容量，默认为 Integer.MAX_VALUE

内部类 Node 存储元素

数据结构：链表（同LinkedBlockingQueue）

存取是同一把锁，操作的是同一个数组对象

锁：ReentrantLock（同ArrayBlockingQueue）

无元素可取时，阻塞在该对象上（count=0）

放不进去时，阻塞在该对象上（count=capacity）

阻塞对象（同LinkedBlockingQueue）

常用于 “工作窃取算法”

应用场景

LinkedBlockingDeque

是一个没有数据缓冲的BlockingQueue，容量为0，它不会为队列中元素维护存储空间，它只是多个线程之间数据交换的媒介。

第一个线程Thread0是消费者访问，此时队列为空，则入队（创建Node结点并赋值）

第二个线程Thread1也是消费者访问，与队尾模式相同，继续入队

第三个线程Thread2是生产者，携带了数据e，与队尾模式不同，不进行入队操作直接将该线程携带的数据e返回给队首的消费者，并唤醒队首线程Thread1（默认非公平策略是栈结构），出队

先消费（take），后生产(put)

在其内部类中维护了数据

数据结构：链表(Node)

锁：CAS+自旋（无锁）

阻塞：自旋了一定次数后调用 LockSupport.park()

put、offer 为生产者，携带了数据 e，为 Data 模式，设置到 SNode或QNode 属性中

take、poll 为消费者，不携帯数据，为 Request 模式，设置到 SNode或QNode属性中

存取调用同一个方法：transfer()

线程访问阻塞队列，先判断队尾节点或者栈顶节点的 Node 与当前入队模式是否相同

相同则构造节点 Node 入队，并阻塞当前线程，元素 e 和线程赋值给 Node 属性

不同则将元素 e（不为 null） 返回给取数据线程，队首或栈顶线程被唤醒，出队

过程

队尾匹配(判断模式)，队头出队，先进先出

TransferQueue

公平模式

栈顶匹配，栈顶出栈，后进先出

TransferStack

非公平模式（默认策略）

SynchronousQueue非常适合传递性场景做交换工作，生产者的线程和消费者的线程同步传递某些信息、事件或者任务。

SynchronousQueue的一个使用场景是在线程池里。如果我们不确定来自生产者请求数量，但是这些请求需要很快的处理掉，那么配合SynchronousQueue为每个生产者请求分配一个消费线程是处理效率最高的办法。Executors.newCachedThreadPool()就使用了SynchronousQueue，这个线程池根据需要（新任务到来时）创建新的线程，如果有空闲线程则会重复使用，线程空闲了60秒后会被回收。

SynchronousQueue

是 SynchronousQueue 和 LinkedBlockingQueue 的合体

一个由链表结构组成的无界阻塞队列

数据结构：链表Node

可以自己控制存元素是否需要阻塞线程，比如使用四个添加元素的方法就不会阻塞线程，只入队元素，使用 transfer() 会阻塞线程

取元素与 SynchronousQueue 基本一样，都会阻塞等待有新的元素进入被匹配到

LinkedTransferQueue

优先级高的先出队，优先级低的后出队

一个支持优先级排序的无界阻塞队列

默认容量11，可指定初始容量，会自动扩容，最大容量是(Integer.MAX_VALUE - 8)

数据结构：数组+二叉堆

存取是同一把锁

出队，队列为空时阻塞

阻塞对象：NotEmpty

不阻塞，永远返回成功，无界

传入比较器对象就按照比较器的顺序排序

如果比较器为 null，则按照自然顺序排序

根据比较器进行堆化（排序）自下而上

优先级最高的元素在堆顶（弹出堆顶元素）

弹出前比较两个子节点再进行堆化（自上而下）

业务办理排队叫号，VIP客户插队

电商抢购活动，会员级别高的用户优先抢购到商品

应用场景：

最小堆演示

PriorityBlockingQueue

一个使用优先级队列实现的无界阻塞队列

与PriorityBlockingQueue类似，不过没有阻塞功能

数据结构：PriorityQueue

阻塞对象：Condition available

入队：不阻塞，无界队列，与优先级队列入队相同，available

为空时阻塞

不为空（已有线程阻塞），直接阻塞

为空，则将当前线程置为leader，并按照过期时间进行阻塞

判断leader线程是否为空（为了保证优先级）

大于0，说明没过期，则阻塞

淘宝订单业务:下单之后如果三十分钟之内没有付款就自动取消订单

商城订单超时关闭

饿了么订餐通知:下单成功后60s之后给用户发送短信通知。

异步短信通知功能

关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭。

缓存过期清除。缓存中的对象，超过了存活时间，需要从缓存中移出。

任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求等。

DelayQueue