AQS原理

一、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）来实现锁的分配

今天的文章AQS原理分享到此就结束了，感谢您的阅读。