多线程下自旋锁设计基本思想

多个进程（线程）之间关系

无关进程（线程）：各个进程（线程）之间各自独立运行，相互之间不会相互影响，也没有任何数据共享。

相关进程（线程）：相关进程（线程）的运行结果因为除自身外与其他多个进程之间直接和间接的交互（通过共享某些变量或消息传递）以及由此引发的影响而变化，由于各个进程执行的结果并不总是确定的（例如:进程本身的异常，时间相关的不确定性：结果不唯一（不同时间不同结果）或永远等待）使得得到的最终结果具有不确定性，所以这种交互必须是有控制的。同时，当多个相关进程需要在共享资源上并发执行或协作完成同一任务时，会产生相互制约关系，必须对它们并发执行的次序加以协调。

进程之间的制约关系分类：

协作-直接制约关系（进程（线程）-进程（线程））：

某些进程（线程）为完成同一任务需要分工协作，这些进程（线程）需要按照一定的正确顺序执行才能保证执行正确并得到符合期望的任务执行结果。由于参与合作的每一个进程（线程）都是独立地以不可预知的速度推进，这就需要相互合作的进程（线程）在某些协调点上对并发执行的次序(即相对执行速率)加以协调，控制自己的执行速度，这便导致了进程（线程）之间的直接制约，而这些制约关系则保证了进程（线程）能以正确顺序的执行。进程间的协作（直接制约关系）可以是双方不知道对方名称或标识的间接协作，例如，两个进程（线程）通过共享访问一个队列进行相互影响的生产者/消费者模式或通过网络收发消息就属于这类（间接）松散式协作；也可以是双方知道对方实例的名称或标识，直接通过通信机制进行紧密协作，远程过程调用 RPC。

直接制约关系具有几种分类：单向依赖关系，互相依赖关系

单向依赖关系：

1)依据业务流程，进程（线程）A 的方法 1 执行之前必须先执行进程（线程）B 方法 2。

图 1

2)进程（线程）B 方法 2 依赖进程（线程）A 的方法 1 执行结果作为输入

图 2

相互依赖关系：

进程（线程）A 和进程（线程）B 相互依赖，如进程（线程）A 中的方法 1 指令的执行依赖于进程 B 中的方法 2 的执行结果，而进程 B 中的方法 3 的执行依赖于进程 A 中方法 1 的执行，而若是进程 A 的第一次执行不受限制，那么可以反复的执行进程 A 和进程 B 中的指令，这就是相互依赖关系

图 3

竞争-间接制约关系("进程（线程）-资源-进程（线程）")：

很多时候，系统中的多个进程之间以及同一个进程内的线程彼此无直接依赖关系，它们并不知道其他进程（线程）的存在，并且也不受其他进程（线程）执行的影响。例如，windows 操作系统中为多个不同的用户账户建立的多个用户进程， web 服务器多个 request 请求。然而，计算机的资源是有限的，为了提升系统的整体资源利用率，各个进程(线程)必然会共享内存，打印机，磁盘等资源。由于各个进程（线程）自行独立运行，当多个进程(线程)同时需要使用这些资源时就会出现竞争。

图 4

竞争就不可避免的涉及到程序的竞态条件(race condition)，在竞态条件下进程(线程)的行为（输出）不再是孤立的，而是取决于多个线程或进程的事件发生的时间或顺序（多个进程（线程）共享同一个时间线。单个进程可以看作一个状态机，若状态机的状态发生变化，则将这个变化称为事件，这里假设事件是瞬时的）。例如：当多个进程（线程）同时执行下面提供的相同代码，当多个线程访问的共享变量 A 时，共享变量的 A 值不再由单一进程（线程）的代码孤立决定而是一个由多个和时间相关的进程（线程）执行顺序组合的结果。这里，所以 A 的值可能是 7 可能是 15 取决于是方法 Y 先执行还是方法 X 先执行。

图 5

多个进程（线程）之间协调：

同步

为了处理直接制约关系，最基本的协调方式是同步。同步 synchronization （名词 ）的原始意义为：同时发生的事实或使事情同时发生的动作。在计算机系统中分为进程同步和数据同步。进程同步一般指多个进程或线程同时运行时的场景下，多个进程在某个点加入或握手，以便达成一致或共同的行动顺序。暂停等待已取得协调的那一点，又称为同步点；需要等待的由其他进程完成的操作或发送的信息，称为同步条件。同步通过对于同步点上的协调实现了进程（线程）之间的直接制约关系，直接制约关系的协调方式有两类情形：

1）进程（线程）B 方法 2 依赖进程（线程）A 的方法 1 执行结果作为输入。

图 6

假设有一个进程 A 到达协调点后，在尚未得到其合作进程发来的消息或信号之前应保持自己的当前状态并阻塞自己，直到其他合作进程发来信号量后方被唤醒并继续执行

2）依据业务流程进程 B 执行之前必须执行进程 A，同时这进程 B 和进程 A 没有直接的交互，为了保证这一点，系统需要定义一个时钟同步 check 进程它不断的将时间与预定事件列表进行比较，并根据事件按时间的发生顺序来对进程 A，进程 B 发送相应的信号来保证相应的执行顺序：

图 7

从计算机设计者的角度来看，与时钟同步的动作与由来自另一个程序的信号触发的动作没有什么不同：都可以表述为信号的交换。由此可以看出，在协调点，进程进行了信息交换并基于合作进程的信号或消息决定自身下一步的工作，当前进程的执行基于外界输入信息以及自身的信息共同决定而不再是仅限于自身，这种合作进程之间相互等待对方消息或信号的协调关系称为进程同步。

互斥

除了同步以外，为了保证在多线程下程序在竞态条件下仍能正确的运行，计算机科学中常采用的协调策略是互斥。首先，将共享的资源（例如：共用设备磁盘，打印机或是内存共享变量）抽象为临界区概念，当两个进程（线程）同时进入临界区，会产生与时间有关的错误，例如：两个进程（线程）同时进入一个共享变量时就会由于竞态条件的存在，导致共享变量内数据的不一致并产生与时间相关的错误。通过互斥防止来两个线程同时进入临界区，保住线程只能一个一个进入。

图 8

任何程序的正确性都要求符合两个基本原则：

安全属性（safety property）----坏事不会发生。

活力属性（liveness property）----好事最终会发生。

基于互斥设计协调进程（线程）进入临界区并符合这两个原则的协议的基本有如下基本属性：

1、任何时候，处于临界区内的进程（线程）数量不可多于一个，符合安全属性（safety property）（互斥）。

2、如果有若干进程（线程）要求进入空闲的临界区则必定有一个成功 ，符合安全属性 (safety property)。如果一个进程（线程）要求进入临界区但一直没有成功，则必有其他进程（线程）无限占用临界区。例如：进程（线程）Pa 占有临界区 A 请求进入临界区 B，进程（线程）Pb 占有 B 临界区请求进入临界区 A。双放都等待的请求进入对方的临界区，同时没有退出自己占用的临界区的机制，则两者都会陷入无尽的等待中，这便是死锁（避免死锁）。

