linux kernel 2.6.24及之前版本的spinlock就是一个整数。其实现基于原子操作。spinlock初始化为1，加锁时，将spinlock减1（原子操作），然后判断其值是否为0，如果为0，则成功获取到锁；如果为负数，则需要忙等，直到spinlock的值变为正数，再次尝试加锁操作。解锁时，将spinlock的值置1即可。

最初的spinlock存在一个重要的缺陷：公平性；其实现机制无法确保等待时间最长的竞争者优先获取到锁。

为了解决这种无序竞争带来的不公平的问题，ticket spinlock被提出了。ticket spinlock的实现类似叫号系统，每个锁的竞争者领取一个号码，锁持有者释放锁的时候递增号码，这样下一个竞争者就能获取到锁。

ticket spinlock存在一个性能问题：cache颠簸；在MP系统中，每次获取锁的值的时候都会刷新所有竞争CPU上的cache，这在竞争激烈的情况下会损耗大量的系统性能。

为了解决ticket spinlock带来的cache颠簸的问题，MCS spinlock被提出了。MCS其实就是这两位作者的简称，John M. Mellor-Crummey and Michael L. Scott，所以MCS并不是一个算法名称，也和自旋锁本身没啥关系。

内核开发者Tim Chen在内核中引入了MCS spinlock，通过让每个CPU在自己的自旋锁结构体变量上自旋，能够避免绝大部分的cache颠簸。

mcs_spinlock包含一个next指针和一个整形变量用于表示当前锁的状态。3.15版本的内核中mcs_spinlock定义如下：

struct mcs_spinlock {
	struct mcs_spinlock *next;
	unsigned int locked; /* 1 if lock acquired */
};

假定多个CPU需要竞争的锁为MCS Lock，MCS Lock初始时next为NULL，locked为0。MCS Lock初始状态如下图所示：

当CPU 0需要获取锁时，会使用CPU 0的锁结构，使用原子指令将自己的锁结构的地址与MCS Lock的next指针交换，并获取MCS Lock的next指针的旧值，如果该旧值为NULL，则CPU 0成功获取到锁。注意：CPU 0是第一个获取锁的，其自己的锁结构的locked的值是不需要设置为1的。CPU 0获取到锁后的状态如下图所示：

当CPU 0持锁时，CPU 1来竞争锁，CPU 1使用原子指令将自己的锁结构的地址与MCS Lock的next指针交换，并获取MCS Lock的next指针的旧值，此时该旧值为CPU 0的锁结构的地址，此时CPU 1不能获取到锁，CPU 1需要将CPU 0的锁结构的next指针指向CPU 1的锁结构地址，这样CPU 0在释放锁的时候就知道下一个排队的是CPU 1；设置好CPU 0的锁结构的next指针之后，CPU 1就需要在自己的锁的locked值上自旋直到其值变为1。CPU 0获取到锁后CPU 1来获取锁时的状态如下图所示：

CPU 0释放锁时，使用原子条件交换指令，如果MCS Lock的next指针指向CPU 0的锁结构，则将MCS Lock的next指针设为NULL，此时没有其他等待者，释放锁的流程结束；如果MCS Lock的next指针不指向CPU 0的锁结构，说明此时还有其他等待者，通过CPU 0的锁结构的next指针可以获取到下一个等待的CPU的锁结构，将下一个等待的CPU的锁结构的locked值置为1，CPU 0的解锁流程结束。注意：CPU 0解锁时如果其锁结构的next指针为NULL，但是MCS Lock的next指针不为NULL，CPU 0需要自旋一段时间以等待CPU 1设置CPU 0的锁结构的next指针。解锁过程如下图所示：

CPU 1一直在自己的锁结构的locked值上自旋，直到其值变为1之后，CPU 1获取到锁，之后就可以开始执行CPU 1临界区的代码。CPU 1获取到锁后的状态如下图所示：

MCS Lock加锁解锁的过程中有两个地方需要注意：

1. 因为每个CPU来获取锁的时候都是使用原子指令将自己的锁结构的地址与MCS Lock的next指针交换，因此MCS Lock的next指针始终指向等待锁队列的最后一个，下一个来获取锁的CPU能将其自己的锁结构的地址添加到等待队列的队尾；该交换指令是原子操作，因此只有一个CPU能获取到当前队尾的CPU的锁结构地址，因此一个MCS Lock只可能存在一个排队队列。
2. 每个CPU都在自己的锁结构的locked值上自旋，可以避免绝大部分的cache颠簸。