BlockingQueue
2024-10-18 15:35:46 0 举报AI智能生成
并发包下常用的阻塞队列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
队首队尾都可，API比较丰富，队首队尾均可添加/删除元素
是一个没有数据缓冲的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
为空时阻塞
小于等于0则出队
不为空（已有线程阻塞），直接阻塞
为空，则将当前线程置为leader，并按照过期时间进行阻塞
判断leader线程是否为空（为了保证优先级）
大于0，说明没过期，则阻塞
检查堆顶元素过期时间
淘宝订单业务:下单之后如果三十分钟之内没有付款就自动取消订单
商城订单超时关闭
饿了么订餐通知:下单成功后60s之后给用户发送短信通知。
异步短信通知功能
关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭。
缓存过期清除。缓存中的对象，超过了存活时间，需要从缓存中移出。
任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求等。
DelayQueue
BlockingQueue
0 条评论
回复 删除
下一页