3、每一个试图获取锁的进程（线程）最终都会成功，符合活力属性 (liveness property) 。若多个线程在面对竞态条件时，当某一个占用着 CPU 线程需要某个资源时，若这个线程检测到自己所需要的资源被其他线程占用，由于线程内的程序逻辑选择退出竞争，从而使这个线程所占用的 CPU 并没有真正得到所需要的资源来完成相应的业务逻辑执行，从而浪费宝贵的 CPU 时间。若线程对应资源竞争激烈，则容易发生某些线程始终找不到空闲资源，从而一直选择退出竞争的情况进入无限等待的情况，从而产生“饥饿”。

锁

互斥类协调方式的一类标准实现方式通过是锁对象来对于临界区访问进行控制。因此，锁都具有两个基本的行为来分别对应临界区的控制权：允许获取（加锁）以及归还释放（解锁）。通过对于这加锁与解锁的协调以实现共享资源的互斥协调。那么如何设计一个高效率的锁呢？

 interface lock {      lock();//获取（加锁）      unlock(); //归还释放（解锁） }

代码 1

两个线程下的锁设计

线程互斥关系中最简单场景是两个线程竞争的场景。 假设有 A，B 两个线程各种对应索引 0，1，这两个线程之间的执行先后关系有两种可能：A 线程在 B 线程之前开始执行或 A 线程和 B 线程同时开始执行。

1）在 A 线程在 B 线程之前开始执行

class LockForOneThreadfirst {private volatile boolean[] threadlocktokens = new boolean[2]; //数组被内存屏障所保护，系统的锁状态// 假设当前thread的索引为 0 或 1public void lock() {int i = currentThreadID.get(); //0 int j = 1 - i;   threadlocktoken [i] = true;   //试图获得锁，需要进入临界区 while (threadlocktokens [j]) {} // 若对方获得了锁，不断重试（等待） } public void unlock() {int i = currentThreadID.get();threadlocktokens [i] = false;  //解锁，退出临界区 } }

代码 2

保证互斥：为了得到各个线程对应的锁状态情况，可以使用布尔值数组来代表 2 个线程下系统的整体锁状态。若线程 A 得到锁则将其线程索引 0 对应的数组元素内的值设为 true（设置加锁标志），并查看另一个线程 B 对应的线程索引 0 对应的数组元素内的值。若那个值为为 true，则说明另外一个线程 B 已经获取了锁，线程 A 被排斥无法进入临界区，开始循环重试（等待），直到线程 B 将其对应的锁状态重新设为 false（临界区释放，解锁），否则加锁成功，线程 A 可以进入临界区。B 线程使用了同样的步骤与逻辑，从而保证了临界区的互斥的实现。

防止死锁：在保证 A 线程在 B 线程之前开始执行的场景下，可以防止死锁的发生，若两个线程同时发生则会发生死锁。

防止活锁：如果每次线程 B 在完成 unlock 操作后，在 A 检查 threadlocktokens 之前又再次调用了 lock()操作并设置 threadlocktoken 为 true，则会发生活锁。

2）在 A 线程在 B 线程同时执行

class LockForTwoThreadAtTheSameTime implements Lock { private volatile int threadlockstatus; //系统的锁状态 public void lock() { int i = currentThreadID.get();// 假设当前thread的索引为 0 或 1 threadlockstatus = i; // 将线程索引存入系统的锁状态中，使线程索引是否是当前值等同于获得锁的状态 while (threadlockstatus == i) {}  //采用谦让原则，当前线程不能获得锁，以当前的线程的id的与锁保存的值相等与否作为锁是否能被获取条件。若相等则说明当前两个线程没有并发运行,没有线程可以谦让， //需要不断重试（等待），否则因为另外一个线程在行4修正了threadlockstatus，说明有另外一个线程要获取锁. } public void unlock() {}  //由于锁状态会由另一个线程进行改变，所以无需解锁。 }

代码 3

保证互斥：为了得到各个线程对应的锁状态情况，可以使用一个 int 类型的值类型来保持两个线程下系统的整体锁状态。这类锁采用谦让策略，即若这个线程检测到自己所需要的资源被其他线程占用，由于线程内的程序逻辑选择退出竞争。当两个线程同时开始，对于锁的状态会出现如： 线程 A 写入 threadlockstatus = 0 （代码第五行，假设线程 A 索引=0）→ 线程 B 写入 threadlockstatus =1 （代码第五行，假设线程 B 索引=1）→ 线程 A 读出 threadlockstatus == 1 （代码第六行 threadlockstatus 不等于线程 A 索引“0”），从而使线程 A 得以进入临界区， 否则线程 A 便会退出竞争，不断重试等待另外一个线程调用 lock() ，从而保证了临界区的互斥的实现。

防止死锁：在保证两个线程同时发生的场景下，可以防止死锁的发生，若 A 个线程在 B 线程之前发生并执行结束则会发生死锁，双方都在等待另外一线程再一次调用 lock 方法并改变 threadlockstatus 的值。

防止活锁：若线程 B 没有试图重复进入临界区，则线程 A 会一直循环而陷入活锁。

3）普林斯顿锁（Peterson Lock）

若将 LockForOneThreadfirst 与 LockForTwoThreadAtTheSameTime 组合便得到了普林斯顿锁。

 class PetersonLock implements Lock { // 假设当前thread的索引为 0 或 1 private volatile boolean[] threadlocktokens  = new boolean[2]; private volatile int threadlockstatus; public void lock() { int i = currentThreadID.get(); int j = 1 - i; threadlocktokens[i] = true; //试图获得锁，需要进入临界区 threadlockstatus = i;  while ( threadlocktokens[j] &&  threadlockstatus == i) {}; // 若另外一个线程需要获得锁，且基于谦让原则，当前线程不能获得锁，以当前的线程的id的与锁保存的值相等与否作为锁是否能被获取条件。 //若相等则说明当前两个线程没有并发运行,没有线程可以谦让，需要不断重试（等待），否则因为另外一个线程在行9修正了threadlockstatus，说明有另外一个线程要获取锁.  } public void unlock() { int i = currentThreadID.get(); threadlocktokens[i] = false; // 解锁，退出临界区 } }

代码 4

保证互斥：由于 LockForOneThreadfirst 与 LockForTwoThreadAtTheSameTime 各自对应情景互为补充，可以结合这两类锁得到普林斯顿锁。行 10 （threadlocktokens[j] && threadlockstatus == i ）表示了系统的两类情况相结合的系统锁的整体状态。 若线程 A 在线程 B 之前执行，则由于 threadlocktokens[j]=false 而可以进入临界区 。若两个线程同时开始，则线程 B 会如 LockForTwoThreadAtTheSameTime 一样在行 9 修正了 threadlockstatus 的值，从而一样可以进入临界区。 若对方获得了锁，且当前的线程的 id 等于锁的状态，则退出竞争不断重试（等待）

防止死锁：普林斯顿锁由于覆盖了两个线程顺序与并发两类情况，从而在系统保证在临界区执行的线程最终会退出临界区的的情况下，可以防止死锁的情况。

防止活锁：普林斯顿锁可以防止活锁，因为 LockForOneThreadfirst 的活锁情况可以通过 threadlockstatus == i 规避，而 LockForTwoThreadAtTheSameTime 则可以通过 unlock 操作的 threadlocktokens[i] = false 规避。

多个线程下的锁设计

普林斯顿锁体现了两个线程下场景下的锁设计如何符合两个基本原则 安全属性（safety property）与活力属性（liveness property）的基本思路。可以将这个思路进行相应的泛化，从而设计出可以应用在多个线程的场景之下的锁。除此以外，线程进入临界区的等待时间长短也是一个重要的问题。虽然普林斯顿锁可以防止活锁，但是并不能保证每个线程需要等多久可以进入临界区，这取决于其他线程以及相应调度机制。调度机制一般对应线程进入临界区的公平性。理想情况下，线程进入临界区顺序的公平的判断和日常生活中一致都是基于先来先服务的原则，即如果线程 A 比线程 B 先发起进入临界区的要求（调用 lock 方法），则线程 A 会比线程 B 先进入临界区。可问题是在并发情况下，实际的系统并不能决定那一个线程会第一个调用 lock 方法。由此可以将 lock 方法含有两个部分：

1. 门道（doorway）部分，这个执行区间由有限数量的步骤组成（无等待部分）。（代码 4: 行 5-行 9）

2. 等待（wait）部分，这个执行区间可能由无限数量的步骤组成。（代码 4: 行 10）

若当一个锁遵循先来先服务的原则，且系统对于线程调用门道（doorway）部分的先后顺序决定了线程进入临界区的先后顺序，则当线程 A 的完成它的门道部分在线程 B 开始它的门道部分之前完成，则系统将保证线程 A 比线程 B 先进入临界区。

Lamport 面包房锁（ Lamport’s Bakery lock）

由于 Lamport 发明的面包房锁便是符合上述设计要求的一种基于先来先服务原则的可以适用于多线程场景下的最简单的锁。

class Bakery implements Lock {private volatile boolean[] threadlocktokens ;private volatile int[] threadlabel;private volatile int threadcount；private static Bakery single_instance = null;
public static Bakery getInstance(int n) //输入最大线程数量{ if (single_instance == null )            single_instance = new  Bakery(n); return single_instance; }    private Bakery (int n) {
threadlocktokens= new boolean[n];threadlabels = new int[n];threadcount=n; //保存最大线程数量for (int i = 0; i < n; i++) {threadlocktokens[i] = false; threadlabels[i] = 0;}}public void lock() {int i =  currentThreadID.get();threadlocktokens[i] = true;threadlabels[i] = max(threadlabels[0], ..., threadlabels[n-1]) + 1; //分配队列中最大的编号，并发线程可能分配到相同的threadlabels编号for (int k = 0; k < threadcount-1; k++) //对于整个线程队列的每一个线程进行检查{   while (threadlocktokens[k] && ((threadlabels[k],k) << (threadlabels[i],i))   //如果已经有线程表示需要获得锁，并且其编号小于当前线程的编号（由于多个线程可能分配到相同的编号，通过字典顺序（如果threadlabels编号相同则对比线程索引））  //则当前线程退出竞争并继续循环（等待）  {};}} public void unlock() {threadlocktokens[currentThreadID.get()] = false; }}

代码 5

保证互斥：行 27 “(threadlocktokens[k] && ((threadlabels[k],k) <<(threadlabels[i],i) ” 采用了普林斯顿锁类似的整体锁状态，不同的是采用了先到先服务的调度方式，每一个线程在门道里面得到一个编号，然后等待直到在其之前领到号的线程都已经进入了临界区，它才有机会试图进入临界区。

防止死锁：在系统保证在临界区执行的线程最终会退出临界区的的情况下，可以防止死锁的情况。

防止活锁：和普林斯顿锁类似的原理，面包房锁可以防止活锁。

程序执行的推进条件与锁状态的共识

由 Lamport 面包房锁的设计可以看出，锁的设计涉及两个重要的概念：程序执行的推进条件（Progress Conditions）以及锁状态的共识

锁状态的共识：若没有线程试图进入或已经在临界区，则锁对象的状态必须和系统全局状态相一致（全局状态：所有对象状态与所有线程本地状态的总和），同时所有的线程要对于这时的锁对象的状态达成共识，因为只有这样单个线程才能决定是否应该去申请进入临界区。如此任何能够防止死锁的锁算法都不会进入一个不一致的全局状态。

程序执行的推进条件：意味着线程在何种条件下可以继续执行。由于互斥以及线程运行环境的存在，所以程序的执行推进条件从 2 个纬度构成对应的特性：

环境：有依赖/无依赖。

实现：有阻塞/无阻塞。

无等待特性/无锁特性：具有无等待特性的数据结构可以保证任何线程都能在有限的步骤内完成其需要执行的操作，如果某一个线程因为某些原因无法继续执行，其他线程仍旧可以继续运行不受影响，同时其也实现了无依赖/无阻塞的推进条件，Lamport 面包房锁的门道部分代码（代码 5 行 24-27）便具有有边界的无等待特性。无等待特性 通过多个进程（线程）之间通过同步达成共识，其避免了由互斥造成的死锁、低效、恢复、优先级逆转等问题。比无等待特性弱一些的是无锁特性。若某个数据结构具有无锁特性，则它可以保证虽然某个操作虽然总体上会被无限次的调用，但是部分线程对这个操作的调用会在有限的步骤中完成，无锁特性在部分线程中实现了无依赖，无阻塞的推进条件。实现无锁特性的系统仍旧会有“饥饿”情况出现，毕竟只有部分线程才能有限的步骤中完成调用，其他线程可能会一直等待而没有机会执行。无等待特性必然是无锁特性的，但是无锁特性不是无等待特性的。无等待特性排除了互斥的情景，而且为了保持线程的独立性，不能依赖操作系统的调度，这便要求系统的寄存器的实现本身具有无等待特性。无等待特性的实现可以通过线性一致性（线性一致性是非阻塞特性，可组合的特性，实现线性一致性的系统的每个对象都必然是线性一致性的，所以每个对象也必然是具有非阻塞特性的）进行验证，实现了线性一致性也就实现了无等待特性。

无阻碍特性：无阻碍物特性就属于有依赖，无阻塞的推进条件。无阻碍特性指的是单个线程在某一个点之后能够独自运行且不会受到任何其他线程的阻碍从而可以在有限的步骤后结束。无锁特性必然是无障碍物特性的，但是无障碍物特性不是无锁特性的。

死锁或者活锁下的推进：有依赖，有阻塞的推进条件一般指程序代码的执行会有阻塞（阻塞：互斥场景下，一个线程的意外延迟可能会阻止其他线程取得进展），并且对其外界平台或环境（往往指操作系统）有依赖。前面提及的死锁或者活锁的避免属于有依赖/有阻塞的推进条件。它们需要依赖操作系统保证能够让每一个线程最终并及时的的离开临界区来实现的。

无等待特性使每个线程都能够保证程序执行的推进，它避免了死锁， 和有阻塞的实现相抵的相比显得很有优势。然而，刻意追求无等待作为设计目标一方面会使系统设计难度变高，另一方面设计不佳的无等待实现的执行效率也往往不佳。所以，一般选取相对较弱的无阻塞设计例如：无锁特性作为设计目标显得更符合实际系统。尽管无锁设计可能会有“饥饿”情况，然而如果经过与其他系统设计因素以及系统需求的权衡之后，发现可以接受这样的风险且系统的执行效率在需求中的比重更高，则高效的无锁特性更加适合。

同步原语（Synchronization Primitive）

同步原语指的是将基本同步指令视为对象，它们对外导出的方法被视作指令自身，这些方法便称为同步原语。同步原语是解决在共享内存的系统中，线程间同步问题并达成共识的基石。并发对象是一类使多个线程达成共识的数据结构。一个并发对象（或共享对象）的无等待（wait free）共识实现能够通过具有相同的同步数量的任意其他类似对象来构建，所以其也是构建无等待以比其弱的及无锁等实现的基础。若需要线程摆脱对于环境的依赖以实现无等待特性，则线程操作所需要的寄存器的实现本身需要具有无等待特性，这也意味着寄存器本身具必须有线性一致性。原子寄存器是寄存器的线性化实现，所以实现同步原语的原子寄存器成为了现在解决线程间同步问题以及无等待实现的基础。系统可以通过一组调用实现同步原语的原子寄存器的 decide 方法来处理各个线程需要达成共识的值以及随后一些执行步骤来组成各类共识协议。每个线程可以调用共识 decide 方法最多一次，通过这个方法来对各个进程的输入的值进行决策，从而保证这个方法返回的值具有以下两点：

1） 所有线程需要对某一个值达成一致

2 ）这个达成一致的值必须是某一个线程的输入值

由于同步原语是多种多样的，选择实现哪些同步原语以原子寄存器实现并提供是当下多核 CPU 设计的一个重要方面。不同的同步原语解决线程的同步并达成共识的能力是不同的，1991 年 Herlihy 的论文 Wait-free synchronization 提出通过基于同步原语的共识协议 (consensus protocol) 对于多个进程（线程）下对于任意多个进程（线程）的输入达成共识的能力来衡量同步原语的同步能力。由于不存在使用低共识数字的对象用来实现高共识数字的方法，所以形成了如下的等级结构：

上述同步原语与对象中 getAndSet(), getAndAdd()与 compareAndSet()等都属于 Read-Modify-Write（RMW）类原子寄存器，Read-Modify-Write（RMW）类指一种通用的原子寄存器模式，其能原子的完成将寄存器中当前 v 值替换为一个函数 f(v)的值的操作。由于 Read-Modify-Write（RMW）类原语适合使用的场景范围非常广泛，当前的 x86 实现了指令 CMPXCHG 以对应 Compare-And-Swap (CAS)、操作系统以及开发语言对于 RMW 类同步原语都有支持。

例如：对于 getAndAdd()原语在 Win32 中有 _InterlockedIncrement，

C++11 中有 std::atomic::fetch_add。

而 compareAndSet()则被称为“原语之王”。由于 compareAndSet()原子寄存器原语由于具有无限的共识数目，所以成为了最广泛使用的原语，主流的 CPU 指令集都有对应的实现（例如：intel CPU 指令 CMPXCHG）。compareAndSet() 含有 2 个参数，第一个是预期的值，第二个是更新值。 使用 compareAndSet 原语可以在任意对象中实现无等待特性，所以几乎所有的开发语言例如：Java 语言等，在任何适宜使用无等待特性的并发实现（可参考 java.util.concurrent.atomic 包的实现）中几乎都使用了 compareAndSet。然而在某些场景（如基于对象引用进行操作的场景），compareAndSet 容易造成 ABA 问题。对于当代开发语言来说，对象引用是基本设计思想之一，是面向对象的基础，所以基于 compareAndSet 对对象引用进行搞并发操作时：若线程 A 对同一对象引用（内存地址）进行了两次读操作，而两次读操作得到了相同的对象引用（内存地址）。这时，如果采用 "引用地址相同" 作为判定 "对象实例没有变化"的依据，则会有几率出现以下场景：在这两次读操作的时间间隔之内，线程 B 可能已经修改了该对象实例的某一个属性的值，那么对于前一个线程 A 来说，对象的实例已经被改变而无法被察觉。

void propose(T value) {proposed[ThreadID.get()] = value; //当前线程的index } ·class CASConsensus extends ConsensusProtocol {private final int INIT = -1; //假设与任何线程提供的索引值都不相同private AtomicInteger rmw = new AtomicInteger(FIRST);private volatile int setValue=0；public Object decide(Object value) {propose(value); //保存当前线程输入的值并放入对应的存储空间int i = ThreadID.get();if (rmw.compareAndSet(INIT, i)) // 若当前值是FIRST则说明当前线程是第一个线程，并将i存入r并返回其对应的值，从而当后面的线程调用时，r的值再也不会和INIT一致setValue=i；//r的值便不会更新，而只能返回第一个线程存入的值return proposed[i]; //返回当前线程返回的值else // 不是第一个，而是任意数量的其他线程return proposed[setValue]; // 第一个线程对应的值，从而达成共识 }}

实际系统中锁设计限制

早期由于硬件的限制，计算机只能提供基本同步原语(原子寄存器 (atomic registers) 的读、写)和少数经典原语。理论上仅使用基本同步原语可以实现多进程（线程）下符合安全属性和活力属性的锁，例如上面介绍的普林斯顿锁，伯克利锁以及其他的如过滤锁等都可以实现。但是，这类锁有如下的限制：

1）任何能够防止死锁的锁设计算法，如果只通过读、写内存，则在最糟糕的情况下都需要有至少 n 个不同的地址空间来存放各个进程（线程）的独有信息(如进程/线程的唯一标签）。

由此可以看出，在使用这类锁的系统中，每一个锁都需要预先确定其所需的内存空间，进程（线程）数量越多则需要的内存空间必然越多，两者之间呈正相关关系。这对于内存资源宝贵的计算系统来说容易出现内存溢出。对于一个只能通过读、写访问内存地址的系统来说，如果想减少内存方面的占用负担，必然需要将每个锁所需要的内存空间限定在一个有限范围，这便需要处理一个棘手的问题，即某一个线程在某个地址空间信息被其他的进程或线程所覆盖。

2）这类锁都需要系统保证读、写是原子操作，并能保证系统内存的读、写操作在多进程（线程）下仍能保证线性一致性或顺序一致性。即系统中的任意两个内存地址，如果由同一个进程（线程）访问，即使是两个分开的不同变量，系统的总体执行顺序能仍能保证会按程序代码的执行顺序生效。

这一假设在当前的处理器架构中不能成立，当代处理器的内存模型（Memory Model）并不能多个线程代码及其对应 cpu 在访问系统内存时提供顺序一致性。为了补偿高速缓存一致性 MESI 协议在执行方面的性能损失（考虑一个简单情景，假设某个 CPU 内核要对变量 A 存入值“1”，但发现其拥有的缓存行不存在某个变量 A，则说明它需要的变量在其他 CPU 的缓存中，所以这个 CPU 需要发送"read invalidate"消息，并获取缓存行，并且告知其他 CPU 丢弃该缓存行，然后该 CPU 必须等待，直到收到来自其他 CPU 的确认响应为止），在 cpu 内核和 cache 之间加入一个 store buffer。cpu 内核可以先将数据写到 store buffer，同时给其他 cpu 发送消息，继续异步执行其他操作，同时等待其他 CPU 内存对于 read invalidate 的响应，再将数据从 store buffer 移到缓存行,store buffer 提升了 CPU 内核的允许效率。但是，如果内存全部基于 cache 读取数据的话，store buffer 内的值会由于 CPU 的异步操作出现和 cache 的值不统一的情况，（例如：CPU 内核收到了"read invalidate"的 response 生成了变量 A 并初始化为 0 还没有来得及 store buffer 的值存入，这个时候变量 A 给 CPU 读取就会出错。）,由此又加入了 Store Forwarding 技术:cpu 可以直接从 store buffer 中加载数据，即支持将 cpu 内核存入 store buffer 的数据传递(forwarding)给后续的加载操作。然而绕过 cache，又会发生内核得到值的顺序和程序代码顺序不统一的问题，使写操作在服务器共享的主内存不一定保证实时完成也就是不能保证线性一致性。由于在大多数程序中，绝大多数的写操作不需要立即在共享主内存中生效，所以经过权衡还是被广泛使用了。因此，现代多处理器通常不能提供具有顺序一致能力的主内存，也不保证单个线程读写能按照程序编写顺序执行。（当然，在必须保证写操作在主内存的实时完成以保证执行顺序的准确的场景之下，现在计算机体系结构提供了内存屏障（memory barrier）。例如：java 中的 volatile 关键字，来强制保证相应的未完全执行完毕的指令发生作用。这种方式所带来的副作用是，由于内存屏障（memory barrier）需要的性能代价较高，绝大多数操作又用不上，所以需要由程序员来决定什么时间使用。）综上所述一个实际可用的锁的设计无法基于同步数目等于一的原子读、写寄存器 (atomic registers) ，而必须使用更为复杂的基于更高等级共识数目的同步原语。

实际系统中锁设计

从上一节的描述中可以看到，一个实际可用的锁的设计无法基于同步数目等于一的原子读、写寄存器 (atomic registers) 得到，而是必须使用更为复杂的基于更高等级共识数目的同步原语以突破限制。除此以外，锁的设计对于获取锁失败的处理情景也要进行考虑。

获取锁失败的处理（阻塞与自旋锁）

在互斥场景下能够进入临界区的只有一个线程，而其他锁都必然是失败者。采用何种策略安排这些失败者， 对于锁的效率影响很大。能给出处理策略有两个：

第一类主动等待：线程在无法进入临界区时主动选择等待，进入不断继续重试也就是自旋模式，使用这种方式可以减少由线程切换造成的系统资源浪费，这在多核处理器下才有意义。

第二类被动等待：阻塞当前进程（线程）切换到其他线程。当当前线程有长时间的阻塞，其占用系统资源的造成的代价比线程切换更大时，这个策略较有意义。

在多核处理器下，一般锁的设计都是这两类策略的混用，先自旋一段时间然后阻塞这样比较符合实际需求场景。

基于同步原语的自旋锁设计

下面对于多核处理器下的几类自旋类锁进行介绍(Java 语言提供了包含内存屏障的关键字 volatile 以保证读写正确，以及 atomic 包，lock 包，提供了 getAndSet()以及 compareAndSet()等丰富的同步指令，所以选择 Java 语言作为说明使用的语言)：

TAS（ test-and-set ）锁：

TAS 锁基于共识数目为 2 的 test-and-set 同步指令实现，test-and-set 是早期多处理器都会提供的同步原语，此原语保证原子的保存 true 值在字节内并返回字节中原来保存的值，并将保存的 true 值作为当前值。

public class TASLock { private AtomicBoolean lockstate = new AtomicBoolean(false); // 加锁 public void lock() { while (lockstate.getAndSet(true)) {  //getAndSet(true) 等同于test-and-set，会造成CPU内核缓存失效} } // 解锁 public void unlock() { lockstate.set(false);   } }

若将 java.util.concurrent.atomic 包中的原子类型实现类AtomicBoolean类的方法 getAndSet()并将参数设为 ture，则 getAndSet(true)便和 test-and-set 具有相同语义，并能保证多线程下数据的一致性。所以 TASLock 的 java 语言实现选择 AtomicBoolean 类型的字段 state 来标示锁的状态，初始值为 false。state 为 true 说明某个线程占有锁，false 则说明锁空闲。

加锁的过程如下：假设有 a、b、c 等多个线程。若 a 线程先执行并需要进入临界区故而试图获得 lock，此时获取的 state 是 false 也就意味着可以获得锁并进入临界区，所以 a 线程会直接退出尝试循环，并通过将 state 设置为 true 表示已经临界区已经占用。此时，b 线程或 c 线程开始执行，因为也需要进入临界区故而也申请获得锁，此时 b 线程或 c 线程获取的锁的 state 值是 true，也就是锁已经被使用，获取锁失败。这时，线程 b 或 c 线程采取的策略是自旋也就是通过重复的执行 getAndSet 操作来不停的试图获取锁。如果此时线程 a 在临界区执行退出临界区并交出锁也就调用 unlock()方法，则设置 state 为 false，此时，若正在不停重试试图获取锁的 b 线程或 c 线程将检测到锁状态 state 为 false，说明临界区已控，其他线程可以进入临界区了，则在重试的线程中随机有一个线程将设置 state 为 true，表明这个线程获取锁成功，并退出重试获取锁的循环，从而进入临界区。

图 9

TTASlock 锁

TASLock 锁虽然比较简单，但是其执行效率随着线程争用数量的增加而呈指数级下降。这是由于 TASLock 通过直接重复执行 getAndSet 方法来试图获取锁，由于 getAndSet 方法本质上通过原子同步原语 CAS 的实现，其必然使用内存屏障。当试图进入临界区的线程失败而选择进行自旋测试时，这意味着每自旋一次（getandset）该线程都会去设置 state 值，并由于使用内存屏障而通过总线导致其他 CPU 内核的本地缓存无效，CPU 每次读取本地缓存都会发现不命中的情况，从而只能通过系统总线从主内存中得到最新的数据。频繁的缓存缺失会导致总线资源被严重的占用（每次都得从主存中加载值）甚至导致解锁线程因为总线资源的阻塞而延迟，所以对于总线资源的消耗极大，从而造成系统性能的下降。因此，针对 TASLocks 锁在缓存方面的问题进行改进，提出了 TTASlock 锁。

public class TTASLock {private AtomicBoolean lockstate = new AtomicBoolean(false);// 加锁public void lock() {while (true) {  while (lockstate.get()) {//检查锁状态部分：只读自旋不会引发数据修正从而造成CPU内核缓存失效，第一次除外}if (!lockstate.getAndSet(true)) {  //获得锁部分：仅在临界区空出来后，第一个获得的临界区线程会造成缓存失效，//即使有其他线程已经通过检查锁状态这一部分代码并得到false，由于getAndSet使用属于原子寄存器的原语，所以只有一个线程会得到falsebreak;}}}// 解锁public void unlock() {state.set(false);}}

TTASlock 锁基于 TASLock 锁进行了相应的优化，优化主要集中于在多个线程在使用自旋策略下锁状态的检查与更新方面。依据锁状态的检查和更新分为检查锁状态和获得锁两部分，当线程 a 先试图获取锁时，先进入无限循环，然后在此循环中通过 get 方法读取锁状态判断 state 的值是否为 true 也就是锁已经被其他线程占领。如果为 true，则进入只读自旋检查锁的状态。如果发现 state 为 false，锁可以获得，此时跳出循环并执行 getAndSet 方法将 state 设置为 true 并取得原先的 false 的值，下一步对于取得原先的锁状态 false 取反从而跳出循环获得锁成功，使当前线程进入临界区。在高并发场景下，这两步之间即使有其他线程已经通过检查锁状态这一部分代码，由于 getAndSet 使属于原子寄存器的原语，所以只有一个线程会得到 false，所有其他线程取反这一步只能为 ture，从而说明已经有其他线程占用了锁，当前线程继续自旋。

TTASlock 锁分为检查锁状态和获得锁两部分的原因是，前文介绍过由于现代 CPU 有 store buffer 的结构的存在，因此利用时间局部性，当某个线程因为获取锁失败而重复访问时，每次读取都是从 CPU 本地的 store buffer 中读取 state 值（本地旋转），从而避免消耗总线资源。

TTASLock 只是改善了 TASLock 的性能问题，当占用临界区的线程易主之时，仍需要进行基于内存屏障进行相应的 CPU 本地缓存同步，从而消耗总线资源，并且竞争锁的线程都会因为 CPU 本地缓存缺失（不命中）从主存中读取 state 值。同时，高度竞争场景下，在 A 线程执行检查锁状态和获得锁两部分之间，若有 B 线程或其他线程也执行了检查锁状态，并试图获取锁，此时会造成了和 TASLock 类似的性能问题。

BackoffLock 锁

既然 TTASLock 仍有性能问题，而我们的设计目标是在大量线程进行高度竞争的场景下，锁的性能仍保持高效。那么接下来如何优化呢？通过前面对于 TTAS 锁的分析，可以发现在高度竞争场景下，当因某个线程获得锁而进行的修正锁状态带来的总线资源消耗对于锁性能影响最明显。解决方式很朴素就是让竞争临界区失败的线程后退（Backoff）一段时间减少竞争，其原理如同一堆行人拥挤在地铁出站闸机想要出战，而一台闸机一次仅能通过一人，人越多越是相互拥挤就会产生相互阻拦，其结果就是闸机这边通过效率快速下降。高效的解决的方式是让一些人后退并等待一段时间以减少拥挤，等前面的行人通过之后，再参与竞争通过闸机，从而提高效率。那么等多久比较合适呢?一般来说竞争越激烈,等待的时间越久。例如:获取锁失败一次就回退一个随机时间,如果再次失败则时间加倍，基于这个思路，可以创建一个负责后退以及等待时间（BackoffAndDelay）的类如下：

 public class BackoffAndDelay { final int minDelay, maxDelay; int delayLimit; final Random random; public BackoffAndDelay (int min, int max) { minDelay = min; //最大等待时间 maxDelay = min; //最小等待时间 limit = minDelay; //最小等待时间 random = new Random(); //随机等待时间 }public void backoff() throws InterruptedException { int delay = random.nextInt(limit); //以最小等待时间为基础，取随机等待时间 limit = Math.min(maxDelay, 2 * limit); //对于最小等待时间进行翻倍 Thread.sleep(delay); //线程进行限时休眠 } }

然后将回退机制和 TTAS 锁相结合，便得到了基于 TTAS 的回退（BackoffTTASLock）锁。

public class BackoffTTASLock implements Lock {private AtomicBoolean lockstate = new AtomicBoolean(false);private static final int MIN_DELAY = ...;  //随系统需求确定private static final int MAX_DELAY = ...;  //随系统需求确定public void lock() {BackoffAndDelay backoff = new BackoffAndDelay(MIN_DELAY, MAX_DELAY);while (true) {   while (lockstate.get())    {};    if (!lockstate.getAndSet(true)) { return;    } else {         backoff.backoff(); //等待一个随机时间 }} }public void unlock() {lockstate.set(false);}...}

虽然 BackoffLock 锁在大量线程竞争的场景下较 TTAS 锁的效率更高，但仍有两个问题没有解决：

1 所有的线程还是在共享的变量上基于 getAndSet 方法自旋，虽然和 TTAS 比要缓和不少，然而 CPU 的缓存一致性问题没有得到彻底解决。

2 临界区的利用率可能下降，如果回退的时间如果设置不合理，那么临界区就可能出现很对线程在后退等待，而临界区反而空闲的情况。

为了处理这两种情况，可以将各个无序的线程进行排队, 由此便推出了基于队列的 Queue Locks 的锁。有了队列,每个线程就可以知道前面的是不是已经处理完毕,就如同我们日常的排队一样,前面空了就立马补上,从而提高了锁的执行效率，以及临界区的利用率。由于排队,各个线程就可以在各自本地缓存自旋而不会造成缓存的一致性问题，且有了队列还能和 Bakery 锁一样提供先来先得的公平调度机制.

Array-Based Locks 基于数组的锁

Array-Based Locks 就是用一个数组 Array 来实现队列（Queue）的锁。对于系统的锁对象整体状态，使用布尔值 true 表示锁的临界区空闲，而变量 capacity 表示 Array-Based Locks 的队列容量的上限。代码中的 queueTail 作为已经在队列里面的最后一个线程的标志,其是一个原子增长的 AtomicInteger 整数，初始值为 0。同时将数组的第一个元素 flag[0]，作为队列的一个虚头部. 线程的队列通过一个布尔值的数组，并将数组第一个的默认值设置为 ture。每当有一个线程试图进入临界区，则通过对于 AtomicInteger 加 1 并基于容量的上限数取模得到相应的数组里面数组下标，然后此数组下标放入各个线程的本地变量（Threadlocal）mySlotIndex（见上文线程结构中的线程局部存储 （thread local storage） TLS 的 Java 实现）中。 然后读取这个下标对应的数组的值作为锁的状态，如果值是 false 则说明锁已经被占，和 TTAS 锁相比主要区别在于锁的状态不再是单一的公共变量而是每个线程有一个锁状态的 copy 由各个线程独立维护，当各个线程重复试图获得锁状态时，尽管 flag 数组是各个线程共用的，但是每次读取都是各个线程自己拥有的数组值使竞争降到了最低，各个线程从 CPU 本地的 store buffer 中读取 state 值（本地旋转），从而最大限度避免了同步和内存屏障，减少了消耗总线资源。

public class ArrayQueueLock implements Lock {ThreadLocal<Integer> mySlotIndex = new ThreadLocal<Integer> (){ //使用java语言中的ThreadLocal，从而来保存这个线程对应的索引值protected Integer initialValue() {return 0; } };AtomicInteger queueTail;boolean[] queue;//每个线程对应数组的一个元素int maxsize;public ArrayQueueLock (int capacity) { //设置队列容量上限maxsize = capacity; queueTail = new AtomicInteger(0);queue= new boolean[capacity];  queue[0] = true; //第一个虚头部，通过设置true说明当前线程需要获得锁并进入临界区 }public void lock() {int slot = queueTail.getAndIncrement() % maxsize;//当前线程对应索引的一个值 mySlotIndex.set(slot);//在当前线程的ThreadLocal中保存线程在锁数组队列中对应的索引 while (! queue[slot]) {}; //当前线程没有给调度到则自旋等待 }public void unlock() {int slot = mySlotIndex.get();queue[slot] = false;queue[(slot + 1) % maxsize] = true; //将下一个线程对应的数组元素的值通过设置true，并将索引+1从而调度下一个线程获得锁并进入临界区 } }

Array-Based Locks 也有自身的问题，由于 CPU 缓存设计的结构因素，当相邻数据项目（如数组元素）共享于单个缓存行时会发生这类现象，Array-Based Locks 会产生一种称为虚假共享（false sharing）的现象。即，若对于缓存中的某一个行写入某一个值会使该值所在的缓存行无效，然而这会造成这个缓存行里面所有的值无效。由于缓存存放的内容是随机的，所以必然有概率导致其他没有值变化的自旋的线程与造成缓存变化线程落在同一缓存行中，从而造成不必要的总线消耗。为了处理这类情况可以给数组加垫，也就是将 array 扩大，以便将不同的值映射到不同的缓存行的几率加大。但是，这也会造成资源的浪费。

The CLH(Craig, Landin, and Hagersten) Queue Lock

从上一节的介绍可以看出，Array-Based Locks 虽然优点不少，但是它内存使用效率较差，因为其需要一个已知的最大线程数来确定存放每个线程获得的锁状态的数组的大小。如果有 L 个对象需要加锁，即使一个线程对每个对象只需要一个锁也需要 O(L*n) 的空间（n 为线程的数量）。那么如何改进它呢？关键还是在于改进队列 Queue 的结构。设计目标是通过对于 Queue 的结构的改进从而得到一个无活锁发生,并且保证先进先出公平性的锁。Craig, Landin, and Hagersten 三人在 Array-Based Lock 的思路的基础上提出了基于虚链的 CLH 锁。CLH 锁和 Array-Based 锁一样将每个线性得到查询锁状态后得到状态值分别保存，不过 CLH 锁将每个状态保存在一个对应的 Qnode 对象之中。每个 Qnode 是一个 AtomicReference 对象，其可以保证多进程之间对同一个对象引用值的各类操作的原子性（基于 CAS），以保证一致性。当某一个 Qnode 对象的值为 true,则说明其对应的线程试图获得锁对象,如果值为 false 则表明释放了锁对。

CLH 锁的队列可以看作一个逻辑上的虚拟的链表（实际不是）, 当每个线程需要知道排在它前面的线程的锁的情况，则可以通过当前线程的本地缓存 threadlocal 获得。锁初始化的时候在创建队列的尾部也就是 tail 对象，作为最近添加到队列的锁状态。

当线程试图获取一个锁时候(也就是执行 lock 方法) 先创建线程已经获得锁(设置为 true)的状态 Node 对象,通过调用前文说明过的 getAndSet 方法进行值设置到队列 tail 的尾部,并得到前一个线程的锁状态并保存早当前线程的 Threadlocal 类实现的 myPred 字段(线程的 TLS)当中.个当这个状态为 true 则说明这个锁已经被占用,则重复读取这锁状态直到获得锁. 当在临界区的线程离开时便释放这个锁,此时将当前的 node 的状态设为 false。同时,将当前节点设置为队列里面前一个线程的节点,因为前一个线程也做了相同的事情所以这个节点无主可以复用,这主要是为了复用对象以节省内存(对于由 GC 的 Java 来说,可有可无)。

class QNode {        private volatile boolean locked = false;//被第一个线程取得的锁状态必然为false说明临界区为无人占用
        public boolean getLocked() {            return locked;        }
        public void setLocked(boolean locked) {            this.locked = locked;        }    }  public class CLHLock implements Lock { private AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode()); //intanse1 private ThreadLocal<QNode> preThreadLockStateNode;//当前线程前面一个线程的锁对象的缓存，不能省略，防止死锁（假设线程1重复进入而lock方法而线程2的lock的方法 while (pred.getLocked()))还未完成，造成两个线程都指向同一个QNode对象而造成死锁） private ThreadLocal<QNode> currentThreadLockStateNode;//当前线程的锁对象的缓存  public CLHLock() {lastNode = new AtomicReference<QNode>(new QNode());//尾部对象  currentThreadLockStateNode = new ThreadLocal<QNode>() { //当前线程的锁对象的缓存，并初始化锁对象      protected QNode initialValue() {      return new QNode();//intanse2 如果当前线程的ThreadLocal为第一次调用而没有值，则会在其get方法中调用initialValue()，从而得到这个线程对应的新的QNode对象    } }; preThreadLockStateNode = new ThreadLocal<QNode>() {  protected QNode initialValue() { //初始化值为null     return null;     } };} ...}
 public void lock() { QNode qnode = currentThreadLockStateNode.get(); //从当前线程的缓存中得到其锁状态对应的存储节点对象，如果没有则调用 currentThreadLockStateNode的initialValue() qnode.setLocked（true）; //表明当前线程需要获得锁，设置锁状态为true QNode pred = tail.getAndSet(qnode);//得到前一个线程的锁状态的存储节点对象，并保存当前节点的引用与尾部节点连接，从而使当前线程成为最新一个申请临界区的线程。 //如果是第一次调用，则将一个tail初始化的对象返回，若两个线程同时第一次调用，则通过AtomicReference保证原子性，不会两个线程得到同一个qnode对象  preThreadLockStateNode.set(pred);//在前面一个线程的锁对象的缓存中保存前一个线程的锁状态的存储节点对象     while (pred.getLocked())) {}//若当前线程之前一个线程试图获得锁或已经在临界区则当前线程进入等待（自旋） } public void unlock() {   QNode qnode = currentThreadLockStateNode.get(); //得到当前锁   qnode.setLocked(false); //当前线程退出临界区，设置锁状态为false   currentThreadLockStateNode.set(preThreadLockStateNode.get()); //当前线程的锁对象缓存保存前一个线程的锁状态的存储节点对象   //如果当前线程再次调用lock方法，则可以复用前一个线程的Node对象，从而节省内存空间，  } }

Tail 初始化

线程 1（红色表示）先调用 lock 的 tail.getAndSet(qnode)后的快照，两个 threadlocal 缓存所对应的对象。

线程 1（红色表示）与线程 2（黄色表示）同时调用 lock 后，若线程 1 在 t1 时刻先执行了 lock 方法后线程 2 在紧接着的在 t2 时刻也调用了 lock 方法后的对象对应的两个快照的合并快照，两个线程以及 4 个 threadlocal 缓存所对应的对象。

线程 1 执行 unlock()完毕后，线程 2 执行完 lock()中 line37 tail.getAndSet(qnode)后的对象映射的快照，两个线程以及 4 个 threadlocal 缓存所对应的对象。

CLHLock 锁的空间效率较高,在使用线程数量固定的线程池的场景下，可以使用环形连接。由于每个线程最多一个节点。所以 CLHLock 需要的节点空间数量为 O(L + n)，这个数量和 Alock 的 O(L*n)相比有了巨大的精简。在采用 SMP 体系且缓存集中的系统中，CLHLock 锁从各方面看与前面的锁相比已经十分完美了。它唯一缺陷在于，若共享内存的分布式系统使用的是 cache-less，NUMA(Non-Uniform Memory Access)架构则有可能较大的性能惩罚。这是因为 NUMA 架构各个 CPU 的内存都是各自独立持有并不是一个完整的共享内存一个 CPU 读取另外一个 CPU 内存中的内容属于远程内存读取，所以性能会受到影响。当每一个线程通过自旋调用 Qnode 的 getLocked()方法来临界区对应锁状态是否为 false 的时候，若 getLocked()方法属于的这个 QNode 的实例并不属于本地 CPU 而是属于另外一个 CPU 的内存上执行线程所有，则会造成远程内存内容的读取。

MCS（John Mellor-Crummey&Michael Scott ）Lock

针对 CLHLock 锁的缺陷，基于其思路，通过将虚拟的链表实体化，John Mellor-Crummey 和 Michael Scott 发明了 MCS 锁。MCS 提供一个明确的链表来构造自旋锁。Qnode 类增加了 next 字段用来存放当前的 Node 也就是当前线程的锁的状态。在释放锁阶段，将 node 的状态改为 false,并将 next 字段设置为 null 保证链表缩短,在做两件事情之前,要保证除尾节点外，前一个线程的 node 的状态已经放入链表也就是 pred.next=qnode 已经执行了,这个通过 不断的测试 qnode.next==null 来完成。

class QNode {        private volatile boolean locked = false;//被第一个线程取得的锁状态必然为false说明临界区为无人占用        private volatile QNode next = null;        public boolean getLocked() {            return locked;        }
        public void setLocked(boolean locked) {            this.locked = locked;        }                public boolean getNext() {            return  next;        }
        public void setNext(QNode next) {            this. next = next;        }    }    public class MCSLock implements Lock {private AtomicReference<QNode> linktail;private ThreadLocal<QNode> currentThreadLockStateNode;
public MCSLock() {    queue = new AtomicReference<QNode>(null);        currentThreadLockStateNode = new ThreadLocal<QNode>() {    protected QNode initialValue() {    return new QNode(); }};}... } public void lock() { QNode qnode = currentThreadLockStateNode.get(); QNode preThreadLockStateNode = linktail.getAndSet(qnode);//得到前一个线程的锁状态对象 if (preThreadLockStateNode!= null) { //如果是第一次则preThreadLockStateNode为null 则由于tail的Qnode的默认值为false而直接返回并进入临界区。除了第一次外设置当前线程的锁状态为true    qnode.locked.setLocked(true);    preThreadLockStateNode.setNext(qnode);//将前一个线程的锁状态节点指向当前线程的锁状态节点 	while (qnode.getLocked())) {} //和CLH锁不同，若检验当前线程的锁状态节点的状态为true，则自旋阻塞自己，等待前面一个线程放弃其已经占用临界区并释放它的锁   } }  public void unlock() { 	 QNode qnode = currentThreadLockStateNode.get(); //当前线程储存的锁对象    if (qnode.next == null) { //如果当前线程的锁状态链表没有后续线程的锁状态节点   	if (linktail.compareAndSet(qnode, null)) //如果是当前线程的锁对象和尾部对象是同一个对象（通过compareAndSet验证）则说明是最后一个线程，则设置值为null并返回，否则则说明有其他线性调用了lock方法    	  return;            while (qnode.getNext() == null) {} //等待其他线程将lock方法中的line42中的setNext（）方法完成    	}    qnode.getNext().setLocked(false); //当前线程退出临界区，并将下一个线程的锁状态设置为false    qnode.getNext() = null;//并将后一个线程的关联设为空（null），从而离开链接队列。     }

基于自旋锁的扩展

在基于多 CPU 的并行/并发编程的编程实践中，发生临界区竞争的场景众多，需求各不相同。有的场景中对于线程等待锁的时间的最大值需要做出相应的约束.有的场景需要线程满足某些条件才能获得锁，对于线程的阻塞的处理提出了要求，有的场景需要锁可以多于一个进程(线程)可以持有，提供共享锁以提高系统运行效率，例如在读多写少的场景下，读写锁效率更高。有的场景需要同一个线程可以多次获得锁，也就是可重入锁，例如：某段代码在执行时获得了锁，在任意时刻被操作系统中断然后操作系统调度执行另外一段代码，而那段代码又调用了一开始的这段代码并再一次试图获得锁，这时要不会发生死锁，就需要锁可以重复获得也就是重入。有的场景需要锁有公平性，有的场景又需要非公平。对于这众多的场景，自旋锁提供了比较好的扩展性基础，在基本自旋锁的基础上可以通过添加种种逻辑和结构以提供支持。例如：自 JDK1.5 以后，java.util.concurrent 包以 AbstractQueuedSynchronizer 类为基础设计并提供了 ReentrantLock 、ReentrantReadWriteLock 以及条件锁等适用于不同环境的锁。