免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3139 | 回复: 5

[内核同步] MCS自旋锁实现原理与解析 [复制链接]

论坛徽章:
0
发表于 2014-07-27 22:30 |显示全部楼层
这两天在研究mutex实现时, 发现其中优化路径用了一种叫MCS自旋锁的方案.

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

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

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

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

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

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

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

论坛徽章:
0
发表于 2014-07-27 22:58 |显示全部楼层
看了第一篇,写的很精彩,这个思路我觉得关键是由锁持有者来更新自旋者的轮询标志。
有个小疑问,文章里说,mutex 是用这个思路实现,我以为mutex获取不到锁就直接阻塞了,避免cache抖动的地方是哪一块代码呢?
收藏楼主博客了。

论坛徽章:
0
发表于 2014-07-27 23:16 |显示全部楼层
本帖最后由 l4rmbr 于 2014-07-27 23:21 编辑
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本地锁上更改状态,  这样仅
涉及到一次缓存行失效, 相比传统的做法, 有大大的改进.

论坛徽章:
17
水瓶座
日期:2013-08-29 12:09:27白羊座
日期:2014-08-07 12:36:42丑牛
日期:2014-07-24 12:44:41寅虎
日期:2014-04-16 16:15:33寅虎
日期:2014-03-12 09:28:43摩羯座
日期:2014-03-06 13:22:04技术图书徽章
日期:2014-03-06 11:34:50天蝎座
日期:2014-01-09 11:31:44寅虎
日期:2013-12-27 17:01:44双子座
日期:2013-12-27 12:32:29双子座
日期:2013-12-25 09:03:33丑牛
日期:2013-12-24 16:18:44
发表于 2014-07-28 08:46 |显示全部楼层
恩,其实有篇 lwn的文章解释的比较清楚:

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

论坛徽章:
1
lufei
日期:2016-06-17 17:49:16
发表于 2014-07-31 18:08 |显示全部楼层
本帖最后由 adidiaos丶丶 于 2014-07-31 18:26 编辑

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

论坛徽章:
15
射手座
日期:2014-02-26 13:45:082015年迎新春徽章
日期:2015-03-04 09:54:452015年辞旧岁徽章
日期:2015-03-03 16:54:15羊年新春福章
日期:2015-02-26 08:47:552015年亚洲杯之卡塔尔
日期:2015-02-03 08:33:45射手座
日期:2014-12-31 08:36:51水瓶座
日期:2014-06-04 08:33:52天蝎座
日期:2014-05-14 14:30:41天秤座
日期:2014-04-21 08:37:08处女座
日期:2014-04-18 16:57:05戌狗
日期:2014-04-04 12:21:33技术图书徽章
日期:2014-03-25 09:00:29
发表于 2014-08-01 15:58 |显示全部楼层
写得很好,感谢分享。。。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP