Java并发之高级自旋锁CLH锁和MCS锁
自旋锁
自旋锁(spin lock)是一个典型的对临界资源的互斥手段，自旋锁是基于CAS原语的，所以它是轻量级的同步操作，它的名称来源于它的特性。自旋锁是指当一个线程尝试获取某个锁时，如果该锁已被其他线程占用，就一直循环检测锁是否被释放，而不是进入线程挂起或睡眠状态。由于自旋锁只不进行线程状态的改变（挂起线程），所以当线程竞争不激烈时，它的响应速度极快（因为避免了线程调度的上下文切换）。自旋锁适用于锁保护的临界区很小的情况，线程竞争不激烈的场景下。如果线程之间竞争激烈或者临界区的操作特别耗时，那么线程的自旋操作就会耗费大量的cpu资源，所以这种情况下性能就会下降明显。
现代计算机CPU的处理结构
由于自旋锁受不同的硬件处理器和架构的影响，我们来简单了解一下相关的知识，重点关注SMP和NUMA。
（1）多线程
（2）多核心
（3）SMP SMP（Symmetric Multi-Processing），对称多处理结构的简称，是指在一个计算机上汇集了一组处理器（多CPU），各CPU之间共享内存子系统以及总线结构。在这种技术的支持下，一个服务器系统可以同时运行多个处理器，并共享内存和其他的主机资源。像双至强，也就是所说的二路，这是在对称处理器系统中最常见的一种（至强MP可以支持到四路，AMD Opteron可以支持1-8路）。也有少数是16路的。但是一般来讲，SMP结构的机器可扩展性较差，很难做到100个以上多处理器，常规的一般是8个到16个，不过这对于多数的用户来说已经够用了。在高性能服务器和工作站级主板架构中最为常见，像UNIX服务器可支持最多256个CPU的系统。
（4）NUMA
NUMA即非一致访问分布共享存储技术，它是由若干通过高速专用网络连接起来的独立节点构成的系统，各个节点可以是单个的CPU或是SMP系统。在NUMA中，Cache 的一致性有多种解决方案，一般采用硬件技术实现对cache的一致性维护，通常需要操作系统针对NUMA访存不一致的特性（本地内存和远端内存访存延迟和带宽的不同）进行特殊优化以提高效率，或采用特殊软件编程方法提高效率。NUMA系统的例子。这里有3个SMP模块用高速专用网络联起来，组成一个节点，每个节点可以有12个CPU。像Sequent的系统最多可以达到64个CPU甚至256个CPU。显然，这是在SMP的基础上，再用NUMA的技术加以扩展，是这两种技术的结合。
（4）乱序执行
（4）分枝技术
（4）控制器
自旋锁的分类及特点
关于自旋锁的种类大体上有四种：
（1）简单自旋锁（非公平）
不能保证公平性
（2）基于票据的自旋锁（公平）
虽然解决了公平性的问题，但是多处理器系统上，每个进程/线程占用的处理器都在读写同一个变量serviceNum ，每次读写操作都必须在多个处理器缓存之间进行缓存同步，这会导致繁重的系统总线和内存的流量，大大降低系统整体的性能
（3）CLH自旋锁（公平）
作者：CLH：Craig，Landin and Hagersten。 锁的名称都来源于发明人的名字首字母
CLH自旋锁是一种基于隐式链表（节点里面没有next指针）的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋。CLH队列锁的优点是空间复杂度低（如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O（L+n），n个线程有n个。myNode，L个锁有L个tail），CLH的一种变体被应用在了JAVA并发框架中。 CLH在SMP系统结构下该法是非常有效的。但在NUMA系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的locked域，性能将大打折扣
（4）MCS自旋锁（公平）
作者：MCS：John Mellor-Crummey and Michael Scott。 锁的名称都来源于发明人的名字首字母
MCS Spinlock是一种基于显式链表（节点里面拥有next指针）的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，由直接前驱负责通知其结束自旋（与CLH自旋锁不同的地方，不在轮询前驱的状态，而是由前驱主动通知），从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。而MCS是在自己的结点的locked域上自旋等待。正因为如此，它解决了CLH在NUMA系统架构中获取locked域状态内存过远的问题。
实现CLH和MCS自旋锁
关于简单的自旋锁和基于票号的自旋锁前面的文章已经介绍过，这里不再重复介绍。
首先看CLH自旋锁的实现方式：
package concurrent.spinlock;
import java.util.concurrent.atomic.AtomicReference;
/**
* Created by qindongliang on 2018/8/5.
*/
public class CLHLock {
class Node{
//false代表没人占用锁
volatile boolean locked=false;
}
//指向最后加入的线程
final AtomicReference<Node> tail=new AtomicReference<>(new Node());
//使用ThreadLocal保证每个线程副本内都有一个Node对象
final ThreadLocal<Node> current;
public CLHLock(){
//初始化当前节点的node
current=new ThreadLocal<Node>(){
@Override
protected Node initialValue() {
return new Node();
}
};
}
public void lock() throws InterruptedException {
//得到当前线程的Node节点
Node own=current.get();
//修改为true，代表当前线程需要获取锁
own.locked=true;
//设置当前线程去注册锁，注意在多线程下环境下，这个
//方法仍然能保持原子性，，并返回上一次的加锁节点（前驱节点）
Node preNode=tail.getAndSet(own);
//在前驱节点上自旋
while(preNode.locked){
System.out.println(Thread.currentThread().getName()+" 开始自旋.... ");
Thread.sleep(2000);
}
}
public void unlock(){
//当前线程如果释放锁，只要将占用状态改为false即可
//因为其他的线程会轮询自己，所以volatile布尔变量改变之后
//会保证下一个线程能立即看到变化，从而得到锁
current.get().locked=false;
}
public static void main(String[] args) throws InterruptedException {
CLHLock lock=new CLHLock();
Runnable runnable=new Runnable() {
@Override
public void run() {
try {
lock.lock();
System.out.println(Thread.currentThread().getName()+" 获得锁 ");
//前驱释放，do own work
Thread.sleep(5000);
System.out.println(Thread.currentThread().getName()+" 释放锁 ");
lock.unlock();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Thread t1=new Thread(runnable,"线程1");
Thread t2=new Thread(runnable,"线程2");
Thread t3=new Thread(runnable,"线程3");
t1.start();
t2.start();
t3.start();
}
}在三个线程下面的输出结果：
线程1 获得锁
线程3 开始自旋....
线程2 开始自旋....
线程3 开始自旋....
线程2 开始自旋....
线程2 开始自旋....
线程3 开始自旋....
线程1 释放锁
线程2 获得锁
线程3 开始自旋....
线程3 开始自旋....
线程3 开始自旋....
线程2 释放锁
线程3 获得锁
线程3 释放锁MCS锁的实现方式：
package concurrent.spinlock;
import java.util.concurrent.atomic.AtomicReference;
/**
* Created by qindongliang on 2018/8/5.
*/
public class MCSLock {
class Node{
volatile Node next;//后继节点
//默认false
volatile boolean locked;
}
//指向最后加入的线程
final AtomicReference<MCSLock.Node> tail=new AtomicReference<>(null);
ThreadLocal<Node> current;
public MCSLock(){
//初始化当前节点的node
current=new ThreadLocal<MCSLock.Node>(){
@Override
protected MCSLock.Node initialValue() {
return new MCSLock.Node();
}
};
}
public void lock() throws InterruptedException {
//获取当前线程的Node
Node own=current.get();
//获取前驱节点
Node preNode=tail.getAndSet(own);
//如果前驱节点不为null，说明有线程已经占用
if(preNode!=null){
//设置当前节点为需要占用状态；
own.locked=true;
//把前面节点的next指向自己
preNode.next=own;
//在自己的节点上自旋等待前驱通知
while(own.locked){
System.out.println(Thread.currentThread().getName()+" 开始自旋.... ");
Thread.sleep(2000);
}
}
System.out.println(Thread.currentThread().getName()+" 获得了锁.... ");
}
public void unlock(){
//获取自己的节点
Node own=current.get();
//
if(own.next==null){
//判断是不是自身是不是最后一个线程
if(tail.compareAndSet(own,null)){
//是的话就结束
return;
}
//在判断过程中，又有线程进来
while (own.next==null){
}
}
//本身解锁，通知它的后继节点可以工作了，不用再自旋了
own.next.locked=false;
own.next=null;// for gc
}
public static void main(String[] args) {
MCSLock lock=new MCSLock();
Runnable runnable=new Runnable() {
@Override
public void run() {
try {
lock.lock();
System.out.println(Thread.currentThread().getName()+" 获得锁 ");
//前驱释放，do own work
Thread.sleep(4000);
System.out.println(Thread.currentThread().getName()+" 释放锁 ");
lock.unlock();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
};
Thread t1=new Thread(runnable,"线程1");
Thread t2=new Thread(runnable,"线程2");
Thread t3=new Thread(runnable,"线程3");
t1.start();
t2.start();
t3.start();
}
}输出结果：
线程1 获得了锁....
线程2 开始自旋....
线程3 开始自旋....
线程1 获得锁
线程3 开始自旋....
线程2 开始自旋....
线程1 释放锁
线程3 开始自旋....
线程2 开始自旋....
线程3 获得了锁....
线程3 获得锁
线程2 开始自旋....
线程2 开始自旋....
线程2 开始自旋....
线程3 释放锁
线程2 获得了锁....
线程2 获得锁
线程2 释放锁详细介绍，在代码的注释里面写的很清楚了，这里再给一张图来帮助我们我们理解基于链表实现公平方式的过程：
CLH 对比 MCS
（1）从代码实现来看，CLH比MCS要简单得多。
（2）从自旋的条件来看，CLH是在前驱节点的属性上自旋，而MCS是在本地属性变量上自旋。
（3）从链表队列来看，CLH的队列是隐式的，CLHNode并不实际持有下一个节点；MCS的队列是物理存在的。
（4）CLH锁释放时只需要改变自己的属性，MCS锁释放则需要改变后继节点的属性。
（5）CLH适合CPU个数不多的计算机硬件架构上，MCS则适合拥有很多CPU的硬件架构上
（6）CLH和MCS实现的自旋锁都是不可重入的
总结
本文主要介绍了目前主流的4种自旋锁的特点和实现，此外众所周知，AbstractQueuedSynchronizer是Java并发包的基石之一，而CLH锁的原理和思想则是AbstractQueuedSynchronizer的基石之一，JDK里面的CLH锁的是增强改进后的CLH锁。理解清楚CLH锁的原理和实现对后面学习和理解AbstractQueuedSynchronizer是非常重要的。最后文中所有的代码已经上传我的github上，感兴趣的朋友可以研究学习。