Java CAS

SpinLock
a spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available. Since the thread remains active but is not performing a useful task, the use of such a lock is a kind of busy waiting. Once acquired, spinlocks will usually be held until they are explicitly released, although in some implementations they may be automatically released if the thread being waited on (that which holds the lock) blocks, or "goes to sleep".
http://stackoverflow.com/questions/195853/spinlock-versus-semaphore

https://dzone.com/articles/how-cas-compare-and-swap-java

AtomicInteger, AtomicLong etc. makes use of CAS. CAS does not make use of locking rather it is very optimistic in nature. It follows these steps:

• Compare the value of the primitive to the value we have got in hand.
• If the values do not match it means some thread in between has changed the value. Else it will go ahead and swap the value with new value.

public final long incrementAndGet() {
    for (;;) {
        long current = get();
        long next = current + 1;
        if (compareAndSet(current, next))
          return next;
    }
}

In JDK 8 the above code has been changed to a single intrinsic:

public final long incrementAndGet() {
        return unsafe.getAndAddLong(this, valueOffset, 1L) + 1L;
}

What advantage this single intrinsic have?
Actually this single line is JVM intrinsic which is translated by JIT into an optimized instruction sequence. In case of x86 architecture it is just a single CPU instruction LOCK XADD which might yield better performance than classic load CAS loop.

LongAdder is not always a replacement for AtomicLong. We need to consider the following aspects:

• When no contention is present AtomicLong performs better.
• LongAdder will allocate Cells (a final class declared in abstract class Striped64) to avoid contention which consumes memory. So in case we have a tight memory budget we should prefer AtomicLong.

Java之CAS的应用(一)

Java1.5引入的CAS（Compare and Swap）指令需要cpu底层的支持，其实在不支持CAS指令的cpu平台上，JVM对该指令通过其他方式做了兼容。可以说CAS是Java Concurrent包的基石。关于CAS指令的语义以及更详细的介绍请自行查看

本文主要记录一下CAS指令的两个应用：自旋锁、非阻塞的栈和非阻塞的链表

SpinLock

public class SpinLock {

    AtomicReference<Thread> sign = new AtomicReference<>();

     

    public void lock(){

        Thread current = Thread.currentThread();

        while(!sign.compareAndSet(null, current));

    }

     

    public void unlock(){

        Thread current = Thread.currentThread();

        while(!sign.compareAndSet(current, null));

    }

}

非阻塞的栈
https://courses.cs.washington.edu/courses/cse451/08wi/ConcurrentStack.java
http://fm.csl.sri.com/SSFT13/ConcurrentStack.java
https://mishrabagish.wordpress.com/2014/03/03/implementing-concurrent-stack-using-atomicreference/
https://github.com/xieqilu/Qilu-leetcode/blob/master/PureStorage/ConcurrentStack.cs

public class ConcurrentStack<T> {

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

     

    public void push(T item){

        Node<T> newHead = new Node<T>(item);

        Node<T> oldHead ;

        do{

            oldHead = top.get();

            newHead.next = oldHead;

        } while(!top.compareAndSet(oldHead, newHead));

    }

     

    public T pop(){

        Node<T> oldHead;

        Node<T> newHead;

         

        do{

            oldHead = top.get();

            if(oldHead == null)

                return null;

            newHead = oldHead.next;

        }while(!top.compareAndSet(oldHead, newHead));

        return oldHead.item;

    }

     

    private static class Node <T>{

        public final T item;

        public Node<T> next;

        public Node(T item) {

            super();

            this.item = item;

        }

    }

}

这几个应用都比较简单，而且他们的实现完全依赖cas指令。其中ConcurrentLinkQueue用到了线程协作推进的trick。
无阻塞的链表（队列）

public class ConcurrentLinkQueue<T> {

    private static class Node<T> {

        final T item;

        final AtomicReference<Node<T>> next ;

        public Node(T item, AtomicReference<Node<T>> next) {

            super();

            this.item = item;

            this.next = next;

        }

    }

     

    private final Node<T> dummy = new Node<T>(null,null);

    private final AtomicReference<Node<T>> head = new AtomicReference<Node<T>>(dummy);

    private final AtomicReference<Node<T>> tail = new AtomicReference<Node<T>>(dummy);

    public boolean put(T item){

        Node<T> newNode = new Node<T>(item, null);

         

        while(true){

            Node<T> curTail = tail.get();

            Node<T> curNext = curTail.next.get();

            if(curTail == tail.get()){

                if(curNext != null){

                    tail.compareAndSet(curTail, curNext);

                }else{

                    if(curTail.next.compareAndSet(null, newNode)){

                        tail.compareAndSet(curTail, curNext);

                        return true;

                    }

                }

            }

        }

    }

     

    public T get(){

        Node<T> oldHead;

        Node<T> newHead;

        do{

            oldHead = head.get();

            if(oldHead.item == null)

                return null;

            newHead = oldHead.next.get();

        }while(!head.compareAndSet(oldHead, newHead));

        return oldHead.item;

    }

     

    public T peek(){

        return head.get().item;

    }

}

CAS (Compare-and-Swap) 以及相关问题

CAS (Compare-and-Swap) 是一种硬件上, 实现非锁同步的一种方法. 这种方法比传统的blocked方法在硬件上实现, 效率高而且内存命中率高.

CAS实现的是一种先验的赋值方法, 即: 给出一个当前值v, 当想改变这个当前值的时候, 一个线程需要进行先验操作, 以当前线程为观察者, 查看改变对象是否是当前线程中期待的对象的值. 如果是才去改变它.  整个行为并非通过锁住线程实现的, 而在硬件上, 访问一个内存片段上的速度远远快于在更高层锁住当前线程的速度. 所以CAS被认为是比所要快速的实现原子化操作的方法之一.CAS 和 CAS2 被用在了Java自带的AtomicInteger, AtomicBoolean, AtomicReference上. 这些变量都是可以常常用作判断线程进行状态的flag. 传统的关键字volatile只保证了变量的visibility, 却缺乏了accessibility. 而使用Java自带的原子变量, 可以更有效的, 快速的解决并发的实际问题.

一个CAS的赋值操作, 由一个pair组成: (expectedCurrentValue, newValue). 当赋值实现了CAS的变量一个新值的时候, 先验当前值是否等于expectedCurrentValue, 如果等于, 则赋newValue, 否则返回CAS变量的值, 这样, 通过比较返回的值, 就可以知道是否赋值成功.

通过以上的CAS, 延伸出了ConcurrentStack (Treiber, 1986), Non-blocking Queue (Michael and Scoot, 1996) 等non-blocking的数据结构. 这些数据结构因为更贴近硬件操作并且是线程安全的, 所以在新的JVM中, 很多Concurrent的数据结构都使用了这种CAS的思想.

但是设计一个CAS的数据结构, 需要充分理解数据结构在并发下的state机制, 设置一个或者两个CAS的flag解决对个state之间转换, 来增加运行速度, 当CAS的变量过多, 并发下, 其实与blocked的数据结构比并没有太大优势