简介
论文地址：The java.util.concurrent synchronizer framework
译文系列 The j.u.c Synchronizer Framework翻译(一)背景与需求
introduction 部分
J2SE-1.5 introduces package java.util.concurrent, a collection of medium-level concurrency support classes（medium-level 的并发支持类） created via Java Community Process (JCP) Java Specification Request (JSR) 166.
Among these components are a set of synchronizers – abstract data type (ADT) classes that maintain an internal synchronization state (for example, representing whether a lock is locked or unlocked), operations to update and inspect that state, and at least one method that will cause a calling thread to block if the state requires it, resuming when some other thread changes the synchronization state to permit it. Examples include various forms of mutual exclusion locks, read-write locks, semaphores, barriers, futures, event indicators, and handoff queues.
abstract data type (ADT) classes 作者将同步器 描述为一个抽象的数据类型，包含几个要素
- an internal synchronization state
- operations to update and inspect that state
- at least one method that cause a calling thread to if the state requires it, resuming when some other thread changes the synchronization state to permit it.
any synchronizer can be used to implement nearly any other.可以用一个同步器实现另一个同步器，就好像乘法可以换算为加法一样，但有几个问题
- doing so often entails enough complexity, overhead, and inflexibility to be at best a second-rate engineering option. 比较复杂，有性能瓶颈，是一个二流的实现方案。
- it is conceptually unattractive. If none of these constructs are intrinsically（本质的） more primitive than the others。 developers should not be compelled to arbitrarily choose one of them as a basis for building others. 所有同步器 都属于同一个抽象层次，以一个为基础实现另一个不科学。
因此，提出了一个AQS，提供了大部分同步器都会用到的基础特性， 比同步器more primitive
实现同步器要考虑的几个问题
为什么要同步？
线程同步出现的根本原因是访问公共资源需要多个操作，而这多个操作的执行过程不具备原子性，被任务调度器分开了，而其他线程会破坏共享资源，所以需要在临界区做线程的同步，这里我们先明确一个概念，就是临界区，他是指多个任务访问共享资源如内存或文件时候的指令，他是指令并不是受访问的资源。POSIX 定义了五种同步对象：互斥锁，条件变量，自旋锁，读写锁，信号量，这些对象在 JVM 中也都有对应的实现
实现什么
同步器有两类（注意不是两个）方法：acquire和release，但java 没有定义类似interface Synchronizer 的接口，因此acquire 和 release 就衍生出诸多称谓：
- Lock.lock
- Semaphore.acquire
- CountDownLatch.await
- FutureTask.get 这次我第一次看到将Future 与 同步器串联起来
并且acquire 还有tryAcquire非阻塞版本、支持timeout版本、 Cancellability via interruption
同时，synchronizer 维护的state 还有 是否 exclusive的划分，即同时时刻是否允许多个线程通过
性能目标
-
公平性和aggregate throughput 的矛盾。
- 一个线程，占用了资源，但多久之后释放是不知道的，排队是公平的。对于连接池这类场景来说，公平性很重要。。但业务中若是大部分线程占用的时间短，少部分线程占用的时间长，则排队会影响线程通过的吞吐量
- 新的线程进来，总是先测试下state，不符合条件时才加入队列。此时，在高并发情况下，当state 可用时，实际上是新加入线程和队列头节点在竞争。按等待时间来说，这是不公平的，并且容易导致队列尾部的线程饥饿。
-
在cpu time requirements,memory traffic,thread scheduling 之间取得平衡.比如自旋锁，获取锁的速度倒是快，但是浪费cpu cycle，导致大量的memory contention，所以大部分时候不适用。
设计
synchronizer requires the coordination of three basic components:
- Atomically managing synchronization state
- Blocking and unblocking threads
- Maintaining queues
It might be possible to create a framework that allows each of these three pieces to vary independently。 同步器框架的核心决策是为这三个组件选择一个具体实现，同时在使用方式上又有大量选项可用 。这段话反映了一个很好的设计思路：
- 将同步器接口 acquire和release 具体为几个实际组件
- 组件之前可以各自抽象，彼此独立。（当然，AQS中没有这样做）
Concrete classes based on AbstractQueuedSynchronizer must define methods tryAcquire and tryRelease in terms of these exported state methods in order to control the acquire and release operations.
阻塞和恢复线程 参见Unsafe
队列
- The heart of the framework is maintenance of queues of blocked threads, which are restricted here to FIFO queues. 队列用来存储 blocked 线程，先进先出
- there is little controversy that the most appropriate choices for synchronization queues are non-blocking data structures. 同步队列的最佳选择是自身没有使用底层锁来构造的非阻塞数据结构，这样的locks有两种：MCS locks and CLH locks，因为后者对cancellation 和 timeout 的支持更好，因此选择了 CLH，并对其做了一些改动。
不管是业务层面的秒杀、还是数据库锁、还是操作系统锁，底层都是线程排队 线程排队
思维顺序
- 数据结构/容器层面，一般阻塞队列，锁其实可以变量的理解为一个长度为1的阻塞队列，put 成功就相当于获取到了锁
- 数据结构/容器层面，一般非阻塞队列/无锁队列 无锁队列
- 操作系统中的队列情况显式地提升到了应用层
- 并发/线程排队层面，CLH
- 并发/线程排队层面，AQS 对CLH 的改动
传统CLH 队列
The j.u.c Synchronizer Framework翻译(二)设计与实现
CLH队列实际上并不那么像队列，因为它的入队和出队操作都与它的用途（即用作锁）紧密相关。PS： 以至于一些文章 直接称之为锁 并发编程——详解 AQS CLH 锁 CLH队列实际上并不那么像队列，因为它的入队和出队操作都与它的用途（即用作锁）紧密相关。它是一个链表队列，通过两个字段head和tail来存取，这两个字段是可原子更新的，两者在初始化时都指向了一个空节点。
一个新的节点，node，通过一个原子操作入队：
do {
pred = tail;
} while(!tail.compareAndSet(pred, node));
每一个节点的“释放”状态都保存在其前驱节点中。因此，自旋锁的“自旋”操作就如下：
while (pred.status != RELEASED); // spin
自旋后的出队操作只需将head字段指向刚刚得到锁的节点：
head = node;
AQS 对 CLH 的变动
为了将CLH队列用于阻塞式同步器，需要做些额外的修改以提供一种高效的方式定位某个节点的后继节点，因为一个节点需要显式地唤醒（unpark）其后继节点。AQS队列的节点包含一个next链接到它的后继节点
第二个对CLH队列主要的修改是将每个节点都有的状态字段用于控制阻塞而非自旋。队列节点的状态字段也用于避免没有必要的park和unpark调用。虽然这些方法跟阻塞原语一样快，但在跨越Java和JVM runtime以及操作系统边界时仍有可避免的开销。在调用park前，线程设置一个“唤醒（signal me）”位，然后再一次检查同步和节点状态。一个释放的线程会清空其自身状态。这样线程就不必频繁地尝试阻塞
从JUC lock - AQS - CLH queue /【死磕Java并发】—–J.U.C之AQS：CLH同步队列 可以看到，acquire 和 release 和一般的无锁队列 是一致的
-
入队，先创建Node，然后cas 竞争tail 指向 Node
-
出队，cas 竞争head， 使得head 指向自己
区别在于
- 入队后，设置前驱节点状态，告诉他：你释放锁的时候记得唤醒我，然后park 自己
- head 表示当前持有锁的节点，release操作 upark head 之后的线程
tips
使用时为什么不直接继承AQS？因为AQS的子类必须实现 tryAcquire 和 tryRelease 方法，这个命名 对一些类并不合适，比如Mutex 更适合叫lock/unlock。
尽管同步器是基于FIFO队列的，但它们并不一定就得是公平的。可以注意到，在基础的acquire算法中，tryAcquire是在入队前被执行的。因此一个新的acquire线程能够“窃取”本该属于队列头部第一个线程通过同步器的机会。 通常情况下 这种闯入策略 能够提供更高的吞吐量，论文中解释了两点。
如果需要严格的公平性，程序员可以把tryAcquire方法定义为，若当前线程不是队列的头节点（可通过getFirstQueuedThread方法检查，这是框架提供的为数不多的几个检测方法之一），则立即失败（返回false）。
内置锁和同步器类之间的主要差别，显然是由于Hotspot锁在锁定和解锁时都使用了一次compareAndSet，而同步器的acquire操作使用了一次compareAndSet，但release操作用的是一次volatile写（即，多处理器上的一次内存屏障以及所有处理器上的重排序限制）。
为什么 推出AQS
这个问题，通常需要拿AQS 与 synchronized 关键字做对比，并且 人通常的直觉是说 synchronized 性能不行。
从文章可以看到，考虑这个问题，一定要从同步器 整个宏观概念、构成和实现入手，主要有几块：
- 同步器的三大组件，状态、阻塞/恢复线程、队列，AQS 深入打磨了队列的实现，闯入策略等可以上层来控制。
- 功能上，synchronized 使用简单，但对取消和超时的支持有限
- 性能上，synchronized 的偏向锁、轻量级锁 偏向于对无锁环境（零竞争）时的优化（强竞争环境下则乏善可陈）。
同步器需要的 几个基本能力和组件，AQS 用到的技术 理论上 synchronized 都可以用（所以纠结 多几次compareAndSet 不是重点）。我觉得关键就是 synchronized 没让用户 更多的介入 其工作流程（比如闯入策略、超时等），因此只能是采用通用方案，通用就意味着中规中矩。
算法领域上曾经说过，凡是递归都可以用非递归算法实现。同样的，凡是满足原子性、可见性和有序性的都可以线程安全的操作变量。凡实现同步器三大组件都可以作为同步器来使用。是不是可以说：凡是锁能干的事儿都可以无锁化。聊聊原子变量、锁、内存屏障那点事 实际上无锁的代码仅仅是不需要显式的Mutex来完成，但是存在数据竞争（Data Races）的情况下也会涉及到同步（Synchronization）的问题。从某种意义上来讲，所谓的无锁，仅仅只是颗粒度特别小的“锁”罢了，从代码层面上逐渐降低级别到CPU的指令级别而已，总会在某个层级上付出等待的代价，除非逻辑上彼此完全无关
AbstractQueuedSynchronizer与synchronized优缺对比及AQS 源码分析笔记
- 多线程去竞争获取锁 有两个地方：初次获取锁的时候；占有锁的线程释放锁，通知其它等待线程重新尝试获取锁。
- 这里说一下羊群效应，当有多个线程去竞争同一个锁的时候，假设锁被某个线程释放，那么如果有成千上万个线程在等待锁，有一种做法是同时唤醒这成千上万个线程去去竞争锁，这个时候就发生了羊群效应，海量的竞争必然造成资源的剧增和浪费（缓存同步开销，我们知道volatile 的工作原理，强制线程从内存读取数据 是有开销的。所有等待线程 突然去争抢一个锁（也就是检测锁变量），必然会所有等待线程强制去内存读取这个变量的值）。因为终究只能有一个线程竞争成功，其他线程还是要老老实实的回去等待。
如果你的目标是让端到端的延迟只有 10毫秒，而其中花80纳秒去主存拿一些未命中数据的过程将占很重的一块。
- AQS的FIFO的等待队列给解决在锁竞争方面的羊群效应问题提供了一个思路：保持一个FIFO队列，队列每个节点只关心其前一个节点的状态，线程唤醒也只唤醒队头等待线程。
沪江——写个AQS 是个系列，值得一读，可以学习到：
- 本文说的实现的同步器的三种能力，如何应用在lock和unlock 操作上
小结一下
- cpu 层面有内存屏障、cas、关中断 等指令，有l1/l2/l3 cache ，cpu 会对指令重排序
- 操作系统 提供 锁抽象，但aqs 这里没用。并且锁的实现 是否用到了cas 、内存屏障等指令待分析。
- 编译器会对 代码重排序
- 因为cpu、编译器等基本特性，所以线程安全的操作一个变量需要原子性、有序性和可见性
- jvm 提供 volatile（对应读写屏障指令）、cas 等cpu 级别的操作
- 因此，使用volatile、cas 等 可以在java 层面 线程安全操作一个变量，无锁化的
- 同步器的三大组件，状态、阻塞/恢复线程、队列，具备这个能力就可以实现一个同步器。如果可以无锁化的更改状态、操作队列，则可以实现一个无锁化的同步器。