Read-copy-update
|
|
Read-copy-update is an operating system kernel technology for improving performance on computers with more than one CPU.
The basic idea is as follows. Assume you have a data structure which is shared by multiple threads of execution. When a thread wants to read the structure, it uses a pointer to the structure and continues on, without any locking or checking. This makes reading the data structure as efficient as reading a non-shared data structure.
When a thread wants to write to the structure, it
- creates a new structure,
- copies the data from the old structure into the new one, and saves a pointer to the old structure,
- modifies the new, copied, structure
- updates the global pointer to refer to the new structure, and then
- sleeps until the operating system kernel determines that there are no readers left using the old structure.
When the thread which made the copy is woken up by the kernel, it can safely deallocate the old structure.
This technique is great for data which is read frequently but updated infrequently, but is not designed to be efficient in other cases.
The technique is covered by U.S. software patent 5,442,758, issued August 15, 1995 and assigned to Sequent Computer Systems. It is also the topic of one of the claims in the SCO v. IBM lawsuit.
External links
- Paul McKenney's RCU Page (http://www.rdrop.com/users/paulmck/RCU/)
- Patent 5,442,758 (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=5,442,758.WKU.&OS=PN/5,442,758&RS=PN/5,442,758) from the United States Patent and Trademark Office website
- Using RCU in the Linux 2.5 kernel (http://www.linuxjournal.com/article.php?sid=6993)
- Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques in Operating System Kernels (http://www.rdrop.com/users/paulmck/rclock/RCUdissertation.2004.07.14e1.pdf)