免费注册 查看新帖 |

ChinaUnix.net

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

[内核同步] 关于rcu的问题 [复制链接]

论坛徽章:
8
羊年新春福章
日期:2015-03-19 02:03:312015亚冠之北京国安
日期:2015-06-16 22:04:45程序设计版块每日发帖之星
日期:2015-06-23 22:20:00每日论坛发贴之星
日期:2015-06-23 22:20:002015亚冠之首尔
日期:2015-06-24 19:18:072015亚冠之广州恒大
日期:2015-08-06 10:29:442015亚冠之柏太阳神
日期:2015-11-02 11:21:0515-16赛季CBA联赛之辽宁
日期:2015-12-09 15:05:02
发表于 2015-05-24 20:23 |显示全部楼层
我在Paul的RCU文章, What is RCU, Fundamentally?
关于文中给出的问题, 百思不得其解, 实际上是没看懂答案:
Quick Quiz 5: How many RCU versions of a given list can be active at any given time?

Answer: That depends on the synchronization design. If a semaphore protecting the update is held across the grace period, then there can be at most two versions, the old and the new.

However, if only the search, the update, and the list_replace_rcu() were protected by a lock, then there could be an arbitrary number of versions active, limited only by memory and by how many updates could be completed within a grace period. But please note that data structures that are updated so frequently probably are not good candidates for RCU. That said, RCU can handle high update rates when necessary.

我认为, list可以任意多个. 不太理解semaphore带来的影响, 为什么只有两个?

论坛徽章:
20
程序设计版块每日发帖之星
日期:2015-08-17 06:20:00程序设计版块每日发帖之星
日期:2016-07-16 06:20:00程序设计版块每日发帖之星
日期:2016-07-18 06:20:00每日论坛发贴之星
日期:2016-07-18 06:20:00黑曼巴
日期:2016-12-26 16:00:3215-16赛季CBA联赛之江苏
日期:2017-06-26 11:05:5615-16赛季CBA联赛之上海
日期:2017-07-21 18:12:5015-16赛季CBA联赛之青岛
日期:2017-09-04 17:32:0515-16赛季CBA联赛之吉林
日期:2018-03-26 10:02:16程序设计版块每日发帖之星
日期:2016-07-15 06:20:0015-16赛季CBA联赛之江苏
日期:2016-07-07 18:37:512015亚冠之萨济拖拉机
日期:2015-08-17 12:21:08
发表于 2015-05-25 10:44 |显示全部楼层
本帖最后由 nswcfd 于 2015-05-25 10:53 编辑

Quiz#5是紧跟着Quiz#4来的。

Quiz#4,How would you modify the deletion example to permit more than two versions of the list to be active?
这个问题又是针对正文中的删除算法提出的。

正文的算法,example 1,是这样的
  1.   1 p = search(head, key);
  2.   2 if (p != NULL) {
  3.   3   list_del_rcu(&p->list);
  4.   4   synchronize_rcu();
  5.   5   kfree(p);
  6.   6 }
复制代码
Quiz#4前有段话,These examples assumed that a mutex was held across the entire update operation, which would mean that there could be at most two versions of the list active at a given time.
即,不允许同时修改,所以最多list有两个版本存在。(<------ 楼主可能是没注意这句话)
并且synchronzie_rcu是包含在这个mutex里的,即Quiz#5里提到的,“... a semaphore protecting the update is held across the grace period”(mutex跨越了grace period)

Quiz#4的(一种)答案是
  1. spin_lock(&mylock);
  2. p = search(head, key);
  3. if (p == NULL)
  4.         spin_unlock(&mylock);
  5. else {
  6.         list_del_rcu(&p->list);
  7.         spin_unlock(&mylock);
  8.         synchronize_rcu();
  9.         kfree(p);
  10. }
复制代码
答案跟正文的区别在于,lock的范围不一样(并且一个是spin一个是mutex)。
这样在多核环境下,正文的代码,一个cpu删除一个节点后,其它cpu之后等到其完成synchronize之后才能删除,所以list最多两个版本(一个是带被删除节点的,一个是不带被删除节点的);
而Quiz#4中,一个cpu删除后其它cpu可以立刻删除,大家都进入synchronize等待状态(multiple concurrent deletions might be waiting in synchronize_rcu());对于reader而言,list就会有多个版本(原始版本、cpu1删除后的版本、cpu2删除后的版本……)。

