allbet欧博真人客户端:解读 java 并发行列 BlockingQueue

admin 1个月前 (09-22) 科技 56 1

 

点击添加图片形貌(最多60个字)编辑

 

 

今天呢!灯塔君跟人人讲:

解读 java 并发行列 BlockingQueue

最近得空,想写篇文章好好说说 java 线程池问题,我信赖很多人都一知半解的,包罗我自己在仔仔细细看源码之前,也有许多的不解,甚至有些地方我一直都没有明了到位。

说到线程池实现,那么就不得不涉及到种种 BlockingQueue 的实现,那么我想就 BlockingQueue 的问题和人人分享分享我领会的一些知识。

本文没有像之前剖析 AQS 那样一行一行源码剖析了,不外照样把其中最重要和最难明了的代码说了一遍,以是难免篇幅略长。本文涉及到对照多的 Doug Lea 对 BlockingQueue 的设计头脑,希望有心的读者真的可以有一些收获,我以为自己照样写了一些干货的。

本文直接参考 Doug Lea 写的 Java doc 和注释,这也是我们在学习 java 并发包时最好的质料了。希望人人能有所思、有所悟,学习 Doug Lea 的代码气概,并将其优雅、严谨的作风应用到我们写的每一行代码中。

目录:

BlockingQueue

开篇先先容下 BlockingQueue 这个接口的规则,后面再看实在现。

首先,最基本的来说, BlockingQueue 是一个先进先出的行列(Queue),为什么说是壅闭(Blocking)的呢?是由于 BlockingQueue 支持当获取行列元素然则行列为空时,会壅闭守候行列中有元素再返回;也支持添加元素时,若是行列已满,那么等到行列可以放入新元素时再放入。

BlockingQueue 是一个接口,继续自 Queue,以是实在现类也可以作为 Queue 的实现来使用,而 Queue 又继续自 Collection 接口。

BlockingQueue 对插入操作、移除操作、获取元素操作提供了四种差别的方式用于差别的场景中使用:1、抛出异常;2、返回特殊值(null 或 true/false,取决于详细的操作);3、壅闭守候此操作,直到这个操作乐成;4、壅闭守候此操作,直到乐成或者超时指定时间。总结如下:

 

点击添加图片形貌(最多60个字)编辑

 

BlockingQueue 的各个实现都遵照了这些规则,固然我们也不用死记这个表格,知道有这么回事,然后写代码的时刻凭据自己的需要去看方式的注释来选取合适的方式即可。

对于 BlockingQueue,我们的关注点应该在 put(e) 和 take() 这两个方式,由于这两个方式是带壅闭的。

BlockingQueue 不接受 null 值的插入,响应的方式在碰着 null 的插入时会抛出 NullPointerException 异常。null 值在这里通常用于作为特殊值返回(表格中的第三列),代表 poll 失败。以是,若是允许插入 null 值的话,那获取的时刻,就不能很好地用 null 来判断到底是代表失败,照样获取的值就是 null 值。

一个 BlockingQueue 可能是有界的,若是在插入的时刻,发现行列满了,那么 put 操作将会壅闭。通常,在这里我们说的无界行列也不是说真正的无界,而是它的容量是 Integer.MAX_VALUE(21亿多)。

BlockingQueue 是设计用来实现生产者-消费者行列的,固然,你也可以将它当做通俗的 Collection 来用,前面说了,它实现了 java.util.Collection 接口。例如,我们可以用 remove(x) 来删除随便一个元素,然则,这类操作通常并不高效,以是只管只在少数的场所使用,好比一条新闻已经入队,然则需要做作废操作的时刻。

BlockingQueue 的实现都是线程平安的,然则批量的聚集操作如 addAll, containsAll, retainAll 和 removeAll  纷歧定是原子操作。如 addAll(c) 有可能在添加了一些元素后中途抛出异常,此时 BlockingQueue 中已经添加了部门元素,这个是允许的,取决于详细的实现。

BlockingQueue 不支持 close 或 shutdown 等关闭操作,由于开发者可能希望不会有新的元素添加进去,此特征取决于详细的实现,不做强制约束。

最后,BlockingQueue 在生产者-消费者的场景中,是支持多消费者和多生产者的,说的实在就是线程平安问题。

信赖上面说的每一句都很清晰了,BlockingQueue 是一个对照简朴的线程平安容器,下面我会剖析其详细的在 JDK 中的实现,这里又到了 Doug Lea 演出时间了。

BlockingQueue 实现之 ArrayBlockingQueue

ArrayBlockingQueue 是 BlockingQueue 接口的有界行列实现类,底层接纳数组来实现。

其并发控制接纳可重入锁来控制,不管是插入操作照样读取操作,都需要获取到锁才气举行操作。

