On Tue, Jan 20, 2009 at 10:23:52AM +0800, Peter Teoh wrote: > Thank you Paul. As I read the Documentation/RCU/whatisRCU.txt, I > began to understand perhaps ONE aspect of it, based on my Oracle > database experience and background. > > In Oracle, there is a concept of reader does not block reader, writer > does not block reader, but writer will block another writer. > > And how Oracle can achieve that, is because upon every write, which > open up a new transaction, the rollback segment entry will be created. > All read operation always read the old data, not those in the RBS. > Until the transaction is committed, the RBS element will remain only > visible to the session that issued the write operation. So > effectively, the writer will see his own written data, but all other > reader will always see the old data. But another writer comes along, > and since the previous session is incomplete, it will BLOCK. > > All these easily can be seen to map directly to RCU's reader / writer, > which also explained the need for spinlock/semphore/mutex locking > mechanism needed IF MULTIPLE RCU writer is envisage. There is indeed a strong analogy between the multi-version concurrency control (MVCC) schemes used in databases on the one hand and RCU on the other. However, it is useful to call out a couple of the differences: 1. In MVCC, readers see a consistent view of a given transaction. In RCU, complex updates can be seen by readers before they are fully completed (though it is possible to use RCU in a way that mimics MVCC in this respect). 2. In the form of MVCC that you describe, readers check for updates, and look in the rollback segment when they detect one. In RCU, readers do not check for updates, instead, the updates are responsible for maintaining sufficient state to allow the readers to be "naive" (and thus fast/deterministic) in their accesses. 3. Most MVCC implementations require that the readers synchronize with the history, e.g., with the rollback segment. In RCU, readers are allowed to be completely oblivious to updates. 4. RCU does allow multiple writers in some cases, for example, given a hash table, updaters can concurrently modify the table as long as they are all accessing different hash chains. (Some versions of MVCC allow this as well, particularly those featuring "dirty reads".) > My personal summary, therefore is "reader does not block reader, > writer does not reader, but writer block writer". But there are > other variations of RCU.....which I am still struggling to > understand.....!!!! Good job for the innovation Paul!!! All the variations of RCU have the same general properties, they are just adapted to different environments within the kernel (and, more recently, user space). Glad you like it! ;-) Thanx, Paul > On Tue, Jan 20, 2009 at 7:52 AM, Paul E. McKenney > <paulmck@xxxxxxxxxxxxxxxxxx> wrote: > > On Sat, Jan 17, 2009 at 03:09:16PM +0100, Leon Woestenberg wrote: > >> Hello, > >> > >> On Mon, Jan 12, 2009 at 3:25 PM, Peter Teoh <htmldeveloper@xxxxxxxxx> wrote: > >> > An incredible good technical article: > >> > > >> > http://lwn.net/Articles/305782/ > >> > > >> > May be someone would like to summarize it in 3 or 4 sentences? > >> > > >> Uhh, impossible. My lousy attempt, I have CC: Paul as the designer and author: > >> > >> Read-copy update (RCU) is a novel synchronization mechanism added to > >> the Linux kernel that allows readers to execute concurrently with > >> writers. The classic RCU mechanism scales well up to systems with > >> hundreds of processors, but does not scale well to emerging larger > >> multi-core systems as there is a global lock involved that must be > >> acquired by each CPU. Also, CPUs are woken up regularly, even if they > >> sit idle. A new hierarchical implementation of RCU reduces lock > >> contention and avoids unnecessarily awakening sleeping CPUs. Design by > >> Paul McKenney. > > > > Well done! I doubt that I could do better in 3-4 sentences. > > > > The best introduction to RCU that I know of is the three-part > > LWN series: > > > > http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?) > > http://lwn.net/Articles/263130/ (What is RCU's Usage?) > > http://lwn.net/Articles/264090/ (What is RCU's API?) > > > > Although this series is a great improvement over earlier documentation, > > I am sure that there is ample room for further improvement, and would > > welcome thoughts on its shortcomings and on how it could be improved. > > > > Thanx, Paul > > > > > > -- > Regards, > Peter Teoh -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
