下载文档原格式
C#lock⾃旋锁，互斥锁，混合锁，读写锁介绍c# 并⾏编程、多线程开发中，经常要⽤到线程锁，so, 看了许多⽂章，想总结⼀下，供⾃⼰理解记忆，以及园丁们参考使⽤，理解的不怎么全⾯，勿喷！在多线程环境中，多个线程可能会同时访问同⼀个资源，为了避免访问发⽣冲突，可以根据访问的复杂程度采取不同的措施，原⼦操作适⽤于简单的单个操作，⽆锁算法适⽤于相对简单的⼀连串操作，⽽线程锁适⽤于复杂的⼀连串操作1.lock锁的解释和⽤法官⽅MSDN的说法：lock 关键字可确保当⼀个线程位于代码的临界区时，另⼀个线程不会进⼊该临界区。
如果其他线程尝试进⼊锁定的代码，则它将⼀直等待（即被阻⽌），直到该对象被释放。
lock 关键字在块的开始处调⽤ Enter，⽽在块的结尾处调⽤ Exit。
ThreadInterruptedException 引发，如果 Interrupt 中断等待输⼊ lock 语句的线程。
通常，应避免锁定 public 类型，否则实例将超出代码的控制范围。
1private static readonly object objlock = new object();2lock (objlock )3 {4//要执⾏的代码逻辑5 }1using System;2using System.Collections.Generic;3using System.Linq;4using System.Text;5using System.Threading;6using System.Threading.Tasks;78namespace LockTest9 {10class Program11 {12static void Main(string[] args)13 {14 TestLock testlock = new TestLock();15 Thread th = new Thread(() =>16 {17//模拟死锁：造成死锁，使lock⽆法释放，在i=5时，跳出死循环，释放lock18 testlock.DoWorkWithLock();19 });20 th.Start();21 Thread.Sleep(1000);22 Thread th2 = new Thread(() =>23 {24//这个地⽅你可能会有疑惑，但存在这种情况，⽐如你封装的dll，对其它开发⼈员不是可见的25//开发⼈员很有可能在他的逻辑中，加上⼀个lock保证⽅法同时被⼀个线程调⽤，但这时有其它的线程正在调⽤该⽅法，26//但并没有释放，死锁了，那么在这⾥就不会被执⾏，除⾮上⾯的线程释放了lock锁定的对象。
【C#线程】SpinLock⾃旋锁
SpinLock⾃旋锁
概述
⾃旋锁是⼀种⾮阻塞锁、低级互斥锁，也就是说，如果某线程需要获取⾃旋锁，但该锁已经被其他线程占⽤时，该线程不会被挂起，⼀直循环在那⾥看是否该⾃旋锁的保持者已经释放了锁，不停的试图获取⾃旋锁会不断的消耗CPU的时间。
"⾃旋"⼀词就是因此⽽得名。
因为⾃旋锁不会引起调⽤者睡眠，所以⾃旋锁的效率远⾼于其他互斥锁。
可⽤于等待时间⾮常短的⽅案，避免了⽤户进程和内核切换的消耗。
SpinLock 不可重⼊。
进⼊锁后，线程必须先正确退出锁定，然后才能再次进⼊。
原理
⾃旋锁的原理⽐较简单，如果持有锁的线程能在短时间内释放锁资源，那么那些等待竞争锁的线程就不需要做内核态和⽤户态之间的切换进⼊阻塞状态，它们只需要等⼀等(⾃旋)，等到持有锁的线程释放锁之后即可获取，这样就避免了⽤户进程和内核切换的消耗。
作⽤
作为开发的辅助⼿段，System.Threading.SpinLock ⽀持线程跟踪模式
缺点
在较短的时间内⼀直占⽤cpu，因此在单核cpu 情况下代价是很⼤的。
c#命名空间：System.Threading
public struct SpinLock
继承
SpinLock
使⽤案例。
Java⾃旋锁的⼏种实现什么是⾃旋锁⾃旋锁是指当⼀个线程尝试获取某个锁时，如果该锁已被其他线程占⽤，就⼀直循环检测锁是否被释放，⽽不是进⼊线程挂起或睡眠状态。
为什么要使⽤⾃旋锁多个线程对同⼀个变量⼀直使⽤CAS操作，那么会有⼤量修改操作，从⽽产⽣⼤量的缓存⼀致性流量，因为每⼀次CAS操作都会发出⼴播通知其他处理器，从⽽影响程序的性能。
线程⾃旋与线程阻塞阻塞的缺点显⽽易见，线程⼀旦进⼊阻塞(Block)，再被唤醒的代价⽐较⾼，性能较差。
⾃旋的优点是线程还是Runnable的，只是在执⾏空代码。
当然⼀直⾃旋也会⽩⽩消耗计算资源，所以常见的做法是先⾃旋⼀段时间，还没拿到锁就进⼊阻塞。
JVM在处理synchrized实现时就是采⽤了这种折中的⽅案，并提供了调节⾃旋的参数。
SpinLock简单⾃旋锁（可重⼊）spin-lock 是⼀种基于test-and-set操作的锁机制。
test_and_set是⼀个原⼦操作，读取lock，查看lock值，如果是0，设置其为1，返回0。
如果是lock值为1，直接返回1。
这⾥lock的值0和1分别表⽰⽆锁和有锁。
由于test_and_set的原⼦性，不会同时有两个进程/线程同时进⼊该⽅法，整个⽅法⽆须担⼼并发操作导致的数据不⼀致。
这⾥⽤AtomicReference是为了使⽤它的原⼦性的compareAndSet⽅法（CAS操作），解决了多线程并发操作导致数据不⼀致的问题，确保其他线程可以看到锁的真实状态。
缺点：CAS操作需要硬件的配合；保证各个CPU的缓存（L1、L2、L3、跨CPU Socket、主存）的数据⼀致性，通讯开销很⼤，在多处理器系统上更严重；没法保证公平性，不保证等待进程/线程按照FIFO顺序获得锁。
public class SpinLock implements Lock {/*** use thread itself as synchronization state* 使⽤Owner Thread作为同步状态，⽐使⽤⼀个简单的boolean flag可以携带更多信息*/private AtomicReference<Thread> owner = new AtomicReference<>();/*** reentrant count of a thread, no need to be volatile*/private int count = 0;@Overridepublic void lock() {Thread t = Thread.currentThread();// if re-enter, increment the count.if (t == owner.get()) {++count;return;}//spinwhile (pareAndSet(null, t)) {}}@Overridepublic void unlock() {Thread t = Thread.currentThread();//only the owner could do unlock;if (t == owner.get()) {if (count > 0) {// reentrant count not zero, just decrease the counter.--count;} else {// compareAndSet is not need here, already checkedowner.set(null);}}}}TicketLockTicket Lock 是为了解决上⾯的公平性问题，类似于现实中银⾏柜台的排队叫号：锁拥有⼀个服务号，表⽰正在服务的线程，还有⼀个排队号；每个线程尝试获取锁之前先拿⼀个排队号，然后不断轮询锁的当前服务号是否是⾃⼰的排队号，如果是，则表⽰⾃⼰拥有了锁，不是则继续轮询。
Java⾃旋锁（spinlock）相关知识总结⽬录⼀、前⾔⼆、锁的优化：⾃旋锁三、⾃旋锁的死锁3.1、系统中断3.2、中断处理程序3.3、中断上下⽂ Context四、死锁解决⼀、前⾔谈到『⾃旋锁』，可能⼤家会说，这有啥好讲的，不就是等待资源的线程"原地打转"嘛。
嗯，字⾯理解的意思很到位，但能深⼊具体点吗？⾃旋锁的设计真就这么简单？本⽂或者说本系列的⽬的，都是让⼤家不要停留在表⾯，⽽是深⼊分析，做到：灵活使⽤掌握原理优缺点⼆、锁的优化：⾃旋锁当多个线程想同时访问同⼀个资源时，就存在资源冲突，这时，⼤家最直接想到的就是加锁来互斥访问，加锁会有这么⼏个问题：1. 等待资源的线程进⼊睡眠，发⽣⽤户态向内核态的切换，有⼀定的性能开销；2. 占⽤资源的线程很快就⽤完并释放，这时等待的线程被唤醒，⼜要⽴即切换回⽤户态；那么，如果有⼀种⽅式，使得等待的线程先短暂的等待⼀会⼉，有可能有两种结果：1. 等待的时间超过了这⼀会⼉，那没办法，只好进⼊睡眠；2. 等待的时间还未超过，占⽤资源的线程释放了，这时等待的线程就可以直接占⽤资源。
这就是锁的⼩优化：⾃旋锁！⾃旋锁并不是真正的锁，⽽是让等待的线程先原地"⼩转"⼀下，⼩转⼀下，通常⼩转⼀下的实现⽅式很简单：int SPIN_LOCK_NUM = 64;int i = 0;boolean wait = true;do {wait = // 尝试获取资源锁} while (wait && (++i) < SPIN_LOCK_NUM);我们通过循环⼀定的次数来⾃旋。
\color{red}{但是我们也应该知道，不进⼊休眠⽽原地打转，是会⼀直消耗 CPU 资源的，因此，才有了⾃旋限制！}但是我们也应该知道，不进⼊休眠⽽原地打转，是会⼀直消耗CPU资源的，因此，才有了⾃旋限制！看下⾯的JDK源码：public final class Unsafe {public final int getAndSetInt(Object var1, long var2, int var4) {int var5;do {var5 = this.getIntVolatile(var1, var2);} while(!pareAndSwapInt(var1, var2, var5, var4));return var5;}}我们可以看到，CAS就是采⽤的⾃旋锁⽅式，持续的尝试读取最新的 volatile 修饰的变量的值，并尝试去⽤期望的值去⽐较，然后更新。
自旋锁原理
自旋锁，也称为自旋锁定，是一种软件设计技术，用于控制多个线程间的访问权限。
它的主要目的是防止多个线程的竞争条件的发生，保护共享资源的完整性。
在多处理器系统中，自旋锁是控制系统中多个处理器之间的共享内存的一种重要技术手段。
自旋锁的原理很简单，它是一种软件中的原子操作，在自旋锁定期间，如果线程被中断，它将会一直保持锁定状态，直到它自己检测到锁定条件解除才会释放锁定，这样就保证了锁定条件不会在线程被中断时被其他线程获取。
自旋锁有多种不同的实现方式，但通常它包括一个用于阻止其他线程进入临界区的原子操作，一个用于等待锁定解除的计数器，以及一个用于检查锁定的值。
其中，原子操作用于保证只有一个线程可以访问临界区，计数器用于记录有多少线程在等待锁定解除，这将决定锁定的解除时间，而检查锁定的值用于检查锁定条件是否已解除，以便能够正确释放锁定。
自旋锁，与其他锁定技术相比，具有很多很大的优势，其中最主要的优势之一就是它可以非常有效地解决多处理器系统上的共享资
源管理问题。
无需使用繁琐的中断处理过程，就可以有效解决竞争条件的问题。
此外，它也可以在很大程度上减少开销，因为它只需要很少的计算机指令就可以达到同样的效果，并且不需要额外的硬件资源来支持。
自旋锁，作为一种非常有效的多处理器系统资源管理技术，已经
得到了广泛的应用，它可以有效地解决多处理器系统中多线程之间竞争条件的发生，保护共享资源的完整性。
但是，自旋锁也有一些缺点，它的效率可能不如其他类型的锁定技术，而且它不能用于跨处理器的多线程环境中。
因此，在使用自旋锁定的时候，应该根据不同的应用场景，选择最合适的锁定机制。
linux内核锁实现原理Linux内核锁是Linux操作系统中实现多线程同步和互斥的一种机制。
在并发编程中，多个线程同时访问共享资源时，为了避免出现数据竞争和不一致的情况，需要使用锁来保护共享资源的访问。
Linux内核提供了多种类型的锁，例如互斥锁（mutex）、读写锁（rwlock）、自旋锁（spinlock）等。
不同类型的锁适用于不同的场景和需求。
下面将详细介绍Linux内核锁的实现原理。
1. 互斥锁（Mutex）：互斥锁是最常用的一种锁，用于实现对临界区的互斥访问。
Linux 内核中的互斥锁实现主要依赖于原子操作和等待队列。
原子操作用于实现锁的获取和释放操作，保证了这些操作的原子性，避免了竞态条件。
等待队列用于管理等待锁的线程，当一个线程尝试获取锁失败时，会被放入等待队列中，直到锁被释放后再唤醒等待队列中的线程。
2. 读写锁（RWLock）：读写锁是一种特殊的锁，用于实现对共享资源的读写操作。
它允许多个线程同时读取共享资源，但在写操作时必须互斥。
Linux内核中的读写锁实现主要依赖于原子操作和等待队列。
读操作不需要加锁，只有写操作需要加锁。
读写锁内部维护了两个计数器，一个用于记录读操作的数量，一个用于记录写操作的数量。
读操作时，会增加读计数器；写操作时，会判断读计数器和写计数器是否为零，如果不为零则等待；如果为零则增加写计数器。
当读操作和写操作完成后，会相应地减少计数器。
3. 自旋锁（Spinlock）：自旋锁是一种特殊的锁，用于实现对临界区的互斥访问。
与互斥锁不同的是，自旋锁不会主动释放CPU资源，而是一直尝试获取锁，直到获取成功。
自旋锁的实现主要依赖于原子操作。
当一个线程尝试获取自旋锁失败时，会不断地尝试获取锁，直到获取成功。
这种方式适用于临界区的持有时间很短的情况，避免了线程切换的开销。
除了上述常用的锁类型，Linux内核还提供了一些其他类型的锁，如信号量（Semaphore）、屏障（Barrier）等。
（转）自旋锁（spinlock）解释得经典，透彻-unbutun的专栏-CSDN博客自旋锁与互斥锁有点类似，只是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。
由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。
信号量和读写信号量适合于保持时间较长的情况，它们会导致调用者睡眠，因此只能在进程上下文使用（_trylock的变种能够在中断上下文使用），而自旋锁适合于保持时间非常短的情况，它可以在任何上下文使用。
如果被保护的共享资源只在进程上下文访问，使用信号量保护该共享资源非常合适，如果对共巷资源的访问时间非常短，自旋锁也可以。
但是如果被保护的共享资源需要在中断上下文访问（包括底半部即中断处理句柄和顶半部即软中断），就必须使用自旋锁。
自旋锁保持期间是抢占失效的，而信号量和读写信号量保持期间是可以被抢占的。
自旋锁只有在内核可抢占或SMP的情况下才真正需要，在单CPU且不可抢占的内核下，自旋锁的所有操作都是空操作。
跟互斥锁一样，一个执行单元要想访问被自旋锁保护的共享资源，必须先得到锁，在访问完共享资源后，必须释放锁。
如果在获取自旋锁时，没有任何执行单元保持该锁，那么将立即得到锁；如果在获取自旋锁时锁已经有保持者，那么获取锁操作将自旋在那里，直到该自旋锁的保持者释放了锁。
无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。
自旋锁的API有：spin_lock_init(x)该宏用于初始化自旋锁x。
自旋锁在真正使用前必须先初始化。
该宏用于动态初始化。
DEFINE_SPINLOCK(x)该宏声明一个自旋锁x并初始化它。
该宏在2.6.11中第一次被定义，在先前的内核中并没有该宏。
SPIN_LOCK_UNLOCKED该宏用于静态初始化一个自旋锁。
自旋锁实现原理范文自旋锁是一种基本的同步原语，用于在并发环境中保护共享数据，同一时刻只允许一个线程访问共享数据。
当一个线程尝试获取自旋锁时，如果自旋锁已经被其他线程获取，则该线程会处于自旋状态，一直在循环中忙等待，直到获得锁。
自旋锁的实现原理可以分为两个方面：硬件层面的支持和软件层面的实现。
在软件层面，自旋锁通常由两个基本操作组成：获取锁和释放锁。
获取锁的操作可以分为以下几个步骤：1.检查自旋锁的状态，如果锁处于空闲状态，则将锁状态设置为占用，并继续执行后续操作。
2.如果锁已经被其他线程占用，则线程处于忙等待状态，反复尝试获取锁，直到成功获取为止。
这里可以使用循环来实现忙等待。
释放锁的操作也比较简单：1.将锁状态设置为空闲状态，表示该锁可以被其他线程获取。
自旋锁的实现原理可以通过以下伪代码来表示：```class SpinLockprivate boolean locked = false;public void acquirwhile (true)return; // 成功获取锁，退出循环}}}public void releaslocked = false; // 释放锁}//原子的比较并交换操作if (locked == expect)locked = update;return true;}return false;}```通过上述代码可以看出，自旋锁是一种非阻塞的同步机制，在没有获取到锁时，线程会一直自旋在获取锁的代码处，直到成功获取锁为止。
这种方式可以避免线程切换的开销，适用于对共享数据的访问时间很短的场景。
然而，自旋锁也有一些缺点和适用条件：1.当锁竞争激烈时，自旋锁可能导致线程长时间忙等待，浪费CPU资源。
所以，在多核处理器上，自旋锁一般用于保护共享数据访问时间较短的临界区。
2.自旋锁不能解决线程优先级反转的问题。
如果优先级低的线程持有锁并且长时间不释放，优先级高的线程就会被阻塞，导致线程优先级反转。
关键代码段（CriticalSections）和⾃旋锁（Spinlocks）写在前⾯：今天⼀哥们问我，windows的临界代码是⾃旋还是等待，当时想了想应该是等待，后来翻了⼀下《Windows via C/C++》，发现还有点⼩意思。
总结⼀下先。
关键代码段是指⼀个⼩代码段，在代码能够执⾏前，它必须独占对某些共享资源的访问权。
这是让若⼲⾏代码能够“以原⼦操作⽅式”来使⽤资源的⼀种⽅法。
所谓原⼦操作⽅式，是指该代码知道没有别的线程要访问该资源。
当然，系统仍然能够抑制你的线程的运⾏，⽽抢先安排其他线程的运⾏。
不过，在线程退出关键代码段之前，系统将不给想要访问相同资源的其他任何线程进⾏调度。
来看⼀段使⽤关键代码段的程序：const int COUNT = 10;int g_nSum = 0;CRITICAL_SECTION g_cs;DWORD WINAPI FirstThread(PVOID pvParam) {EnterCriticalSection(&g_cs);g_nSum = 0;for (int n = 1; n <= COUNT; n++) {g_nSum += n;}LeaveCriticalSection(&g_cs);return(g_nSum);}DWORD WINAPI SecondThread(PVOID pvParam) {EnterCriticalSection(&g_cs);g_nSum = 0;for (int n = 1; n <= COUNT; n++) {g_nSum += n;}LeaveCriticalSection(&g_cs);return(g_nSum);}当⼀个线程进⼊关键代码段，其它请求进⼊关键代码段的线程就会进⼊等待状态，这意味着该线程必须从⽤户⽅式转⼊内核⽅式（⼤约1000个C P U周期），这种转换是要付出很⼤代价的。
1.什么是自旋锁自旋锁（spinlock）：是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。
获取锁的线程一直处于活跃状态，但是并没有执行任何有效的任务，使用这种锁会造成busy-waiting。
2.Java如何实现自旋锁？先看一个实现自旋锁的例子，java.util.concurrent包里提供了很多面向并发编程的类. 使用这些类在多核CPU的机器上会有比较好的性能.主要原因是这些类里面大多使用(失败-重试方式的)乐观锁而不是synchronized方式的悲观锁.class spinlock {private AtomicReference<Thread> cas;spinlock(AtomicReference<Thread> cas){this.cas = cas;}public void lock() {Thread current = Thread.currentThread();// 利用CASwhile (!pareAndSet(null, current)) { //为什么预期是null？？// DO nothingSystem.out.println("I am spinning");}}public void unlock() {Thread current = Thread.currentThread();pareAndSet(current, null);}}lock（)方法利用的CAS，当第一个线程A获取锁的时候，能够成功获取到，不会进入while循环，如果此时线程A没有释放锁，另一个线程B又来获取锁，此时由于不满足CAS，所以就会进入while循环，不断判断是否满足CAS，直到A线程调用unlock方法释放了该锁。
自旋锁验证代码package ddx.多线程;import java.util.concurrent.atomic.AtomicReference;public class自旋锁{public static void main(String[] args) {AtomicReference<Thread> cas = newAtomicReference<Thread>();Thread thread1 = new Thread(new Task(cas));Thread thread2 = new Thread(new Task(cas));thread1.start();thread2.start();}}//自旋锁验证class Task implements Runnable{private AtomicReference<Thread> cas;private spinlock slock ;public Task(AtomicReference<Thread> cas) {this.cas = cas;this.slock = new spinlock(cas);}@Overridepublic void run() {slock.lock(); //上锁for (int i = 0; i < 10; i++) {//Thread.yield();System.out.println(i);}slock.unlock();}}通过之前的AtomicReference类创建了一个自旋锁cas，然后创建两个线程，分别执行，结果如下：I am spinI am spinI am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin I am spin 1I am spin I am spin I am spin I am spin I am spin 23456789I am spin 0123456789通过对输出结果的分析我们可以得知，首先假定线程一在执行lock方法的时候获得了锁，通过方法pareAndSet(null, current)将引用改为线程一的引用，跳过while循环，执行打印函数而线程二此时也进入lock方法，在执行比较操作的时候发现，expect value ！= update value，于是进入while循环，打印i am spinning。
高性能自旋锁MCS Spinlock 的设计与实现林昊翔，计算机科学硕士，毕业于清华大学计算机系，Linux 内核爱好者秦君(qinjun@), 软件工程师, IBM简介：自旋锁（Spinlock）是一种在Linux 内核中广泛运用的底层同步机制。
排队自旋锁（FIFO Ticket Spinlock）是Linux 内核2.6.25 版本中引入的一种新型自旋锁，它解决了传统自旋锁由于无序竞争导致的“公平性”问题。
但是由于排队自旋锁在一个共享变量上“自旋”，因此在锁竞争激烈的多核或NUMA 系统上导致性能低下。
MCS Spinlock 是一种基于链表的高性能、可扩展的自旋锁，本文详细剖析它的原理与具体实现。
发布日期： 2008 年10 月30 日一、引言自旋锁（Spinlock）是一种在Linux 内核中广泛运用的底层同步机制，长期以来，人们总是关注于自旋锁的安全和高效，而忽视了自旋锁的“公平”性。
排队自旋锁（FIFO Ticket Spinlock）是内核开发者Nick Piggin 在Linux Kernel2.6.25[1] 版本中引入的一种新型自旋锁，它通过保存执行线程申请锁的顺序信息解决了传统自旋锁的“不公平”问题[4]。
排队自旋锁仍然使用原有的raw_spinlock_t 数据结构，但是赋予slock 域新的含义。
为了保存顺序信息，slock 域被分成两部分，低位部分保存锁持有者的票据序号（Ticket Number），高位部分则保存未来锁申请者的票据序号。
只有Next 域与Owner 域相等时，才表明锁处于未使用状态（此时也无执行线程申请该锁）。
排队自旋锁初始化时slock 被置为0，即Owner 和Next 置为0。
内核执行线程申请自旋锁时，原子地将Next 域加1，并将原值返回作为自己的票据序号。
如果返回的票据序号等于申请时的Owner 值，说明自旋锁处于未使用状态，则直接获得锁；否则，该线程忙等待检查slock 的Owner 部分是否等于自己持有的票据序号，一旦相等，则表明锁轮到自己获取。
线程释放锁时，原子地将Owner 域加1 即可，下一个线程将会发现这一变化，从忙等待状态中退出。
线程将严格地按照申请顺序依次获取排队自旋锁，从而完全解决了“不公平”问题。
但是在大规模多处理器系统和NUMA系统中，排队自旋锁（包括传统自旋锁）存在一个比较明显的性能问题：由于执行线程均在同一个共享变量slock 上自旋，申请和释放锁的时候必须对slock 进行修改，这将导致所有参与排队自旋锁操作的处理器的缓存变得无效。
如果排队自旋锁竞争比较激烈的话，频繁的缓存同步操作会导致繁重的系统总线和内存的流量，从而大大降低了系统整体的性能。
二、MCS Spinlock 的原理为了解决自旋锁可扩展性问题，学术界提出了许多改进版本，其核心思想是：每个锁的申请者（处理器）只在一个本地变量上自旋。
MCS Spinlock[2] 就是其中一种基于链表结构的自旋锁（还有一些基于数组的自旋锁）。
MCS Spinlock的设计目标如下：1.保证自旋锁申请者以先进先出的顺序获取锁（FIFO Ordering）。
2.只在本地可访问的标志变量上自旋。
3.在处理器个数较少的系统中或锁竞争并不激烈的情况下，保持较高性能。
4.自旋锁的空间复杂度（即锁数据结构和锁操作所需的空间开销）为常数。
5.在没有处理器缓存一致性协议保证的系统中也能很好地工作。
MCS Spinlock采用链表结构将全体锁申请者的信息串成一个单向链表，如图1 所示。
每个锁申请者必须提前分配一个本地结构mcs_lock_node，其中至少包括2 个域：本地自旋变量waiting 和指向下一个申请者mcs_lock_node 结构的指针变量next。
waiting 初始值为1，申请者自旋等待其直接前驱释放锁；为0 时结束自旋。
而自旋锁数据结构mcs_lock 是一个永远指向最后一个申请者mcs_lock_node 结构的指针，当且仅当锁处于未使用（无任何申请者）状态时为NULL 值。
MCS Spinlock 依赖原子的“交换”（swap）和“比较-交换”（compare_and_swap）操作，缺乏后者的话，MCS Spinlock 就不能保证以先进先出的顺序获取锁，从而可能造成“饥饿”（Starvation）。
图 1. MCS Spinlock 示意图MCS Spinlock 申请操作描述如下：1.申请者 B 使用原子交换操作将自旋锁mcs_lock 指向自己的mcs_lock_node 结构以确定在链表中的位置，并返回mcs_lock原来的值pre_mcs_lock。
即使多个执行线程同时申请锁，由于交换操作的原子性，每个执行线程的申请顺序将会被唯一确定，不会出现不一致的现象。
2.如果pre_mcs_lock 为NULL，表明锁无人使用，B 立即成为锁的拥有者，申请过程结束。
3.如果pre_mcs_lock 不为NULL，则表明pre_mcs_lock 指向申请者 B的直接前驱 A 的mcs_lock_node 结构，因此必须通过pre_mcs_lock 来修改A 的next 域指向B 自己，从而将链表构建完整。
4.然后B 一直在自己的mcs_lock_node 结构的waiting 域上自旋。
当B的直接前驱A 释放自旋锁时，A 只须通过next 域将B 的waiting 域修改为0 即可。
MCS Spinlock 释放操作描述如下：1.释放自旋锁时，锁的拥有者A 必须十分小心。
如果有直接后继B，即A的mcs_lock_node 结构的next 域不为NULL，那么只须将 B 的waiting 域置为0 即可。
2.如果A 此时没有直接后继，那么说明A “可能”是最后一个申请者（因为判断是否有直接后继和是否是最后一个申请者的这两个子操作无法原子完成，因此有可能在操作中间来了新的申请者），这可以通过使用原子比较-交换操作来完成，该操作原子地判断mcs_lock 是否指向 A 的mcs_lock_node 结构，如果指向的话表明 A 是最后一个申请者，则将mcs_lock 置为NULL；否则不改变mcs_lock 的值。
无论哪种情况，原子比较-交换操作都返回mcs_lock 的原值。
3.如果A 不是最后一个申请者，说明中途来了新的申请者B，那么A必须一直等待B 将链表构建完整，即A 的mcs_lock_node 结构的next 域不再为NULL。
最后A 通过next 域将B 的waiting 域置为0。
三、MCS Spinlock 的实现目前Linux 内核尚未使用MCS Spinlock。
根据上节的算法描述，我们可以很容易地实现MCS Spinlock。
本文的实现针对x86 体系结构(包括IA32 和x86_64)。
原子交换、比较-交换操作可以使用带LOCK 前缀的xchg(q)，cmpxchg(q)[3] 指令实现。
为了尽量减少工作量，我们应该重用现有的自旋锁接口[4]。
下面详细介绍raw_spinlock_t 数据结构，函数__raw_spin_lock、__raw_spin_unlock、__raw_spin_is_locked 和__raw_spin_trylock 的实现。
1.raw_spinlock_t数据结构由于MCS Spinlock 的申请和释放操作需要涉及同一个mcs_lock_node 结构，而且这个结构在现有的接口函数中并不存在，因此不适合使用接口函数的局部变量或是调用接口的外层函数的局部变量。
一个简单的方法是在raw_spinlock_t 数据结构中为每个处理器预备一个mcs_lock_node 结构（因为申请自旋锁的时候会关闭内核抢占，每个处理器上至多只有一个执行线程参与锁操作，所以只需要一个mcs_lock_node）。
在NUMA 系统中，mcs_lock_node 结构可以在处理器所处节点的内存中分配，从而加快访问速度。
为简化代码，本文的实现使用mcs_lock_node 数组。
清单1. raw_spinlock_t 数据结构typedef struct _mcs_lock_node {volatile int waiting;struct _mcs_lock_node *volatile next;} ____cacheline_aligned_in_smp mcs_lock_node;typedef mcs_lock_node *volatile mcs_lock;typedef struct {mcs_lock slock;mcs_lock_node nodes[NR_CPUS];} raw_spinlock_t;因为waiting 和next 会被其它处理器异步修改，因此必须使用volatile 关键字修饰，这样可以确保它们在任何时间呈现的都是最新的值。
加上____cacheline_aligned_in_smp 修饰在多处理器环境下会增加mcs_lock_node 结构的大小，但是可以使其按高速缓存管线（cache line）大小对齐以消除False Sharing[5]。
这是因为由于mcs_lock_node 结构比较小，每个等待的处理器在自己的mcs_lock_node 的waiting 域上自旋的时候，相邻处理器的mcs_lock_node 结构会一齐放在同一个高速缓存管线中（一般L1，L2 的高速缓存管线为64 字节），一旦锁拥有者处理器在释放锁阶段修改其直接后继的waiting 域时，会无效化整个高速缓存管线，因此可能造成一些后续等待者处理器的相应高速缓存管线也被迫更新，增加了系统总线的无谓开销。
1.__raw_spin_lock 函数清单2. __raw_spin_lock 函数static __always_inline void __raw_spin_lock(raw_spinlock_t *lock){int cpu;mcs_lock_node *me;mcs_lock_node *tmp;mcs_lock_node *pre;cpu = raw_smp_processor_id();(a)me = &(lock->nodes[cpu]);tmp = me;me->next = NULL;pre = xchg(&lock->slock, tmp); (b)if (pre == NULL) {/* mcs_lock is free */return;(c)}me->waiting = 1;pre->next = me; (d)while (me->waiting) { (e)rep_nop();}}1.raw_smp__processor_id() 函数获得所在处理器的编号，用以索引mcs_lock_node 结构。
