分析Java非阻塞算法Lock-Free的实现

非阻塞的栈

我们先使用CAS来构建几个非阻塞的栈。栈是最简单的链式结构，其本质是一个链表，而链表的根节点就是栈顶。

我们先构建Node数据结构：

public class Node<E> {
    public final E item;
    public Node<E> next;

    public Node(E item){
        this.item=item;
    }
}

这个Node保存了内存item和它的下一个节点next。

然后我们构建非阻塞的栈，在该栈中我们需要实现pop和push方法，我们使用一个Atomic类来保存top节点的引用，在pop和push之前调用compareAndSet命令来保证命令的原子性。同时，我们需要不断的循环，以保证在线程冲突的时候能够重试更新。

public class ConcurrentStack<E> {

    AtomicReference<Node<E>> top= new AtomicReference<>();

    public void push(E item){
        Node<E> newNode= new Node<>(item);
        Node<E> oldNode;
        do{
            oldNode=top.get();
            newNode.next= oldNode;
        }while(!top.compareAndSet(oldNode, newNode));
    }

    public E pop(){
        Node<E> oldNode;
        Node<E> newNode;
        do {
            oldNode = top.get();
            if(oldNode == null){
                return null;
            }
            newNode=oldNode.next;
        }while(!top.compareAndSet(oldNode, newNode));
        return oldNode.item;
    }

}

非阻塞的链表

构建链表要比构建栈复杂。因为我们要维持头尾两个指针。以put方法来说，我们需要执行两步操作：1. 在尾部插入新的节点。2.将尾部指针指向最新的节点。

我们使用CAS最多只能保证其中的一步是原子执行。那么对于1和2的组合步骤该怎么处理呢？

我们再仔细考虑考虑，其实1和2并不一定要在同一个线程中执行，其他线程在检测到有线程插入了节点，但是没有将tail指向最后的节点时，完全帮忙完成这个操作。

我们看下具体的代码实现：

public class LinkedNode<E> {
    public final E item;
    public final AtomicReference<LinkedNode<E>> next;

    public LinkedNode(E item, LinkedNode<E> next){
        this.item=item;
        this.next=new AtomicReference<>(next);
    }
}

先构建一个LinkedNode类。

public class LinkedQueue<E> {
    private final LinkedNode<E> nullNode= new LinkedNode<>(null, null);
    private final AtomicReference<LinkedNode<E>> head= new AtomicReference<>(nullNode);
    private final AtomicReference<LinkedNode<E>> tail= new AtomicReference<>(nullNode);

    public boolean put(E item){
    LinkedNode<E> newNode = new LinkedNode<>(item, null);
    while (true){
        LinkedNode<E> currentTail= tail.get();
        LinkedNode<E> tailNext= currentTail.next.get();
        if(currentTail == tail.get()){
            if (tailNext != null) {
                //有其他的线程已经插入了一个节点，但是还没有将tail指向最新的节点
                tail.compareAndSet(currentTail, tailNext);
            }else{
                //没有其他的线程插入节点，那么做两件事情：1. 插入新节点，2.将tail指向最新的节点
                if(currentTail.next.compareAndSet(null, newNode)){
                    tail.compareAndSet(currentTail, newNode);
                }
            }
        }
    }
    }
}

