美文网首页
RCU设计原理

RCU设计原理

作者: 谭英智 | 来源:发表于2023-01-11 17:43 被阅读0次

    RCU设计原理

    [toc]

    概要

    RCU全名 Read, Copy, Update

    是一种针对多线程读多写少的数据的更新方法

    它的读性能高于读写锁和自旋锁

    通过牺牲写性能,让读性能最大化

    rcu-performence_cmp

    设计

    std::atomic<node*> head;
    

    Reader

    原子遍历链表

    node* p = head.load(std::memory_order_acquire);
    do_search(p);
    

    Writer

    原子更新需要修改的节点

    写入需要加mutex lock,避免多个线程冲突修改数据结构

    mutex_lock();
    node* new_node = new node(…);
    new_node->next =
    head.load(std::memory_order_relaxed)->next;
    head.store(new_node, std::memory_order_release);
    
    rcu-write

    旧版本节点内存回收

    可以通过share_pointer来管理每个节点
    • 优点,写的速度比较快,不会阻塞
    • 缺点:频繁更新原子计算,导致读性能下降
    通过以版本号为单位来做引用计数
    • 每次更新节点后,版本号自增一
    • 每次需要读,都对对应的版本的引用计数加一
    • 读完需要释放,把对应版本的引用计数减一
    • gc时判断历史版本的计数是不是为零,为零则可以回收对应版本的内存

    代码如下:

    Reader代码

    每次操作数据时需要调用rcu_read_lock,来把对应版本的引用加一

    操作完数据后需要调用rcu_read_unlock,来把对应版本的引用减一

    rcu_read_lock();
    node* p = head.load(std::memory_order_acquire);
    do_search(p);
    rcu_read_unlock();
    

    lock和unlock的实现如下:

    std::atomic<unsigned long> generation;
    std::atomic<unsigned long> refcount[max_generations];
    class handle_t {…}; // Contains reader generation
    handle_t rcu_read_lock() {
     size_t cg=generation;
     ++refcount[cg];
     return handle_t(cg);
    }
    void rcu_read_unlock(handle_t handle) {
     --refcount[handle.get()];
    }
    
    Writer代码

    内存回收需要判断旧版本的引用计数是否为零

    为零则回收

    std::atomic<unsigned long> generation;
    std::atomic<unsigned long> refcount[max_generations];
    std::queue<data_t*> garbage[max_generations];
    unsigned long last_gc_gen = 0;
    void synchronize_rcu() {
     unsigned long last_gen = generation++;
     while (last_gc_gen < last_gen) {
     while (refcount[last_gc_gen] > 0) wait();
     delete_garbage(garbage[last_gc_gen]);
     ++last_gc_gen;
     }
    }
    
    某线程长时间持有节点的内存

    需要有超时策略,超时则强制回收内存,回收后的内存不做delete操作,而是复用到新版本的节点,在读操作后,需要判断内存是否已被修改,如果修改了,则需要redo

    reader:

    do {
        rcu_read_lock();
        node* p = head.load(std::memory_order_acquire);
        do_search(p);
    } while(rcu_read_unlock());
    
    多线程(读线程)共享一个原子变量带来的性能问题

    通过cache line对齐,减少伪共享带来的性能问题

    struct alignas(64) GenHash {
        std::atomic<unsigned long> ref_count;
    };
    std::atomic<unsigned long> generation;
    vector<GenHash> refcount[max_generations];
    
    性能对比
    RCU Atomic shared_ptr
    Readers fast slow
    Writers slow fast
    Reclamation blocking lock-free
    Garbage blocking lock-free
    Ease of use very easy easy

    RCU在不同场景下的应用选择比较

    rcu-use

    相关文章

      网友评论

          本文标题:RCU设计原理

          本文链接:https://www.haomeiwen.com/subject/gvticdtx.html