专栏首页无题BlockingQueue源码分析

BlockingQueue源码分析

*

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

ArrayBlockingQueue

ArrayBlockingQueue是一个用数组实现的有界阻塞队列。此队列按照先进先出(FIFO)的原则对元素进行排序。默认情况下不保证访问者公平的访问队列,所谓公平访问队列是指阻塞的所有生产者线程或消费者线程,当队列可用时,可以按照阻塞的先后顺序访问队列,即先阻塞的生产者线程,可以先往队列里插入元素,先阻塞的消费者线程,可以先从队列里获取元素。通常情况下为了保证公平性会降低吞吐量。我们可以使用以下代码创建一个公平的阻塞队列:

需要我们记住的是:

1、ArrayBlockingQueue队列是基于数组+Condition类来实现的。

2、线程安全是通过ReentrantLock来保证的。

3、队列中不允许元素为null.

LinkedBlockingQueue

LinkedBlockingQueue是一个用链表实现的有界阻塞队列。此队列的默认和最大长度为Integer.MAX_VALUE。此队列按照先进先出的原则对元素进行排序。

关于LinkedBlockingQueue我们只需要记住以下几点

1、是基于链表来实现的

2、使用了两个锁,take、put操作各一把锁。以及借用了两个Condition来进行阻塞和唤醒操作。

SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列。每一个put操作必须等待一个take操作,否则不能继续添加元素。SynchronousQueue可以看成是一个传球手,负责把生产者线程处理的数据直接传递给消费者线程。队列本身并不存储任何元素,非常适合于传递性场景,比如在一个线程中使用的数据,传递给另外一个线程使用,SynchronousQueue的吞吐量高于LinkedBlockingQueue 和 ArrayBlockingQueue。

LinkedBlockingDeque

LinkedBlockingDeque是一个由链表结构组成的双向阻塞队列。所谓双向队列指的你可以从队列的两端插入和移出元素。双端队列因为多了一个操作队列的入口,在多线程同时入队时,也就减少了一半的竞争。相比其他的阻塞队列,LinkedBlockingDeque多了addFirst,addLast,offerFirst,offerLast,peekFirst,peekLast等方法,以First单词结尾的方法,表示插入,获取(peek)或移除双端队列的第一个元素。以Last单词结尾的方法,表示插入,获取或移除双端队列的最后一个元素。另外插入方法add等同于addLast,移除方法remove等效于removeFirst。但是take方法却等同于takeFirst,不知道是不是Jdk的bug,使用时还是用带有First和Last后缀的方法更清楚。

PriorityBlockingQueue

PriorityBlockingQueue是一个支持优先级的无界队列。默认情况下元素采取自然顺序排列,也可以通过比较器comparator来指定元素的排序规则。元素按照升序排列。

DelayQueue

DelayQueue是一个支持延时获取元素的无界阻塞队列。队列使用PriorityQueue来实现。队列中的元素必须实现Delayed接口,在创建元素时可以指定多久才能从队列中获取当前元素。只有在延迟期满时才能从队列中提取元素。我们可以将DelayQueue运用在以下应用场景:

  • 缓存系统的设计:可以用DelayQueue保存缓存元素的有效期,使用一个线程循环查询DelayQueue,一旦能从DelayQueue中获取元素时,表示缓存有效期到了。
  • 定时任务调度。使用DelayQueue保存当天将会执行的任务和执行时间,一旦从DelayQueue中获取到任务就开始执行,从比如TimerQueue就是使用DelayQueue实现的。

2、ArrayBlockingQueue

ArrayBlockingQueue是一个基于数组且有界的阻塞队列。此队列按FIFO(先进先出)原则对元素进行排序。即队列头保存的是在队列中待的时间最长的元素。队列尾则是待的时间最短的元素。元素插入到对尾,在队首获取元素。

ArrayBlockingQueue的构造方法

//创建一个指定大小的队列对象。
publicArrayBlockingQueue(intcapacity) {
    this(capacity, false);
}