以上就是分析Java非阻塞算法Lock-Free的实现的详细内容，更多关于Java非阻塞算法Lock-Free的实现的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • 处理java异步事件的阻塞和非阻塞方法分析

    处理java异步事件的阻塞和非阻塞方法分析

    前言 由于多核系统普遍存在,并发性编程的应用无疑比以往任何时候都要广泛.但并发性很难正确实现,用户需要借助新工具来使用它.很多基于 JVM 的语言都属于这类开发工具,Scala 在这一领域尤为活跃.本系列文章将介绍一些针对 Java 和 Scala 语言的较新的并发性编程方法. 在任何并发性应用程序中,异步事件处理都至关重要.事件来源可能是不同的计算任务.I/O 操作或与外部系统的交互.无论来源是什么,应用程序代码都必须跟踪事件,协调为响应事件而采取的操作. Java 应用程序可采用两种基本的异

  • java 同步、异步、阻塞和非阻塞分析

    java 同步、异步、阻塞和非阻塞分析

    java 同步.异步.阻塞和非阻塞分析 概要: 正常情况下,我们的程序以同步非阻塞的方式在运行.但是我们的程序总会出现一些耗时操作,比如复杂的计算(找出1到10亿之间的素数)和程序本身无法控制的操作(IO操作.网络请求).包含这些耗时操作的方法我们可以把它称为阻塞方法,包含这些耗时操作的任务我们可以把它称为阻塞任务.阻塞与非阻塞是以是否耗时来定义的. 如果程序中存在大量阻塞操作,就会影响程序性能.但是阻塞的存在是客观事实,我们的程序是无法改变它的,一个网络请求需要3秒才能响应,我们不可能让它1毫

  • 浅谈Java非阻塞同步机制和CAS

    什么是非阻塞同步 非阻塞同步的意思是多个线程在竞争相同的数据时候不会发生阻塞,从而能够在更加细粒度的维度上进行协调,从而极大的减少线程调度的开销,从而提升效率.非阻塞算法不存在锁的机制也就不存在死锁的问题. 在基于锁的算法中,如果一个线程持有了锁,那么其他的线程将无法进行下去.使用锁虽然可以保证对资源的一致性访问,但是在挂起和恢复线程的执行过程中存在非常大的开销,如果锁上面存在着大量的竞争,那么有可能调度开销比实际工作开销还要高. 悲观锁和乐观锁 我们知道独占锁是一个悲观锁,悲观锁的意思就是假设

  • Java并发编程之原子变量与非阻塞同步机制

    1.非阻塞算法 非阻塞算法属于并发算法,它们可以安全地派生它们的线程,不通过锁定派生,而是通过低级的原子性的硬件原生形式 -- 例如比较和交换.非阻塞算法的设计与实现极为困难,但是它们能够提供更好的吞吐率,对生存问题(例如死锁和优先级反转)也能提供更好的防御.使用底层的原子化机器指令取代锁,比如比较并交换(CAS,compare-and-swap). 2.悲观技术 独占锁是一种悲观的技术.它假设最坏的情况发生(如果不加锁,其它线程会破坏对象状态),即使没有发生最坏的情况,仍然用锁保护对象状态.

  • Java非阻塞I/O模型之NIO相关知识总结

    组件说明 (1)Channel:NIO模型中的管道,管道是链接建立和通信的重要组件,我们可以理解管道是一个容器环境,我们所有的I/O的建立读取都可以在这个容器中进行 (2)Selector:NIO中的选择器,NIO是由事件驱动的,当有链接事件或者读取事件发生时,这个事件可以注册到这个选择器上,并且最终被我们检测到. (3)SelectionKey:我们可以在Selector中进行检测是否有SelectionKey产生,并且根据这个SelectionKey中的信息判断时什么事件发生了. 代码说明

  • java并发之原子操作类和非阻塞算法

    背景 近年来,在并发算法领域的大多数研究都侧重于非阻塞算法,这种算法用底层的原子机器指令(例如比较并发交换指令)代替锁来确保数据在并发访问中的一致性.非阻塞算法被广泛的用于在操作系统和JVM中实现线程/进程调度机制.垃圾回收机制以及锁和其他并发数据结构. 与基于锁的方案相比,非阻塞算法在设计和实现上都要复杂的多,但他们在可伸缩性和活跃性上却拥有巨大的优势,由于非阻塞算法可以使多个线程在竞争相同数据时不会发生阻塞,因此它能在粒度更细的层次上面进行协调,并且极大的减少调度开销.锁虽然Java语言锁定

  • 简述JAVA同步、异步、阻塞和非阻塞之间的区别

    同步和异步,阻塞和非阻塞是大家经常会听到的概念,但是它们是从不同维度来描述一件事情,常常很容易混为一谈. 1. 同步和异步 同步和异步描述的是消息通信的机制. 同步 当一个request发送出去以后,会得到一个response,这整个过程就是一个同步调用的过程.哪怕response为空,或者response的返回特别快,但是针对这一次请求而言就是一个同步的调用. 异步 当一个request发送出去以后,没有得到想要的response,而是通过后面的callback.状态或者通知的方式获得结果.可

  • java 中同步、异步、阻塞和非阻塞区别详解

    java 中同步.异步.阻塞和非阻塞区别详解 简单点说: 阻塞就是干不完不准回来,一直处于等待中,直到事情处理完成才返回: 非阻塞就是你先干,我先看看有其他事没有,一发现事情被卡住,马上报告领导. 我们拿最常用的send和recv两个函数来说吧... 比如你调用send函数发送一定的Byte,在系统内部send做的工作其实只是把数据传输(Copy)到TCP/IP协议栈的输出缓冲区,它执行成功并不代表数据已经成功的发送出去了,如果TCP/IP协议栈没有足够的可用缓冲区来保存你Copy过来的数据的话

  • Java 非阻塞I/O使用方法

    绝大部分知识与实例来自O'REILLY的<Java网络编程>(Java Network Programming,Fourth Edition,by Elliotte Rusty Harold(O'REILLY)). 非阻塞I/O简介 非阻塞I/O(NIO)是处理高并发的一种手段.在高并发的情况下,创建和回收线程以及在线程间切换的开销变得不容忽视,此时就可以使用非阻塞I/O技术.这种技术的核心思想是每次选取一个准备好的连接,尽快地填充这个连接所能管理的尽可能多的数据,然后转向下一个准备好的连接.

  • 分析Java非阻塞算法Lock-Free的实现

    非阻塞的栈 我们先使用CAS来构建几个非阻塞的栈.栈是最简单的链式结构,其本质是一个链表,而链表的根节点就是栈顶. 我们先构建Node数据结构: public class Node<E> { public final E item; public Node<E> next; public Node(E item){ this.item=item; } } 这个Node保存了内存item和它的下一个节点next. 然后我们构建非阻塞的栈,在该栈中我们需要实现pop和push方法,我们

  • 详细分析JAVA加解密算法

    加解密算法分析 日常开发中,无论你是使用什么语言,都应该遇到过使用加解密的使用场景,比如接口数据需要加密传给前端保证数据传输的安全:HTTPS使用证书的方式首先进行非对称加密,将客户端的私匙传递给服务端,然后双方后面的通信都使用该私匙进行对称加密传输:使用MD5进行文件一致性校验,等等很多的场景都使用到了加解密技术. 很多时候我们对于什么时候要使用什么样的加解密方式是很懵的.因为可用的加解密方案实在是太多,大家对加解密技术的类型可能不是很清楚,今天这篇文章就来梳理一下目前主流的加解密技术,本篇文

  • 浅谈Java并发编程之Lock锁和条件变量

    简单使用Lock锁 Java 5中引入了新的锁机制--java.util.concurrent.locks中的显式的互斥锁:Lock接口,它提供了比synchronized更加广泛的锁定操作.Lock接口有3个实现它的类:ReentrantLock.ReetrantReadWriteLock.ReadLock和ReetrantReadWriteLock.WriteLock,即重入锁.读锁和写锁.lock必须被显式地创建.锁定和释放,为了可以使用更多的功能,一般用ReentrantLock为其实例

随机推荐