非阻塞同步机制

1、JAVA并发编程实践中提供了 3中非阻塞算法的示例。第一个示例，非阻塞计数器。CAS比较并交换即Compare-And-Swap。假设CAS有3个操作数-内存位置V、旧的预测值A和新值B,那么它的典型模式为：首先从 V中读取值A,由A生成新值B,然后使用CAS 原子化地把V的值改成B,并且期间不能有其他线程改变V的值，因为CAS能够发现来自其他线程的干扰。view plaincopy to clipboardprint?01.代码1使用CAS实现的非阻塞计数器02.ThreadSafe03.public class CasCounter 04.private SimulatedCAS valu

2、e;05.publicintgetValue() 06.return value.get(); TOC o 1-5 h z 07.08. v;do v = value.get(); 1while(v !=pareAndSwap(v, v + 1);2return v +1;代码2模才C CAS操作ThreadSafepublic class SimulatedCAS GuardedBy(this) private int value;public synchronized int get() return value; public synch

3、ronized 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);代码1使用CAS实现的非阻塞计数器Thre

4、adSafe public class CasCounter private SimulatedCAS value; public int getValue() return value.get(); public int increment() int v; do v = value.get(); 1 while (v != pareAndSwap(v, v + 1);2return v + 1; 代码2模CAS操作 ThreadSafe public class SimulatedCAS GuardedBy(this) private int value;public synchroniz

5、ed int get() return value; 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(exp

6、ectedValue, newValue); 假设有两个线程，同时执行到 1 ,获得了 value的旧值；然后同时执行到2 ,根据原则当多个线程试图使用CAS同时更新相同的变量时，其中一个会胜出，并更新变量的值，而其他线程都会失败，重新尝试。”可知，其中一个线程完成了加1操作，而另一个线程失败，重新do循环。让我们细细体会一下这个原则是怎么得到的：一个线程完成了加1操作后，另一个线程使用 CAS时，旧的预期值没有变但内存位置V的值已经更新了，所以此时V的值不等于旧的预期值而导致失败！ 第二个示例，非阻塞栈view plaincopy to clipboardprint?01.代码3使用Trei

7、ber算法的非阻塞栈02.ThreadSafe03.public class ConcurrentStack 04.05.06.07.08.09.代码3AtomicReferenceNode top = new AtomicReferenceNode(); public void push(E item) Node newHead = new Node(item);Node oldHead;do oldHead = top.get();newHead.next = oldHead; 1 while (!pareAndSet(oldHead, newHead); 2public E pop()

8、Node oldHead;Node newHead;do oldHead = top.get();if (oldHead = null)return null;newHead = oldHead.next; while (!pareAndSet(oldHead, newHead);return oldHead.item;private static class Node public final E item;public Node next;public Node(E item) this.item = item;使用Treiber算法的非阻塞栈ThreadSafepublic class

9、ConcurrentStack AtomicReferenceNode top = new AtomicReferenceNode(); public void push(E item) Node newHead = new Node(item);Node oldHead;do oldHead = top.get();newHead.next = oldHead;1 while (!pareAndSet(oldHead, newHead); 2 public E pop() Node oldHead;Node newHead;do oldHead = top.get(); if (oldHea

10、d = null) return null; newHead = oldHead.next; while (!pareAndSet(oldHead, newHead); return oldHead.item;private static class Node public final E item;public Node next; public Node(E item) this.item = item; 注： AtomicReferencecompareAndSet ( V expect, V update)若当前值与期望值 expect相等时，原子化地将update值赋给当前值。假设有

11、两个线程，同时执行到1，获得了栈顶元素，并创建了一个新节点指向当前栈顶； 然后同时执行到2 ,根据原则”当多个线程试图使用CAS同时更新相同的变量时，其中一个会胜出，并更新变量的值，而其他线程都会失败，重新尝试。”可知，其中一个线程完成了插入操作，而另一个线程失败，重新 do循环。让我们细细体会一下这个原则是怎么得 到的：一个线程完成了插入操作后，另一个线程使用CAS时，旧的预期值没有变但当前栈顶的值已经更新了，所以此时栈顶的值不等于旧的预期值而导致失败！ 第三个示例，非阻塞链表view plaincopy to clipboardprint?01.代码4 Michael-Scott非阻塞队列

12、算法中的插入02.ThreadSafe03.public class LinkedQueue 04. private static class Node 05.final E item;06.final AtomicReferenceNode next;07.public Node(E item, Node next) 08.this.item = item;09.this.next = new AtomicReferenceNode(next);private final Node dummy = new Node(null, null);private final AtomicRefere

13、nceNode head= new AtomicReferenceNode(dummy);private final AtomicReferenceNode tail= new AtomicReferenceNode(dummy);public boolean put(E item) Node newNode = new Node(item, null);while (true) Node curTail = tail.get();Node tailNext = curTail.next.get();if (curTail = tail.get() ?if (tailNext != null)

14、 A/ Queue in intermediate state, advance tailpareAndSet(curTail, tailNext); B else /In quiescent state, try inserting new nodeif (curTpareAndSet(null, newNode) C/ Insertion succeeded, try advancing tail TOC o 1-5 h z pareAndSet(curTail, newNode);Dreturn true;代码4 Michael-Scott非阻塞队列算法中的插入ThreadSafepub

15、lic class LinkedQueue private static class Node final E item;final AtomicReferenceNode next;public Node(E item, Node next) this.item = item;this.next = new AtomicReferenceNode(next);private final Node dummy = new Node(null, null);private final AtomicReferenceNode head=new AtomicReferenceNode(dummy);

16、private final AtomicReferenceNode tail=new AtomicReferenceNode(dummy);public boolean put(E item) Node newNode = new Node(item, null);while (true) Node curTail = tail.get();Node tailNext = curTail.next.get();if (curTail = tail.get() ?if (tailNext != null) A/ Queue in intermediate state, advance tail

17、pareAndSet(curTail, tailNext); B else / In quiescent state, try inserting new nodeif (curTpareAndSet(null, newNode) C/ Insertion succeeded, try advancing tail pareAndSet(curTail, newNode); D return true;首先看？处，为什么要判断 curTail = tail.get()呢？必须要有这个判断来保证数据结构总能处于一致状态。如果没有这个判断的话可能出现下面状况。细细思索一下，如果没有 curTail

18、 = tail.get（）这个的话，一个线程将元素3加入队列，而另一个线程却把next指针的指向了 3,元素3就这样被丢弃了，这当然是不行的！也就是我们 下文所说的第一个诀窍。插入新的元素涉及到两个指针的更新（两个指针分别为队尾指针和队尾元素的next指针），需要两个操作过程。第一，更新当前队尾元素的 next指针，将新元素插入到列表队尾；第 二，释放队尾指针，指向新的最末元素。在这两个操作之间，队列处于中间状态，看图示。图a插入前稳定状态图b插入期间，队列处于中间状态图c插入完成后，队列再一次回到稳定状态有几个诀窍来完成我们的链表。第一个诀窍是即使在多步更新中，也要确保数据结构总能处 于一致状态。也就是说，如果线程B到达时发现线程 A正在更新中，B能够知晓操作已经部 分完成并且知道不能立即开始自己的更新。那么B就开始等待（通过反复检查队列状态）直到A完成更