- 1. 锁
- 1.1 自旋锁与互斥锁
- 1.2 乐观锁与悲观锁
- 1.3 公平锁与非公平锁
- 1.4 共享锁与独占锁
- 1.5 分段锁
- 2. 自旋锁基础之CAS自旋
- 2.1 CAS介绍
- 2.2 CAS的优缺点
- 3. AQS
- 3.1 AQS的核心思想
- 3.2 CLH锁
- 3.3 MCS锁
- 3.4 AQS源码解析
自旋锁指多线程下，当一个线程尝试获取锁的时候，如果锁被占用，则在当前线程循环检查锁是否被释放，此时当前线程并没有休眠或挂起。 1. 锁
在前面提到了synchronized关键字，其也是Java实现的一种锁机制，但本人认为其并不能实现广义锁的多种特性（公平性、乐观性等），因此将锁的介绍放在此处。
通常情况下，锁用来将某个对象或某段代码标记，使得JVM在程序执行时根据锁的状态来实现特定操作，而锁的状态由分为很多种，并且也能从不同的角度来讨论锁。
1.1 自旋锁与互斥锁- 自旋锁：尝试获取锁的线程不会立即阻塞，而是采用循环的方式去尝试获取锁
- 优点是减少线程上下文切换的消耗，因为线程不会阻塞，也就不会产生内核态和用户态的切换
- 缺点是长时间循环获取会无谓的CPU消耗
- 互斥锁：线程获取资源前必须获得该资源的锁，否则无法操纵资源
- 优点是确保了资源能被某线程安全的访问
- 缺点是可能造成死锁，且加锁/解锁开销较大
- 乐观锁：认为读多写小，遇到并发写的可能性低。指对资源的访问不会上锁，而在更新前判断在操作过程中有没有线程已经更新过此数据
- 悲观锁：认为读少写多，遇到并发写的可能性高。在访问资源时一定会对资源上锁，其他线程在锁释放之前无法访问
我们知道多线程下必然存在某个线程在执行，多个线程在等待（就绪态），在线程执行完毕后等待线程中出现一个线程执行，而根据挑选的原则，将锁分为公平锁和非公平锁
- 公平锁：就绪队列中的线程按照申请锁的顺序来获取锁（等待时间长短）
- 非公平锁：与公平锁不同。JVM按照随机、就近原则给等待线程分配锁
- 独占锁：指某个线程独占一个锁，独占期间其他线程无法访问，是一种悲观锁，互斥锁就是独占锁的一种实现
- 共享锁：指允许多个线程共享某资源，是一种乐观锁
分段锁是一种设计思想，通过对要访问的内存分段进行加锁来实现粒度更小的保护。
比如在Java1.7的ConcurrentHashMap实现中就利用了分段锁。
ConcurrentHashMap内部通过数组+链表时间，当需要put元素的时候，并不是对整个hashmap进行加锁，而是先通过hashcode来知道他要放在那一个分段中，然后对这个分段进行加锁，所以当多线程put的时候，只要不是放在一个分段中，就实现了真正的并行的插入。
2. 自旋锁基础之CAS自旋 2.1 CAS介绍
Compare And Swap ========>compareAndSwapInt，它是一条CPU并发原语。它的功能时判断内存的某个位置的值是否为预期值，如果是则更改为新的值，这个过程是原子的。
系统原语： 由若干条指令组成，用于完成某个功能的一个过程，并且原语的执行不能被打断。
2.2 CAS的优缺点- CASS是一种乐观锁，其具有非阻塞性，对死锁问题天然免疫，在高并发下，比其他锁有更好的实现
- 一般情况下开销更小，但可能存在饥饿现象（线程数较多，等待时间长)
- ABA问题：A变成B再变成A，解决方案有
- 版本号
- 使用JDK1.5后的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。（还是版本号）
- 只能保证一个共享变量的原子操作：但从Java1.5开始 JDK 提供了 AtomicReference类 来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。
3. AQS
AbstractQueuedSynchronizer（AQS）这个抽象类，是Java并发包 java.util.concurrent 的基础工具类，是实现 ReentrantLock、CountDownLatch、Semaphore、FutureTask 等类的基础，实现了除了java自带的synchronized关键字之外的锁机制
3.1 AQS的核心思想如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并将共享资源设置为锁定状态，如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制AQS是用CLH队列锁实现的，即将暂时获取不到锁的线程加入到队列中。
AQS就是基于CLH队列，用volatile修饰共享变量state，线程通过CAS去改变状态符，成功则获取锁成功，失败则进 入等待队列，等待被唤醒。
3.2 CLH锁CLH锁是基于链表实现的自旋锁，它不断的轮询前驱的状态，如果前驱释放锁，它就结束自旋转。
CLH锁实现如下：
- 线程持有自己的node变量，node中有一个locked属性，true代表需要锁，false代表不需要锁。
- 线程持有前驱的node引用，轮询前驱node的locked属性，true的时候自旋，false的时候代表前驱释放了锁，结束自旋。
- tail始终指向最后加入的线程。
模拟过程：
- 初始化的时候tail指向一个类似head的节点，此时node的locked属性为false，preNode为空。
- 当线程A进来的时候，线程A持有的node节点，node的locked属性为true，preNode指向之前的head节点。
- 当线程B进来的时候，线程B持有的node节点，node的locked属性为true，preNode指向线程A的node节点，线程B的node节点locked属性为true，线程A轮询线程B的node节点的locked状态，为true自旋。
- 线程A执行完后释放锁（修改locked属性为false），线程B轮询到线程A的node节点locked属性为false，结束自旋。
介绍缺点前先说一下NUMA和SMP两种处理器结构
SMP(Symmetric Multi-Processor)，即对称多处理器结构，指服务器中多个CPU对称工作，每个CPU访问内存地址所需时间相同。其主要特征是共享，包含对CPU，内存，I/O等进行共享。SMP的优点是能够保证内存一致性，缺点是这些共享的资源很可能成为性能瓶颈，随着CPU数量的增加，每个CPU都要访问相同的内存资源，可能导致内存访问冲突，可能会导致CPU资源的浪费。常用的PC机就属于这种。
NUMA(Non-Uniform Memory Access)，非一致存储访问，将CPU分为CPU模块，每个CPU模块由多个CPU组成，并且具有独立的本地内存、I/O槽口等，模块之间可以通过互联模块相互访问，访问本地内存的速度将远远高于访问远地内存(系统内其它节点的内存)的速度，这也是非一致存储访问NUMA的由来。NUMA优点是可以较好地解决原来SMP系统的扩展问题，缺点是由于访问远地内存的延时远远超过本地内存，因此当CPU数量增加时，系统性能无法线性增加。
**现在说CLH锁的缺点是在NUMA系统结构下性能很差，在这种系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的locked域，性能将大打折扣。**因此有人提出了MCS锁
MCS Spinlock 是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，直接前驱负责通知其结束自旋（与CLH自旋锁不同的地方，不在轮询前驱的状态，而是由前驱主动通知），从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。
模拟过程：
-
每个线程持有一个自己的node，node有一个locked属性,true表示等待获取锁，false表示可以获取到锁，并且持有下一个node（后继者）的引用（可能存在）
-
线程在轮询自己node的locked状态，true表示锁被其他线程暂用，等待获取锁，自旋。
-
线程释放锁的时候，修改后继者（nextNode）的locked属性，通知后继者结束自旋。
AQS中维护着一个同步队列。队列中头结点headNode只能是null或者是已经获取到锁的线程，只有第二个节点能够尝试获取锁，而第二个节点获取到锁之后变为头结点。
-
acquire()方法会调用tryAcquire()获取锁。tryAcquire()获取到锁，完成。如果获取锁失败（没有竞争到锁），当前线程T会封装成Node插入同步队列中，并且将当前线程T park()。
-
release()方法调用tryRelease()方法释放锁，当前线程释放锁之后，会unpark()下一节点（也就是唤醒第二节点，因为持有锁的一定是头节点线程或者不在队列中的线程）
首先我们看AQS的数据结构，其中封装了一条双向队列，队列中存储线程的相关信息。同时，还保存了多个offset，以实现CAS操作。
{
// 封装了线程
static final class Node {
static final Node SHARED = new Node();
static final Node EXCLUSIVE = null;
// 节点的4种状态
static final int CANCELLED = 1;
static final int SIGNAL = -1;
static final int ConDITION = -2;
static final int PROPAGATE = -3;
// 获取锁的状态
volatile int waitStatus;
// 前后指针
volatile Node prev;
volatile Node next;
volatile Thread thread;
Node nextWaiter;
}
// CLH队列的头尾指针
private transient volatile Node head;
private transient volatile Node tail;
// 对象的当前同步状态
private volatile int state;
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long stateOffset;
private static final long headOffset;
private static final long tailOffset;
private static final long waitStatusOffset;
private static final long nextOffset;
static {
try {
// 通过native方法获取变量在内存中的位移
stateOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("state"));
headOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("head"));
tailOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
waitStatusOffset = unsafe.objectFieldOffset
(Node.class.getDeclaredField("waitStatus"));
nextOffset = unsafe.objectFieldOffset
(Node.class.getDeclaredField("next"));
} catch (Exception ex) { throw new Error(ex); }
}
}
AQS的设计模式采用的模板方法模式，子类通过继承的方式，实现它的抽象方法来管理同步状态，对于子类而言它并没有太多的活要做，AQS提供了大量的模板方法来实现同步。
