QueueConcurrentLinkedQueue
QueueConcurrentLinkedQueue
脑丨残 发表于6个月前
QueueConcurrentLinkedQueue
  • 发表于 6个月前
  • 阅读 21
  • 收藏 0
  • 点赞 0
  • 评论 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;
}
标签: 队列
共有 人打赏支持
粉丝 8
博文 55
码字总数 19033
×
脑丨残
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: