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

与基于锁的方案相比，非阻塞算法在设计和实现上都要负责得多，但它们在可伸缩性和活跃性上拥有巨大的优势。
原子变量提供了与volatile类型变量相同的内存语义，此外还支持原子的更新操作，从而使它们更加适用于实现计数器、序列发生器和统计数据收集等，同时还能比基于锁的方法提供更高的可伸缩性。
独占锁是一种悲观技术----它假设最坏的情况。
现在，几乎所有的现代处理器中都包含了某种形式的原子读-改-写指令，例如比较并交换（Compare-and-Swap）或者关联加载/条件存储（Load-Linked/Store-Condition）。

1. 比较并交换（CAS）

CAS包含了3个操作数----需要读写的值V、进行比较的值A和拟写入的新值B。当且仅当V的值等于A时，CAS才会通过原子方式用新值B来更新V的值，否则不会执行任何操作，无论V的值是否等于A，都将返回V的原值。
当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其他线程都将失败，然而，失败的线程并不会挂起，而是被告知在这次竞争中失败，并可以再次尝试。

2. JVM对CAS的支持

在Java5.0中引入了地城的支持，在int、long和对象的引用等类型上都公开了CAS操作，并且JVM把它们编译为底层提供的最有效方法。

3. 原子变量类

共有12个原子变量类，可分为4组：标量类（Scalar）、更新器类、数组类以及复合变量类。最常用的原子变量就是标量类：AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。所有这些类都支持CAS，此外，AtomicInteger和AtominLong还支持算术运算。

• 原子变量是一种“更好的volatile”
• 原子变量的效率更高，可伸缩性更好

4. 非阻塞算法

如果在某种算法中，一个线程的失败或挂起不会导致其他线程也失败或挂起，那么这种算法就被称为非阻塞算法。如果在算法的每个步骤中都存在某个线程能够执行下去，那么这种算法也被称为无锁（Lock-Free）算法。

5. ABA问题

ABA问题是一种异常现象：如果在算法中的节点可以被循环使用，那么在使用“比较并交换”指令时就可能出现这种问题。在CAS操作中将判断“V的值是否仍然为A？”，并且如果是的话就继续执行更新操作，在大多数情况下，包括本章给出的示例，这种判断是完全足够的。然而，有时候还需要知道“自从上次看到V的值为A以来，这个值是否发生了变化？”，在某些算法中，如果V的值首先由A变成B，再由B变成A，那么仍然被认为是发生了变化，并需要重新执行算法中的某些步骤。
解决ABA问题的一个简单方法是：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号。即使这个值由A变为B，然后又变为A，版本号也将是不同的。
AtomicStampedReference、AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference将更新一个“对象-引用”二元组，通过在引用上加上“版本号”，从而避免ABA问题。AtomicMarkableReference将更新一个“对象引用-布尔值”二元组，在某些算法中将通过这种二元组使节点保存在链表中同时又将其标记为“已删除的节点”。