3 原子变量类
J.U.C的AtomicXXX。
例如一个AtomictReference的使用如下:
public class CasNumberRange { @Immutable private static class IntPair { // INVARIANT: lower <= upper final 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)) 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; } } }
4 非阻塞算法
Lock-free算法,可以实现栈、队列、优先队列或者散列表。
4.1 非阻塞的栈
Trebier算法,1986年提出。
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)); } 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)); return oldHead.item; } private static class Node <E> { public final E item; public Node<E> next; public Node(E item) { this.item = item; } } }
4.2 非阻塞的链表
J.U.C的ConcurrentLinkedQueue也是参考这个由Michael and Scott,1996年实现的算法。
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) { // Queue in intermediate state, advance tail tail.compareAndSet(curTail, tailNext); } else { // In quiescent state, try inserting new node if (curTail.next.compareAndSet(null, newNode)) { // Insertion succeeded, try advancing tail tail.compareAndSet(curTail, newNode); return true; } } } } } }
4.3 原子域更新
AtomicReferenceFieldUpdater,一个基于反射的工具类,能对指定类的指定的volatile引用字段进行原子更新。(该字段不能是private的)
通过调用AtomicReferenceFieldUpdater的静态方法newUpdater就能创建它的实例,该方法要接收三个参数:
- 包含该字段的对象的类
- 将被更新的对象的类
- 将被更新的字段的名称
AtomicReferenceFieldUpdater updater=AtomicReferenceFieldUpdater.newUpdater(Dog.class,String.class,"name"); Dog dog1=new Dog(); updater.compareAndSet(dog1,dog1.name,"test") ; System.out.println(dog1.name); class Dog { volatile String name="dog1"; }