若是读者看过我之前写的《一行一行源码剖析清晰 AbstractQueuedSynchronizer(二)》 的关于 Condition 的文章的话,那么你一定能很容易看懂 ArrayBlockingQueue  的源码,它接纳一个 ReentrantLock 和响应的两个 Condition 来实现。

ArrayBlockingQueue 共有以下几个属性:

点击添加图片形貌(最多60个字)编辑

 

我们用个示意图来形貌其同步机制:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第1张 点击添加图片形貌(最多60个字)编辑

 

ArrayBlockingQueue 实现并发同步的原理就是,读操作和写操作都需要获取到 AQS 独占锁才气举行操作。若是行列为空,这个时刻读操作的线程进入到读线程行列排队,守候写线程写入新的元素,然后叫醒读线程行列的第一个守候线程。若是行列已满,这个时刻写操作的线程进入到写线程行列排队,守候读线程将行列元素移除腾出空间,然后叫醒写线程行列的第一个守候线程。

对于 ArrayBlockingQueue,我们可以在组织的时刻指定以下三个参数:

  1. 行列容量,其限制了行列中最多允许的元素个数;
  2. 指定独占锁是公正锁照样非公正锁。非公正锁的吞吐量对照高,公正锁可以保证每次都是守候最久的线程获取到锁;
  3. 可以指定用一个聚集来初始化,将此聚集中的元素在组织方式时代就先添加到行列中。

更详细的源码我就不举行剖析了,由于它就是 AbstractQueuedSynchronizer 中 Condition 的使用,感兴趣的读者请看我写的《一行一行源码剖析清晰 AbstractQueuedSynchronizer(二)》,由于只要看懂了那篇文章,ArrayBlockingQueue 的代码就没有剖析的必要了,固然,若是你完全不懂 Condition,那么基本上也就可以说看不懂 ArrayBlockingQueue 的源码了。

BlockingQueue 实现之 LinkedBlockingQueue

底层基于单向链表实现的壅闭行列,可以当做无界行列也可以当做有界行列来使用。看组织方式:

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第2张 点击添加图片形貌(最多60个字)编辑

 

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第3张 点击添加图片形貌(最多60个字)编辑

我们看看这个类有哪些属性:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第4张 点击添加图片形貌(最多60个字)编辑

这里用了两个锁,两个 Condition,简朴先容如下:

takeLock 和 notEmpty 怎么搭配:若是要获取(take)一个元素,需要获取 takeLock 锁,然则获取了锁还不够,若是行列此时为空,还需要行列不为空(notEmpty)这个条件(Condition)。

putLock 需要和 notFull 搭配:若是要插入(put)一个元素,需要获取 putLock 锁,然则获取了锁还不够,若是行列此时已满,还需要行列不是满的(notFull)这个条件(Condition)。

首先,这里用一个示意图来看看 LinkedBlockingQueue 的并发读写控制,然后再最先剖析源码:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第5张 点击添加图片形貌(最多60个字)编辑

 

看懂这个示意图,源码也就简朴了,读操作是排好队的,写操作也是排好队的,唯一的并发问题在于一个写操作和一个读操作同时举行,只要控制好这个就可以了。

先上组织方式:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第6张 点击添加图片形貌(最多60个字)编辑

注重,这里会初始化一个空的头结点,那么第一个元素入队的时刻,行列中就会有两个元素。读取元素时,也总是获取头节点后面的一个节点。count 的计数值不包罗这个头节点。

我们来看下 put 方式是怎么将元素插入到队尾的:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第7张 点击添加图片形貌(最多60个字)编辑

我们再看看 take 方式:

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第8张 点击添加图片形貌(最多60个字)编辑

源码剖析就到这里竣事了吧,究竟照样对照简朴的源码,基本上只要读者认真点都看得懂。

BlockingQueue 实现之 SynchronousQueue

它是一个特殊的行列,它的名字实在就蕴含了它的特征 - - 同步的行列。为什么说是同步的呢?这里说的并不是多线程的并发问题,而是由于当一个线程往行列中写入一个元素时,写入操作不会立刻返回,需要守候另一个线程来将这个元素拿走;同理,当一个读线程做读操作的时刻,同样需要一个相匹配的写线程的写操作。这里的 Synchronous 指的就是读线程和写线程需要同步,一个读线程匹配一个写线程。

我们对照少使用到 SynchronousQueue 这个类,不外它在线程池的实现类 ThreadPoolExecutor 中得到了应用,感兴趣的读者可以在看完这个后去看看响应的使用。

虽然上面我说了行列,然则 SynchronousQueue 的行列实在是虚的,其不提供任何空间(一个都没有)来存储元素。数据必须从某个写线程交给某个读线程,而不是写到某个行列中守候被消费。

