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

锁的优势：

当线程在锁上发生竞争时，智能的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
    
      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
    
      {	private AtomicReference
     
      
       > top = new AtomicReference
       
        
         >();		public void push(E item){		Node
         
           newHead = new Node
          
           (item); Node
           
             oldHead; do{ oldHead = top.get(); newHead.next = oldHead; } while (!top.compareAndSet(oldHead, newHead)); } public E pop(){ Node
            
              oldHead; Node
             
               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
              
               { public final E item; public Node
               
                 next; public Node(E item){ this.item = item; } }}

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

/** * 链表中非阻塞算法中的插入排序，来自Michael-Scott */public class LinkedQueue
    
      {	private static class Node
     
      {		final E item;		final AtomicReference
      
       
        > next;				public Node(E item, Node
        
          next){ 			this.item = item;			this.next = new AtomicReference<>(next);		}	}		private final Node
         
           dummy = new Node
          
           (null, null); private final AtomicReference
           
            
             > head = new AtomicReference<>(dummy); private final AtomicReference
             
              
               > tail = new AtomicReference<>(dummy); public boolean put(E item){ Node
               
                 newNode = new Node
                
                 (item, null); while (true){ Node
                 
                   curTail = tail.get(); Node
                  
                    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
    
     {		private final E item;		private volatile Node
     
       next; // volatile变量				public Node(E item){			this.item = item;		}	}	// 基于CAS的更新器	private static AtomicReferenceFieldUpdater
      
        nextUpdater		= AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "next");