阻塞队列(Blocking Queue)
一、队列的定义
说的阻塞队列,就先了解下什么是队列,队列也是一种特殊的线性表结构,在线性表的基础上加了一条限制:那就是一端入队列,一端出队列,且需要遵循FIFO(先进先出)的原则
队列的入口一端叫做队尾(rear),出口一端叫做队头(front),最简单的比如就是排队买火车票,新加入的排队者必须在队尾插入,而下一个排队结束的永远的队伍的第一个人
如下图示:
二、阻塞队列的定义
了解了队列,就很好理解什么是阻塞队列,既然是阻塞的,那就是需要等待,而队列的操作只有入队和出队,那就是在入队和出队的时候等待了,所以总结下阻塞队列就是:
1、入队时,如果队列已经满了,就阻塞等待直到队列中有位置可以插入
2、出队时,如果队列中为空,就阻塞等待直到队列中有数据可以出队列
三、Java队列的定义
Java集合体系分为Collection和Map两大阵营,而队列Queue则属于Collection系列
3.1、Queue接口
Queue接口继承之Collection接口,在Collection的继承上增加了队列独有的方法
boolean offer(E e):向队列中插入元素,插入成功返回true;插入失败返回false
E peek():获取队列头部的元素,如果队列为空则返回null
E poll():获取并移除头部的元素,队列为空则返回null,和peek的区别是获取头部元素之后将头部元素删除,符合队列的出队操作
E remove():获取并移除头部的元素,如果为空则抛异常
3.2、BlockingQueue接口
BlockingQueue接口是继承之Queue,在Queue方法的继承上添加了抛出异常操作,因为BlockingQueue上阻塞队列,所以就存在阻塞时间过长需要中断阻塞操作,或者是超时中断阻塞操作
而BlockingQueue也就是阻塞队列的*接口,BlockingQueue不同的实现类就是实现了不同的阻塞队列的效果
阻塞队列的入队和出队操作可以分为多种操作方式:
1、抛异常:入队时队列满了直接抛异常;出队时队列为空直接抛异常 如:add方法和remove方法
2、返回boolean:入队或出队成功返回true;失败返回false 如:offer方法和poll方法
3、阻塞:入队或出队失败则一直阻塞直到成功或者被其他线程唤醒 如:put方法和take方法
4、超时阻塞:入队和出队失败则阻塞指定的时间,超时了还是失败则取消阻塞 如:offer(timeout)和poll(timeout)方法
四、Java中阻塞队列的不同实现
4.1、ArrayBlockingQueue
基于数组实现的阻塞队列,初始化时需要定义数组的大小,也就是队列的大小,所以这个队列是一个有界队列。
ArrayBlockingQueue的主要属性有:
//存储元素的数组
final Object[] items; //下一个出队的索引
int takeIndex; //下一个入队的索引
int putIndex; //队列的大小
int count; //可重入锁
final ReentrantLock lock; //出队操作的等待
private final Condition notEmpty; //入队操作的等待
private final Condition notFull;
实现原理:通过可重入锁ReenTrantLock+Condition 来实现多线程之间的同步效果
入队过程:
add方法:插入成功返回true;插入失败抛异常
put方法:插入元素到尾部,如果失败则调用Condition.await()方法进行阻塞等待,直到被唤醒;
offer方法:插入元素到尾部,如果失败则直接返回false,
offer(timeout):插入元素到尾部,如果失败则调用Condition.await(timeout)方法进行阻塞等待指定时间,直到被唤醒或阻塞超时,还是失败就返回false
而一旦插入成功,就会唤醒出队的等待操作,执行出队的Condition的signal()方法
出队过程:
主要方法为:poll()、take()、remove()
基本上和入队过程类似,出队结束会唤醒入队的等待操作,执行入队的Condition的signal()方法
而不管是入队操作还是出队操作,都会通过ReentrantLock来控制同步效果,通过两个Condition来控制线程之间的通信效果
另外入队和出队操作分别通过两个索引 takeIndex 和putIndex来指定数组的位置,默认从0开始分别递增,如果达到数组的容量大小,就表示到了数组的边界了,此时再设置index=0,相当于数组是一个环形数组
环形数组的好处是增删数据时不需要挪动数组中的其他数据,只需要改变入队和出队的指针即可。而如果不是环形数组而是顺序数组的话,入队和出队就需要大量移动数据,否则数组空间一下就被用完了,性能较差
4.2、LinkedBlockingQueue
基于链表实现的阻塞队列,既然是链表,那么就可以看出这种阻塞队列含有链表的特性,那就是*。但是实际上LinkedBlockingQueue是有界队列,默认大小是Integer的最大值,而也可以通过构造方法传入固定的capacity大小设置
LinkedBlockingQueue有一个内部类Node,属性有:E ite和Node next,所以可以看出LinkedBlockingQueue是一个单向链表
基本属性为:
//队列大小,默认为Integer的最大值
private final int capacity; //当前队列元素个数
private final AtomicInteger count = new AtomicInteger(); //队列的头部元素
transient LinkedBlockingQueue.Node<E> head; //队列的尾部元素
private transient LinkedBlockingQueue.Node<E> last; //出队锁
private final ReentrantLock takeLock = new ReentrantLock(); //出队的condition
private final Condition notEmpty = takeLock.newCondition(); //入队锁
private final ReentrantLock putLock = new ReentrantLock(); //入队的condition
private final Condition notFull = putLock.newCondition();
可以看出LinkedBlockingQueue的属性和ArrayBlockingQueue的属性大致差不多,都是通过ReentrantLock和Condition来实现多线程之间的同步,而LinkedBlockingQueue却多了一个ReentrantLock,而不是入队和出队共用同一个锁
那么为什么ArrayBlockingQueue只需要一个ReentrantLock而LinkedBlockingQueue需要两个ReentrantLock呢?
个人想法;
首先,ReentrantLock肯定是越多越好,锁越多那么相同锁的竞争就越少;LinkedBlockingQueue分别有入队锁和出队锁,所以入队和出队的时候不会有竞争锁的关系;而ArrayBlockingQueue只有一个Lock,那么不管是入队还是出队,都需要竞争同一个锁,所以效率会低点。ArrayBlockingQueue是环形数组结构,入队的地址和出队的地址可能是同一个,比如数组table大小为1,那么第一次入队和出队需要操作的位置都是table[0]这个元素,所以入队和出队必须共用同一把锁;而LinkedBlockingQueue是链表形式,内存地址是散列的,入队的元素地址和出队的元素地址永远不可能会是同一个地址。所以可以采用两个锁,分别对入队进行加锁同步和对出队进行加锁同步即可。
4.3、DelayQueue
延迟队列,顾名思义就是只有当元素达到指定的时间后才可以从队列中取出。
根据这个思路可以满足下面几种需求:
1.定时任务:将任务放入队列中设置时间,循环阻塞地从队列中取任务,当从队列中取出数据就表示时间到了
2.缓存过期:循环从队列中取数据,一旦取出数据就表示数据过期了,直接删除即可
DelayQueue主要也是通过ReentrantLock+Condition来保证线程安全,而内部还采用了ProrityQueue来保证队列的优先级,实际就是按延时的时间来进行排序,延迟时间最短的排在队列的头部,
所以每次从头部获取的元素都是最先会过期的数据。
4.4、PriorityBlockingQueue
有优先级的阻塞队列,底层也是通过数组实现,默认初始容量为11,容量不够会自动扩容,扩容的最大值为Integer的最大值-8(有些虚拟机再实现数组头部存储内容所预留的空间),所以基本上可以认为是*阻塞队列
扩容时的线程安全通过ReentrantLock+CAS+volatine实现
用法基本上和ArrayBlockingQueue差不多,只不过PriorityBlockingQueue相当于是*,另外最重要的一点是它是有优先级的,既然有优先级就涉及到排序
PriorityBlockingQueue默认采用Comparator,或者存储的元素有自定义的比较器。
而存储数据的数组也不是简单的数组,而是采用了二叉堆的数据结构,同时满足完全二叉树+堆的数据结构(最大堆上层的元素必须大于所有下层的元素;最小堆或者上层的元素必须小于所有下层的元素)
而PriorityBlockingQueue默认是采用的最小堆,即每次取出的元素都是优先级最小的。那么问题来了,如果通过数组来实现一个二叉堆呢?见下面的图解:
先看下二叉堆的数据结构:
可以看出二叉堆的上层永远比下层的优先级要高,而且可以发现上层节点和子节点的关系:父节点序号=(子节点序号-1)/2;左字节点序号=父节点序号*2+1;右字节点序号=父节点序号*2+2
那么上面的数据结构就可以通过数组来存储,如下图示:
插入操作:将元素直接插入到最底层的节点,如上图插入节点88
1. 节点88成为节点40到左子节点,新加入的节点遍历和自己的父节点进行比较,
2.节点88比节点40大,两者互换位置;继续88比80大,互换位置,88比100小,位置不动,
3.结果是新插入的节点88成为节点100的左子节点,节点80成为节点88点右子节点,节点40成功节点80点右子节点
删除操作:阻塞队列的删除是只删除位置为0的元素,也就是节点100
1.直接取出数组[0]位置的元素
2.将队列尾部节点放到头部来,如上图就是把节点5放到最顶层,
3.然后将头节点依次和子节点进行比较,然后进行位置互换操作
所以每次插入和删除元素最多操作次数就是 二叉堆的高度
代码不再分析,主要就是实现来二叉堆的逻辑,并且通过ReentrantLock+Condition来保证线程间的同步效果
4.5、SynchronousQueue
SynchonousQueue是比较特殊的阻塞队列,特殊之处就是这个叫队列的队列没有容量,又或者说容量为0,所以一旦有元素插入此队列,由于没有容量,就必须被阻塞直到元素被取出
所以SynchronousQueue更像是一个通道,一端发数据,一端消费数据,数据不可以被堆积,发送方或消费方处理不过来或者是不处理都会导致阻塞
五、阻塞队列的应用
5.1、线程池
线程池的构造函数就包含了阻塞队列
Java集合--阻塞队列及各种实现的解析的更多相关文章
-
Java多线程 阻塞队列和并发集合
转载:大关的博客 Java多线程 阻塞队列和并发集合 本章主要探讨在多线程程序中与集合相关的内容.在多线程程序中,如果使用普通集合往往会造成数据错误,甚至造成程序崩溃.Java为多线程专门提供了特有的 ...
-
Java:阻塞队列
Java:阻塞队列 本笔记是根据bilibili上 尚硅谷 的课程 Java大厂面试题第二季 而做的笔记 1. 概述 概念 队列 队列就可以想成是一个数组,从一头进入,一头出去,排队买饭 阻塞队列 B ...
-
java 多线程阻塞队列 与 阻塞方法与和非阻塞方法
Queue是什么 队列,是一种数据结构.除了优先级队列和LIFO队列外,队列都是以FIFO(先进先出)的方式对各个元素进行排序的.无论使用哪种排序方式,队列的头都是调用remove()或poll()移 ...
-
Java -- 使用阻塞队列(BlockingQueue)控制线程通信
BlockingQueeu接口是Queue的子接口,但是它的主要作用并不是作为容器,而是作为线程同步的工具. 特征: 当生产者线程试图向BlockingQueue中放入元素时,如果该队列已满,则该线程 ...
-
Java并发--阻塞队列
在前面几篇文章中,我们讨论了同步容器(Hashtable.Vector),也讨论了并发容器(ConcurrentHashMap.CopyOnWriteArrayList),这些工具都为我们编写多线程程 ...
-
JAVA可阻塞队列-ArrayBlockingQueue
在前面的的文章,写了一个带有缓冲区的队列,是用JAVA的Lock下的Condition实现的,但是JAVA类中提供了这项功能,就是ArrayBlockingQueue, ArrayBlockingQu ...
-
Java 集合与队列的插入、删除在并发下的性能比较
这两天在写一个java多线程的爬虫,以广度优先爬取网页,设置两个缓存: 一个保存已经访问过的URL:vistedUrls 一个保存没有访问过的URL:unVistedUrls 需要爬取的数据量不大,对 ...
-
java 可伸缩阻塞队列实现
最近一年多写的最虐心的代码.必须好好复习java并发了.搞了一晚上终于测试都跑通过了,特此纪念,以资鼓励! import java.util.ArrayList; import java.util.L ...
-
java多线程-阻塞队列BlockingQueue
大纲 BlockingQueue接口 ArrayBlockingQueue 一.BlockingQueue接口 public interface BlockingQueue<E> exte ...
随机推荐
-
ios 开发之单例模式
在iOS开发中,有很多地方都选择使用单例模式.有很多时候必须要创建一个对象,并且不能创建多个,用单例就为了防止创建多个对象.单例模式的意思就是某一个类有且只有一个实例.单例模式确保某一个类只有一个实例 ...
-
Visual Studio Code编写HTML
第一步双击打开Visual Studio Code,我们发现什么也没有,但是有一个默认打开的编辑页面.我们先点击File->OpenFoldor 为什么先这么做呢,有两个原因,第一个原因假如你有 ...
-
重构:用Command替换条件调度程序
注:该随笔受启发于 <重构与模式> 第七章 第7.6小节 用Command替换条件调度程序 . 对于Command不做过多解释,这里我找了两个例子.供部分园友参阅:Command例子1 ...
-
asp.net中当点击按钮时出现grid编辑弹框
<dx:ASPxButton runat="server" ID="NewGridButton" Text="新增授权" CssCla ...
-
css cursor属性详解
cursor // 鼠标移上去的鼠标状态 属性值有以下: (可以将鼠标移上以下属性值看看效果) auto crosshair default pointer ...
- Python 文件读和写
-
Android的Handler与Activity线程同步
假设这里有同一个Runnable对象r. 可能采用的方法有: 第一种: handler.post(r); 实际上这种方法并没有调用线程someThread的start方法,而是直接调用了Runaabl ...
-
auto ash v1
startdate=$1enddate=$2#reporttype=$3#reportformat='text'oraclehome=`echo $ORACLE_HOME` dbid=`sqlplus ...
-
Node.js WEB服务器(1)——编写简单的HTTP服务器
基于分而治之的思想,很多架构都会采用分层的模式来处理某类应用.Node.js在Web开发上也是采用这种模式,分别提供了如下的三个层: Node核心 社区模块 应用逻辑 下面是一个最简形式的web服务器 ...
-
洛谷P2569 股票交易
题目传送门https://www.luogu.org/problemnew/show/P2569 第一眼看题就觉得是个dp ,然后看到2000的范围,hmm大概是个n^2的2维dp 开始设状态,第一维 ...