posts - 158,  comments - 28,  trackbacks - 0

在Set中有一个排序的集合SortedSet,用来保存按照自然顺序排列的对象。Queue中同样引入了一个支持排序的FIFO模型。

并发队列与Queue简介 中介绍了,PriorityQueue和PriorityBlockingQueue就是支持排序的Queue。显然一个支持阻塞的排序Queue要比一 个非线程安全的Queue实现起来要复杂的多,因此下面只介绍PriorityBlockingQueue,至于PriorityQueue只需要去掉 Blocking功能就基本相同了。

 转自: http://www.blogjava.net/xylz/archive/2010/07/30/327582.htm

排序的BlockingQueue — PriorityBlockingQueue

先简单介绍下PriorityQueue,因为PriorityBlockingQueue内部就是通过PriorityQueue适配实现的,只不过通过锁进行同步和阻塞而已。

PriorityQueue是一个数组实现的,是一个二叉树的实现,这个二叉树的任意一个节点都比其子节点要小,这样顶点就是最小的节点。每一个元 素或者节点要么本身是可比较的(Comparable),或者队列本身带有一个比较器(Comparator<? super E>),所有元素就是靠比较自身的大小来确定顺序的。而数组中顶点就是数组的第0个元素,因此出队列的话总是取第0个元素。对于第0个元素,其子节 点是第1个元素和第2个元素,对于第1个元素,其子元素又是第3/4个元素,以此类推,第i个元素的父节点就是(i-1)/2。这样任意一个元素加入队列 就从其父节点(i-1)/2开始比较,一旦新节点比父节点小就交换两个节点,然后继续比较新节点与其新的父节点。知道所有节点都是按照父节点一定比子节点 小的顺序排列。这是一个有点复杂的算法,此处不再讨论更多的细节。不管是删除还是查找,我们只需要了解的顶点(索引为0的元素)总是最小的。

特别需要说明的是PriorityQueue是一个无界的队列,也就是说一旦元素的个数达到了数组的大小,那么就将数组扩大50%,这样这个数组就是无穷大的。当然了如果达到了整数的最大值就会得到一个OutOfMemoryError,这个是由逻辑保证的。

 

对于PriorityBlockingQueue而言,由于是无界的,因此就只有非空的信号,也就是说只有take()才能阻塞,put是永远不会阻塞(除非达到Integer.MAX_VALUE直到抛出一个OutOfMemoryError异常)。

只有take()操作的时候才可能因为队列为空而挂起。同时其它需要操作队列变化和大小的只需要使用独占锁ReentrantLock就可以了,非常方便。需要说明的是PriorityBlockingQueue采用了一个公平的锁。

 

总的来说PriorityBlockingQueue 不是一个FIFO的队列,而是一个有序的队列,这个队列总是取“自然顺序”最小的对象,同时又是一个只能出队列阻塞的BlockingQueue,对于入队列却不是阻塞的。所有操作都是线程安全的。

 

直接交换的BlockingQueue — SynchronousQueue

 

这是一个很有意思的阻塞队列,其中每个插入操作必须等待另一个线程的移除操作,同样任何一个移除操作都等待另一个线程的插入操作。因此此队列内部其 实没有任何一个元素,或者说容量是0,严格说并不是一种容器。由于队列没有容量,因此不能调用peek操作,因为只有移除元素时才有元素。

一个没有容量的并发队列有什么用了?或者说存在的意义是什么?

SynchronousQueue 的实现非常复杂,当然了如果真要去分析还是能够得到一些经验的,但是前面分析了过多的结构后,发现越来越陷于数据结构与算法里面了。我的初衷是通过研究并 发实现的原理来更好的利用并发来最大限度的利用可用资源。所以在后面的章节中尽可能的少研究数据结构和算法,但是为了弄清楚里面的原理,必不可免的会涉及 到一些这方面的知识,希望后面能够适可而止。

再回到话题。SynchronousQueue 内部没有容量,但是由于一个插入操作总是对应一个移除操作,反过来同样需要满足。那么一个元素就不会再SynchronousQueue 里面长时间停留,一旦有了插入线程和移除线程,元素很快就从插入线程移交给移除线程。也就是说这更像是一种信道(管道),资源从一个方向快速传递到另一方 向。

需要特别说明的是,尽管元素在SynchronousQueue 内部不会“停留”,但是并不意味之SynchronousQueue 内部没有队列。实际上SynchronousQueue 维护者线程队列,也就是插入线程或者移除线程在不同时存在的时候就会有线程队列。既然有队列,同样就有公平性和非公平性特性,公平性保证正在等待的插入线 程或者移除线程以FIFO的顺序传递资源。

显然这是一种快速传递元素的方式,也就是说在这种情况下元素总是以最快的方式从插入着(生产者)传递给移除着(消费者),这在多任务队列中是最快处理任务的方式。在线程池的相关章节中还会更多的提到此特性。

 

事实上在《并发队列与Queue简介》 中介绍了还有一种BlockingQueue的实现DelayQueue,它描述的是一种延时队列。这个队列的特性是,队列中的元素都要延迟时间(超时时 间),只有一个元素达到了延时时间才能出队列,也就是说每次从队列中获取的元素总是最先到达延时的元素。这种队列的场景就是计划任务。比如以前要完成计划 任务,很有可能是使用Timer/TimerTask,这是一种循环检测的方式,也就是在循环里面遍历所有元素总是检测元素是否满足条件,一旦满足条件就 执行相关任务。显然这中方式浪费了很多的检测工作,因为大多数时间总是在进行无谓的检测。而DelayQueue 却能避免这种无谓的检测。在线程池的计划任务部分还有更加详细的讨论此队列实现。

 

下面就对常见的BlockingQueue进行小节下,这里不包括双向的队列,尽管ConcurrentLinkedQueue不是可阻塞的Queue,但是这里还是将其放在一起进行对比。

 

并发队列比较

如果不需要阻塞队列,优先选择ConcurrentLinkedQueue;如果需要阻塞队列,队列大小固定优先选择 ArrayBlockingQueue,队列大小不固定优先选择LinkedBlockingQueue;如果需要对队列进行排序,选择 PriorityBlockingQueue;如果需要一个快速交换的队列,选择SynchronousQueue;如果需要对队列中的元素进行延时操 作,则选择DelayQueue。

posted on 2012-03-19 14:45 David1228 阅读(281) 评论(0)  编辑  收藏 所属分类: JAVA

只有注册用户登录后才能发表评论。


网站导航:
 

<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

常用链接

留言簿(3)

随笔分类

随笔档案

文章档案

新闻分类

新闻档案

相册

收藏夹

Java

Linux知识相关

Spring相关

云计算/Linux/虚拟化技术/

友情博客

多线程并发编程

开源技术

持久层技术相关

搜索

  •  

积分与排名

  • 积分 - 253804
  • 排名 - 187

最新评论

阅读排行榜

评论排行榜