BlockingQueue
2023-04-07 23:06:49 0 举报AI智能生成
Java阻塞队列总结思维导图
作者其他创作
大纲/内容
ArrayBlockingQueue
有界阻塞队列，先进先出，存取相互排斥
数据结构：静态数组
容量固定必须指定长度，没有扩容机制
没有元素的位置也占用空间，被 null 占位
锁：ReentrantLock
存取是同一把锁，操作的是同一个数组对象，存取互相排斥
阻塞对象
notEmpty
出队：队列count=0，无元素可取时，阻塞在该对象上
notFull
入队：队列count=length，放不进去元素时，阻塞在该对象上
入队
从队首开始添加元素，记录putIndex（到队尾时设置为0）
唤醒notEmpty
出队
从队首开始取出元素，记录takeIndex（到队尾时设置为0）
唤醒notFull
两个指针都是从队首向队尾移动，保证队列的先进先出原则
LinkedBlockingQueue
无界阻塞队列，可以指定容量，默认为 Integer.MAX_VALUE，先进先出，存取互不干扰
数据结构：链表
可以指定容量，默认为Integer.MAX_VALUE，内部类 Node 存储元素
锁分离：存取互不干扰，存取操作的是不同的Node对象
takeLock
取Node节点保证前驱后继不会乱
putLock
存Node节点保证前驱后继不会乱
阻塞对象
notEmpty
出队：队列count=0，无元素可取时，阻塞在该对象上
notFull
入队：队列count=capacity，放不进去元素时，阻塞在该对象上
入队
队尾入队，由last指针记录
出队
队首出队，由head指针记录
线程池中为什么使用LinkedBlockingQueue而不用ArrayBlockingQueue？
锁分离
LinkedBlockingDeque
一个链表阻塞双端队列，无界可以指定容量，默认为 Integer.MAX_VALUE
数据结构：链表（同LinkedBlockingQueue）
内部类 Node 存储元素
锁：ReentrantLock（同ArrayBlockingQueue）
存取是同一把锁，操作的是同一个数组对象
阻塞对象（同LinkedBlockingQueue）
notEmpty
无元素可取时，阻塞在该对象上（count=0）
notFull
放不进去时，阻塞在该对象上（count=capacity）
入队
出队
应用场景
常用于 “工作窃取算法”
SynchronousQueue
是一个没有数据缓冲的BlockingQueue，容量为0，它不会为队列中元素维护存储空间，它只是多个线程之间数据交换的媒介。
数据结构：链表(Node)
在其内部类中维护了数据
先消费（take），后生产(put)
第一个线程Thread0是消费者访问，此时队列为空，则入队（创建Node结点并赋值）
第二个线程Thread1也是消费者访问，与队尾模式相同，继续入队
第三个线程Thread2是生产者，携带了数据e，与队尾模式不同，不进行入队操作；直接将该线程携带的数据e返回给队首的消费者，并唤醒队首线程Thread1（默认非公平策略是栈结构），出队
反之，先生产(put)后消费(take)，原理一样
锁：CAS+自旋（无锁）
阻塞：自旋了一定次数后调用 LockSupport.park()
存取调用同一个方法：transfer()
put、offer 为生产者，携带了数据 e，为 Data 模式，设置到 SNode或QNode 属性中
take、poll 为消费者，不携帯数据，为 Request 模式，设置到 SNode或QNode属性中
过程
线程访问阻塞队列，先判断队尾节点或者栈顶节点的 Node 与当前入队模式是否相同
相同则构造节点 Node 入队，并阻塞当前线程，元素 e 和线程赋值给 Node 属性
不同则将元素 e（不为 null） 返回给取数据线程，队首或栈顶线程被唤醒，出队
公平模式
TransferQueue
队尾匹配(判断模式)，队头出队，先进先出
非公平模式（默认策略）
TransferStack
队尾匹配(判断模式)，队头出队，先进先出
应用场景
SynchronousQueue非常适合传递性场景做交换工作，生产者的线程和消费者的线程同步传递某些信息、事件或者任务。
SynchronousQueue的一个使用场景是在线程池里。如果我们不确定来自生产者请求数量，但是这些请求需要很快的处理掉，那么配合SynchronousQueue为每个生产者请求分配一个消费线程是处理效率最高的办法。Executors.newCachedThreadPool()就使用了SynchronousQueue，这个线程池根据需要（新任务到来时）创建新的线程，如果有空闲线程则会重复使用，线程空闲了60秒后会被回收。
LinkedTransferQueue
一个由链表结构组成的无界阻塞队列
是 SynchronousQueue 和 LinkedBlockingQueue 的合体
数据结构：链表Node
锁：CAS+自旋（无锁）
阻塞：自旋了一定次数后调用 LockSupport.park()
可以自己控制存元素是否需要阻塞线程，比如使用四个添加元素的方法就不会阻塞线程，只入队元素，使用 transfer() 会阻塞线程
取元素与 SynchronousQueue 基本一样，都会阻塞等待有新的元素进入被匹配到
PriorityBlockingQueue
一个支持优先级排序的无界阻塞队列
优先级高的先出队，优先级低的后出队
数据结构：数组 + 二叉堆
默认容量11，可指定初始容量，会自动扩容，最大容量是(Integer.MAX_VALUE - 8)
锁：ReentrantLock
存取是同一把锁
阻塞对象：NotEmpty
出队，队列为空时阻塞
入队
不阻塞，永远返回成功，无界
根据比较器进行堆化（排序）自下而上
传入比较器对象就按照比较器的顺序排序
如果比较器为 null，则按照自然顺序排序
出队
优先级最高的元素在堆顶（弹出堆顶元素）
弹出前比较两个子节点再进行堆化（自上而下）
应用场景：
业务办理排队叫号，VIP客户插队
电商抢购活动，会员级别高的用户优先抢购到商品
最小堆演示
DelayQueue
一个使用优先级队列实现的无界阻塞队列
数据结构：PriorityQueue
与PriorityBlockingQueue类似，不过没有阻塞功能
锁：ReentrantLock
阻塞对象：Condition available
入队：不阻塞，无界队列，与优先级队列入队相同，available
出队
为空时阻塞
检查堆顶元素过期时间
小于等于0则出队
大于0，说明没过期，则阻塞
判断leader线程是否为空（为了保证优先级）
不为空（已有线程阻塞），直接阻塞
为空，则将当前线程置为leader，并按照过期时间进行阻塞
应用场景
商城订单超时关闭
淘宝订单业务:下单之后如果三十分钟之内没有付款就自动取消订单
异步短信通知功能
饿了么订餐通知:下单成功后60s之后给用户发送短信通知。
关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭。
缓存过期清除。缓存中的对象，超过了存活时间，需要从缓存中移出。
任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求等。
0 条评论
下一页
