一、AQS（AbstractQueuedSynchronizer）
- AQS概念：Java的并发工具包JUC下locks包内的一个类。
- 主要思想：FIFO（先进先出队列）
- 实现算法：CLH队列算法
- 底层数据结构：双项链表
二、CLH锁
CLH是一种基于单向链表的高性能、公平的自旋锁。
1、申请加锁的线程通过前驱节点的变量进行自旋。
2、在前置节点解锁后，当前节点会结束自旋，并进行加锁。
3、在SMP架构下，CLH更具有优势。在NUMA架构下，如果当前节点与前驱节点不在同一CPU模块下，跨CPU模块会带来额外的系统开销，而MCS锁更适用于NUMA架构。【SMP和NUMA请参考下文拓展】
锁值：我把自旋条件定义为锁值 locked。locked == true 表示节点的处于加锁状态或者等待加锁状态，locked == false 表示节点处于解锁状态。
基于线程当前节点的前置节点的锁值（locked）进行自旋，locked == true 自旋，locked == false 加锁成功。
locked == true 表示节点处于加锁状态或者等待加锁状态。
locked == false 表示节点处于解锁状态。
每个节点在解锁时更新自己的锁值（locked），在这一时刻，该节点的后置节点会结束自旋，并进行加锁。
2.1 加锁逻辑
获取当前线程的锁节点，如果为空则进行初始化。
通过同步方法获取尾节点，并将当前节点置为尾节点，此时获取到的尾节点为当前节点的前驱节点。
如果尾节点为空，则表示当前节点为第一个节点，加锁成功。
如果尾节点不为空，则基于前驱节点的锁值（locked==true）进行自旋，直到前驱节点的锁值 locked == false。
2.2 解锁逻辑
获取当前线程的锁节点，如果节点为空或者锁值（locked== false）则无需解锁，直接返回。
使用同步方法为尾节点赋空值，赋值不成功则表示当前节点不是尾节点，需要将当前节点的 locked == false 已保证解锁该节点。如果当前节点为尾节点，则无需设置该节点的锁值。因为该节点没有后置节点，即使设置了，也没有实际意义。
2.3 CLH底层实现源码：
import java.util.concurrent.atomic.AtomicReference;
/**
* MCS：John Mellor-Crummey and Michael Scott
* CLH：Craig，Landin and Hagersten
* @author zhibo
* @version 1.0
* @date 2018/11/7 10:39
*/
public class CLHLock implements Lock {
private AtomicReference<CLHNode> tail;
private ThreadLocal<CLHNode> threadLocal;
public CLHLock() {
this.tail = new AtomicReference<>();
this.threadLocal = new ThreadLocal<>();
}
@Override
public void lock() {
CLHNode curNode = threadLocal.get();
if(curNode == null){
curNode = new CLHNode();
threadLocal.set(curNode);
}
CLHNode predNode = tail.getAndSet(curNode);
if(predNode != null){
while (predNode.getLocked()){
}
}
}
@Override
public void unlock() {
CLHNode curNode = threadLocal.get();
threadLocal.remove();
if(curNode == null || curNode.getLocked() == false){
return;
}
if(!tail.compareAndSet(curNode, null)){
curNode.setLocked(false);
}
}
public static void main(String[] args) {
final Lock clhLock = new CLHLock();
for (int i = 0; i < 10; i++) {
new Thread(new DemoTask(clhLock, i + "")).start();
}
}
class CLHNode {
private volatile boolean locked = true;
public boolean getLocked() {
return locked;
}
public void setLocked(boolean locked) {
this.locked = locked;
}
}
}
package org.learn.lock;
/**
* @author zhibo
* @version 1.0
* @date 2018/11/7 14:22
*/
public class DemoTask implements Runnable {
private Lock lock;
private String taskId;
public DemoTask(final Lock lock, final String taskId){
this.lock = lock;
this.taskId = taskId;
}
@Override
public void run() {
try {
lock.lock();
Thread.sleep(500);
System.out.println(String.format("Thread %s Completed", taskId));
} catch (Exception e) {
e.printStackTrace();
} finally {
lock.unlock();
}
}
}
部分内容原文链接：https://blog.csdn.net/claram/article/details/83828768
拓展：
一、 架构概述
1、从系统架构来看，目前的商用服务器大体可以分为三类：
- 对称多处理器结构(SMP：Symmetric Multi-Processor)
- 非一致存储访问结构(NUMA：Non-Uniform Memory Access)
- 海量并行处理结构(MPP：Massive Parallel Processing)。
2、共享存储型多处理机有两种模型：
- 均匀存储器存取（Uniform-Memory-Access，简称UMA）模型
- 非均匀存储器存取（Nonuniform-Memory-Access，简称NUMA）模型
1.1 SMP：对称多处理器结构（也被称为一致存储器访问结构），属于并行技术。在由多个CPU组成的计算机中，多个CPU对称工作，无主次或从属关系。所有的CPU都可以平等地访问内存（共享资源）、I/O和外部中断。 可以这么理解：操作系统将任务队列平均的分配到多个CPU上。
特征：资源共享，系统中所有资源(CPU、内存、I/O等)都是共享的
缺点：1、每一个共享的环节都可能造成SMP服务器扩展时的瓶颈
2、由于每个CPU必须通过相同的内存总线访问相同的内存资源，因此随着CPU数量的增加，内存访问冲突将迅速增加，最终会造成CPU资源的浪费，使CPU性能的有效性大大降低（实验证明，SMP服务器CPU利用率最好的情况是2至4个CPU）
1.2 NUMA(Non-Uniform Memory Access)：*非一致存储访问，每个CPU都有独立的本地内存以及I/O接口，CPU模块；模块之间内存资源交互可以通过交集模块来进行访问
特点：访问本地内存（本CPU模块的内存）的速度将远远高于访问远地内存(其他CPU模块的内存)的速度
缺点：由于访问远地内存的延时远远超过本地内存，因此当CPU数量增加时，系统性能无法线性增加
详细处理器结构参考博客：https://blog.csdn.net/gatieme/article/details/52098615
**总结：**QS内部维护了一个CLH队列来管理锁。线程会首先尝试获取锁，如果失败就将当前线程及等待状态等信息包装成一个node节点加入到同步队列sync queue里。 接着会不断的循环尝试获取锁，条件是当前节点为head的直接后继才会尝试。如果失败就会阻塞自己直到自己被唤醒。而当持有锁的线程释放锁的时候，会唤醒队列中的后继线程。
CLH(Craig,Landin,and Hagersten)队列是一个虚拟的双向队列（虚拟的双向队列即不存在队列实例，仅存在结点之间的关联关系）。AQS是将每条请求共享资源的线程封装成一个CLH锁队列的一个结点（Node）来实现锁的分配
相关文章