你不能在 SynchronousQueue 中使用 peek 方式(在这里这个方式直接返回 null),peek 方式的语义是只读取不移除,显然,这个方式的语义是不符合 SynchronousQueue 的特征的。SynchronousQueue 也不能被迭代,由于根本就没有元素可以拿来迭代的。虽然 SynchronousQueue 间接地实现了 Collection 接口,然则若是你将其当做 Collection 来用的话,那么聚集是空的。固然,这个类也是不允许通报 null 值的(并发包中的容器类似乎都不支持插入 null 值,由于 null 值往往用作其他用途,好比用于方式的返回值代表操作失败)。

接下来,我们来看看详细的源码实现吧,它的源码不是很简朴的那种,我们需要先搞清晰它的设计头脑。

源码加注释大概有 1200 行,我们先看大框架:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第9张 点击添加图片形貌(最多60个字)编辑

 

Transferer 有两个内部实现类,是由于组织 SynchronousQueue 的时刻,我们可以指定公正计谋。公正模式意味着,所有的读写线程都遵守先来后到,FIFO 嘛,对应 TransferQueue。而非公正模式则对应 TransferStack。

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第10张 点击添加图片形貌(最多60个字)编辑

我们先接纳公正模式剖析源码,然后再说说公正模式和非公正模式的区别。

接下来,我们看看 put 方式和 take 方式:

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第11张 点击添加图片形貌(最多60个字)编辑

我们看到,写操作 put(E o) 和读操作 take() 都是挪用 Transferer.transfer(…) 方式,区别在于第一个参数是否为 null 值。

我们来看看 transfer 的设计思绪,其基本算法如下:

  1. 当挪用这个方式时,若是行列是空的,或者行列中的节点和当前的线程操作类型一致(如当前操作是 put 操作,而行列中的元素也都是写线程)。这种情形下,将当前线程加入到守候行列即可。
  2. 若是行列中有守候节点,而且与当前操作可以匹配(如行列中都是读操作线程,当前线程是写操作线程,反之亦然)。这种情形下,匹配守候行列的队头,出队,返回响应数据。

实在这里有个隐含的条件被知足了,行列若是不为空,一定都是同种类型的节点,要么都是读操作,要么都是写操作。这个就要看到底是读线程积压了,照样写线程积压了。

我们可以假设出一个男女配对的场景:一个男的过来,若是一个人都没有,那么他需要守候;若是发现有一堆男的在守候,那么他需要排到行列后面;若是发现是一堆女的在排队,那么他直接牵走队头的谁人女的。

既然这里说到了守候行列,我们先看看实在现,也就是 QNode:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第12张 点击添加图片形貌(最多60个字)编辑

信赖说了这么多以后,我们再来看 transfer 方式的代码就轻松多了。

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第13张 点击添加图片形貌(最多60个字)编辑

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第14张 点击添加图片形貌(最多60个字)编辑

 

Doug Lea 的巧妙之处在于,将各个代码凑在了一起,使得代码异常简练,固然也同时增加了我们的阅读肩负,看代码的时刻,照样得仔细想想种种可能的情形。

下面,再说说前面说的公正模式和非公正模式的区别。

信赖人人心内里已经有了公正模式的事情流程的概念了,我就简朴说说 TransferStack 的算法,就不剖析源码了。

  1. 当挪用这个方式时,若是行列是空的,或者行列中的节点和当前的线程操作类型一致(如当前操作是 put 操作,而栈中的元素也都是写线程)。这种情形下,将当前线程加入到守候栈中,守候配对。然后返回响应的元素,或者若是被作废了的话,返回 null。
  2. 若是栈中有守候节点,而且与当前操作可以匹配(如栈内里都是读操作线程,当前线程是写操作线程,反之亦然)。将当前节点压入栈顶,和栈中的节点举行匹配,然后将这两个节点出栈。配对和出栈的动作实在也不是必须的,由于下面的一条会执行同样的事情。
  3. 若是栈顶是举行匹配而入栈的节点,辅助其举行匹配并出栈,然后再继续操作。

应该说,TransferStack 的源码要比 TransferQueue 的庞大一些,若是读者感兴趣,请自行举行源码阅读。

BlockingQueue 实现之 PriorityBlockingQueue

带排序的 BlockingQueue 实现,其并发控制接纳的是 ReentrantLock,行列为无界行列(ArrayBlockingQueue 是有界行列,LinkedBlockingQueue 也可以通过在组织函数中传入 capacity 指定行列最大的容量,然则 PriorityBlockingQueue 只能指定初始的行列巨细,后面插入元素的时刻,若是空间不够的话会自动扩容)。

简朴地说,它就是 PriorityQueue 的线程平安版本。不可以插入 null 值,同时,插入行列的工具必须是可对照巨细的(comparable),否则报 ClassCastException 异常。它的插入操作 put 方式不会 block,由于它是无界行列(take 方式在行列为空的时刻会壅闭)。

它的源码相对对照简朴,本节将先容其焦点源码部门。

