原子变量与非阻塞算法

java传统上是使用锁来实现线程间的同步。每一个object都有一个内部锁(intrinsic lock)，关键字synchronized实现了锁的互斥。方法Object.wait主动的放弃锁，而方法Object.notify(All)则用来唤醒waiting中的线程。使用synchronized确保线程同步的正确性，但是也容易造成线程的阻塞。

volatile变量与锁相比是更轻量级的同步机制，但仅仅能保证内存的可见性，而不能用于原子化的操作。++i看起来是原子的，而实际上却是取当前值，自增加一，然后回写更新。

使用锁有以下的缺点：

(1) ?如果线程持有锁而延迟，会导致其他的线程的等待。

(2) ?高优先级的线程阻塞，而低优先级的线程持有锁造成优先级倒置(priority inversion)。

(3) ?死锁(dead lock)。

独占锁是一种悲观的技术，总是假设闯入的线程会改变共享的变量。而对于细粒度的操作应该采用的乐观的解决方法。容许其他线程的闯入，但是在需要改变共享变量之前总是要检测其是否被修改。如果没有被修改，则完成更新，否则就放弃更新。CAS(compare and swap)就是这样的一种技术，现在已经被大多数处理器直接支持。

使用CAS的经典场景是：首先从V中读取值A，由A生成新值B，然后使用CAS原子化的把V的值由A改为B。如果V中的值A被改为其他的值，则CAS操作失败。所以在不使用锁的情况下，也可以解决读-写-改的问题。

CAS的模拟：

队列总是处在两种状态：正常状态(图1和图3)和中间状态(图2)。在插入之前和第二个CAS之后，队列处在正常状态；在第一个CAS之后，第二个CAS之前，队列处在中间状态。在正常状态下，tail的next节点为null；中间状态下tail的next节点为非null。通过步骤A就可以知道队列的状态。
图2 插入新节点后，中间状态的队列

?在插入新节点前(A)检查队列是否处于中间状态。如果是，则说明有他线程是在插入途中，即(C)和(D)之间。不必等待其完成，直接帮助其完成，把tail节点向前移动(B)。如果有必要(又有其他线程插入新的节点)，则接续向前移动tail节点，直到处于正常状态，再开始自己的插入操作。
图3 插入完成后，有3个节点，正常状态的队列

?总之，如果第一个CAS(C)因两个线程竞争tail节点导致失败，这种情况下没有反生修改，失去CAS的线程载入tail节点再次尝试。如果第二个CAS(D)失败，插入线程不需要重试，其他线程会帮助完成(B)。
?
非阻塞算法比非阻塞算法复杂的多，但是能更细粒度的共享变量，有更好的并发性能。
?
参考：
1. https://www.ibm.com/developerworks/cn/java/j-jtp11234/
2.?http://www.ibm.com/developerworks/cn/java/j-jtp04186/
3. java concurrency in practice, Brian Goetz