Java 并发容器(四):并发队列

  1. Java 中并发队列有哪些?
    答:这些队列迭代都不会抛出 ConcurrentModificationException 异常,都是弱一致的

    • 无锁非阻塞并发队列ConcurrentLinkedQueueConcurrentLinkedDeque
    • 普通阻塞队列:基于数组的 ArrayBlockingQueue,基于链表的 LinkedBlockingQueueLinkedBlockingDeque
    • 优先级阻塞队列PriorityBlockingQueue
    • 延时阻塞队列DelayQueue
    • 其他阻塞队列SynchronousQueueLinkedTransferQueue
  2. 无锁非阻塞和阻塞队列分别是什么意思?
    答:

    • 无锁非阻塞:这些队列不使用锁,所有操作总是可以立即执行,主要通过循环 CAS 实现并发安全
    • 阻塞队列:这些队列使用锁和条件,很多操作都需要先获取锁或满足特定条件,获取不到锁或等待条件时,会等待(即阻塞),获取到锁或条件满足再返回。
  3. 怎样理解无锁非阻塞并发队列 ConcurrentLinkedQueueConcurrentLinkedDeque
    答:

    • 它们适用于多个线程并发使用一个队列的场合,都是基于链表实现的,都没有限制大小,是无界的
    • ConcurrentLinkedQueue 实现了 Queue 接口,表示一个先进先出的队列,从尾部入队,从头部出队,内部是一个单向链表ConcurrentLinkedDeque 实现了 Deque 接口,表示一个双端队列,在两端都可以入队和出队,内部是一个双向链表。它们的用法类似于 LinkedList
    • 这两个类最基础的原理是循环 CASConcurrentLinkedQueue 的算法基于一篇论文《Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithm》https://www.research.ibm.com/people/m/michael/podc-1996.pdf);ConcurrentLinkedDeque 扩展了 ConcurrentLinkedQueue 的技术,但它们具体的实现都非常复杂
  4. 怎样理解普通阻塞队列 ArrayBlockingQueueLinkedBlockingQueueLinkedBlockingDeque
    答:

    • 除了无锁非阻塞并发队列,其他队列都是阻塞队列,都实现了接口 BlockingQueue,在入队/出队时可能等待
    • 普通阻塞队列是常用的队列,常用于生产者/消费者模式
    • ArrayBlockingQueueLinkedBlockingQueue 都实现了 Queue 接口,表示先进先出队列,尾部进,头部出。LinkedBlockingDeque 实现了 Deque 接口,是一个双端队列。
    • ArrayBlockingQueue 是基于循环数组实现的,有界,创建时需要指定大小,且在运行过程中不会改变。与 ArrayDeque 不同,ArrayDeque 也是基于循环数组实现的,但是是无界的,会自动扩展。
    • LinkedBlockingQueue 是基于单向链表实现的,在创建时可以指定最大长度,也可以不指定,默认是无限的,节点都是动态创建的。LinkedBlockingDequeLinkedBlockingQueue 一样,最大长度也是在创建时可选的,默认无限,是基于双向链表实现的
    • 在内部,它们都是使用显示锁 ReentrantLock 和显示条件 Condition 实现的
    • ArrayBlockingQueue 的实现很直接,有一个数组存储元素,有两个元素表示头和尾,有一个变量表示当前元素个数,有一个锁保护所有访问,有“不满”和“不空”两个条件用于协作。
    • LinkedBlockingDeque 也是使用一个锁和两个条件,使用锁保护所有操作,使用“不满”和“不空”两个条件。LinkedBlockingQueue 因为使用链表,且只从头部出队、从尾部入队,做了些 优化,使用了两个锁,一个保护头部,一个保护尾部,每个锁关联一个条件。
  5. 怎样理解优先级阻塞队列 PriorityBlockingQueue
    答:

    • PriorityBlockingQueuePriorityQueue 的并发版本
    • 优先级队列是按优先级出队的,优先级高的先出
    • PriorityQueue 一样,没有大小限制,是无界的,内部的数组大小会动态扩展,要求元素要么实现 Comparable 接口,要么创建 PriorityBlockingQueue 时提供一个 Comparator 对象。
    • PriorityQueue 的区别是,PriorityBlockingQueue 实现了 BlockingQueue 接口,在队列为空时,take() 方法会阻塞等待。另外,PriorityBlockingQueue 是线程安全的,它的基本实现原理和 PriorityQueue 是一样的,也是基于堆,但它使用了一个锁 ReentrantLock 保护所有访问,使用了一个条件协调阻塞等待
  6. 怎样理解延时阻塞队列 DelayQueue
    答:

    • DelayQueue 是一种特殊的优先级队列,是无界的,要求每个元素都实现 Delayed 接口。
    • Delayed 接口的声明为:public interface Delayed extends Comparable<Delayed> {long getDelay(TimeUnit unit);}
    • Delayed 扩展了 Comparable 接口,即,DelayQueue 的每个元素都是可比较的。它有一个额外方法 getDelay() 返回一个给定时间单位 unit 的整数,表示再延迟多长时间,如果小于等于 0,则表示不再延迟。
    • DelayQueue 可以用于实现定时任务,按照元素的延时时间出队。它的特殊之处在于,只有当元素的延时过期之后才能被从队列中拿走,即,take() 方法总是返回第一个过期的元素,如果没有,则阻塞等待
    • DelayQueue 是基于 PriorityQueue 实现的,它使用一个锁 ReentrantLock 保护所有访问,使用一个条件 available 表示头部是否有元素,当头部元素的延时未到时,take() 操作会根据延时计算需睡眠的时间,然后唤醒,如果在此过程中有新的元素入队,且成为头部元素,则阻塞睡眠的线程会被提前唤醒然后重新检查。这是基本思路,DelayQueue 的实现有一些优化,以减少不必要的唤醒。
  7. 怎样理解其他阻塞队列 SynchronousQueueLinkedTransferQueue
    答:

    • SynchronousQueue 与一般的队列不同,它不算一种真正的队列,没有存储元素的空间,连存储一个元素的空间都没有。它的入队操作要等待另一个线程的出队操作,反之亦然
    • 如果没有其他线程在等待从队列中接收元素,put() 操作就会等待。take() 操作需要等待其他线程往队列中放元素,如果没有,也会等待。SynchronousQueue 适用于两个线程之间直接传递信息、事件或任务
    • LinkedTransferQueue 实现了 TransferQueue 接口TransferQueueBlockingQueue 的子接口,但增加了一些额外功能,生产者往队列中放元素时,可以等待消费者接收后再返回,适用于一些消息传递类型的应用中
    • LinkedTransferQueue 是基于链表实现的、无界的 TransferQueue,具体实现比较复杂