分析Java非阻塞算法Lock

分析Java非阻塞算法Lock

非阻塞的栈

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

我们先构建Node数据结构：

public class Node {

public final E item;

public Node next;

public Node(E item){

this.item=item;

}

}

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

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

public class ConcurrentStack {

AtomicReference> top= new AtomicReference<>();

public void push(E item){

Node newNode= new Node<>(item);

Node oldNode;

do{

oldNode=top.get();

newNode.next= oldNode;

}while(!top.compareAndSet(oldNode, newNode));

}

public E pop(){

Node oldNode;

Node newNode;

do {

oldNode = top.get();

if(oldNode == null){

return null;

}

newNode=oldNode.next;

}while(!top.compareAndSet(oldNode, newNode));

return oldNode.item;

}

}

非阻塞的链表

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

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

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

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

public class LinkedNode {

public final E item;

public final AtomicReference> next;

public LinkedNode(E item, LinkedNode next){

this.item=item;

this.next=new AtomicReference<>(next);

}

}

先构建一个LinkedNode类。

public class LinkedQueue {

private final LinkedNode nullNode= new LinkedNode<>(null, null);

private final AtomicReference> head=QJqtL new AtomicReference<>(nullNode);

private final AtomicReference> tail= new AtomicReference<>(nullNode);

public boolean put(E item){

LinkedNode newNode = new LinkedNode<>(item, null);

while (true){

LinkedNode currentTail= tail.get();

LinkedNode 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的实现的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。