mcs_spinlock可谓是linux内核中，知名度相当高的锁实现了。以mcs_spinlock作为我们这个系列的第一篇文章，更多的是考虑到后续很多的锁实现，均是以mcs_spinlock为基础之上的优化，因此为了方便大家的理解，关于mcs_spinlock的介绍必不可可少。废话不多说，让我们开始吧～
在维基百科的定义中，lock是多线程环境中，对于资源访问的一种同步机制[1]。而最简单的lock的实现，莫过于spin lock[2]。spin lock顾名思义，就是线程在发现lock被他人持有后，会在原地反复检察锁是否可用。这样的实现，能想到的优点首先就是简单。足够简单的实现可以减少实现的指令数，从而对于程序执行本身就是有好处的。第二个优点就是避免了操作系统的任务调度开销以及上下文切换的开销。但是缺点也很明显，就是在lock被别人长期持有的场景下，无谓的重试会带来不必要的cpu开销。但是这类场景本身就不是spinlock应该出现的地方，因此也不是本章主角mcs_spinlock要优化的目标。其实朴素的spin lock的实现中，还有两个隐藏得比较深的缺点：
1)在持续冲突的情况下，等锁任务可能会存在starvation[3]饿死的可能。
2)在多核架构下，运行在各个核上的等锁任务，在锁释放的时候，均会出现cache line失效的情况，但是实际上只有一个等锁任务会获得锁，其他等锁任务带来的cache line失效其实是毫无意义的。在现代处理器的架构中，功耗和制程限制了主频的提升，核数越来越多是不可避免的趋势。因此这点显得越来越重要。
关于缺点2，举个例子，线程a持有spinlock，线程b，c，d分别在spin等锁中，此时线程b，c，d所运行的对应的cpu核中，cache line缓存的关于spinlock的状态是有效的，因此spin的动作不需要去访问其他核上的cache line（这点如果有对cache line状态同步行为不太清楚的，可以先看下MESI协议[4]）。但是当锁释放的时候，释放线程会修改锁的状态，同时会造成b，c，d上的cache line失效，此时b，c，d会访问a上cache line的最新状态，并试图修改spinlock在cache line上的状态，通过cache line协议广播出去。第一个成功修改spinlock状态的线程会成功持有锁，而其他“陪跑”的线程会更新本地的cache line状态，并再次陷入对本地cache line的原地自旋中。远程cache line的访问和本地cache line的更新均是有代价的，例如总线拥堵，cache line miss rate升高等等。在核数越多的情况下，代价会被成倍的放大。
因此，更好的spinlock实现呼之欲出，mcs_spinlock就是在这种背景下诞生的。先来看下mcs_spinlock的数据结构。
struct mcs_spinlock {struct mcs_spinlock *next;int locked; /* 1 if lock acquired */};locked用于表示，是否上锁成功，而相对于朴素spinlock实现中，多出来的next指针，正是mcs_spinlock的灵魂所在。在mcs_spinlock实现中，可以看到，
void mcs_spin_lock(struct mcs_spinlock **lock, struct mcs_spinlock *node){struct mcs_spinlock *prev;/* Init node */node->locked = 0;node->next = NULL;//将lock指针指向node，并返回lock指针原来的指向的值。prev = xchg(lock, node);if (likely(prev == NULL)) {// 如果lock指针原来指向NULL，所以持有锁成功，可以直接返回。return;} // 将本等待任务的node，串到上一个等锁任务的node的后面WRITE_ONCE(prev->next, node);// 等待本等锁任务的node中的locked标记被设置为1，代表本任务持有锁成功arch_mcs_spin_lock_contended(&node->locked);}每个尝试获取lock的任务都会分配一个mcs_spinlock的数据结构，通过原子操作xchg，先后尝试获取lock的任务被串成了单向链表。最后本函数会在原地等待本任务的locked标记被设置为1。和朴素spinlock相比，最大的不同在于，1）首先先来后到的等锁任务被有顺序地串联起来，唤醒顺序是有序的，不会再出现饿死的情况。2）接着就是，每个等锁任务只会等待在属于自己的locked标记中，不会再出现多个任务都等在同一个标记中，因此而导致的每次标记的修改均会引起多核上所有等待任务的cache line同时失效的情况。
对于解锁操作，大家应该可以猜到了，就是每一个任务会将串连在自己等锁node后面的node的locked标记设置为1，从而唤醒后面的等待任务。代码就不贴出来了。整个流程的图示如下：
相对于朴素的spinlock实现，虽然引入了一些复杂度，但是带来的收益是相当可观的。能够较好的减少多核架构下的cache line频繁失效问题，而且也更公平。后续会在mcs_spinlock的基础上，继续聊聊几种进一步的优化实现，欢迎订阅呀～
[1] https://en.wikipedia.org/wiki/Lock_(computer_science)
[2] https://en.wikipedia.org/wiki/Spinlock
[3] https://en.wikipedia.org/wiki/Starvation_(computer_science)
[4] https://en.wikipedia.org/wiki/MESI_protocol