阻塞队列

阻塞队列 (BlockingQueue) 是 java.util.concurrent 包下重要的数据结构，BlockingQueue 提供了线程安全的队列访问方式：当阻塞队列进行插入数据时，如果队列已满，线程将会阻塞等待直到队列非满；从阻塞队列取数据时，如果队列已空，线程将会阻塞等待直到队列非空。阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。并发包下很多高级同步类的实现都是基于 BlockingQueue 实现的。

阻塞队列是一个在队列基础上又支持了两个附加操作的队列。

• 支持阻塞的插入方法：队列满时，队列会阻塞插入元素的线程，直到队列不满。
• 支持阻塞的移除方法：队列空时，获取元素的线程会等待队列变为非空。

在阻塞队列不可用的时候，上述2个附加操作提供了四种处理方法

• ThrowsException：如果操作不能马上进行，则抛出异常
• SpecialValue：如果操作不能马上进行，将会返回一个特殊的值，一般是true或者false
• Blocks:如果操作不能马上进行，操作会被阻塞
• TimesOut:如果操作不能马上进行，操作会被阻塞指定的时间，如果指定时间没执行，则返回一个特殊值，一般是true或者false

提供了可阻塞的put和take方法，以及支持定时的offer和poll方法。 适用于生产者、消费者模式（线程池和工作队列-Executor），同时也是同步容器

JDK7 提供了7个阻塞队列。（也属于并发容器）

• ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。
• LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。
• PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。
• DelayQueue：一个使用优先级队列实现的无界阻塞队列。
• SynchronousQueue：一个不存储元素的阻塞队列。
• LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。
• LinkedBlockingDeque：一个由链表结构组成的双向阻塞队列。

ArrayBlockingQueue

数组结构组成的有界阻塞队列。

此队列按照先进先出（FIFO）的原则对元素进行排序，但是默认情况下不保证线程公平的访问队列，即如果队列满了，那么被阻塞在外面的线程对队列访问的顺序是不能保证线程公平（即先阻塞，先插入）的。

1
2
3

BlockingQueue<String> queue = new ArrayBlockingQueue<>(1024);
queue.put("1");
Object object = queue.take();

LinkedBlockingQueue

LinkedBlockingQueue 阻塞队列大小的配置是可选的，如果我们初始化时指定一个大小，它就是有边界的，如果不指定，它就是无边界的。说是无边界，其实是采用了默认大小为Integer.MAX_VALUE的容量 。它的内部实现是一个链表。

1
2
3
4

BlockingQueue<String> unbounded = new LinkedBlockingQueue<String>();
BlockingQueue<String> bounded   = new LinkedBlockingQueue<String>(1024);
bounded.put("Value");
String value = bounded.take();

PriorityBlockingQueue

PriorityBlockingQueue 是一个没有边界的队列，它的排序规则和 java.util.PriorityQueue 一样。需要注意，PriorityBlockingQueue 中允许插入null对象。

所有插入PriorityBlockingQueue的对象必须实现 java.lang.Comparable接口，队列优先级的排序规则就是按照我们对这个接口的实现来定义的。

另外，我们可以从PriorityBlockingQueue获得一个迭代器Iterator，但这个迭代器并不保证按照优先级顺序进行迭代。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class PriorityElement implements Comparable<PriorityElement> {
private int priority;//定义优先级
PriorityElement(int priority) {
    //初始化优先级
    this.priority = priority;
}
@Override
public int compareTo(PriorityElement o) {
    //按照优先级大小进行排序
    return priority >= o.getPriority() ? 1 : -1;
}
public int getPriority() {
    return priority;
}
public void setPriority(int priority) {
    this.priority = priority;
}
@Override
public String toString() {
    return "PriorityElement [priority=" + priority + "]";
}
}

PriorityBlockingQueue<PriorityElement> queue = new PriorityBlockingQueue<>();
    for (int i = 0; i < 5; i++) {
        Random random=new Random();
        PriorityElement ele = new PriorityElement(random.nextInt(10));
        queue.put(ele);
    }
    while(!queue.isEmpty()){
        System.out.println(queue.take());
    }

