原子變數與非阻塞的同步機制

一、鎖的劣勢

　　1.在多執行緒下：鎖的掛起和復原等過程存在著很大的開銷（及時現代的jvm會判斷何時使用掛起，何時自旋等待）

　　2.volatile：輕量級級別的同步機制，但是不能用於構建原子複合操作

　　因此：需要有一種方式，在管理執行緒之間的競爭時有一種粒度更細的方式，類似與volatile的機制，同時也要支援原子更新操作

二、CAS

#獨佔鎖是一種悲觀的技術--它假設最壞的情況，所以每個線程是獨佔的

　　而CAS比較並交換：compareAndSwap/Set(A,B):我們認為內存處值是A，如果是A，將其修改為B，否則不進行操作；傳回記憶體處的原始值或是否修改成功

　　如：模擬CAS運算

//模拟的CASpublic class SimulatedCAS {private int value;public synchronized int get() {return value;
    }//CAS操作public synchronized int compareAndSwap(int expectedValue, int newValue) {int oldValue = value;if (oldValue == expectedValue) {
            value = newValue;
        }return oldValue;
    }public synchronized boolean compareAndSet(int expectedValue, int newValue) {return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}//典型使用场景public class CasCounter {private SimulatedCAS value;public int getValue() {return value.get();
    }public int increment() {int v;do {
            v = value.get();
        } while {
            (v != value.compareAndSwap(v, v + 1));
        }return v + 1;
    }
}

　　JAVA提供了CAS的操作

　　　　原子狀態類別：AtomicXXX的CAS方法

#　　　　　　原子狀態類別：AtomicXXX的CAS方法

#　　　　JAVA7/8：對Map的操作：

　　　　JAVA7/8：對Map的操作：putIfAbs、computerIf.Pcomputerf. ....

三、原子變數類別

　　AtomicRefence原子更新對象，可以是自訂的對象；如：

public class CasNumberRange {private static class IntPair {// INVARIANT: lower  values = new AtomicReference<intpair>(new IntPair(0, 0));    //封装对象public int getLower() {return values.get().lower;
    }public int getUpper() {return values.get().upper;
    }public void setLower(int i) {while (true) {
            IntPair oldv = values.get();if (i > oldv.upper) {throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            }
            IntPair newv = new IntPair(i, oldv.upper);  //属性为不可变域，则每次更新新建对象if (values.compareAndSet(oldv, newv)) {     //原子更新，如果在过程中有线程修改了，则其他线程不会更新成功，因为oldv与内存处值就不同了return;
            }
        }
    }//同上public void setUpper(int i) {while (true) {
            IntPair oldv = values.get();if (i <p></p> <p></p>　　效能問題：使用原子變數在中低並發（競爭）下，比使用鎖定速度快，一般情況下是比鎖定速度快的<h3></h3> <p></p>#四、非阻塞演算法<p></p>　　許多常見的資料結構中都可以使用非阻塞演算法<p></p>　　非阻塞演算法：在多執行緒中，工作是否成功有不確定性，需要循環執行，並且透過CAS進行原子運算<p></p>　　1、上面的CasNumberRange<div class="cnblogs_code"></div>　　2、堆疊的非阻塞演算法：只儲存頭部指針，只有一個狀態<p></p>
<pre class="brush:php;toolbar:false">//栈实现的非阻塞算法：单向链表public class ConcurrentStack <e> {
    AtomicReference<node>> top = new AtomicReference<node>>();public void push(E item) {
        Node<e> newHead = new Node<e>(item);
        Node<e> oldHead;do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞    }public E pop() {
        Node<e> oldHead;
        Node<e> newHead;do {
            oldHead = top.get();if (oldHead == null) {return null;
            }
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞return oldHead.item;
    }private static class Node <e> {public final E item;public Node<e> next;public Node(E item) {this.item = item;
        }
    }
}</e></e></e></e></e></e></e></node></node></e>

　　3、鍊錶的非阻塞演算法：頭部和尾部的快速訪問，保存兩個狀態，更加複雜

public class LinkedQueue <e> {private static class Node <e> {final E item;final AtomicReference<linkedqueue.node>> next;public Node(E item, LinkedQueue.Node<e> next) {this.item = item;this.next = new AtomicReference<linkedqueue.node>>(next);
        }
    }private final LinkedQueue.Node<e> dummy = new LinkedQueue.Node<e>(null, null);private final AtomicReference<linkedqueue.node>> head = new AtomicReference<linkedqueue.node>>(dummy);private final AtomicReference<linkedqueue.node>> tail = new AtomicReference<linkedqueue.node>>(dummy);  //保存尾节点public boolean put(E item) {
        LinkedQueue.Node<e> newNode = new LinkedQueue.Node<e>(item, null);while (true) {
            LinkedQueue.Node<e> curTail = tail.get();
            LinkedQueue.Node<e> tailNext = curTail.next.get();if (curTail == tail.get()) {if (tailNext != null) {// 处于中间状态，更新尾节点为当前尾节点的next                    tail.compareAndSet(curTail, tailNext);
                } else {// 将当前尾节点的next 设置为新节点：链表if (curTail.next.compareAndSet(null, newNode)) {/** * 此处即为中间状态，虽然在这里进行了两次原子操作，整体不是原子的，但是通过算法保证了安全：
                         * 原因是处于中间状态时，如果有其他线程进来操作，则上面那个if将执行；
                         * 上面if的操作是来帮助当前线程完成更新尾节点操作，而当前线程的更新就会失败返回，最终则是更新成功                         */// 链接成功，尾节点已经改变，则将当前尾节点，设置为新节点                        tail.compareAndSet(curTail, newNode);return true;
                    }
                }
            }
        }
    }
}</e></e></e></e></linkedqueue.node></linkedqueue.node></linkedqueue.node></linkedqueue.node></e></e></linkedqueue.node></e></linkedqueue.node></e></e>

　　3.原子域更新器

　　　　上面的邏輯，實作了鍊錶的非阻塞演算法，使用Node來保存頭結點和尾節點　　　　在實際的ConcurrentLinkedQueue#　　　　在實際的ConcurrentLinkedQueue中使用的是基於反射的

AtomicReferenceFiledUpdater