Date: Thu, 19 Feb 2004 10:14:37 +0000 From: Doug Rabson <dfr@nlsystems.com> To: Ted Unangst <tedu@stanford.edu> Cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update Message-ID: <1077185677.28133.29.camel@herring.nlsystems.com> In-Reply-To: <Pine.GSO.4.44.0402190200440.16174-100000@elaine39.Stanford.EDU> References: <Pine.GSO.4.44.0402190200440.16174-100000@elaine39.Stanford.EDU>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, 2004-02-19 at 10:08, Ted Unangst wrote: > On Wed, 18 Feb 2004, Doug Rabson wrote: > > > I read one of the original papers at > > http://www.rdrop.com/users/paulmck/paper/rclockpdcsproof.pdf and its a > > surprisingly simple idea. Basically for certain data structures which > > are read-mostly, you can make the entire read path lock-free at the > > expense of making updates quite a bit more expensive. They claim that > > its much faster than reader-writer locks both for light contention and > > for heavy contention. > > consider the following for the linked list example given. A -> B -> C > > thread 0 was changing B. creates B', links A -> B' -> C. waits for > quiet time, free(B). > > thread 1 is walking list. when it's done, signals quiet time. > > what if both threads want to change B? > > thread 0 walks list to B. > thread 1 walks list to B. > thread 0 creates B'. > thread 1 creates B''. > thread 0 links list A -> B' -> C > thread 1 links list A -> B'' -> C > thread 0 creates callback. > thread 1 creates callback. > thread 0 callback runs, free(B). > thread 1 callback runs, free(B). *boom* > > excuse me if i missed it, but i didn't see this addressed in the paper. This is mentioned in the paper where they say that 'Thread 0 must use some sort of update discipline to handle concurrent updates'. Effectively, updates to the list must be serialised using e.g. a mutex but simple list traversals don't need to take the mutex.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?1077185677.28133.29.camel>