RCU is an advanced concurrency construct, not implemented in a regular application, but valuable for lock-free interviews.
http://concurrencyfreaks.blogspot.sg/2016/09/a-simple-userspace-rcu-in-java.html is a simple java implementation
The Wikipedia article is accessible until the paragraph introducing read-side-critical-section and grace-period. This is the first paragraph on the implementation. I found it hard. Therefore a few background pointers:
· There must be multiple threads, typically many readers and few writers.
· There must a shared mutable data structure, probably on heap.
· Not all data structures are suitable for RCU. So which subset are? I would say pointer-graph including hash tables.
In the simplified model, we are talking about
· A reader thread R1 executing a block of code that has started reading the shared mutable data structure. This code block is the critical section
· A writer thread W1 executing a block of code attempting to update the same data.
· After the so-called grace period, a GC thread would reclaim the obsolete data that R1 has finished reading.
· A reader R2 enters the critical section after the update is done. R2 would see the new data
GC need to know when it’s safe to reclaim. It needs the wait-for-readers operation and the grace period.
Q: What if R1 gets a reference to the “obsolete node”, performs some slow task, reads the node, then exits the critical section? This node is reclaimable only after R1 exits critical section. The grace period would be long?
Q: Among 9999 nodes, how does system keep track which each node is reclaimable?
%%A: I feel kernel access to CPU registers might be needed.
Q: How does it compare with copy-on-write?
A: COW probably copies the entire data structure. Also, the modified copy is not visible to subsequent readers (like R2)
Q: How does it compare with read/write lock?
A: readlock can block
Q: How does it relate to lock-free concepts?
A: reader threads are lock-free and even better — not required to retry.
A GC threads need to wait.
A: Writer thread (like W1) ? not sure. Might be lock-free in some situations.