这其实跟Quiz#5传递的信息是一致的。
Quiz#5答案的第二段应该说的就是Quiz#4的情况(略有不同,一个是update,一个是delete)。

论坛徽章:
8
羊年新春福章
日期:2015-03-19 02:03:312015亚冠之北京国安
日期:2015-06-16 22:04:45程序设计版块每日发帖之星
日期:2015-06-23 22:20:00每日论坛发贴之星
日期:2015-06-23 22:20:002015亚冠之首尔
日期:2015-06-24 19:18:072015亚冠之广州恒大
日期:2015-08-06 10:29:442015亚冠之柏太阳神
日期:2015-11-02 11:21:0515-16赛季CBA联赛之辽宁
日期:2015-12-09 15:05:02
发表于 2015-05-25 16:50 |显示全部楼层
本帖最后由 firocu 于 2015-05-25 17:05 编辑

回复 2# nswcfd
感谢nswcfd, 细致令人信服的答案.
我没能理解的根源是, 我认为只有一个核在修改, 这个核可以修改任意多次在gp时间内.
我之所以有这种想法是在这篇文章之前有一句:
RCU supports concurrency between a single updater and multiple readers.
我理解成只能有一个synchronize_rcu() 被调用, 同一个gp周期内,

现在理解了
信号量那个只有两个版本, 前提是采用semaphore那种多核更新保护机制时, updater只做了一次更新, 如删除一个node, .如果semaphore保护周期内做了多次修改, 依然会有很多个rcu version list.

再次感谢nswcfd!

   

论坛徽章:
20
程序设计版块每日发帖之星
日期:2015-08-17 06:20:00程序设计版块每日发帖之星
日期:2016-07-16 06:20:00程序设计版块每日发帖之星
日期:2016-07-18 06:20:00每日论坛发贴之星
日期:2016-07-18 06:20:00黑曼巴
日期:2016-12-26 16:00:3215-16赛季CBA联赛之江苏
日期:2017-06-26 11:05:5615-16赛季CBA联赛之上海
日期:2017-07-21 18:12:5015-16赛季CBA联赛之青岛
日期:2017-09-04 17:32:0515-16赛季CBA联赛之吉林
日期:2018-03-26 10:02:16程序设计版块每日发帖之星
日期:2016-07-15 06:20:0015-16赛季CBA联赛之江苏
日期:2016-07-07 18:37:512015亚冠之萨济拖拉机
日期:2015-08-17 12:21:08
发表于 2015-05-26 13:51 |显示全部楼层
回复 3# firocu

Paul关于RCU的一系列文章见解非常深刻,在Quiz Q&A里对这些同步原语的剖析细致到了“令人发指”的地步,
很多我也不是很理解,借助cu这个平台,大家一起分享讨论吧。

lwn.net/Kernel/Index/#Read-copy-update
已经演进了10年了~~~


   

论坛徽章:
8
羊年新春福章
日期:2015-03-19 02:03:312015亚冠之北京国安
日期:2015-06-16 22:04:45程序设计版块每日发帖之星
日期:2015-06-23 22:20:00每日论坛发贴之星
日期:2015-06-23 22:20:002015亚冠之首尔
日期:2015-06-24 19:18:072015亚冠之广州恒大
日期:2015-08-06 10:29:442015亚冠之柏太阳神
日期:2015-11-02 11:21:0515-16赛季CBA联赛之辽宁
日期:2015-12-09 15:05:02
发表于 2015-05-26 15:44 |显示全部楼层
回复 4# nswcfd


lse.sourceforge.net/locking/rcupdate.html
貌似是旧官网
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

基于案例的 SQL 优化实战训练营

讲师:中电福富特级专家梁敬彬,参与本次课程培训,你将收获:
1. 能编写出较为高效的 SQL;
2. 能解决70%以上的数据库常见优化问题;
3. 能得到老师提供的高效的相关工具和解决方案;
4. 能举一反三,收获不仅仅是 SQL 优化。
现在购票享受8.8折优惠!
----------------------------------------
优惠时间:2019年3月20日前

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP