文档章节

java并发面试常识之ArrayBlockingQueue

xpbob
 xpbob
发布于 2017/01/25 22:39
字数 1059
阅读 1463
收藏 91

       ArrayBlockingQueue是常用的线程集合,在线程池中也常常被当做任务队列来使用。使用频率特别高。他是维护的是一个循环队列(基于数组实现),循环结构在数据结构中比较常见,但是在源码实现中还是比较少见的。

线程安全的实现

      线程安全队列,基本是离不开锁的。ArrayBlockingQueue使用的是ReentrantLock,配合两种Condition,实现了集合的线程安全操作。这里稍微说一个好习惯,下面是成员变量的声明。

    private static final long serialVersionUID = -817911632652898426L;
    final Object[] items;
    int takeIndex;
    int putIndex;
    int count;
    final ReentrantLock lock;
    private final Condition notEmpty;
    private final Condition notFull;
    transient Itrs itrs = null;

        赋值的操作基本都是在构造函数里做的。这样有个好处,代码执行可控。成员变量的初始化也是会合并在构造方法里执行的,但是在执行顺序上需要好好斟酌,如果写在构造方法里初始化,则没有相关问题。

        阻塞队列的常用场所就是生产者消费者。一般都是生产者放入,消费者从头取数据。下面重点说这两个操作。

        这两个操作都是依靠锁来保证线程安全的。

生产操作

    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);
        } finally {
            lock.unlock();
        }
    }

        put等放入操作,首先是获取锁,如果发现数据满了,就通过notFull的condition,来阻塞线程。这里的条件判定一定是用while而不是if,多线程情况下,可以被唤醒后发现又满了。

    private void enqueue(E x) {
        final Object[] items = this.items;
        items[putIndex] = x;
        if (++putIndex == items.length)
            putIndex = 0;
        count++;
        notEmpty.signal();
    }

        这个是入队列的操作。首先获取维护的数组。putindex就是放入操作的标志。这个操作会一直加。达到预定的长度后就变成0从头开始计数。这样插入的操作就是一个循环的操作了,count就是用来做计数的,作为能否插入数据的一个标准,插入数据后就通过notEmpty的condition发出一个信号唤醒消费线程。

消费操作

    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            while (count == 0)
                notEmpty.await();
            return dequeue();
        } finally {
            lock.unlock();
        }
    }

        消费的方法也是这样。先获取锁,然后进行条件判断,如果没有数据,则阻塞线程。注意点和put一样。

    private E dequeue() {
        final Object[] items = this.items;
        @SuppressWarnings("unchecked")
        E x = (E) items[takeIndex];
        items[takeIndex] = null;
        if (++takeIndex == items.length)
            takeIndex = 0;
        count--;
        if (itrs != null)
            itrs.elementDequeued();
        notFull.signal();
        return x;
    }

        取数据的时候,也依靠takeIndex,这是一个标志,这个数值也会一直增加,表示取的第一个数据的位置。如果这个标志走到最后,然后变成0,从头再来。这样保证取出的数据都是fifo的顺序。删除的时候如果发现迭代中,则会修改迭代器的遍历。然后通过notFull的condition来唤醒生产线程。

