MCS自旋锁实现原理与解析

l4rmbr

这两天在研究mutex实现时, 发现其中优化路径用了一种叫MCS自旋锁的方案.

MCS自旋锁, 顾名思义, 也是自旋锁的一种实现方式, 不过它的实现方式, 相当巧妙,
可以避免"cpu cacheline bouncing"的问题.  这一问题, 在常规的自旋锁实现方案中,
是一个比较严重的问题, 尤其在锁竞争激烈的时候.

此外, mutex实现用的自旋锁是一种增强版的叫可取消的MCS自旋锁.  也就是在
自旋等待过程中, 可以放弃等待.  这听起来似乎没什么, 不就停止循环吗?  但是, 基于
MCS自旋锁的独特实现方式, 即基于链表的方式, 这种放弃等待, 就不是简单的停止循环了.

这相当于一个链表元素的脱链操作. 这就要考虑到并发问题. 而代码实现中, 是不用锁来
解决并发的. 而是用了原子交换等原语. 所以,  看MCS自旋锁的实现, 会发现这种锁的实现中,
展示了另一种技术, 即无锁并发编程的技术.

这种编程需要极小心来规避并发带来的问题, 因此代码阅读起来有些晦涩, 但又十分刺激.

这个周末分析了下代码, 并写了两篇文章来记录下自己的理解 . 顺便与大家分享.

本来是想原文粘贴在这里, 不过发现惨不忍睹. 所以还是贴我博客链接吧, 顺便为博客带点人气
如有疏漏谬误, 也麻烦指正.

Linux同步机制--MCS自旋锁
Linux同步机制--可取消的MCS自旋锁

chenyu105

看了第一篇，写的很精彩，这个思路我觉得关键是由锁持有者来更新自旋者的轮询标志。
有个小疑问，文章里说，mutex 是用这个思路实现，我以为mutex获取不到锁就直接阻塞了，避免cache抖动的地方是哪一块代码呢？
收藏楼主博客了。

l4rmbr

chenyu105 发表于 2014-07-27 22:58
有个小疑问，文章里说，mutex 是用这个思路实现，我以为mutex获取不到锁就直接阻塞了，避免cache抖动的地方是哪一块代码呢？

不在代码里, 在锁的设计思想里.

传统的自旋锁如下:

   while(ACCESS_ONCE(lock->count) != 0)
            ;

在循环里决断lock->count是否为0, 即锁是否空闲, 不是则自旋.

关键在 ACCESS_ONCE(lock->count) 里, 每一次循环, 都要读取这个字段,
即相当于每一次循环,  都要把该字段加载到本地CPU的缓存行中,  这样造成
cacheline抖动,  多个CPU竞争时, 情况会更加严重, 每个CPU都这么做, 并且
多人竞争,  自旋的次数相应会增加.

MCS自旋锁避免这一做法, 令要获取锁的A在CPU本地的锁上自旋, 这样避免了每次循环一次就
invalidate缓存行一次.  当别人释放锁后, 轮到A时,  别人就会在A本地锁上更改状态,  这样仅
涉及到一次缓存行失效, 相比传统的做法, 有大大的改进.

asuka2001

恩，其实有篇 lwn的文章解释的比较清楚：

MCS locks and qspinlocks
http://lwn.net/Articles/590243/

adidiaos丶丶

当CPU-1准备获取该锁时, 它用G->next字段, 与L1的地址, 进行原子交换操作。这个不懂啊L1这个锁是哪里来的啊？各种锁我有点晕呐。atomic、spin、rcu、mutex。还有什么无锁编程好像很牛B的样子。好乱。

humjb_1983

写得很好，感谢分享。。。