文档章节

BlockingQueue详解

爱宝贝丶
 爱宝贝丶
发布于 2018/12/23 13:06
字数 3869
阅读 152
收藏 0

       BlockingQueue,顾名思义,指的是一个阻塞队列。其主要用于生产者-消费者模式,也就是在多线程场景时生产者线程在队列头部添加元素,而消费者线程则在队列尾部消费元素,通过这种方式能够达到将任务的生产和消费进行隔离的目的。BlockingQueue最典型的两个实现是ArrayBlockingQueue和LinkedBlockingQueue。本文首先会讲解BlockingQueue的API的具体使用方式,然后会讲解ArrayBlockingQueue和LinkedBlockingQueue的实现原理,并且对比两者之间的区别。

1. BlockingQueue使用方式

       BlockingQueue继承自Queue接口,也就是说其实现了队列相关的诸如offer,put,take,poll等一系列操作。如下是BlockingQueue的接口定义:

public interface BlockingQueue<E> extends Queue<E> {
    // 尝试往队列尾部添加元素,添加成功则返回true,添加失败则抛出IllegalStateException异常
    boolean add(E e);

    // 尝试往队列尾部添加元素,添加成功则返回true,添加失败则返回false
    boolean offer(E e);

    // 尝试往队列尾部添加元素,如果队列满了,则阻塞当前线程,直到其能够添加成功为止
    void put(E e) throws InterruptedException;

    // 尝试往队列尾部添加元素,如果队列满了,则最多等待指定时间,
    // 如果在等待过程中还是未添加成功,则返回false,如果在等待
    // 过程中被中断,则抛出InterruptedException异常
    boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;

    // 尝试从队列头部取出元素,如果队列为空,则一直等待队列中有元素
    E take() throws InterruptedException;

    // 尝试从队列头部拉取元素,如果队列为空,则最多等待指定时间,
    // 如果等待过程中拉取到了新元素,则返回该元素,
    // 如果等待过程被中断,则抛出InterruptedException异常
    E poll(long timeout, TimeUnit unit) throws InterruptedException;

    // 获取当前队列剩余可存储元素的数量
    int remainingCapacity();

    // 从队列中移除指定对象
    boolean remove(Object o);

    // 判断队列中是否存在指定对象
    boolean contains(Object o);

    // 将队列中的元素转移到指定的集合中
    int drainTo(Collection<? super E> c);

    // 从队列中最多转移maxElements个元素到指定集合中
    int drainTo(Collection<? super E> c, int maxElements);
}

       关于BlockingQueue的Api,这里需要说明的一点是,BlockingQueue的主要作用是提供一个阻塞队列,以便使用者能够通过其阻塞特性,在队列头部和尾部移除和添加元素,从而达到在多线程环境将任务的生产和消费进行分离的目的。这里添加和移除主要是通过add,offer,put和take,poll方法来进行的,而这些方法的效率是非常高的,因为其只需要在队列两端进行时间复杂度O(1)的操作,即使有多线程的竞争,但由于锁定时间非常短,因而通过多线程的偏向锁等特性,这种消耗是微乎其微的。但是这里可以看到,BlockingQueue还提供了其他的操作,主要包含计算剩余余量,移除指定对象,判断是否包含指定对象和将集合中元素移动到集合中。这些操作则是不建议经常使用的,因为在进行这些操作时,无论是ArrayBlockingQueue还是LinkedBlockingQueue,其都需要将整个队列锁定,然后对整个队列进行遍历,从而实现操作的目的,这将大大地减少队列的吞吐量。

2. ArrayBlockingQueue实现原理

       对于ArrayBlockingQueue,顾名思义,其底层存储结构是一个数组,而我们在创建一个ArrayBlockingQueue的时候,是必须指定其能够存储的元素的数量的,因而通过这种方式,我们就可以保证数组的大小始终固定,而不会出现需要迁移数据的操作。这里我们首先看一下ArrayBlockingQueue的数据结构:

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    // 用于存储当前添加到队列中的元素,使用以Object进行存储,而在取数据时进行转型
    final Object[] items;
    
    // 记录了当前可以被取到的元素的下标索引,该索引位置是存在实际元素的
    int takeIndex;
    
    // 记录了当前可以存放元素的下标索引,该索引位置是空置的,
    // 如果队列满了,则该索引位置指向的元素就不为空
    int putIndex;
    
    // 记录了当前队列中存在的元素个数
    int count;
    
    // 声明的全局锁,用于控制队列的存储元素等各个操作
    final ReentrantLock lock;
    
    // 通过lock创建的一个等待条件,用于当队列为空时,阻塞当前尝试从队列中取元素的线程
    private final Condition notEmpty;
    
    // 通过lock创建的一个等待条件,用于当队列满了时,阻塞当前尝试往队列中添加元素的线程
    private final Condition notFull;

    transient Itrs itrs = null;
}

       通过上述数据结构可以看出,ArrayBlockingQueue是通过一个循环数组的方式来实现存储元素的,这里takeIndex记录了当前可以取元素的索引位置,而putIndex则记录了下一个元素可以存储的位置。当队列满了时,takeIndex和putIndex将指向同一个元素,这里则可以通过count字段来判断当前是处于满状态还是空置状态。通过声明一个全局的锁来控制所有操作的控制权限,也就是说,对于ArrayBlockingQueue而言,其任何一个操作都是阻塞其他操作的。这里notEmpty和notFull则是由lock创建得来的,通过这两个分离的等待条件,可以实现队列两端线程添加和移除操作的分离。如下是ArrayBlockingQueue的入队和出队操作的源码:

