原子变量与非阻塞同步机制：

锁的优势：

• 当线程在锁上发生竞争时，智能的JVM不一定会挂起线程，而是根据之前获取操作中对锁持有时间来判断此线程是挂起还是自旋。

硬件对并发的影响：

• 独占锁是一项悲观技术。

• 现在处理器基本都支持一些读-写-改的指令，如比较并交换(CAS)或关联加载/条件存储(Load-Linked/Store-Conditional)。操作系统和JVM使用这些指令来实现锁和并发数据结构。jdk5之前不能直接使用这些指令。

比较并交换：

• CAS包含了3个操作数--需要读写的内存位置V, 进行比较的值A和拟写入的新值B。

• 一个模拟的CAS操作：

/**
 * 模拟CAS
 */
public class SimulatedCAS {
	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));
	}
}

非阻塞的计数器：

/**
 * 基于CAS实现的非阻塞计数器
 */
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开销的两倍。

JVM对CAS的支持：

• JVM为数字类型和引用类型提供了一些高效的CAS操作，如AtomicXxx。

原子变量类：

原子变量是一种"更好的volatile":

/**
 * 通过CAS来维持包含多个变量的不变性条件
 */
public class CasNumberRange {
	private static class IntPair{
		// 不变性条件: lower <= upper
		final int lower;
		final int upper;
		
		public IntPair(int lower, int upper) {
			this.lower = lower;
			this.upper = upper;
		}
	}
	
	private AtomicReference<IntPair> values = new AtomicReference<>();
	
	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("lower can't > upper");
			}
			IntPair newv = new IntPair(i, oldv.upper);
			if (values.compareAndSet(oldv, newv)){
				return;
			}
		}
	}
}

性能比较：锁与原子变量

• 基于ReentrantLock的随机数生成器：

/**
 * 基于ReentrantLock实现的随机数生成器
 */
public class ReentrantLockPreudoRandom extends PseudoRandom{
	private final Lock lock = new ReentrantLock(false);
	private int seed;
	
	public ReentrantLockPreudoRandom(int seed){
		this.seed = seed;
	}
	
	public int nextInt(int n){
		lock.lock();
		try{
			int  s = seed;
			seed = calculateNext(s);
			int remainder = s % n;
			return remainder > 0 ? remainder : remainder + n;
		} finally{
			lock.unlock();
		}
	}
       ...
}

• 基于AtomicInteger的随机数生成器

/**
 * 基于AtomicInteger实现的随机数生成器
 */
public class AtomicPseudoRandom extends PseudoRandom{
	private AtomicInteger seed;
	
	public AtomicPseudoRandom(int seed){
		this.seed = new AtomicInteger(seed);
	}
	
	public int nextInt(int n){
		while (true){
			int s = seed.get();
			int nextSeed = calculateNext(s);
			if (seed.compareAndSet(s, nextSeed)){
				int remainder = s % n;
				return remainder > 0 ? remainder: remainder + n;
			}
		}
	}
       ...
}

非阻塞算法：

• 一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法就是非阻塞算法。

非阻塞栈实现：

/**
 * 使用Treiber算法构造的非阻塞栈
 */
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;
		}
	}
}

非阻塞链表的插入操作实现：

/**
 * 链表中非阻塞算法中的插入排序，来自Michael-Scott
 */
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<>(next);
		}
	}
	
	private final Node<E> dummy = new Node<E>(null, null);
	private final AtomicReference<Node<E>> head = 
						new AtomicReference<>(dummy);
	private final AtomicReference<Node<E>> tail = 
						new AtomicReference<>(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;
					}
				}
			}
		}
	}
}

原子的域更新器：

private static class Node<E>{
		private final E item;
		private volatile Node<E> next; // volatile变量
		
		public Node(E item){
			this.item = item;
		}
	}
	// 基于CAS的更新器
	private static AtomicReferenceFieldUpdater<Node, Node> nextUpdater
		= AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "next");

ABA问题：

• ABA问题是一种一场现象：如果在算法中的节点可以被循环使用，那么在使用"比较并交换"时就可能出现这种问题。在某些算法中，V的值由A变为B, 再由B变为A,仍然被认为发生了变化，并需要重新执行算法中的某些步骤。

• 可通过AtomicStampedReference或AtomicMarkableReference变量来避免ABA问题。

不吝指正。