What is RCU, Fundamentally? [LWN.net]

What is RCU, Fundamentally?

Posted Dec 27, 2007 19:04 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624)
In reply to: What is RCU, Fundamentally? by union
Parent article: What is RCU, Fundamentally?

Glad you liked it!!!  ;-)

Garbage-collected languages such as Java implement RCU's "wait for pre-existing RCU readers to
complete" implicitly via the garbage collector.  However, in Java, you must make careful use
of atomic variables in order to correctly implement the publish-subscribe mechanism.  Last I
knew, Java would emit memory barriers for the subscribe operation, even when unnecessary, but
perhaps that has changed by now.  However, in many cases, the memory-barrier overhead might
well be acceptable (e.g., when avoiding contention).

So you might well be able to use RCU techniques in Java!  (For whatever it is worth, Kung and
Lehman described the gist of using garbage collectors in this fashion in their paper entitled
"Concurrent Maintenance of Binary Search Trees" in "ACM Transactions on Database Systems" back
in September 1980.)

to post comments

What is RCU, Fundamentally?

Posted Dec 27, 2007 23:47 UTC (Thu) by scottt (subscriber, #5028) [Link] (1 responses)

A link to the paper.

With people doing all these advanced concurrent algorithms in the eighties I wonder why we're only just now getting a formal memory model for the C/C++ programming languages.

What is RCU, Fundamentally?

Posted Dec 28, 2007 15:22 UTC (Fri) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

Thank you for providing the link -- much better than my old hard copy!  It is very good indeed
to see some of these older papers becoming available on the web.

There was indeed some memory-consistency-model research done some decades ago.  Although I
cannot claim comprehensive knowledge of memory-model research, as near as I can tell, almost
all of this older research was swept aside by the notion of sequential consistency in 1979.
The lion's share of later research assumed sequential consistency, which rendered this research
less than helpful on weakly-ordered machines, where "weakly ordered" includes x86.  Algorithms
that fail to work on x86 cannot be said to have much practical value, in my opinion.

There were nevertheless some fundamental papers published in the 90s (e.g., Sarita Adve and
Kourosh Gharachorloo, among others), but many of the researchers focused on "how to emulate
sequential consistency on weak-memory machines" as opposed to "how best to express
memory-ordering constraints while allowing efficient code to be generated for systems with a
wide variety of memory consistency models".  It is this latter statement that the C/C++
standards committee must address.