一、锁的劣势
锁定后如果未释放,再次请求锁时会造成阻塞,多线程调度通常遇到阻塞会进行上下文切换,造成更多的开销。
在挂起与恢复线程等过程中存在着很大的开销,并且通常存在着较长时间的中断。
锁可能导致优先级反转,即使较高优先级的线程可以抢先执行,但仍然需要等待锁被释放,从而导致它的优先级会降至低优先级线程的级别。
二、硬件对并发的支持
处理器填写了一些特殊指令,例如:比较并交换、关联加载/条件存储。
1 比较并交换
CAS的含义是:“我认为V的值应该为A,如果是,那么将V的值更新为B,否则不需要修改告诉V的值实际为多少”。CAS是一项乐观锁技术。
模拟CAS操作例子:
@ ThreadSafe public class SimulatedCAS { @ GuardeBy( "this") private int value ; public synchronized 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(expectedValue, newValue)); } }
2 非阻塞的计数器
基于CAS实现的非阻塞计数器
@ ThreadSafe 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; } }
CAS的主要缺点是:它将使调度者处理竞争问题(通过重试、回退、放弃),而在使用锁中能自动处理竞争问题(线程在获得锁之前将一直阻塞)。
3 JVM对CAS的支持
java.util.concurrent.atomic 类的小工具包,支持在单个变量上解除锁的线程安全编程。 AtomicBoolean 可以用原子方式更新的 boolean 值。 AtomicInteger 可以用原子方式更新的 int 值。 AtomicIntegerArray 可以用原子方式更新其元素的 int 数组。 AtomicIntegerFieldUpdater<T> 基于反射的实用工具,可以对指定类的指定 volatile int 字段进行原子更新。 AtomicLong 可以用原子方式更新的 long 值。 AtomicLongArray 可以用原子方式更新其元素的 long 数组。 AtomicLongFieldUpdater<T> 基于反射的实用工具,可以对指定类的指定 volatile long 字段进行原子更新。 AtomicMarkableReference<V> AtomicMarkableReference 维护带有标记位的对象引用,可以原子方式对其进行更新。 AtomicReference<V> 可以用原子方式更新的对象引用。 AtomicReferenceArray<E> 可以用原子方式更新其元素的对象引用数组。 AtomicReferenceFieldUpdater<T,V> 基于反射的实用工具,可以对指定类的指定 volatile 字段进行原子更新。 AtomicStampedReference<V> AtomicStampedReference 维护带有整数“标志”的对象引用,可以用原子方式对其进行更新。
三、原子变量类
1 原子变量是一种“更好的volatile”通过CAS来维持包含多个变量的不变性条件例子:
import java.util.concurrent.atomic.AtomicReference; public class CasNumberRange { private static class IntPair{ final int lower ; // 不变性条件: lower <= upper 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( "Cant't set lower to " + i + " > upper"); } IntPair newv = new IntPair(i, oldv.upper ); if (values .compareAndSet(oldv, newv)){ return ; } } } // 对setUpper采用类似的方法 }
2 性能比较:锁与原子变量
使用ReentrantLock、AtomicInteger、ThreadLocal比较,通常情况下效率排序是ThreadLocal > AtomicInteger > ReentrantLock。
四、非阻塞算法
1 非阻塞的栈import java.util.concurrent.atomic.AtomicReference; public class ConcurrentStack<E> { private AtomicReference<Node<E>> top = new AtomicReference<ConcurrentStack.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; } } }
2 非阻塞的链表
CAS基本使用模式:在更新某个值时存在不确定性,以及在更新失败时重新尝试。
import java.util.concurrent.atomic.AtomicReference; @ ThreadSafe public class LinkedQueue<E> { private static class Node<E>{ final E item; final AtomicReference<Node<E>> next; public Node(E item, Node<E> next){ this .item = item; this .next = new AtomicReference<Node<E>>(next); } } private final Node<E> dummy = new Node<E>( null , null ); private final AtomicReference<Node<E>> head = new AtomicReference<Node<E>>(dummy); private final AtomicReference<Node<E>> tail = new AtomicReference<Node<E>>(dummy); public boolean put(E item){ Node<E> newNode = new Node<E>(item, null); while (true ){ Node<E> curTail = tail.get(); Node<E> tailNext = curTail.next.get(); if (curTail == tail.get()){ if (tailNext != null){ // 队列处于中间状态,推进尾节点 tail.compareAndSet(curTail, tailNext); } else { // 处于稳定状态, 尝试插入新节点 if (curTail.next.compareAndSet( null, newNode)){ // 插入操作成功,尝试推进尾节点 tail.compareAndSet(curTail, tailNext); return true ; } } } } } }
3 原子的域更新器
原子的域更新器类表示有volatile域的一种基于反射的“视图”,从而能够在已有的volatile域上使用CAS
private static class Node<E>{ private final E item; private volatile Node<E> next; public Node(E item){ this.item = item; } } private static AtomicReferenceFieldUpdater<Node, Node> nextUpdater = AtomicReferenceFieldUpdater.newUpdater(Node.class , Node.class , "next" );
4 ABA问题
处理V的值首先由A变成B,再由B变成A的问题。