移除操作

    public boolean remove(Object o) {
        if (o == null) return false;
        final Object[] items = this.items;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            if (count > 0) {
                final int putIndex = this.putIndex;
                int i = takeIndex;
                do {
                    if (o.equals(items[i])) {
                        removeAt(i);
                        return true;
                    }
                    if (++i == items.length)
                        i = 0;
                } while (i != putIndex);
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

        对于remove操作就比较麻烦了,首先获取锁之后,把两个标志位本地化,然后找到要删除的元素的位置。调用removeAt,这里删除需要对标志位做改变。

    void removeAt(final int removeIndex) {
        final Object[] items = this.items;
        if (removeIndex == takeIndex) {
            items[takeIndex] = null;
            if (++takeIndex == items.length)
                takeIndex = 0;
            count--;
            if (itrs != null)
                itrs.elementDequeued();
        } else {
            final int putIndex = this.putIndex;
            for (int i = removeIndex;;) {
                int next = i + 1;
                if (next == items.length)
                    next = 0;
                if (next != putIndex) {
                    items[i] = items[next];
                    i = next;
                } else {
                    items[i] = null;
                    this.putIndex = i;
                    break;
                }
            }
            count--;
            if (itrs != null)
                itrs.removedAt(removeIndex);
        }
        notFull.signal();
    }

        如果删除的元素是位置和takeindex一样。那就可以直接删除,然后让删除标志位向后移动。如果不是,则从删除的位置开始,进行后面向前面的数据覆盖的操作。直到遇到putindex的前一个位置。然后把那个位置的数据设置为null。并且把putindex的位置往前移动一格,正在迭代的时候要删除数据并且唤醒生产线程。

© 著作权归作者所有

xpbob

xpbob

粉丝 98
博文 98
码字总数 80029
作品 0
高级程序员
私信 提问
加载中

评论(1)

丶生似夏花
看不懂
Java中高级面试必问之多线程TOP50(含答案)

以下为大家整理了今年一线大厂面试被问频率较高的多线程面试题,由于本人的见识局限性,所以可能不是很全面,也欢迎大家在后面留言补充,谢谢。 1、什么是线程? 2、什么是线程安全和线程不安...

老道士
2018/08/28
0
0
JDK容器学习之Queue: ArrayBlockingQueue

基于数组阻塞队列 ArrayBlockingQueue 前面学习了基于数组的非阻塞双端队列,其内部维护一个数组和指向队列头和队列尾索引的两个成员变量;本篇则探究下基于数组的阻塞队列是什么样的数据结构...

小灰灰Blog
2017/11/02
0
0
通俗易懂,JDK 并发容器总结

该文已加入开源项目:JavaGuide(一份涵盖大部分Java程序员所需要掌握的核心知识的文档类项目,Star 数接近 14 k)。地址:https://github.com/Snailclimb/JavaGuide. 一 JDK 提供的并发容器总...

snailclimb
2018/12/10
0
0
读书笔记之《Java并发编程的艺术》-并发编程容器和框架(重要)

读书笔记部分内容来源书出版书,版权归本书作者,如有错误,请指正。 欢迎star、fork,读书笔记系列会同步更新 git https://github.com/xuminwlt/j360-jdk module j360-jdk-thread/me.j360....

Hi徐敏
2015/11/11
0
1
CountDownLatch源码解析

CountDownLatch 相比ReentranceLock,CountDownLatch的流程还是相对比较简单的,CountDownLatch也是基于AQS,它是AQS的共享功能的一个实现。 下面从源代码的实现上详解CountDownLatch。 1、C...

maxam0128
2018/01/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

https://zhuanlan.zhihu.com/p/61408911

在Logistimo,我们的所有应用程序都是Docker化的,并在Kubernetes内以docker容器运行。我们注意到在使用Java的容器上发生了大量重启,并且非常随机。Docker检查发现该pod被OOMKiller代码杀死...

xiaomin0322
5分钟前
0
0
北斗三号IGSO-2卫星发射成功!

6月25日,中国航天科技集团官方公众号宣布,北斗三号IGSO-2卫星发射成功! 航天科技集团表示,6月25日2点09分,我国在西昌卫星发射中心用长征三号乙运载火箭成功将北斗三号第2颗倾斜地球同步...

linux-tao
8分钟前
1
0
oracle通过dblink查询sqlserver报错

报错如下: SQL> select * from t@mstest; select * from t@test * ERROR at line 1: ORA-28545: error diagnosed by Net8 when connecting to an agent Unable to retrieve text of NETWORK......

突突突酱
11分钟前
0
0
docker-elasticsearch学习

如果不适用docker,面临的问题有: 部署非常慢 成本非常高 资源浪费 难于迁移和扩展 可能会被限定硬件厂商 虚拟化技术的优点: 虚拟化技术出现以后,一个物理机可以部署多个App,每个App独立...

Vincent-Duan
21分钟前
0
0
MySQL权限管理坑

权限系统的工作原理 MySQL权限系统通过下面两个阶段进行认证: (1)对连接的用户进行身份认证,合法的用户通过认证、不合法的用户拒绝连接。 (2)对通过认证的合法用户赋予相应的权限,用户...

bengozhong
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部