文档章节

QueueConcurrentLinkedQueue

脑丨残
 脑丨残
发布于 2017/05/22 21:07
字数 1150
阅读 23
收藏 0

#ConcurrentLinkedQueue

  • 线程安全队列,内部链表,节点,volatile修饰,cas轻量级同步。
  • volatile 变量:轻量级多线程同步机制,不会引起上下文切换和线程调度。仅提供内存可见性保证,不提供原子性。 CAS 原子指令:轻量级多线程同步机制,不会引起上下文切换和线程调度。它同时提供内存可见性原子化更新保证 互斥锁:重量级多线程同步机制,可能会引起上下文切换和线程调度,它同时提供内存可见性原子性
  • 头节点,尾节点CAS操作
private transient volatile Node<E> head;
private transient volatile Node<E> tail;
private static final sun.misc.Unsafe UNSAFE;
    private static final long headOffset;
    private static final long tailOffset;
    static {
        try {
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class<?> k = ConcurrentLinkedQueue.class;
            headOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("head"));
            tailOffset = UNSAFE.objectFieldOffset
                (k.getDeclaredField("tail"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

private boolean casTail(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, tailOffset, cmp, val);
}
private boolean casHead(Node<E> cmp, Node<E> val) {
    return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
}
  • offer,无锁同步设置,通过死循环设置的方式保证数据一致,
  • 有一个线程正在入队,那么它必须先获取尾节点,然后设置尾节点的下一个节点为入队节点,但这时可能有另外一个线程插队了,那么队列的尾节点就会发生变化,这时当前线程要暂停入队操作,然后重新获取尾节点(JDK1.8)
    public boolean offer(E e) {
        checkNotNull(e);
        //创建入队节点
        final Node<E> newNode = new Node<E>(e);
        //t为tail节点,p为尾节点,默认相等,采用失败即重试的方式,直到入队成功
        for (Node<E> t = tail, p = t;;) {
            //获得p的下一个节点
            Node<E> q = p.next;
            // 如果下一个节点是null,也就是p节点就是尾节点
            if (q == null) {
              //将入队节点newNode设置为当前队列尾节点p的next节点
                if (p.casNext(null, newNode)) { 
                   //判断tail节点是不是尾节点,也可以理解为如果插入结点后tail节点和p节点距离达到两个结点
                    if (p != t) 
                     //如果tail不是尾节点则将入队节点设置为tail。
                     // 如果失败了,那么说明有其他线程已经把tail移动过 
                        casTail(t, newNode);  
                    return true;
                }
            }
                 // 如果p节点等于p的next节点,则说明p节点和q节点都为空,表示队列刚初始化,所以返回                            head节点
            else if (p == q)
                p = (t != (t = tail)) ? t : head;
            else
                //p有next节点,表示p的next节点是尾节点,则需要重新更新p后将它指向next节点
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }
  • poll
public E poll() {
        // 设置起始点  
        restartFromHead:
        for (;;) {
        //p表示head结点,需要出队的节点
            for (Node<E> h = head, p = h, q;;) {
            //获取p节点的元素
                E item = p.item;
                //如果p节点的元素不为空,使用CAS设置p节点引用的元素为null
                if (item != null && p.casItem(item, null)) {
                    if (p != h) // hop two nodes at a time
                    //如果p节点不是head节点则更新head节点,也可以理解为删除该结点后检查head是否与头结点相差两个结点,如果是则更新head节点
                        updateHead(h, ((q = p.next) != null) ? q : p);
                    return item;
                }
                //如果p节点的下一个节点为null,则说明这个队列为空,更新head结点
                else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                }
                //结点出队失败,重新跳到restartFromHead来进行出队
                else if (p == q)
                    continue restartFromHead;
                else
                    p = q;
            }
        }
    }
  • 首先获取head节点的元素,并判断head节点元素是否为空,如果为空,表示另外一个线程已经进行了一次出队操作将该节点的元素取走,如果不为空,则使用CAS的方式将head节点的引用设置成null,如果CAS成功,则直接返回head节点的元素,如果CAS不成功,表示另外一个线程已经进行了一次出队操作更新了head节点,导致元素发生了变化,需要重新获取head节点。如果p节点的下一个节点为null,则说明这个队列为空(此时队列没有元素,只有一个伪结点p),则更新head节点。
final void updateHead(Node<E> h, Node<E> p) 
{
     // 如果两个结点不相同,尝试用CAS指令原子更新head指向新头节点
     if (h != p && casHead(h, p))
          //将旧的头结点指向自身以实现删除
     h.lazySetNext(h);
}
  • 队列判空,size会遍历链表,通性,isEmpty性能高.
public boolean isEmpty() {
     return first() == null;
}
public int size() {
        int count = 0;
        for (Node<E> p = first(); p != null; p = succ(p))
            if (p.item != null)
                // Collection.size() spec says to max out
                if (++count == Integer.MAX_VALUE)
                    break;
        return count;
}

© 著作权归作者所有

共有 人打赏支持
上一篇: Map.HashMap
下一篇: Queue.LinkedList
脑丨残
粉丝 8
博文 60
码字总数 23267
作品 0
西安
私信 提问

暂无文章

day148-2018-11-15-英语流利阅读-待学习

赴美生子恐结束?特朗普中期选举憋大招 毛西 2018-11-15 1.今日导读 在 2013 年,一部《北京遇上西雅图》让赴美生子这个曾经神秘的话题吸引了很多关注。每年,数以万计的父母远赴美国,并在那...

飞鱼说编程
12分钟前
0
0
OSChina 周四乱弹 —— 每次我穿短裙的时候

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @瘟神灬念 :分享DM DOKURO的单曲《Reality Check Through The Skull》: 差点以为手机卡了 《Reality Check Through The Skull》- DM DOKURO...

小小编辑
21分钟前
20
2
Windows 10 设置 Java 环境变量

首先你需要在我的电脑中打开,找到环境变量属性。 找到环境变量属性 找到环境变量属性后单击将会看到下面的设置界面。 在这个界面中设置高级系统设置。 环境变量 在弹出的界面中选择设置环境...

honeymose
今天
2
0
用any-loader封装jQuery的XHR —— 随便写着玩系列

哎,都说没人用JQuery啦,叫你别写这个。 其实我也是好高骛远使用过npm上某个和某个很出名的XHR库,嗯,认识我的人都知道我喜欢喷JQ,以前天天喷,见面第一句,你还用JQ,赶紧丢了吧。但我也...

曾建凯
今天
8
0
SLF4J的正确打开方式

最近公司好几波人过来问日志打印相关的异常,大多是jar包冲突引起的,发现大部分同事不太清楚各种日志框架以及相关jar包之间的关系,所以今天详细的讲解下常见jar包之间的关系,以及如何正确...

lexus90
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部