private void enqueue(E x) {
    final Object[] items = this.items;
    items[putIndex] = x;  // 将新元素放置到putIndex处
    if (++putIndex == items.length)  // 如果放置后putIndex达到了数组顶部,则将其循环至0号索引处
        putIndex = 0;
    count++;
    notEmpty.signal();  // 由于添加了元素,说明队列不为空,则唤醒一个正在等待获取元素的线程
}
private E dequeue() {
    final Object[] items = this.items;
    @SuppressWarnings("unchecked")
    E x = (E) items[takeIndex];  // 取出takeIndex位置的元素,作为返回值返回
    items[takeIndex] = null;  // 重置takeIndex处的元素
    if (++takeIndex == items.length)  // 如果takeIndex达到了队列顶部,则将其循环至0号索引处
        takeIndex = 0;
    count--;  // 更新元素总量
    if (itrs != null)  // 更新迭代器数据
        itrs.elementDequeued();
    notFull.signal();  // 由于移除了元素,说明队列不满,则唤醒一个尝试往队列添加元素的线程
    return x;
}

       可以看到,这里enqueue()和dequeue()方法是入队和出队的核心方法。在enqueue()方法中,当成功入队之后,其会唤醒一个正在等待取出元素的线程;在dequeue()方法中,当成功出队之后,其会唤醒一个正在等待添加元素的线程。对于外层调用,这里我们主要以阻塞的put()和offer()方法为例进行讲解:

public void put(E e) throws InterruptedException {
    checkNotNull(e);  // 检查元素是否为空,不为空则抛出异常
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();  // 锁定当前操作
    try {
        while (count == items.length)  // 在循环中检查,以防止当前线程是被意外唤醒的
            notFull.await();  // 如果当前队列已满,则当前线程进入等待状态,并释放锁
        enqueue(e);  // 如果通过了while判断,说明队列不满,并且当前线程获取到了锁,则元素入队
    } finally {
        lock.unlock();  // 操作完成,释放当前的锁
    }
}
public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();  // 锁定当前的线程
    try {
        while (count == 0)  // 在循环中检查,以防止当前线程被意外唤醒
            notEmpty.await();  // 如果当前队列为空,则当前线程进入等待状态,并释放锁
        return dequeue();  // 如果通过了while判断,说明队列不为空,并且当前线程获取到了锁,则元素出队
    } finally {
        lock.unlock();  // 操作完成,释放当前锁
    }
}

       在put()和take()操作中,首先都是通过while条件进行前置判断,对于put操作,如果队列满了,则在notFull中进行等待,对于take()操作,如果队列为空,则在notEmpty中进行等待,并且释放锁。在队列中有空闲空间或有元素时,才会继续执行put()或take()操作。

