线程同步技术之RCU

本文出自:【InTheWorld的博客】

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

  • RCU背景

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

image

Figure 1

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

  • 单链表RCU基本原理

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

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

imageimage

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在运行时的比较:

image

这张图可以看出,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,然后释放不被引用的旧节点。

 

参考资料:

《深入理解并行编程》

发表评论