Java 中的优先队列 PriorityQueue 就是基于堆结构实现的

DelayQueue

DelayQueue是一个无界的BlockingQueue，用于放置实现了Delayed接口的对象，其中的对象只能在其到期时才能从队列中取走。这种队列是有序的，即队头对象的延迟到期时间最长。注意：不能将null元素放置到这种队列中。

支持延时获取元素的无界阻塞队列，即可以指定多久才能从队列中获取当前元素

• 每个 DelayQueue 中的元素需要实现 Delayed 接口
• 下单之后如果三十分钟之内没有付款就自动取消订单。
• 下单成功后60s之后给用户发送短信通知。
• 关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭之。
• 缓存。缓存中的对象，超过了空闲时间，需要从缓存中移出。
• 任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求等。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class DelayObject implements Delayed {
    private String data;
    private long startTime;

    public DelayObject(String data, long delayInMilliseconds) {
        this.data = data;
        this.startTime = System.currentTimeMillis() + delayInMilliseconds;
    }

    @Override
public long getDelay(TimeUnit unit) {
    long diff = startTime - System.currentTimeMillis();
    return unit.convert(diff, TimeUnit.MILLISECONDS);
}

@Override
public int compareTo(Delayed o) {
    return Ints.saturatedCast(
      this.startTime - ((DelayObject) o).startTime);
}

延迟队列 DelayQueue 里面就用到了 PriorityQueue

SynchronousQueue 同步队列

SynchronousQueue 内部仅允许容纳一个元素的阻塞队列，每一个put必须等待一个take操作，否则不能继续添加元素。并且他支持公平访问队列。

LinkedTransferQueue

由链表结构组成的无界阻塞 TransferQueue 队列。相对于其他阻塞队列，多了tryTransfer和transfer方法

transfer方法：

如果当前有消费者正在等待接收元素（take或者待时间限制的poll方法），transfer可以把生产者传入的元素立刻传给消费者。如果没有消费者等待接收元素，则将元素放在队列的tail节点，并等到该元素被消费者消费了才返回。

tryTransfer方法：

用来试探生产者传入的元素能否直接传给消费者。，如果没有消费者在等待，则返回false。和上述方法的区别是该方法无论消费者是否接收，方法立即返回。而transfer方法是必须等到消费者消费了才返回。

BlockingDeque

一个 BlockingDeque - 线程在双端队列的两端都可以插入和提取元素。 一个线程生产元素，并把它们插入到队列的任意一端。如果双端队列已满，插入线程将被阻塞，直到一个移除线程从该队列中移出了一个元素。如果双端队列为空，移除线程将被阻塞，直到一个插入线程向该队列插入了一个新元素。

LinkedBlockingDeque

LinkedBlockingDeque 类实现了 BlockingDeque 接口。

deque(双端队列) 是 “Double Ended Queue” 的缩写。因此，双端队列是一个你可以从任意一端插入或者抽取元素的队列。

链表结构的双向阻塞队列，优势在于多线程入队时，减少一半的竞争。

生产者和消费者的场景

通知模式实现：所谓通知模式，就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用。

阻塞队列常用于生产者和消费者的场景，生产者是向队列里添加元素的线程，消费者是从队列里取元素的线程。简而言之，阻塞队列是生产者用来存放元素、消费者获取元素的容器。

为什么 BlockingQueue 适合解决生产者消费者问题：

任何有效的生产者-消费者问题解决方案都是通过控制生产者put()方法（生产资源）和消费者take()方法（消费资源）的调用来实现的，一旦你实现了对方法的阻塞控制，那么你将解决该问题。

Java通过BlockingQueue提供了开箱即用的支持来控制这些方法的调用（一个线程创建资源，另一个消费资源）。java.util.concurrent包下的BlockingQueue接口是一个线程安全的可用于存取对象的队列。

BlockingQueue是一种数据结构，支持一个线程往里存资源，另一个线程从里取资源。这正是解决生产者消费者问题所需要的。