java并发包之队列Queue

Queue的设计目标在于让集合中的元素,在被处理的时候有一种优先级的概念,因此,优先级的概念,成为使用Queue的一个基本场景出现。

Queue除了具有集合(java.util.Collection Collection)的基本操作外,还提供额外的插入(insertion)、提取(extraction)和检查(inspection )等操作。

这些方法都以两种形式存在:

一种是如果操作失败则抛出异常,另一种是返回特殊的值(null或false),具体取决于的操作,后一种操作专门用于对容量有限制的场景,在大多数的队列实现中,插入操作不会失败。

队列中的元素通常(但并不一定)按 FIFO(先进先出)方式进行排序。优先级队列除外,根据提供的比较器对元素进行排序,或元素的自然顺序,有些LIFO 队列(或堆栈) 按LIFO(后进先出)方式对元素进行排序。

无论采用何种方式进行排序,队列的"头部"的元素,都是通过调用remove()或poll()来进行删除。 在FIFO(先进先出)队列中,所有新元素都插入在队列的"尾部"。 

其他类型的队列可能使用不同的放置规则,Queue的具体实现都必须指定其排序属性,后面会看到各种排序队列的具体实现。先看一组队列通用API。

boolean offer(E e);

如果允许放入则插入一个元素,否则返回false。这与java.util.Collection的add方法不同,后者在添加元素失败时,通过抛出一个未经检查的异常来通知。

此API的设计初衷,认为这种添加失败的情况实属正常,例如,在固定容量(orbounded)队列中。

E remove();
E poll();

这两个方法都是用于删除,并返回队列“头部”元素,具体删除队列中的哪个元素(或如何定义“头部”元素),根据不同队列实现的排序策略而定。这两个方法的差异在于,对待队列为空时的态度(queue is empty),remove()方法会抛出异常,poll()方法会返回null。

E element();
E peek();

这两个方法都用来返回元素,但不会把元素从队列中删除,区别依然是队列中的元素为空时,前者抛出NoSuchElementException,而后者返回null。

需要注意的是Queue接口,并未定义阻塞队列(blocking queue)的行为(methods),只是定义了并发编程下常用的方法。那些等待元素出现,或空间可用的方法在java.util.concurrent.BlockingQueue的接口中定义,用于扩展Queue。

Queue的具体实现类

ArrayBlockingQueue

一个基于数组容量有限的队列,此队列的元素按FIFO(先进先出)进行排序。这种队列的“头部”元素,是那个在队列中时间最长的元素,“尾部”是存在于队列中,时间最短的元素。当新元素被放入队列的“尾部”,从这个队列中获取“头部”元素的操作会被恢复。

这是一个经典的有限缓存,在一个固定大小的数组中放入来自生产者元素,并由消费者进行元素的提取。一旦创建,它的大小就不能被改变。试图通过put(E e)方法往一个满的队列中放入一个元素,这个操作将会被阻塞。试图通过public E take()方法从一个空的队列中获取元素,这个操作同样会被阻塞。

ArrayBlockingQueue支持一种可选的公平策略,用于生产者和消费者的线程,处于等待后被唤醒的顺序,默认不支持。然而,通过将一个队列的构造参数设置为true,允许线程以FIFO(先进先出)的顺序公平的进行访问,公平性通常会导致吞吐量降低,同时也降低了易变性,避免了线程饿死,这个类支持Collection的迭代器。

ConcurrentLinkedQueue

一个基于链表的线程安全的容量无限制队列,这个队列的的排序方式是FIFO(先进先出)。当多个线程共享一个公共的集合时,ConcurrentLinkedQueue会是一个不错的选择。和大多并发集合类一样,ConcurrentLinkedQueue不允许null作为元素。

该实现采用有效的非阻塞算法,算法基于 Maged M.Michael和Michael L.Scott的简单、快速、实用的,非阻塞和阻塞并发队列算法中所描述的算法。

DelayQueue

一个无容量限制的队列,DelayQueue中的元素,只能在延迟到期时才能被获取。队列中的“头部”元素,是已经过期并且距离现在时间最远的,如果过期时间未到则没有“头部”元素,poll()方法将返回null。

