BlockingQueue原理分析

BlockingQueue即阻塞队列,它算是一种将ReentrantLock用得非常精彩的一种表现,依据它的基本原理,我们可以实现Web中的长连接聊天功能,当然其最常用的还是用于实现生产者与消费者模式,大致如下图所示:

生产者与消费者模式

在Java中,BlockingQueue是一个接口,它的实现类有ArrayBlockingQueue、DelayQueue、 LinkedBlockingDeque、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等,它们的区别主要体现在存储结构上或对元素操作上的不同,但是对于take与put操作的原理,却是类似的

一、ArrayBlockingQueue

ArrayBlockingQueue底层是使用一个数组实现队列的,并且在构造ArrayBlockingQueue时需要指定容量,也就意味着底层数组一旦创建了,容量就不能改变了,因此ArrayBlockingQueue是一个容量限制的阻塞队列。因此,在队列全满时执行入队将会阻塞,在队列为空时出队同样将会阻塞。

1.1 参数及构造函数

BlockingQueue内部有一个ReentrantLock,其生成了两个Condition,在ArrayBlockingQueue的属性声明中可以看见:

 // 存储队列元素的数组
    final Object[] items;
    // 拿数据的索引,用于take,poll,peek,remove方法
    int takeIndex;
    // 放数据的索引,用于put,offer,add方法
    int putIndex;
    // 元素个数
    int count;
    // 可重入锁
    final ReentrantLock lock;
    // notEmpty条件对象,由lock创建
    private final Condition notEmpty;
    // notFull条件对象,由lock创建
    private final Condition notFull;

    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);//默认构造非公平锁的阻塞队列 
    }
    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        //初始化ReentrantLock重入锁,出队入队拥有这同一个锁 
        lock = new ReentrantLock(fair);
        //初始化非空等待队列
        notEmpty = lock.newCondition();
        //初始化非满等待队列 
        notFull =  lock.newCondition();
    }
    public ArrayBlockingQueue(int capacity, boolean fair,
                              Collection<? extends E> c) {
        this(capacity, fair);

        final ReentrantLock lock = this.lock;
        lock.lock(); // Lock only for visibility, not mutual exclusion
        try {
            int i = 0;
            //将集合添加进数组构成的队列中 
            try {
                for (E e : c) {
                    checkNotNull(e);
                    items[i++] = e;
                }
            } catch (ArrayIndexOutOfBoundsException ex) {
                throw new IllegalArgumentException();
            }
            count = i;
            putIndex = (i == capacity) ? 0 : i;
        } finally {
            lock.unlock();
        }
    }

几个重要的点:

  1. 用到了ReentrantLock锁
  2. 用lock创建了两个Condition,notEmpty和notFull。
    notEmpty是消费队列元素的等待队列(即take、peek、poll方法)
    notFull是生产队列元素的等待队列(即put,offer,add方法)
  3. 用的锁是非公平锁
  4. takeIndex和putIndex

1.2 put方法

put(E e)方法在队列不满的情况下,将会将元素添加到队列尾部,如果队列已满,将会阻塞,直到队列中有剩余空间可以插入。该方法的实现如下:

public void put(E e) throws InterruptedException {
        checkNotNull(e);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            //当元素数量与数组的长度相等,无法添加元素
            while (count == items.length)
                //挂起当前线程,,添加到notFull条件队列中等待唤醒
                notFull.await();
            //添加元素到队列
            enqueue(e);
        } finally {
            //释放锁
            lock.unlock();
        }
    }

lock 与 lockInterruptibly比较区别在于:
lock 优先考虑获取锁,待获取锁成功后,才响应中断。
lockInterruptibly 优先考虑响应中断,而不是响应锁的普通获取或重入获取。 

enqueue方法源码:

private void enqueue(E x) {
        // assert lock.getHoldCount() == 1;
        // assert items[putIndex] == null;
        final Object[] items = this.items;
        //将元素放到putIndex位置
        items[putIndex] = x;
        /*如果putIndex+1后的值==数组的长度,则putIndex重置为0*/
        if (++putIndex == items.length)
            putIndex = 0;
        count++;
        //唤醒notEmpty
        notEmpty.signal();
    }

 从enqueue方法可以看出ArrayBlockingQueue是查数据是按数组下标顺序插入数据的,当插入到最后一个下标时,会再从头开始插入元素。

 关于put方法几个重要的点:

  1. 整个过程是被锁住的
  2. ArrayBlockingQueue不允许元素为null 
  3. 当元素数量与数组的长度相等,无法添加元素,要唤醒notFull等待队列,让它从队列中取数据
  4. enqueue方法中,如果putIndex+1后的值==数组的长度,则putIndex重置为0
  5. 添加元素的最后一个步骤是唤醒notEmpty等待队列,即唤醒消费的等待队列线程