publicArrayBlockingQueue(intcapacity, boolean fair) { if(capacity <= 0) thrownewIllegalArgumentException(); this.items = newObject[capacity]; lock= newReentrantLock(fair); notEmpty = lock.newCondition(); notFull = lock.newCondition(); 13

构造方法就是创建一个指定大小的队列对象。要说明的一点是第二个参数,fair,如果为true,则表示创建一个公平的队列,即所有等待的消费者或者是生产者是按照顺序来访问这个队列。

在API文档中,对公平性由如下的介绍:此类支持对等待的生产者线程和使用者线程进行排序的可选公平策略。默认情况下,不保证是这种排序。然而,通过将公平性(fairness) 设置为true 而构造的队列允许按照FIFO 顺序访问线程。公平性通常会降低吞吐量,但也减少了可变性和避免了“不平衡性”。

2.4 ArrayBlockingQueue类中的put方法

函数功能:插入一个元素到队列的末尾,如果队列已满则等待

源代码如下:(有详细的注释)

publicvoidput(E e) throws InterruptedException {
    checkNotNull(e);//检查是否为空,如果为空,则抛NullPointerException
    //获取锁,
    final ReentrantLock lock= this.lock;
    lock.lockInterruptibly();
    try{
        //检查是否已满,如果已满,则调用Condition的await方法等待并释放锁
        while(count == items.length)
            notFull.await();
        enqueue(e);//如果没满,则直接加入到队列中
    } finally{
        lock.unlock();//最后释放锁
    }
}

privatestaticvoidcheckNotNull(Object v) { if(v == null) thrownewNullPointerException(); } privatevoidenqueue(E x) { // assert lock.getHoldCount() == 1; // assert items[putIndex] == null; final Object[] items = this.items; items[putIndex] = x; if(++putIndex == items.length)//转换下指针 putIndex = 0; count++; //当添加元素后,则唤醒一个消费者 notEmpty.signal(); } 25

  • 31

函数功能:插入一个元素到队列的末尾,如果队列已满则等待

此方法的实现思路如下:

1、判断要添加的元素是否为null,如果为null,则抛异常。否则进行2

2、加锁

3、检测队列是否已满,如果已满,则等待并释放锁(condtion的await方法会释放锁),如果没有满,则将元素加入到队列中即可。

4、释放锁

看了put方法的源码,是不是思路相当的清晰、简单哈。

2.5 ArrayBlockingQueue类中的take方法

源码如下:

publicE take() throwsInterruptedException {
    finalReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try{
        //如果队列中存储的元素为空,则等待直至队列中非空
        while(count == 0)
            notEmpty.await();
        returndequeue();
    } finally{
        lock.unlock();
    }
}

/**

 * Extracts element at current take position, advances, and signals.
 * Call only when holding lock.
 */
privateE dequeue() {
    // assert lock.getHoldCount() == 1;
    // assert items[takeIndex] != null;
    finalObject[] items = this.items;
    @SuppressWarnings("unchecked")
    E x = (E) items[takeIndex];
    items[takeIndex] = null;//置为null
    if(++takeIndex == items.length)
        takeIndex = 0;
    count--;
    if(itrs != null)
        itrs.elementDequeued();
    //唤醒等待的生产者
    notFull.signal();
    returnx;
}

函数功能:取出队列中队首的元素,如果为空,则等待直至队列为非空。

实现思路如下:

1、加锁

2、检查队列是否为空,如果为空,则阻塞等待,否则取出队首的元素并返回。

3、释放锁。

是不是特简单,相信写过生产消费者模型的我们对上面put、take方法实现的代码特别熟悉哈,因为ArrayBlockingQueue的实现就是和生产消费者模型思路一模一样

ArrayBlockingQueue中的其它插入元素的方法基本和put方法一致,获取元素的其它方法与take方法基本一致,这里就不对这些方法的实现一一详细介绍了哈。

小结

关于ArrayBlockingQueue的介绍就到这里为止了哈,确实实现思想特别简单哈。

需要我们记住的是:

1、ArrayBlockingQueue队列是基于数组+Condition类来实现的。

2、线程安全是通过ReentrantLock来保证的。

3、队列中不允许元素为null.

关于BlockingQueue的其它实现类LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue将在明天介绍。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 秒杀系统解决方案

    从架构、产品、前端、后端四个层面针对秒杀场景(可以扩展到所有高并发场景)分别总结了一些解决方案。 要点总结: 1.架构:扩容,业务分离,数据分离 2.产品:下...

    于霆霖
  • Mybatis源码解析

    MyBatis初始化 MyBatis在初始化的时候,会将MyBatis的配置信息全部加载到内存中,使用org.apache.ibatis.session.Con...

    于霆霖
  • SpringBoot自动装配源码解析

    运行原理 在第一次使用spring boot的时候,大家都会惊讶于@SpringBootApplication这个注解,有了它马上就能够让整个应用跑起来。实际上...

    于霆霖
  • 三分钟基础:什么是队列?

    像线程池、异步队列、消息队列等有限的资源容器中,往往存储大量的任务事件,这些大量的任务事件需要进行有条理的进行任务分发以及各种情况处理,为了能够使得资源容器的正...

    帅地
  • AI_第一部分 数据结构与算法(8.队列)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • Hadoop FairScheduler

    本文档描述FairScheduler,一个允许YARN应用程序公平共享集群资源的调度插件。

    用户1217611
  • 前端中的数据结构——队列篇

    队列是数据结构中的一种,它与实际生活中的排队相似:在一条队伍中,先来的人总是能够先得到服务,后来的人只能排在队伍末尾等候。队列也是一样,它符合先进先出 FIFO...

    企鹅号小编
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java
  • 【数据结构(C语言版)系列三】 队列

    队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。在队列中,允许插入的一...

    闪电gogogo
  • 算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

    数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

    lizelu

扫码关注云+社区

领取腾讯云代金券