getDelay(TimeUnit.NANOSECONDS)方法会返回一个小于或等于零的值。即使,使用take()或 poll()也无法删除未到期的元素,相反,它们会像正常元素一样被对待,例如,调用size()方法,将返回已过期和未过期的元素个数。DelayQueue不允许null元素。

LinkedBlockingQueue

一个容量可选的基于链表的FIFO(先进先出)的阻塞队列,队列的“头部”是已经存在的,并排队时间最长的元素。新元素的加入,会使获取头部元素的操作被恢复。链接队列通常比基于阵列的队列,具有更高的吞吐量,但是,大多数并发应用程序的性能预测性较差。

可选的构造方法目的在于,防止过多的队列扩展类(一个类搞定两种应用场景)。如果未指定,则容量等于Integer.MAX_VALUE。每次插入时都会动态创建链接节点,除非当队列超出容量。

LinkedTransferQueue

一个无容量限制基于链表的FIFO(先进先出)队列。队列"头部"为存放时间最长的元素,"尾部"为时间最短者。需要注意的是,与大多数集合size()方法不同,LinkedTransferQueue的size方法的操作不是恒定时间,由于这些队列的异步性质,确定元素数量时,需要遍历元素,因此如果在遍历期间修改此集合,则可能会导致结果不准确。

此外,批量操作addAll、removeAll、retainAll、containsAll、equals和toArray不保证以原子方式执行。例如,与addAll操作同时运行的迭代器可能只能查看一些添加的元素。

PriorityBlockingQueue

一个容量无限制的阻塞队列,它使用与PriorityQueue相同的排序规则,并提供阻塞检索操作。虽然PriorityBlockingQueue队列在逻辑上是无限制的,但由于资源耗尽会导致OutOfMemoryError,尝试添加可能会失败。此类不允许null元素。

依赖于Comparable natural ordering的优先级队列,因此不允许插入不可比较的对象(未实现Comparable接口的对象),这样做会导致ClassCastException。

PriorityBlockingQueue的操作,不保证相同优先级的元素间是有序的,如果需要强制执行排序,则需要定义比较器通过辅助键来断开,与主优先级值中的关系。例如,要打破将先进先出时的平局,需要使用new FIFOEntry(anEntry)而不是普通Entry对象。

SynchronousQueue

每个插入操作,都必须等待另一个线程执行删除操作的阻塞队列。反之亦然,同步队列没有任何内部容量,甚至没有容量。不能在同步队列中调用peek()方法,因为,只有在试图删除元素时才会加入新元素。不能使用任何方法插入一个元素,除非,另一个线程试图删除它。不能迭代,因为没有什么可以迭代的。

队列的"头部"是第一个排队插入的线程,尝试添加到队列的元素,如果没有这样排队的线程,则没有可用于删除的元素,poll()将返回null。出于符合Collection方法的目的(例如contains),SynchronousQueue充当空集合。此队列不允许null元素。

同步队列类似于CSP和Ada中使用的集合点通道,它们非常适用于切换设计,其中在一个线程中运行的对象,必须与在另一个线程中运行的对象同步,以便用于传递某些信息、事件或任务。

SynchronousQueue支持有序等待生产者,和消费者线程的可选公平策略。默认情况下,不保证此顺序,但是,将公平性设置为true的队列,以FIFO顺序授予线程访问权限。

TransferQueue

一个生产者等待消费者,接收元素的阻塞(可选)队列。TransferQueue可能在消息传递应用程序中很有用,其中生产者有时使用transfer方法,等待消费者调用take或poll接收元素。而在其他时间通过put方法,将元素放入队列而无需等待接收。tryTransfer(Object)方法非阻塞。

与其他阻塞队列一样,TransferQueue可能是容量限制的。如果是,则尝试的传输操作可能会被阻止等待可用空间,and/or (继续/等待)消费者接收。

请注意,在容量为零的队列中,例如:SynchronousQueue的put和transfer实际上行为是一致的。