近年来，在并发算法领域的大多数研究都侧重于非阻塞算法，这种算法用底层的原子机器指令(如:cas)代替锁来确保数据在并发访问中保持一致。JVM的版本迭代过程中，并发性能的改进都来自于对非阻塞算法的使用。
非阻塞算法可以使多个线程在竞争相同数据时不会发生阻塞，因此它能在粒度更细的层次上进行协调，并且极大地减少调度开销，提供更好的可伸缩性。
1. 锁的劣势当在锁上存在着激烈的竞争时，调度开销与工作开销的比值会非常高。
与锁相比，volatile变量是一种更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换或线程调度等操作。
锁还有其他的一些缺点：当一个线程正在等待锁时，它不能做任何其他的事情。除了线程会把一些时间花在等待上面，还意味着——持有锁的做法，可能会造成线程活跃性的问题(活锁、死锁等)。
然而，volatile变量同样存在一些局限：虽然它们提供了相似的可见性保证，但不能用于构建原子的复合操作。
2. 硬件对并发的支持我们在假设最坏的情况时，会使用一项悲观的技术——独占锁；
对于细粒度的操作，还有另一种更高效的做法：乐观锁，该做法设计上容许失败的情况；
针对多处理器操作而设计的一些特殊指令，可以帮助我们管理对共享数据的访问(test-and-set、fetch-and-increment,现代处理器还增加了对compare-and -swap、load-linked/store-conditional的支持)
2.1 比较并交换(基于乐观的加锁方式实现CAS)这里不过多赘述CAS了，简单的过一下：原子的读-改-写操作
这是一项乐观的技术：如果期望值与初始值相同，则说明当前线程"看到"的是最新值，此时则做修改
当多个线程尝试使用CAS同时更新同一个变量时，只有一个线程能够更新成功，而其他的线程都将失败。然而，失败的线程并不会被挂起(这与锁的方式不同)，而是被告知在这次竞争中失败，并可以再次尝试、执行一些恢复 或者 什么都不做(一般来说，这是一种理智的做法，当CAS失败，意味着其他线程已经完成了你想要执行的操作)，这种灵活性大大的减少了与锁相关的活跃性风险。
2.2 非阻塞的计数器(使用2.1中的CAS实现类)
初看起来，基于CAS的计数器似乎比基于锁的计数器在性能上更差一些，因为它需要执行更多的操作和更复杂的控制流，并且还依赖看似复杂的CAS操作。但实际上，当竞争程度不高时，基于CAS的计数器在性能上远远超过了基于锁的计数器，而在没有竞争时甚至更高。
这是因为，即便是获取一个无竞争的锁，至少都需要一次CAS操作+获得锁，因此基于锁的计数器即使在最好的情况下也会基于CAS的计数器在一般情况下能执行更多的操作。
加锁时没有使用CAS：
虽然Java语言的加锁语法比较简洁，但JVM和操作在管理锁时需要完成的工作却并不简单：在实现加锁时需要遍历JVM中一条非常复杂的代码路径，并可能导致操作系统的加锁、线程挂起以及上下文切换等操作。在最好的情况下，在加锁时至少需要一次CAS操作，因此虽然在使用锁时没有用到CAS,但实际上也无法节约任何执行的开销；
加锁时使用CAS:
另一个方面，程序内部执行CAS时不需要执行JVM代码、系统调用或线程调度操作 -> 在应用层级上看起来越长的代码路径，但因为没有了JVM和操作系统中的代码调用，代码路径事实上变得更短。
CAS的缺点是需要调用者考虑竞争失败的处理情况(重试、回退、放弃)，而在锁中的部分将处理竞争的问题。
可以说CAS的最大缺陷即，难以围绕CAS正确的构建外部(调用部分)算法
2.3 JVM对CAS的支持Java 5+中引入了对CAS等操作的底层支持，并在int、long和对象引用等类型(j.u.c.atomic中的AtomicXxx)上公开了对应的API。
JVM会在运行时将其解释为相应的机器指令，最坏情况下(环境本身不支持CAS指令)，那么JVM将使用自旋锁。
3. 原子变量类原子变量将发生竞争的范围缩小到单个的变量上
更新原子变量的快速路径(非竞争)不会比获取锁的快速路径慢；并且它的慢速路径肯定比锁的慢速路径快，因为它不需要挂起或重新调度线程。
原子变量类相当于一种泛化的volatile变量，可以分为4组：
- 标量类：AtomicInteger、AtomicLong、AtomicReference
- 更新器类：后面会提及
- 数组类：只支持Integer、Long、Reference的版本(对比volatile修饰的数组，不同的是：除了数组本身具有volatile，其元素也具备)
- 复合变量类：略
其中的标量类继承了Number类，而非继承于Integer、Long等包装类型，并且本身也没有覆写hashCode、equals等方法(Number也是没有覆写这些方法的)，因此原子的标量类是不能作为散列的键的。
以AtomicInteger整型原子类的实现为例：
package java.util.concurrent.atomic;
import java.util.function.IntUnaryOperator;
import java.util.function.IntBinaryOperator;
import sun.misc.Unsafe;
public class AtomicInteger extends Number implements java.io.Serializable {
// 省略一些无关的代码 ...
// 内部维护数值的变量 其实是一个volatile变量
private volatile int value;
// 该类借助机器指令提供了支持cas等操作的本地(native)API，即硬件支持
private static final Unsafe unsafe = Unsafe.getUnsafe();
// cas
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
}
3.1 原子变量是一种"更好的volatile"
除了某些场景下，当我们不关心偶尔丢失一些更新操作(竞争是无害)的时候，那么此时"先检查再运行"就可以说是无伤大雅的：
这里的服务器缓存即便是丢失了，影响也不大(毕竟读缓存的部分不会影响到接口的幂等)
一般来说，"先检查再运行"是不安全的做法：
可能出现竞态条件的情况：getLower、getUpper同时通过边界判断后，各自更新
这里我们借助AtomicReference来管理两个边界状态,可以有效避免竞态条件，从而改良这个NumberRange：
3.2 性能比较：锁与原子变量测试结果中：
在高度竞争的情况下，锁的性能将超过原子变量的性能。这是因为：
- 锁在发生竞争时，将等待线程挂起后，降低了CPU的使用率以及共享内存总线上的同步信号量(这就好比，产消模型中，当生产者被阻塞后，这也有效降低消费者上的工作负载，使消息速度赶上生产速度)
- 另一方面，原子变量的CAS操作在遇到竞争时将立即重试，这在竞争激烈时，会带来更多的竞争
但在更加真实的竞争情况(不可忽略线程本地的计算量，即竞争的频率不那么集中)下，原子变量的性能将超过锁的性能
4. 非阻塞算法定义：一个线程的失败或挂起不会导致其他线程也失败或挂起，也被称为"无锁算法"
该算法不会出现死锁、优先级反转等活跃性问题，许多常见的数据结构中都可以使用非阻塞算法
4.1 非阻塞的栈这里采用原子操作来更新栈顶节点的引用：
之所以能确保线程安全性，是因为compareAndSet像锁一样，即可以提供原子性，又能提供可见性。
4.2 非阻塞的链表链表队列比栈更为复杂，因为它要求对头、尾指针的快速访问。链表的初始状态下，头、尾指针均指向一个哑节点(或称之为 哨兵节点)，后续状态下的链表头、尾的插入或移除均只会更新对应头、尾指针的引用以及头、尾节点的next引用,并不会互相影响。
举个栗子：当我们在链表的尾部做一次插入时，我们需要解决的是
- 尾指针的引用更新 & 尾节点的next引用更新 ,这两次cas中出现失败情况时可能将使链表队列处于不一致的状态
- 一个尾节点插入线程在执行这两次cas的操作中间，另一条线程也在做尾节点的插入，这时候应该应该怎么办
两种解决方案：
- 如果A线程已经在插入尾节点时，B线程则等待(可以自旋)至A线程更新完成 -> 这并不能成为一个非阻塞算法
- 如果A线程已经在插入尾节点时，B线程则可以"帮助"A线程完成剩下的cas操作，因为可见性，A线程所完成更新的部分对B线程也是可见的
非阻塞链表的插入：
实际上的链表实现与 4.2 中的略有区别：并没有使用原子引用类型来链表节点的引用，而是使用volatile类型的引用，并借助基于反射的AtomicReferenceFieldUpdater来进行原子的更新操作。(这么做只是为了减少AtomicReference类型的节点对象的创建开销)
原子的域更新器表示现有的volatile域的一种基于反射的"视图"，从而能够在已有的volatile域上使用cas.
域更新器类并没有与某个特定的实例关联在一起，它可以更新目标类的任意实例中的域。
域更新器提供的原子性保证比原子类更弱一些:无法保证底层的域不被直接修改——cas以及其他算法方法只能确保其他使用原子更新器方法的线程的原子性(人话就是：域更新器提供了 一个只被域更新器修改的变量 的原子性保证)
4.4 ABA这个现象在并发领域的讨论太多太多了，这里不做赘述。
我们知道的一个比较有效的解决方案：修改值的同时修改其版本号，这在编码怎么实现呢？
使用原子的二元组类型AtomicStampedReference
