奇技淫巧——不加锁的并发从/入栈操作

在多线程的情况下，如果有入栈操作，如何保证线程安全呢？可能我们会想到加锁，用一个synchronized来保证线程安全，但是这种方式效率低下，所以我们隆重介绍一种方式在不加锁的情况下进行入栈操作：

public class _DirectoryTest {
    private volatile NodeWaiter waiters;

    static final class NodeWaiter{
        volatile int value;
        volatile NodeWaiter next;
    }

    public void push(){
        boolean queued =false;
        NodeWaiter q =null;
        for(;;){
            if(q ==null){
                q =new NodeWaiter();
            }else if(!queued){
                /*
                使用Unsafe的方法，原子的修改链表的头节点，如果修改成功说明已经入栈，否则重新再来。
                */
                queued =UNSAFE.compareAndSwapObject(this,waitersOffset, q.next =waiters, q);
            else if(queued){
                break;
            }
        }
    }
}

其中这个UNSAFE是这样来的：

private static final sun.misc.Unsafe UNSAFE;
private static final long waitersOffset;
static{
    try {
        Constructor con = Unsafe.class.getDeclaredConstructor();
        con.setAccessible(true);
        UNSAFE = con.newInstance(null);
        Class k = _DirectoryTest.class;
        waitersOffset =UNSAFE.objectFieldOffset(k.getDeclaredField("waiters"));
    }catch (Exception e) {
        throw new Error(e);
    }
}

用到了Unsafe，所以能够较好的保证并发安全性和效率。除此之外，我们还提供一个出栈的操作，同样不加锁：

  public NodeWaiter pop(){
        if(waiters != null){
            for(;;){
                NodeWaiter q=waiters;
                if(q == null){
                    return null;
                }
                NodeWaiter s = q.next;
                if(UNSAFE.compareAndSwapObject(this,waitersOffset,q,s)){
                    q.next=null;
                    return q;
                }
            }
        }
        return null;
    }
  public void push(){
        boolean queued = false;
        NodeWaiter q = null;

        for(;;){
            if(q == null){
                q = new NodeWaiter(1);
            }else if(!queued){
                queued = UNSAFE.compareAndSwapObject(this, waitersOffset, q.next = waiters, q);
            }else if(queued){
                break;
            }
        }
    }

我们还提供一个特别棒的方法，用来在链表里remove掉指定的节点，也是不加锁且线程安全的：

    public void remove(NodeWaiter node){
        if(node.linked != false){
            node.linked = false;
            retry:
            for(;;){
                for(NodeWaiter pred = null, q=waiters,s; q!=null; q=s){
                    s = q.next;
                    if(q.linked != false){pred = q;} //不是这个节点，就往下走
                    else if(pred != null){//是这个节点，而且不是头节点
                        pred.next = s;//直接把q的引用拿走了，等待gc去回收q
                        /*
                        精髓所在，在并发的时候检测的冲突，如果遇到前驱阶段被删除掉，就重新再remove一遍，for(;;)就是干这个用的。
                        当然，如果是后续节点被并发的删除掉，那就相当于那个线程的前驱节点被删除了，那就让那个线程去处理吧
                        */
                        if(pred.linked == false){continue retry;}
                    }
                    else if(!UNSAFE.compareAndSwapObject(this,waitersOffset,q,s)){continue retry;}//如果是头节点要删除，就用UNSAFE做，如果失败了，就从链表头再来
                }
                break;
            }
        }
    }