3. LinkedBlockingQueue实现原理

       对于LinkedBlockingQueue,其底层是通过一个单项链表实现的,由于单项链表需要有一个指向下一个节点的指针,因而其必须使用一个对象(这里是Node)来存储当前元素的值和下一个节点的索引。如下是LinkedBlockingQueue的数据结构:

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    // 记录了当前队列最多可以存储的元素的个数,如果不指定,则默认为Integer.MAX_VALUE
    private final int capacity;
    
    // 记录了当前队列中已经存储的元素个数
    private final AtomicInteger count = new AtomicInteger();
    
    // 记录了当前队列的头结点的指针,该节点中是不存储实际的元素的,头部的元素在下一个节点中存储。
    // 这么处理的目的是,当队列为空时,头指针和尾指针都可以指向同一个不存储任何元素的Node节点。
    transient Node<E> head;
    
    // 记录了当前队列尾部节点的指针
    private transient Node<E> last;
    
    // 从队列中取元素的锁
    private final ReentrantLock takeLock = new ReentrantLock();
    
    // 通过takeLock创建的一个Condition对象,用于控制队列中没有元素时阻塞尝试获取元素的线程
    private final Condition notEmpty = takeLock.newCondition();
    
    // 往队列中存入元素的锁
    private final ReentrantLock putLock = new ReentrantLock();
    
    // 通过putLock创建的一个Condition对象,用于控制队列满了时阻塞尝试往队列中添加元素的线程
    private final Condition notFull = putLock.newCondition();
    
    // 当前用于存储元素的Node对象,其有一个next指针,记录了下一个节点的索引
    static class Node<E> {
        E item;
        Node<E> next;
        Node(E x) { item = x; }
    }
}

       通过上面的数据结构可以看出,LinkedBlockingQueue使用一个head指针指向了队列的头节点,使用一个last指针指向了队列的尾节点,使用capacity指定了队列最多能够存储的元素个数,使用count记录当前已经存储的元素个数,如此就可以对一个单向链表进行完全定性。这里为了实现阻塞的特性,LinkedBlockingQueue分别为队列头部和尾部声明了两个锁,并且创建了两个等待Condition。当往队列添加元素时,使用putLock锁定队列尾部,如果队列满了,则将该线程添加到notFull的Condition中,并且释放锁;当从队列总取元素时,使用takeLock锁定队列头部,如果队列为空,则将该线程添加到notEmpty的Condition中,并且释放锁。这里我们首先看一下LinkedBlockingQueue的入队和出队操作:

private void enqueue(Node<E> node) {
    // 将队列尾部节点的next指针指向新的节点,并且更新last指针指向最新的尾部节点
    last = last.next = node;
}
private E dequeue() {
    Node<E> h = head;
    Node<E> first = h.next;  // 指向当前存储元素的指针
    h.next = h;  // 处理头节点的next指针,以便能更快的GC
    head = first;  // 将头节点指向其下一个节点
    E x = first.item;  // 获取头部节点的元素作为返回值
    first.item = null;  // 更新头节点为空置的节点
    return x;
}

       可以看到,对于链表的入队和出队操作,其是非常简单的,这里仅仅只是单纯的入队和出队,并没有相关的锁的操作。我们还是通过阻塞的put()和take()方法来对LinkedBlockingQueue进行讲解:

public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    int c = -1;
    Node<E> node = new Node<E>(e);
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    putLock.lockInterruptibly();  // 锁定队列尾部
    try {
        while (count.get() == capacity) {  // 在循环中判断,以防止当前线程被意外唤醒
            notFull.await();  // 如果当前队列已满,则使当前线程进入等待状态
        }
        enqueue(node);  // 这里说明队列队列没满,并且当前线程获取到了锁,那么将元素压入队列
        c = count.getAndIncrement();  // 更新元素个数
        if (c + 1 < capacity)  // 该判断说明添加元素后队列还是未满,那么继续唤醒尝试添加元素的线程
            notFull.signal();
    } finally {
        putLock.unlock();  // 释放当前的锁
    }
    if (c == 0)
        // 当前判断说明尝试取出元素的Condition中有等待的线程,因为压入了元素
        // 这里将等待取出元素的线程唤醒
        signalNotEmpty();
}
public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();  // 锁定队列头部
    try {
        while (count.get() == 0) {  // 在循环中判断,以防止当前线程被意外唤醒
            notEmpty.await();  // 如果当前队列为空,则使当前线程进入等待状态
        }
        x = dequeue();  // 这里说明队列不为空,并且当前线程获取到了锁,那么从队列中取出元素返回
        c = count.getAndDecrement();  // 更新记录的元素数量
        if (c > 1)  // 该判断说明取出元素中队列中还是有元素,那么继续唤醒后面等待的线程
            notEmpty.signal();
    } finally {
        takeLock.unlock();  // 释放当前的锁
    }
    if (c == capacity)
        // 当前判断说明尝试存入元素的Condition中有等待的线程,这里因为取了元素,
        // 因而队列中有空闲空间,因此唤醒正在等待存入元素的线程
        signalNotFull();
    return x;
}

       上面的入队和出队操作中,基本都是先判断前置条件是否成立,即队列未满或不为空,如果成立,当前线程才有权限进行入队和出队操作。在操作完成之后,当前线程还会唤醒正在等待尝试获取或取出元素的线程。

