借助shared_ptr模拟RCU(read-copy-update)

RCU较RWL有更好的性能,其读操作几乎是free的;writer需要先对原始数据做一份拷贝,再进行修改(在同一时刻只能有一个writer),完成之后替换掉原来的指针(如果swap不是原子性操作,需要critical section的保护);然后,由reclaimer在适当的时机将原始数据占用的内存释放掉。这样,writer不像RWL会因为有reader而被阻塞。RCU和RWL一样,比较适用于读多写少的情景。

RCU多见于操作系统的内核中,也有user-space的实现可供参考(liburcu)。个人觉得,如果将reclaimer的回收工作分摊到某个reader或writer上,借用tr1::shared_ptr,应该可以很方便的实现。下面是实现的代码,我对并发编程经验尚浅,一直拿不太准,是否正确实现了,贴出来请大家多指正!

基本思路是这样的,reader可以通过get_reading_copy()获得当前数据的shared_ptr(记为Generation 1,G1);不过当m_is_swapping为1时,要阻塞等待。writer通过get_updating_copy()得到当前数据的一个副本(记为Generation 2,G2),由m_is_writing进行保护,只允许有一个写者进入;在更新完成之后,writer调用update()将这个副本的shared_ptr传回来,然后通过swap操作令m_data_ptr指向新的数据(G2),然后打开m_is_writing和m_is_swapping。writer持有的那个shared_ptr在调用update()之后指向了原始数据(G1),之前reader(s)持有的shared_ptr(s)也同样指向的是原始数据(G1),当这些shared_ptr(s)统统被析构时,会释放掉原始数据所占用的内存(可能发生在writer或reader上)。新的reader则会获得新数据的shared_ptr。如果有另外一个writer进入,得到的是新数据的副本(记为Generation 3,G3)。因此,如果指向G1的那些shared_ptr(s)还没有被完全析构时,有可能存在多个不同代(generations)的数据副本。

template <typename T>
class rcu_protected
{
public:
    typedef T                                   type;
    typedef const T                             const_type;
    typedef std::tr1::shared_ptr<type>          rcu_pointer;
    typedef std::tr1::shared_ptr<const_type>    rcu_const_pointer;

    rcu_protected() : m_data_ptr (new type()) {}

    rcu_protected(T* data) : m_data_ptr (data) {}

    rcu_const_pointer get_reading_copy ()
    {
        LockGuard< CRWLock,
                  &CRWLock::read_lock,
                  &CRWLock::read_unlock> l_guard (m_ptr_lock);

        return m_data_ptr;
    }

    rcu_pointer get_updating_copy ()
    {
        m_writer_lock.write_lock();

        LockGuard< CRWLock,
                  &CRWLock::read_lock,
                  &CRWLock::read_unlock> l_guard (m_ptr_lock);

        return rcu_pointer(new type(*m_data_ptr));
    }

    void update (rcu_pointer new_data_ptr)
    {
        LockGuard< CRWLock,
                  &CRWLock::write_lock,
                  &CRWLock::write_unlock> l_guard (m_ptr_lock);

        m_data_ptr.swap (new_data_ptr);

        m_writer_lock.write_unlock();
    }

private:
    CRWLock     m_ptr_lock;
    CRWLock     m_writer_lock;
    rcu_pointer m_data_ptr;
};

自注:

  1. 在VC2005之后(包括2005),编译器对volatile变量的访问会自动加fence,所以那两个barrier(s)可以省去。
  2. 其实在update()中,直接将new_data_ptr赋值给m_data_ptr应该也是可以的,但是可能导致在update()中去析构m_data_ptr指向的数据,而我们应该让update()能尽可能快的完成。
  3. 感谢Dmitry Vyukovreview,我遗漏了一种简单的情况,当reader等到m_is_swapping为0,准备拷贝指针时,突然又有writer线程进入要update指针,这就可能导致crash了… 应该用一个rw_lock将读和写保护起来 … 教训啊,任何关键数据的读写,都应该是全程保护的 …

7 thoughts on “借助shared_ptr模拟RCU(read-copy-update)

  1. 先自己加个comment,在VC2005之后(包括2005),编译器对volatile变量的访问会自动加fence,所以那两个barrier(s)可以省去。

  2. 另有,不知能否将read copy返回为shared_ptr<const type>? 回头试一试 ...

  3. 其实在update时,直接将new_data_ptr赋值给m_data_ptr应该也是可以的,但是可能导致在update()中去析构m_data_ptr指向的数据,而我们应该让update()能尽可能快的完成 ...

  4. 感谢dvyukov@gmail.com的review,我遗漏了一种简单的情况,当reader等到m_is_swapping为0,准备拷贝指针时,突然又有writer线程进入要update指针,这就可能导致crash了... 应该用一个rw_lock将读和写保护起来 ... 教训啊,任何关键数据的读写,都应该是全程保护的 ...

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha