给面试官讲讲无锁编程(Lock-Free Programming)
入门无锁编程对程序员深入学习并发编程有很大的意义。特别一些重要岗位，现在也开始在面试中增加无锁编程的讨论。
每个新人开始接触编发编程，都会经历几个阶段：
- 什么都上锁
- 开始用数据结构，并开始研究数据结构
- 开始自己设计数据结构
- 灵活运用
上面几个阶段，最核心的是从「有锁」到「无锁」(Lock Free)的一种思维变化，慢慢抓住接近解决并发问题的本质。并不是说「有锁」就差，或者一定要用「无锁」，而是开始灵活运用。
无锁编程（Lock Free)我们在前面的课程中或多或少已经碰到了，只不过我们没有给出明确的定义。之所以再安排一堂课，是因为无锁编程是并发算法的一大类，在日后你继续进步前， 咋们把几个基本的类别分清楚，有助于你分类和思考并发问题。
本节课关联的面试题有：
- 什么是无锁编程(Lock Free)？
- 请举一个无锁编程的例子？
- 自旋锁是不是无锁编程的设计？
- Obstruction Free/Lock Free/Wait Free的区别？
- 请举一个Obstruction Free/Wait Free的例子？
- 如何用Lock-Free实现一个栈/队列？
什么是无锁编程(Lock Free Programming)
再给出明确的定义前，我想先请大家思考一个问题，下面这段程序安不安全？
a = a + 1
当然，不安全，需要上锁，这是作为并发编程初学者的第一个想法。但是对于一些深入学习了CAS 原子操作的朋友，可能会思考用下面的解法。下面试图用CAS循环解决a=a+1 的问题。
int a = 0
update() {
while(true) {
if( cas(&a, a, a+1) ) {
return "done";
}
}
}
对于更加优秀的一些朋友，可能会考虑到ABA问题，于是用下面的解法。下面解法中将a 看做了一个二元组，就是<value, version>的二元组。利用CAS 循环同时更新值(value)和版本(version)。这样就不会存在ABA问题。
Pair a = <0, 0>
while(true) {
ver = a.version
val = a.value
if( cas(&a, <val, ver>, <val+1, ver+1>) ) {
return "done"
}
}
然后，我们来思考上面程序和锁的区别。比如下面这段程序，同样是解决了a=a+1 这个问题，但是区别在哪里呢？
synchronized(a) {
a = a + 1;
}
有两个非常显著的区别：
- CAS循环构成的不是排队结构，一个线程休眠不会影响其他线程；
synchronized构成了一种排队结构，如果拥有锁的线程休眠、置换等等，都会导致其他线程阻塞。 - CAS循环构成的算法中，同一时刻，总有线程可以进步；
synchronized，如果拥有锁的线程发生故障，可能导致没有线程可以继续运行。
Lock-Free的定义
在Lock-Free设计中，线程之间互相隔离（一个线程的延迟、阻塞、故障）不会影响其他线程；且同一时刻至少有一个线程可以进步。
Lock-Free核心是两个问题：
- 隔离：一个线程不会影响另一个线程进步
- 进步：达成计算目标（约束：至少有一个线程进步）
Lock-Free设计我们之前已经接触过了，在讲AQS的时候，我们讲过其中一个核心的算法实现——CLH队列。CLH的入队、出队操作都利用CAS Loop进行循环运算，是典型的Lock-Free设计。再比如，之前我们碰到的SynchrounousQueue内部双向队列、双向栈的实现，通过CAS实现的transfer操作，也是一个Lock Free的实现。
难点解析：自旋锁是不是Lock Free
有一个常见的误区，大家会认为使用了CAS操作即是Lock Free。那么我们通常会使用CAS操作实现自旋锁(spin lock)，那么自旋锁是不是Lock Free设计呢？
下面是自旋锁的程序：
volatile int lock = 0;
spinlock(){
while(!cas(&lock, 0, 1)) {
Thread.onSpinWait();
}
}
unlock(){
while(!cas(&lock, 1, 0)) {
Thread.onSpinWait();
}
}
通过spinlock 和unlock 方法可以控制上锁和解锁，上锁的过程我们利用CAS Loop实现，解锁我们也用CAS Loop实现。 接下来，我们思考使用自旋锁实现i++ ：
// 使用
spinlock();
i++;
unlock();
请你思考下，上面这段程序和下面这段程序的区别：
do{
a = i
}while(!cas(&i, a, a+1))
最大的区别在于自旋锁还是上锁，本质是排队，对临界区保护。在同一时刻，拥有锁的线程阻塞没有拿到锁的线程。所以，如果通过spinlock 拿到锁的线程，如果因为突发问题阻塞、被切换——这个时候其他线程只有等待。而第2个程序不同，每个线程都在尝试用cas 进步，如果有一个线程阻塞，其他线程也可以继续工作。
因此，自旋锁不是Lock Free；但是直接利用cas 循环更新i 的值是Lock Free。
实战Lock Free
接下来我带你写一个Lock Free的链表，通过这段程序，实现一个Lock Free的Stack。
Stack采用一个链表实现，push操作采用头插法，在链表头部插入元素。pop操作采用头删法，每次移出头部元素。
如果你阅读下面程序感到吃力，也可以随着课程一起学习，我会在视频中给出Line By Line的讲解。
public class LockFreeStack<T> {
static class Node<T> {
Node<T> next;
T value;
public Node(T value){
this.value = value;
this.next = null;
}
}
AtomicStampedReference<Node<T>> head;
public LockFreeStack(){
var headNode = new Node<T>(null);
head = new AtomicStampedReference<Node<T>>(headNode, 0);
}
public void push(T v){
var newNode = new Node<T>(v);
while(true) {
int stamp = head.getStamp();
Node<T> ref = head.getReference();
newNode.next = ref;
if(head.compareAndSet(ref, newNode, stamp, stamp+1)){
return;
}
}
}
public T pop(){
while(true) {
int stamp = head.getStamp();
Node<T> ref = head.getReference();
if(ref.next == null) {
return null;
}
var next = ref.next;
head.compareAndSet(ref, next, stamp, stamp+1);
return ref.value;
}
}
@Test
public void testSingle(){
var stack = new LockFreeStack<Integer>();
for(int i = 0; i < 100; i++) {
stack.push(i);
}
Integer j = null;
Integer i = 99;
while((j = stack.pop()) != null) {
assertEquals(j+"", i-- +"");
}
}
@Test
public void testMultiThreads() throws InterruptedException {
var stack = new LockFreeStack<Integer>();
for(int i = 0; i < 16; i++) {
var t = new Thread(() -> {
for(int j = 0; j < 100; j++ ){
stack.push(j);
}
});
t.start();
t.join();
}
Integer c = 0;
while(stack.pop() != null) {
c ++;
}
assertEquals(c+"", "1600");
}
}
并发设计思路总结
最后，我们一起总结下并发部分的设计思路。
当我们执行一个并发任务时，因为有共享资源需要访问，最容易想到的方法是互斥（锁、同步队列）都属于这种结构。
在使用锁的过程当中，要注意减少锁的范围。因为锁是一种同步排队的机制，锁的范围越小，相当于并发执行部分占比越大。
无阻碍（Obstruction Free）
当我们开始思考希望多个线程之间不要互相阻塞的时候，我们就开始进入一个新的世界，比如开始使用Lock Free设计数据结构。
其实还有一种比Lock Free更宽松的限制，叫做Obstruction Free设计。这种设计要求线程之间隔离，但不要求任何时刻都有线程进步。
比如下面这段程序：
Pair a = <0, 0>
while(true) {
ver = a.version
val = a.value
if( cas(&a, <val, ver>, <val, ver+1>) ) {
if( cas(&a, <val, ver+1>, <val+1, ver+1> ) ) {
return "done"
}
}
}
还是以a=a+1 为例，第一个CAS操作实际上是一种检验操作，它在尝试检当前线程是否可以拿到最新版本号，相当于少量的进步。第二个CAS操作才是我们真实的目的。
上面这种设计如果线程A通过第1个CAS，可能会被后来的线程B通过CAS的线程抢先1步拿到下个版号(ver)。而这个时刻，线程A的进步会被中断，线程B的进步还没有开始。这种设计我们称为Obstruction Free。线程B和线程A竞争进步，但是线程B如果阻塞、延迟、异常，不会影响线程A最终进步。这种设计，就是Obstruction Free。
Lock Free是Obstruction Free。Obstruction Free的要求比Lock Free更弱。Lock Free要求总是有线程在进步，因此Obstruction Free的算法更好实现一些。Obstruction Free的算法往往是多个CAS操作嵌套在执行，其中有的在进步，有的在检查。对于一个CAS Loop，多几步检查可以让线程停留在不同的步骤上，从而减少竞争的激烈程度。
无等待（Wait Free）
无等待(Wait Free)在Lock Free基础上，增加了更强的约束。是并发设计的最高境界。 所有线程都在进步，不需要等待。
举个例子，比如说Copy On Write模型。比如我们要更新对象o，需要3步：
- 拷贝o到一个新对象p
- 更新p
- 替换指向o的所有引用为p
在上述过程内，所有对o的读者(Reader)都不需要锁。所以从这个角度看，CopyOnWrite算法的所有读者是Wait Free的。
从约束关系上，Wait Free > Lock Free > Obstruction Free。 从性能角度，包括在内，4种设计不能说一定谁块谁慢。 但是Obstruction Free的算法，因为没有阻碍，不会出现死锁、饥饿等问题。要注意死锁，饥饿等问题的根源，还是资源的抢占伴随着阻塞造成的。
其实最核心的，是要为想要解决的问题，找到合适的算法。学习这几个概念最大的作用是，当你实现了一个并发控制算法的时候，可以将它归类，并且可以做这样的思考：能不能找到一个LockFree的算法？
关于LockLess
我们经常还会听到一个词汇，叫做LockLess——翻译过来也好像是无锁。其实LockLess指的是不用锁进行编程，不用synchronized 关键字，不用ReentrantLock 等等都是LockLess。由此可见，LockLess是个笼统概念，就是没有用锁。
信号量、阻塞队列、其他并发数据结构，包括Lock Free，只要没有直接用到锁，都算成LockLess。
总结
程序员开始针对自己遇到的场景开始设计数据结构，是读并发编程原理层面掌握的开始。往后深造，自己就可以开始设计并发的算法和库。并发的知识，千万不要孤立的看。并发，是为了更好的利用单机性能，解决更多的问题；也是为了在工作中提升自己系统的性能瓶颈。单机的处理学号，到了分布式领域，还是会基于单机处理的思路，继续扩展。比如解决分布式一致性的若干思路，和解决内存一致性是类似的。
这节课属于一个对之前所学的一个总结个拔高。下一节课，我们会从另一个角度，优化一个实际问题：哲学家就餐问题，帮助你继续提高。