什么是RCU

这篇文章What is RCU, Fundamentally?     

作者:

Paul E. McKenney, IBM Linux Technology Center

Jonathan Walpole, Portland State University Department of Computer Science

RCU : read-copy-update (RCU) is a synchronization mechanism based on mutual exclusion

        对于RCU机制保护下的数据, 读数据不需要获得任何锁或者很小代价的开销就可以访问, 对于写者需要先拷贝一份副本, 然后修改,最后使用一个回调(callback)机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的操作。

本文主要介绍RCU同步机制的三个部分:

  1. 针对插入操作的发布订阅机制;
  2. 针对删除操作的等待预先启动读者完成机制;
  3. 维护最新更新对象多个版本;

文章中以链表为例介绍了RCU处理过程:

  1. 删除情况下保持多版本:
  1 struct foo {
  2   struct list_head list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 LIST_HEAD(head);
  8 
  9 /* . . . */
 10 
 11 p = search(head, key);
 12 if (p != NULL) {
 13   list_del_rcu(&p->list);
 14   synchronize_rcu();
 15   kfree(p);
 16 }

找到要删除的节点

Initial list
state.

调用list_del_rcu, 但是此时还为真正删除节点

After
deletion.

通过synchronize_rcu等待所有reader  走完grace period.

After deletion.

通过kfree删除节点

After deletion.

  1. 更新情况下保持多版本:
1 struct foo {
  2   struct list_head list;
  3   int a;
  4   int b;
  5   int c;
  6 };
  7 LIST_HEAD(head);
  8 
  9 /* . . . */
 10 
 11 p = search(head, key);
 12 if (p == NULL) {
 13   /* Take appropriate action, unlock, and return. */
 14 }
 15 q = kmalloc(sizeof(*p), GFP_KERNEL);
 16 *q = *p;
 17 q->b = 2;
 18 q->c = 3;
 19 list_replace_rcu(&p->list, &q->list);
 20 synchronize_rcu();
 21 kfree(p);

申请一个要替换的元素

List state after
allocation.

copy旧节点到要替换的元素

List state after
copy.

更新新节点的元素的值,这里是将q->b的值更新为2, q->c的值更新为3:

List state after
update of b.

List state after
update of c.

 这时存在两个版本的链表

List state after
replacement.

通过synchronize_rcu将等待所有reader走出 grace period

List state after
grace period.

通过kfree 删除旧节点

List state after
grace period.

     个人理解RCU机制比较适合大规模CPU场景, 适合大量读并且读数据实时性不是很高的场景,对于写端还是需要锁机制(如spin)来保证并发的一致性。读端与写端, synchronize_rcu回调机制判断reader是否已经完成 grace period。 

     当然RCU 除了linux内核态应用(linux kernel), 也有用户态的一些API liburcu

参考:

Linux 2.6内核中新的锁机制--RCU

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注