baiwfg2
commented
3 years ago http://www2.rdrop.com/users/paulmck/RCU/ 这里有关RCU的论文、文章
上面的链接转向了这里：https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit
2001, paper
http://www2.rdrop.com/~paulmck/RCU/rclock_OLS.2001.05.01c.pdf 路由表更新属read-mostly 的结构？
举了kernel module unloading 的例子
a quiescent state is a point in the code at which it's guaranteed that all previous operations have completed. the end of the grace period is detected via quiescent states
Without special action in the deletion code, the search code would be prone to races with those deletions, described in Section 2.1. To handle such race conditions, the update side performs the update in two phases as follows: (1) remove permanent-variable pointers to the item being deleted, and (2) after a grace period has elapsed, free up the item's memory.
The grace period is not a fixed time duration, but is instead inferred by checking for per-CPU quiescent states, such as context switches in non-preemptive environments. Since kernel threads are prohibited from holding locks across a context switch, they also prohibited from holding pointers to data structures protected by those locks across context switches-after all, the entire data structure could well be deleted by some other CPU at any time this CPU does not hold the lock.
A trivial implementation of RCU in a non-preemptive kernel could simply declare the grace period over once it observed each CPU undergoing a context switch. Once the grace period completes, no CPU references the deleted item, and no CPU can gain such a reference. It is therefore safe to free up the deleted item.
With this approach, searches already in progress when the first phase executes might (or might not) see the item being deleted. However, searches that start after the first phase completes are guaranteed to never reference this item. Efficient mechanisms for determining the duration of the grace period are key to RCU, and are described fully elsewhere [McK02a]. These mechanisms track ``naturally occurring'' quiescent states, which removes the need for adding expensive context switches. In addition, these mechanisms take advantage of the fact that a single grace period can satisfy multiple concurrent updates, amortizing the cost of detecting a grace period over the updates
RCU 适合场景条件：
- 可以将update 拆成两个阶段
- 允许操作stale data
- 破坏性更新很少见 这些情况在OS 中很常见
traditional locking is limited by worse-case memory latency. 因为获取锁意味着要写锁结构，这样cache line就不断失效，下次获取锁就得remote acccess
RCU一个问题是可能需要维护一定量的等待free的内存。
另外，perfbook 第9章 Deferred Processing, Michael Scott 的 Shared-Memory Synchronization 6.3节，都谈到了 RCU
🍅 [1] what is RCU , perfbook 作者 Paul McKenney
http://www.rdrop.com/~paulmck/RCU/whatisRCU.html
在linux kernel 里是有单独的线程去做updater的回收过程（处理directory-entry cache 时）
synchronize_rcu()只是等待在它调用之前的read-side CS，不用等之后的reader；且不一定在最后一个 read-side CS 完成后立即返回，一方面有调度时延，另一方面批处理会有拖延即只能在 read lock , read unlock 之间使用
内核中使用RCU （read-copy-update） 这种机制来同步updater和reader，避免用锁。
updater之间还是要同步的（可能用锁、信号量之类的），原语本身仅是在同步updater和reader； 如果不希望updater因调用
synchronize_rcu()被阻塞，则可以换成call_rcu()异步方式，待reader 都离开了CS后，注册的回调被调用(即是update 的second phase，reclaimer 过程)；toy implementations列举了两种，一种是基于锁实现，另一种是classic RCU,借助
run_on(cpu)，当reader干完了，自然run_on 也就返回了？最常见的用途就是并发读写时，类比于reader-writer locking