文档章节

QueueConcurrentLinkedQueue

脑丨残
 脑丨残
发布于 2017/05/22 21:07
字数 1150
阅读 23
收藏 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
博文 60
码字总数 23267
作品 0
西安

暂无文章

Centos7通过yum安装nginx

添加源地址(直接install可能不是最新版本的) sudo rpm -Uvh http://nginx.org/packages/centos/7/noarch/RPMS/nginx-release-centos-7-0.el7.ngx.noarch.rpm 安装 sudo yum install -y ng......

iplusx
9分钟前
0
0
ef .core Dapper Helper

using System; using System.Collections.Generic; using System.Configuration; using System.Data; using System.Data.SqlClient; using System.Threading.Tasks; using Dapper; using Dap......

Lytf
11分钟前
0
0
iOS 小笔记

1.以下代码打印什么     __block int val = 10;    void (^blk)(void) = ^{        printf("val=%d\n",val);        };       val = 2;    blk(); /...

风了个1
12分钟前
0
0
【Spring Boot 系列 Spring Boot示例程序】

入门程序步骤,创建一个Maven项目。继承Spring Boot官方提供的父工程。再引入一个Web的应用启动器。 1、选择一个合适的IDEA工具 创建一个Maven工程,并添加如下配置 <parent> <...

HansonReal
14分钟前
0
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意:判断数组中是否有重复元素 思路:构造一个set,不重复就加进去,重复返回true,如果数据量大的话,可以用布隆过滤器 Java实现: publ...

yysue
18分钟前
0
0
istio 处理失败 (理论)

Envoy提供了一套开箱即用的选择加入故障恢复功能,可以通过应用程序中的服务进行利用。功能包括: 超时 具有超时预算和重试之间的可变抖动的有界重试 限制并发连接数和对上游服务的请求 对负...

xiaomin0322
19分钟前
0
0
eclipse解决git冲突举例

本地修改了两个文件,提交时提示有冲突,想来应该是没有从远程仓库下载最新代码导致的。通过右击项目 -> Team -> Sychronized WorkSpace,比较本地仓库和远程仓库的异同:   此时没有更好的...

Code辉
28分钟前
0
0
运行.jar后缀的文件

前提必须安装了jdk,正确配置环境变量。 在dos窗口执行以下命令即可。 java -jar C:\Users\10492\Desktop\turn.jar

haha360
30分钟前
0
0
Java程序员如何做代码压力测试?【JWordPress前台项目实战】

代码 pom.xml文件引入包 <dependency><groupId>com.taobao.stresstester</groupId><artifactId>stresstester</artifactId><version>1.0</version></dependency> 编写测试代码 /**......

迷你芊宝宝
35分钟前
0
0
面试宝典-什么是缓存穿透?

缓存穿透是说收到了一个请求,但是该请求缓存里没有,只能去数据库里查询,然后放进缓存。 这里面有两个风险,一个是同时有好多请求访问同一个数据,然后业务系统把这些请求全发到了数据库;...

suyain
41分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部