文档章节

Java中的队列都有哪些,有什么区别。

郑加威
 郑加威
发布于 02/27 20:30
字数 1042
阅读 1413
收藏 20

Java中的队列都有哪些,实际上是问queue的实现有哪些,如:ConcurrentLinkedQueue、LinkedBlockingQueue 、ArrayBlockingQueue、LinkedList。

源于我经历过的一次生产事故,有个服务会收集业务系统的日志,此服务的开发人员在给业务系统的sdk中就因为使用了LinkedList,又没有做并发控制,就造成了此服务经常不能正常收集到业务系统的日志(丢日志以及日志上报的线程停止运行)。

看一下add()方法的源码,我们就可以知道原因了:


public boolean add(E e) {
    linkLast(e);//调用linkLast,在队列尾部添加元素
    return true;
} 

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;//多线程情况下,如果业务系统没做并发控制,size的数量会远远大于实际元素的数量
    modCount++;
}

上面这个示例中,展示了LinkedList在多线程且没有做并发控制的环境下,size的值远远大于了队列的实际值,100个线程,每个添加1000个元素,最后实际只加进去2030个元素:

List的变量size值为:88371
第2031个元素取出为null

解决方案,使用锁或者使用ConcurrentLinkedQueue、LinkedBlockingQueue等支持添加元素为原子操作的队列。

我们已经分析过LinkedBlockingQueue的put等方法的源码,是使用ReentrantLock来实现的添加元素原子操作。那么再简单看一下高并发queue的add和offer()方法,方法中使用了CAS来实现的无锁的原子操作:

public boolean add(E e) {
  return offer(e);
}
public boolean offer(E e) {

        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p is last node
                if (p.casNext(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }else if (p == q)
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

接下来,我们再利用高并发queue对上面的demo进行改造,大家只要改变demo中的内容,讲下面两行的注释内容颠倒,即可发现没有丢失任何的元素:

public static LinkedList list = new LinkedList();
//public static ConcurrentLinkedQueue list = new ConcurrentLinkedQueue();

再看一下高性能queue的poll()方法,才觉得NB,取元素的方法也用CAS实现了原子操作,因此在实际使用的过程中,当我们不那么在意元素处理顺序的情况下,队列元素的消费者,完全可以是多个,不会丢任何数据:

public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;

                if (item != null && p.casItem(item, null)) {
                    // Successful CAS is the linearization point
                    // for item to be removed from this queue.
                    if (p != h) // hop two nodes at a time
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }

关于ConcurrentLinkedQueue和LinkedBlockingQueue:

  • LinkedBlockingQueue是使用锁机制,ConcurrentLinkedQueue是使用CAS算法,虽然LinkedBlockingQueue的底层获取锁也是使用的CAS算法
  • 关于取元素,ConcurrentLinkedQueue不支持阻塞去取元素,LinkedBlockingQueue支持阻塞的take()方法,如若大家需要ConcurrentLinkedQueue的消费者产生阻塞效果,需要自行实现
  • 关于插入元素的性能,从字面上和代码简单的分析来看ConcurrentLinkedQueue肯定是最快的,但是这个也要看具体的测试场景,我做了两个简单的demo做测试,测试的结果如下,两个的性能差不多,但在实际的使用过程中,尤其在多cpu的服务器上,有锁和无锁的差距便体现出来了,ConcurrentLinkedQueue会比LinkedBlockingQueue快很多:ConcurrentLinkedQueuePerform:在使用ConcurrentLinkedQueue的情况下100个线程循环增加的元素数为:33828193 
    LinkedBlockingQueuePerform:在使用LinkedBlockingQueue的情况下100个线程循环增加的元素数为:33827382

 

© 著作权归作者所有

共有 人打赏支持
郑加威
粉丝 100
博文 382
码字总数 675408
作品 0
杭州
架构师
备战一线互联网公司Java工程师面试题 (2)

JVM 1、请介绍一下JVM内存模型??用过什么垃圾回收器都说说呗 2、线上发送频繁full gc如何处理? CPU 使用率过高怎么办? 如何定位问题?如何解决说一下解决思路和处理方法 3、知道字节码吗?字节...

j4love
04/14
0
0
阿里高级Java面试题(首发,70道,带详细答案)

整理的70道阿里的Java面试题,都来挑战一下,看看自己有多厉害。下面题目都带超详细的解答,详情见底部。 1、java事件机制包括哪三个部分?分别介绍。 2、为什么要使用线程池? 3、线程池有什...

java技术栈
2017/11/11
0
0
Java架构师面试题全分享,你离架构师还有多远?

经常面试一些候选人,整理了下我面试使用的题目,陆陆续续整理出来的题目很多,所以每次会抽一部分来问。答案会在后面的文章中逐渐发布出来。 基础题目 Java线程的状态 进程和线程的区别,进...

重走Java
07/05
0
0
经过了这么多场Java面试,我明白了这些道理

最近3个月一口气面了十几家公司的Java开发岗,大大小小的面试笔试加起来快20场,收获很多。本人毕业快2年了,毕业时在学校所在的2线省会城市找了家开发公司做java的开发,前前后后做了1年半,...

snailclimb
08/24
0
0
Java中高级面试必问之多线程TOP50(含答案)

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

老道士
08/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

00.编译OpenJDK-8u40的整个过程

前言 历经2天的折腾总算把OpenJDK给编译成功了,要说为啥搞这个,还得从面试说起,最近出去面试经常被问到JVM的相关东西,总感觉自己以前学的太浅薄,所以回来就打算深入学习,目标把《深入理...

凌晨一点
今天
2
0
python: 一些关于元组的碎碎念

初始化元组的时候,尤其是元组里面只有一个元素的时候,会出现一些很蛋疼的情况: def checkContentAndType(obj): print(obj) print(type(obj))if __name__=="__main__": tu...

Oh_really
昨天
6
2
jvm crash分析工具

介绍一款非常好用的jvm crash分析工具,当jvm挂掉时,会产生hs_err_pid.log。里面记录了jvm当时的运行状态以及错误信息,但是内容量比较庞大,不好分析。所以我们要借助工具来帮我们。 Cras...

xpbob
昨天
113
0
Qt编写自定义控件属性设计器

以前做.NET开发中,.NET直接就集成了属性设计器,VS不愧是宇宙第一IDE,你能够想到的都给你封装好了,用起来不要太爽!因为项目需要自从全面转Qt开发已经6年有余,在工业控制领域,有一些应用...

飞扬青云
昨天
4
0
我为什么用GO语言来做区块链?

Go语言现在常常被用来做去中心化系统(decentralised system)。其他类型的公司也都把Go用在产品的核心模块中,并且它在网站开发中也占据了一席之地。 我们在决定做Karachain的时候,考量(b...

HiBlock
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部