1.2.1 put方法总结与图解

put方法是一个阻塞的方法,如果队列元素已满,那么当前线程将会被notFull条件对象挂起加到等待队列中,直到队列有空档才会唤醒执行添加操作。但如果队列没有满,那么就直接调用enqueue(e)方法将元素加入到数组队列中。到此我们对三个添加方法即put,offer,add都分析完毕,其中offer,add在正常情况下都是无阻塞的添加,而put方法是阻塞添加。这就是阻塞队列的添加过程。说白了就是当队列满时通过条件对象Condtion来阻塞当前调用put方法的线程,直到线程又再次被唤醒执行。总得来说添加线程的执行存在以下两种情况,一是,队列已满,那么新到来的put线程将添加到notFull的条件队列中等待,二是,有移除线程执行移除操作,移除成功同时唤醒put线程,如下图所示

 

1.3 take方法 

take()方法用于取走队头的元素,当队列为空时将会阻塞,直到队列中有元素可取走时将会被释放。其实现如下:

public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        //加锁
        lock.lockInterruptibly();
        try {
            如果队列为空,唤醒notEmpty等待队列,让其插入元素
            while (count == 0)
                notEmpty.await();
            //队列不为空,调用dequeue()出队    
            return dequeue();
        } finally {
            lock.unlock();
        }
    }

dequeue方法实现如下:

private E dequeue() {
        // assert lock.getHoldCount() == 1;
        // assert items[takeIndex] != null;
        //拿到数组数据
        final Object[] items = this.items;
        @SuppressWarnings("unchecked")
        //拿到takeIndex下标的元素
        E x = (E) items[takeIndex];
        // 将数组中takeIndex索引位置设置为null
        items[takeIndex] = null;
        /*takeIndex索引加1并判断是否与数组长度相等,
          如果相等说明已到尽头,恢复为0*/
        if (++takeIndex == items.length)
            takeIndex = 0;
        //队列个数减1
        count--;
        if (itrs != null)
            //同时更新迭代器中的元素数据
            itrs.elementDequeued();
        //删除了元素说明队列有空位,唤醒notFull条件对象添加线程,执行添加操作
        notFull.signal();
        return x;
    }

关于take方法几个重要的点: 

  1. 整个过程是被锁住的
  2. dequeue方法中,如果takeIndex+1后的值==数组的长度,则takeIndex重置为0。
    与enqueue方法中的putIndex相似。保证了FIFO
  3. 取出元素的最后一个步骤是唤醒notEmpty等待队列,即唤醒生产元素等待队列线程

1.3.1 take方法总结与图解 

take方法其实很简单,有就删除没有就阻塞,注意这个阻塞是可以中断的,如果队列没有数据那么就加入notEmpty条件队列等待(有数据就直接取走,方法结束),如果有新的put线程添加了数据,那么put操作将会唤醒take线程,执行take操作。图示如下:

1.4 全流程图

1.5 ArrayBlockingQueue的方法对比

  • add方法在添加元素的时候,若超出了度列的长度会直接抛出异常。
  • put方法,若向队尾添加元素的时候发现队列已经满了会发生阻塞一直等待空间,以加入元素。
  • offer方法在添加元素时,如果发现队列已满无法添加的话,会直接返回false。

  • remove:若队列为空,抛出NoSuchElementException异常。
  • take:若队列为空,发生阻塞,等待有元素。
  • poll: 若队列为空,返回null。
  • peek:该方法返回存在于此队列开头的元素

 这些方法我就不做源码分析了,有兴趣可以自行查看,大致都差不多。

二、ArrayBlockingQueue与LinkedBlockingQueue异同

LinkedBlockingQueue和ArrayBlockingQueue的异同

深入剖析java并发之阻塞队列LinkedBlockingQueue与ArrayBlockingQueue

ArrayBlockingQueue跟LinkedBlockingQueue的区别

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…