基于数组阻塞队列 ArrayBlockingQueue
前面学习了基于数组的非阻塞双端队列ArrayDeque,其内部维护一个数组和指向队列头和队列尾索引的两个成员变量;本篇则探究下基于数组的阻塞队列是什么样的数据结构,又有什么特性,相较于ArrayDeque又有什么异同;然后就是使用场景了
I. 底层数据结构
先看内部成员变量定义, 和ArrayDequeue相比,差别不大,一个数组,两个索引;此外多了一个锁和两个判定条件
注意
底层数据结构依然是数组,注释上并没有说明要求容量是2的n次方(ArrayDequeue有这个强制限定)
初始化时必须指定队列的容量(即数组的长度,构造方法中的必选参数)
count直接表示队列的元素个数(注意DelayQueue是通过遍历来获取队列长度,且并发修改会有问题,那么这个是如何保证并发的?)
留一个疑问,塞入队列超过数组容量,是否会出现扩容
数据结构如下图
II. 阻塞实现原理
0. Prefer
分析阻塞原理之前,先通过注释解释下ArrayBlockingQueue的使用场景
先进先出队列(队列头的是最先进队的元素;队列尾的是最后进队的元素)
有界队列(即初始化时指定的容量,就是队列最大的容量,不会出现扩容,容量满,则阻塞进队操作;容量空,则阻塞出队操作)
队列不支持空元素
1. 进队
通用的进队方法如下,是非阻塞的方式,当数组满时,直接返回false,为保证并发安全,进队操作是加锁实现
阻塞方式的进队实现如下
源码分析,阻塞入队的逻辑比较清晰,小结一下
非阻塞调用方式offer(e)
阻塞调用方式put(e)或offer(e, timeout, unit)
阻塞调用时,唤醒条件为超时或者队列非满(因此,要求在出队时,要发起一个唤醒操作)
进队成功之后,执行notEmpty.signal()唤起被阻塞的出队线程
2. 出队
非阻塞出队方法如下
阻塞的实现,逻辑比较清晰,首先竞争锁,判断是否为空,是阻塞直到非空;否则弹出队列头元素
小结
非阻塞出队调用poll()方法
阻塞出队调用take()或poll(long,TimeUnit)方法
出队之后,会唤醒因队列满被阻塞的入队线程
出队count计数减1(因为每次只能一个线程出队,所以count的值可以保证并发准确性)
支持在遍历队列时,出队
III. 应用场景及case
创建线程池时,通常会用到ArrayBlockingQueue或者LinkedBlockingQueue,如
延迟队列也是并发安全,ArrayBlockingQueue相比较DelayQueue应用场景的区别主要在
有界和无界(ArrayBlockingQueue不会扩容,而DelayQueue会出现扩容)
前者队列非空就可以出队;后者则需要队列头生效(getDelay()返回值小于0)
前者队列满,则无法入队;后者一直都可以入队
前者FIFO;后者优先级队列,延迟时间小的优先出队
IV. 小结
基于数组阻塞队列ArrayBlockingQueue
有界数组阻塞队列,FIFO,先进先出,初始化时指定数组长度
阻塞出队方法:take()或poll(long, TimeUnit)
非阻塞出队方法:poll()
阻塞入队方法:offer(E, long, TimeUnit)或put(E)
非阻塞入队方法:offer(E) add(E)
队列为空,出队会被阻塞;队列满时,进队会被阻塞
根据内部计数count,可以直接获取队列长度(count的并发安全是由进队出队上锁,保证同一时刻只有一个线程修改count值保证的)