java并发编程(8)原子变量和非阻塞的同步机制
原子变量和非阻塞的同步机制
一、锁的劣势
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方法
JAVA7/8:对Map的操作:putIfAbsent、computerIfAbsent、computerIfPresent.........
三、原子变量类
AtomicRefence原子更新对象,可以是自定义的对象;如:
public class CasNumberRange {private static class IntPair {// INVARIANT: lower <= upperfinal int lower; //将值定义为不可变域final int upper; //将值定义为不可变域public IntPair(int lower, int upper) {this.lower = lower;this.upper = upper; } }private final AtomicReference<IntPair> 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 < oldv.lower)throw new IllegalArgumentException("Can't set upper to " + i + " < lower"); IntPair newv = new IntPair(oldv.lower, i);if (values.compareAndSet(oldv, newv))return; } } }
性能问题:使用原子变量在中低并发(竞争)下,比使用锁速度要快,一般情况下是比锁速度快的
四、非阻塞算法
许多常见的数据结构中都可以使用非阻塞算法
非阻塞算法:在多线程中,工作是否成功有不确定性,需要循环执行,并通过CAS进行原子操作
1、上面的CasNumberRange
2、栈的非阻塞算法:只保存头部指针,只有一个状态
//栈实现的非阻塞算法:单向链表public class ConcurrentStack <E> { AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();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; } } }
3、链表的非阻塞算法:头部和尾部的快速访问,保存两个状态,更加复杂
public class LinkedQueue <E> {private static class Node <E> {final E item;final AtomicReference<LinkedQueue.Node<E>> next;public Node(E item, LinkedQueue.Node<E> next) {this.item = item;this.next = new AtomicReference<LinkedQueue.Node<E>>(next); } }private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);private final AtomicReference<LinkedQueue.Node<E>> head = new AtomicReference<LinkedQueue.Node<E>>(dummy);private final AtomicReference<LinkedQueue.Node<E>> tail = new AtomicReference<LinkedQueue.Node<E>>(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; } } } } } }
3.原子域更新器
上面的逻辑,实现了链表的非阻塞算法,使用Node来保存头结点和尾节点
在实际的ConcurrentLinkedQueue中使用的是基于反射的AtomicReferenceFiledUpdater来包装Node
五、ABA问题
CAS操作中容易出现的问题:
判断值是否为A,是的话就继续更新操作换为B;
但是如果一个线程将值A改为C,然后又改回A,此时,原线程将判断A=A成功执行更新操作;
如果把A改为C,然后又改回A的操作,也需要视为变化,则需要对算法进行优化
解决:添加版本号,每次更新操作都要更新版本号,即使值是一样的
以上就是java并发编程(8)原子变量和非阻塞的同步机制的详细内容,更多请关注其它相关文章!