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 |
网友评论