4. 对比

       从上面的实现方式可以看出,ArrayBlockingQueue和LinkedBlockingQueue主要有如下几点区别:

  • 两者底层数据结构不同,ArrayBlockingQueue是通过循环数组来实现的,而LinkedBlockingQueue是通过单向链表来实现的;
  • 两者阻塞方式不同,ArrayBlockingQueue使用了一个全局锁来处理所有的操作,也就是说无论是队列头部还是尾部,只要一个线程获取到了锁,那么其他所有的线程将都会被阻塞,只不过由于锁定的时间非常短,因而这种消耗可以忽略不计;ArrayBlockingQueue为队列头部和尾部分别使用了两个不同的锁,在元素入队和出队操作时,两者几乎是互不干扰的;
  • 两者初始化大小不同,ArrayBlockingQueue必须指定一个初始化大小,而LinkedBlockingQueue可以指定初始大小,也可以不指定,不指定时默认为Integer.MAX_VALUE。

5. 小结

       本文首先讲解了BlockingQueue的API的使用方式,并且讲解了其使用时需要注意的点。然后讲解了BlockingQueue的两个实现类ArrayBlockingQueue和LinkedBlockingQueue的使用方式和核心实现原理。最后对ArrayBlockingQueue和LinkedBlockingQueue进行了对比。

© 著作权归作者所有

上一篇: https加密
下一篇: 多线程编程
爱宝贝丶

爱宝贝丶

粉丝 348
博文 140
码字总数 473198
作品 0
武汉
程序员
私信 提问
BlockingQueue详解

本例再次实现前面介绍的篮子程序,不过这个篮子中最多能放得苹果数不是1,可以随意指定。当篮子满时,生产者进入等待状态,当篮子空时,消费者等待。 BlockingQueue定义的常用方法如下: ad...

wow863597
2016/05/09
62
0
集合框架 Queue---BlockingQueue详解

本例介绍一个特殊的队列:BlockingQueue,如果BlockingQueue是空的,从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒,同样,如果BlockingQueue是...

长平狐
2012/11/28
606
0
【Java并发专题】27篇文章详细总结Java并发基础知识

努力的意义,就是,在以后的日子里,放眼望去全是自己喜欢的人和事! github:https://github.com/CL0610/Java-concurrency,欢迎题issue和Pull request。所有的文档都是自己亲自码的,如果觉...

你听___
2018/05/06
0
0
Callable,Future,FutrueTask,CompletionService 详解

package com.dy.pool; import java.util.concurrent.*; /** 1: Callable<V> 返回结果并且可能抛出异常的任务。实现者定义了一个不带任何参数的叫做 call 的方法。 2: Future<V> 表示异步计算...

洋哥6
2016/04/15
240
1
java 队列阻塞方法ArrayBlockingQueue学习

本例介绍一个特殊的队列:BlockingQueue,如果BlockQueue是空的,从BlockingQueue取东西的操作将会被阻断进入等待状态,直到BlockingQueue进了东西才会被唤醒.同样,如果BlockingQueue是满的,任何...

孟飞阳
2016/07/01
110
0

没有更多内容

加载失败,请刷新页面

加载更多

php7-internal 7 zval的操作

## 7.7 zval的操作 扩展中经常会用到各种类型的zval,PHP提供了很多宏用于不同类型zval的操作,尽管我们也可以自己操作zval,但这并不是一个好习惯,因为zval有很多其它用途的标识,如果自己...

冻结not
昨天
4
0
溢出\越界\泄漏

溢出:栈溢出是指函数中的局部变量造成的溢出,递归次数太多也会栈溢出 一是分配的大小超过栈的最大值,char a[99999999999999999]; 二是分配的大小没有超过最大值,但是接收的buff比新buff小...

SibylY
昨天
3
0
线性表-链式(c/c++实现)

在写数据的结构就是自己排兵布阵,根据客户的需求可增删功能,顺序与链式编程思想是一样的,两个比较只需要改变实现功能这一块。 线性表(链式)实现的三个步骤: 定义所需的功能(LinkList....

白客C
昨天
4
0
导览Linux系统文件系统类型

虽然对于普通用户来说可能并不明显,但在过去十年左右的时间里,Linux 文件系统已经发生了显著的变化,这使它们能够更好对抗损坏和性能问题。 如今大多数 Linux 系统使用名为 ext4 的文件系统...

老孟的Linux私房菜
昨天
4
0
Eureka重要对象简介

在进行分析EurekaClient和EurekaServer之间通信的源码之前,我们首先需要熟悉一下几个实体类 InstanceInfo 这个类代表着EurekaClient实例,客户端向服务端请求注册时就会携带着这个实例,这个...

Java学习录
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部