我们来看看它有哪些属性:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第15张 点击添加图片形貌(最多60个字)编辑

 

此类实现了 Collection 和 Iterator 接口中的所有接口方式,对其工具举行迭代并遍历时,不能保证有序性。若是你想要实现有序遍历,建议接纳 Arrays.sort(queue.toArray()) 举行处置。PriorityBlockingQueue 提供了 drainTo 方式用于将部门或所有元素有序地填充(准确说是转移,会删除原行列中的元素)到另一个聚集中。另有一个需要说明的是,若是两个工具的优先级相同(compare 方式返回 0),此行列并不保证它们之间的顺序。

PriorityBlockingQueue 使用了基于数组的二叉堆来存放元素,所有的 public 方式接纳同一个 lock 举行并发控制。

二叉堆:一颗完全二叉树,它异常适适用数组举行存储,对于数组中的元素 a[i],其左子节点为 a[2*i+1],其右子节点为 a[2*i + 2],其父节点为 a[(i-1)/2],其堆序性子为,每个节点的值都小于其左右子节点的值。二叉堆中最小的值就是根节点,然则删除根节点是对照贫苦的,由于需要调整树。

简朴用个图解释一下二叉堆,我就不说太多专业的严谨的术语了,这种数据结构的优点是一目了然的,最小的元素一定是根元素,它是一棵满的树,除了最后一层,最后一层的节点从左到右慎密排列。

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第16张 点击添加图片形貌(最多60个字)编辑

下面最先 PriorityBlockingQueue 的源码剖析,首先我们来看看组织方式:

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第17张 点击添加图片形貌(最多60个字)编辑

 

接下来,我们来看看其内部的自动扩容实现:

 

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第18张 点击添加图片形貌(最多60个字)编辑

 

扩容方式对并发的控制也异常的巧妙,释放了原来的独占锁 lock,这样的话,扩容操作和读操作可以同时举行,提高吞吐量。

下面,我们来剖析下写操作 put 方式和读操作 take 方式。

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第19张 点击添加图片形貌(最多60个字)编辑

对于二叉堆而言,插入一个节点是简朴的,插入的节点若是比父节点小,交流它们,然后继续和父节点对照。

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第20张 点击添加图片形貌(最多60个字)编辑

 

我们用图来示意一下,我们接下来要将 11 插入到行列中,看看 siftUp 是怎么操作的。

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第21张 点击添加图片形貌(最多60个字)编辑

 

 

我们再看看 take 方式:

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第22张 点击添加图片形貌(最多60个字)编辑

dequeue 方式返回队头,并调整二叉堆的树,挪用这个方式必须先获取独占锁。

空话不多说,出队是异常简朴的,由于队头就是最小的元素,对应的是数组的第一个元素。难点是队头出队后,需要调整树。

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第23张 点击添加图片形貌(最多60个字)编辑

 

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第24张 点击添加图片形貌(最多60个字)编辑

 

记着二叉堆是一棵完全二叉树,那么根节点 10 拿掉后,最后面的元素 17 必须找到合适的地方放置。首先,17 和 10 不能直接交流,那么先将根节点 10 的左右子节点中较小的节点往上滑,即 12 往上滑,然后原来 12 留下了一个空节点,然后再把这个空节点的较小的子节点往上滑,即 13 往上滑,最后,留出了位子,17 补上即可。

我稍微调整下这个树,以便读者能更明了:

allbet欧博真人客户端:解读 java 并发行列 BlockingQueue 第25张 点击添加图片形貌(最多60个字)编辑

好了, PriorityBlockingQueue 我们也说完了。

总结

我知道本文过长,信赖一字不漏看完的读者一定是少数。

ArrayBlockingQueue 底层是数组,有界行列,若是我们要使用生产者-消费者模式,这是异常好的选择。

LinkedBlockingQueue 底层是链表,可以当做无界和有界行列来使用,以是人人不要以为它就是无界行列。

SynchronousQueue 自己不带有空间来存储任何元素,使用上可以选择公正模式和非公正模式。

PriorityBlockingQueue 是无界行列,基于数组,数据结构为二叉堆,数组第一个也是树的根节点总是最小值。

,

欧博手机版

欢迎进入欧博手机版(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

皇冠APP声明:该文看法仅代表作者自己,与本平台无关。转载请注明:allbet欧博真人客户端:解读 java 并发行列 BlockingQueue

网友评论

  • (*)

最新评论

  • UG环球注册 2020-09-22 00:02:36 回复

    欧博网址欢迎进入欧博网址(Allbet Gaming):www.aLLbetgame.us,欧博网址开放会员注册、代理开户、电脑客户端下载、苹果安卓下载等业务。我是看文小能手

    1

文章归档

站点信息

  • 文章总数:544
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1015
  • 评论总数:168
  • 浏览总数:3181