素心如何天上月

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 Vyukov的review，我遗漏了一种简单的情况，当reader等到m_is_swapping为0，准备拷贝指针时，突然又有writer线程进入要update指针，这就可能导致crash了… 应该用一个rw_lock将读和写保护起来 … 教训啊，任何关键数据的读写，都应该是全程保护的 …