您现在的位置是:网站首页> 内容页

阻塞队列分析

  • 老子有钱送体验卡
  • 2019-03-20
  • 136人已阅读
简介转载请标注来源:https://www.cnblogs.com/xmzJava/p/9380649.html前言 在分析多线程的文章中,我们知道了Executors是通过阻塞队列接受任

转载请标注来源:https://www.cnblogs.com/xmzJava/p/9380649.html

前言


 在分析多线程的文章中,我们知道了Executors是通过阻塞队列接受任务。例如 FixedThreadPool 使用的是 LinkedBlockingQueue, CachedThreadPool 使用的是 SynchronousQueue。阻塞队列的基类是 BlockingQueue,他的实现类如下所示

 

BlockingQueue的api我们需要重点关注下,理解了这些api的作用,对于实现类的分析会轻松很多。

类型api名称是否阻塞简述
放入数据offer(anObject)将anObject加到BlockingQueue里,即如果BlockingQueue可以容纳,则返回true,否则返回false
offer(E o, long timeout, TimeUnit unit)可以设定等待的时间,如果在指定的时间内,还不能往队列中加入BlockingQueue,则返回失败
put(anObject)把anObject加到BlockingQueue里,如果BlockQueue没有空间,则调用此方法的线程被阻断直到BlockingQueue里面有空间再继续
获取数据poll(time)取走BlockingQueue里排在首位的对象,若不能立即取出,则可以等time参数规定的时间,取不到时返回null
poll(long timeout, TimeUnit unit)同上
take()取走BlockingQueue里排在首位的对象,若BlockingQueue为空,阻断进入等待状态直到BlockingQueue有新的数据被加入
drainTo()一次性从BlockingQueue获取所有可用的数据对象(还可以指定获取数据的个数),通过该方法,可以提升获取数据效率;不需要多次分批加锁或释放锁

 

 

 

 

 

 

 

 

重点关注表中的阻塞类型的方法,他们是阻塞队列的核心。接下来讲述几个常用的阻塞队列的存取数据api。

ArrayBolckingQueue


在ArrayBlockingQueue内部,维护了一个定长数组,以便缓存队列中的数据对象。我们先看offer方法

我们再看下 enqueue

 

以上是非阻塞的存放。我们再看阻塞版本的存放

可以看到,两种方式的差别其实很小,一个是阻塞一段时间后直接返回false,一个是无限期的阻塞。我们再看下取数据的api。

再看下dequeue

 以上就是ArrayBlockingQunue的具体分析。

 

LinkedBlockingQueue


 LinkedBlockingQueue是基于链表的阻塞队列,首先需要注意的是LinkedBlockingQueue是可以无界的,当你不指定容量时他默认的大小是 Integer.MAX_VALUE

链表通过内部的Node来实现,可以看出这是个单项链表。

接下来,我们再看下具体的api 

我们看下 enqueue,就是一个简单的链表操作。

put的操作和offer相似,这里就省略了,再看下poll

看下dequeue,把头结点取出来,把下个节点设为头结点

以上就是LinkedBlockingQueue。

通过上述两种队列的讲解,我们大概知道了队列存取元素的大致过程,其他队列和上述两种队列的api大致相同,所以接下重点讲述队列的大致特点,不再对api进行详细的描述。

 

PriorityQueue


     PriorityQueue并不是阻塞队列,在这里讲述是因为,接下来的几个队列都是基于他的扩展。PriorityQueue和ArrayBlockingQueue一样,内部维护了一个定长数组,如果不指定长度,默认长度就是11。PriorityQueue是一个优先级队列,元素的顺序并不是按照插入顺序而来,而是按照元素的大小来判断。默认的比较器是从小到大,即队首的元素总是最小的。当然。可以自定义比较器。

    PriorityQueue的优先级通过二叉小顶堆实现,他的逻辑结构是一棵完全二叉树,存储结构其实是一个数组。逻辑结构层次遍历的结果刚好是一个数组。这里借鉴网上的一幅图

 

我们看下添加元素的过程,这里重点是siftUp方法

            

由上图可以看出,PriorityQunue 最关键的便是 比较-交换 步骤。 添加元素都是先放到最后,然后再与自己的父节点比较

再看下获取元素的步骤

      

 这里还有种情况,就是方法,删除中间的某个元素,这就是上述两种变化的结合,首先删除 i 下标的元素,然后把末尾的元素放置到 i 坐标,先向下比较看看,再向上比较。具体的代码这里就省略了。

 以上就是PriorityQueue的具体分析。

 

DelayQueue


DelayQueue 是延迟阻塞队列,队列中的元素只有当其指定的延迟时间到了,才能够从队列中获取到该元素。DelayQueue是一个没有大小限制的队列,因此往队列中插入数据的操作(生产者)永远不会被阻塞,而只有获取数据的操作(消费者)才会被阻塞。

DelayQueue内部通过PriorityQueue实现延迟的权重排序 ,其比较器是 Comparable<Delayed> 

主要看存元素的api

这里关键的是  

first.getDelay(NANOSECONDS)>0

 所以我们在实现 Delayed的时候 实现类里面一定得要有时间可以记录到什么过期,如果过期了一定要返回负数

DelayQueue平时比较少见,但是我们可以用它做一些很灵活的事情,例如缓存过期,空闲连接去除。按照DelayQueue的特性,队首的元素总是最先过期的,我们可以用一个后台线程监听DelayQueue的队首元素。

这里  大家可以参考下用 DelayQueue实现一个过期缓存清除的功能。

 

PriorityBlockingQueue


 PriorityBlockingQueue是优先级阻塞队列,他和我们上文讲的PriorityQueue非常相似。但是呢他又多了点阻塞的东西,准确来说是多了半点。因为在做put操作的时候是不会有阻塞的

就算我们给他一个初始大小,但是如果容量不够还会去扩容

所以我们在往里面put的时候要注意,万一生产者一直在生产,消费者挂了,那么内存很容易就会被耗尽

 

SynchronousQueue


 在线程池里面,大家一定见到过这个队列。这是一个不直接存放元素的队列,他存储的实际上是他内置的Node。它生产产品(即put的时候),如果当前没有人想要消费产品(即当前没有线程执行take),此生产线程必须阻塞,等待一个消费线程调用take操作,take操作将会唤醒该生产线程,同时消费线程会获取生产线程的产品。具体的流程我举个例子

步骤一,调用put线程,存储元素

 

步骤二,再次调用put线程,存储元素 ,在调用一个take线程,取出一个元素

这个时候take线程会和put("b")配对,配对成功后put("a")线程就会成为头结点,整个流程如下图所示

SynchronousQueue有两种模式,公平和非公平,默认是非公平的。内部有两种数据结构,分别是是队列和栈来表示公平和非公平两种模式。上图所描述的是非公平模式,即先进后出。具体细节还是得从代码里看。

首先看下存取元素的api

 

 

两个方法都调用的  transfer 方法,这就是一个配对的方法。这里截取核心部分的transfer方法供大家参考

这里采用了大量的CAS操作进行更新,初看有点乱,但是心中熟记这是个配对方法,再debug几次。代码就会很清晰了。

 

文章评论

Top