Date: Thu, 19 Feb 2004 02:08:53 -0800 (PST) From: Ted Unangst <tedu@stanford.edu> To: Doug Rabson <dfr@nlsystems.com> Cc: freebsd-arch@freebsd.org Subject: Re: Read Copy Update Message-ID: <Pine.GSO.4.44.0402190200440.16174-100000@elaine39.Stanford.EDU> In-Reply-To: <1077137806.28133.10.camel@herring.nlsystems.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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. --
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.GSO.4.44.0402190200440.16174-100000>