《非阻塞同步机制》由会员分享，可在线阅读，更多相关《非阻塞同步机制（7页珍藏版）》请在金锄头文库上搜索。
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.ThreadSafe 03.public class
2、CasCounter 04. private SimulatedCAS value; 05. public int getValue() 06. return value.get(); 07. 08. public int increment() 09. int v; 10. do 11. v = value.get(); 1 12. 13. while (v != pareAndSwap(v, v + 1); 2 14. return v + 1; 15. 16. 17.代码 2 模拟 CAS 操作 18.ThreadSafe 19.public class SimulatedCAS 20.
3、 GuardedBy(“this“) private int value; 21. public synchronized int get() return value; 22. public synchronized int compareAndSwap(int expectedValue, 23. int newValue) 24. int oldValue = value; 25. if (oldValue = expectedValue) 26. value = newValue; 27. return oldValue; 28. 29. public synchronized boo
4、lean compareAndSet(int expectedValue, 30. int newValue) 31. return (expectedValue 32. = compareAndSwap(expectedValue, newValue); 33. 34. 代码 1 使用 CAS 实现的非阻塞计数器 ThreadSafe public class CasCounter private SimulatedCAS value; public int getValue() return value.get(); public int increment() int v; do v =
5、 value.get(); 1 while (v != pareAndSwap(v, v + 1); 2 return v + 1; 代码 2 模拟 CAS 操作 ThreadSafe public class SimulatedCAS GuardedBy(“this“) private int value; public synchronized int get() return value; public synchronized int compareAndSwap(int expectedValue, int newValue) int oldValue = value; if (ol
6、dValue = expectedValue) value = newValue; return oldValue; public synchronized boolean compareAndSet(int expectedValue, int newValue) return (expectedValue = compareAndSwap(expectedValue, newValue); 假设有两个线程，同时执行到 1 ，获得了 value 的旧值 ；然后同时执行到 2 ， 根据 原则“ 当多个线程试图使用 CAS 同时更新相同的变量时，其中一个会胜出，并更新变量 的值，而其他线程都会失
7、败，重新尝试。 ”可知，其中一个线程完成了加 1 操作，而另一 个线程失败，重新 do 循环。让我们细细体会一下这个原则是怎么得到的： 一个线程完成 了加 1 操作后，另一个线程使用 CAS 时，旧的预期值没有变但内存位置 V 的值已经更新 了，所以此时 V 的值不等于旧的预期值而导致失败！ 第二个示例，非阻塞栈 view plaincopy to clipboardprint? 01.代码 3 使用 Treiber 算法的非阻塞栈 02.ThreadSafe 03.public class ConcurrentStack 04. AtomicReference top = new Atomi
8、cReference(); 05. public void push(E item) 06. Node newHead = new Node(item); 07. Node oldHead; 08. do 09. oldHead = top.get(); 10. newHead.next = oldHead; 1 11. while (!pareAndSet(oldHead, newHead); 2 12. 13. public E pop() 14. Node oldHead; 15. Node newHead; 16. do 17. oldHead = top.get(); 18. if
9、(oldHead = null) 19. return null; 20. newHead = oldHead.next; 21. while (!pareAndSet(oldHead, newHead); 22. return oldHead.item; 23. 24. private static class Node 25. public final E item; 26. public Node next; 27. public Node(E item) 28. this.item = item; 29. 30. 31. 代码 3 使用 Treiber 算法的非阻塞栈 ThreadSa
10、fe public class ConcurrentStack AtomicReference top = new AtomicReference(); 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()
11、; 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; 注： AtomicReference compareAndSet ( V expect, V update) 若当前值与期望值 expect 相等时，原子化地
12、将 update 值赋给当前值。 假设有两个线程，同时执行到 1 ，获得了 栈顶元素，并创建了一个新节点指向当前栈 顶；然后同时执行到 2 ， 根据原则“ 当多个线程试图使用 CAS 同时更新相同的变量 时，其中一个会胜出，并更新变量的值，而其他线程都会失败，重新尝试。 ”可知，其中 一个线程完成了插入操作，而另一个线程失败，重新 do 循环。让我们细细体会一下这个原 则是怎么得到的：一个线程完成了插入操作后，另一个线程使用 CAS 时，旧的预期值没有 变但当前栈顶的值已经更新了，所以此时栈顶的值不等于旧的预期值而导致失败！ 第 三 个示例，非阻塞 链表 view plaincopy to c
13、lipboardprint? 01.代码 4 Michael-Scott 非阻塞队列算法中的插入 02.ThreadSafe 03.public class LinkedQueue 04. private static class Node 05. final E item; 06. final AtomicReference next; 07. public Node(E item, Node next) 08. this.item = item; 09. this.next = new AtomicReference(next); 10. 11. 12. private final Node dummy = new Node(null, null); 13. private final AtomicReference head 14. = new AtomicReference(dummy); 15. private final AtomicReference tail 16. = new AtomicReference(dummy); 17
