线程同步技术之RCU

本文出自:【InTheWorld的博客】

多核程序设计其实挺困难的，就拿RCU(Read-Copy-Update)技术来说，我现在已经不知道自己看《深入理解并行编程》的RCU多少次了。到现在为止，还是有一些东西没有完全理解。这篇blog算是对我所领会到的RCU知识的暂时性总结。

• RCU背景

从个人的理解来讲，RCU其实是对rwLock的一种优化。从不区分读写的粗粒度锁到读写锁，然后到RCU机制，这就体现着并行程序设计的不断演进。rwLock的思路是，多线程读取不存在同步问题，所以放宽了读取锁，提高了并发读取的效率。而RCU的思路是，维持临界区多个版本（完整的非中间版本），同时取消读取锁，这种优化将会进一步的提高读取效率。事实上，在多数的多线程应用场景上，读取频率都是远远大于改写频率的。特别是在Linux内核中，很多全局数据结构会被同时读取，其次数远高于写入次数。

Figure 1

Figure1所示的是RCU相较于rwLock的读端性能优势。从图中可以明显的看出，随着CPU数目的增多，rwlock读取性能下降明显。这是因为在读写锁中，写锁排斥读取的特点导致很多CPU的读取被整体拖慢。而对于RCU来说，CPU的增多却不会明显导致读取性能下降。因为RCU的读端基本是没有锁的。

• 单链表RCU基本原理

RCU在多种数据结构中都有相应的实现，这里我们主要讨论一下RCU在单链表中的实现。单链表的核心就在于指针域，RCU就是利用了指针的一些特性，完成了多版本的维护。RCU保护的是指针，因为指针赋值是一条单指令。配合内存屏障与Lock前缀，指针赋值是一个原子操作，更改指针指向没必要考虑它的同步，只需要考虑cache的影响。

RCU可以支持多种链表操作，下图以链表的修改为例说明RCU的工作原理。

RCU的关键步骤在于两次指针的改写，第一次出现在Copy的步骤中，一次出现在synchronize_rcu()中。代码段如下：

   q = kmalloc(sizeof(*p), GFP_KERNEL);
    *q = *p;
    q->b = 2;
    q->c = 3;
    list_replace_rcu(&p->list, &q->list);
    synchronize_rcu();
    kfree(p);

list_replace_rcu()即是实现了Copy的操作，这个操作要保证是原子性的。RCU写端的最重要的逻辑都在这synchronize_rcu()里面。synchronize_rcu会阻塞一定时间，等待读取端释放掉旧的引用，这段时间被称为Grace Period。synchronize_rcu的具体实现在下一节详细讲。下图中是，rwlock与RCU在运行时的比较：

这张图可以看出，rwlock与RCU区别非常大，效率上RCU是优于rwlock的，而且在RCU updater运行期间会存在多个版本。

• 简单的RCU实现

这一节RCU的实现其实来自于《深入理解并行编程》中的一个简单RCU实现。

   atomic_t rcu_refcnt;
    
    static void rcu_read_lock(void)
    {
        atomic_inc(&rcu_refcnt);
        smp_mb();
    }
    
    static void rcu_read_unlock(void)
    {
        smp_mb();
             atomic_dec(&rcu_refcnt);
    }
    
    void synchronize_rcu(void)
    {
        smp_mb();
        while (atomic_read(&rcu_refcnt) != 0) {
            poll(NULL, 0, 10);
        }
        smp_mb();
    }

这个RCU基本上只是一个demo型的实现，性能非常差。其中这个RCU的读端，使用原子操作实现了引用技术的功能。在synchronize_rcu()作为写端实现，主要的内容就是等待引用计数为0，然后释放不被引用的旧节点。

参考资料：

《深入理解并行编程》