Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | Read the F-ing Papers! |
2 | ||
3 | ||
4 | This document describes RCU-related publications, and is followed by | |
5 | the corresponding bibtex entries. | |
6 | ||
7 | The first thing resembling RCU was published in 1980, when Kung and Lehman | |
8 | [Kung80] recommended use of a garbage collector to defer destruction | |
9 | of nodes in a parallel binary search tree in order to simplify its | |
10 | implementation. This works well in environments that have garbage | |
11 | collectors, but current production garbage collectors incur significant | |
12 | read-side overhead. | |
13 | ||
14 | In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring | |
15 | destruction until all threads running at that time have terminated, again | |
16 | for a parallel binary search tree. This approach works well in systems | |
17 | with short-lived threads, such as the K42 research operating system. | |
18 | However, Linux has long-lived tasks, so more is needed. | |
19 | ||
20 | In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive | |
21 | serialization, which is an RCU-like mechanism that relies on the presence | |
22 | of "quiescent states" in the VM/XA hypervisor that are guaranteed not | |
23 | to be referencing the data structure. However, this mechanism was not | |
24 | optimized for modern computer systems, which is not surprising given | |
25 | that these overheads were not so expensive in the mid-80s. Nonetheless, | |
26 | passive serialization appears to be the first deferred-destruction | |
27 | mechanism to be used in production. Furthermore, the relevant patent has | |
28 | lapsed, so this approach may be used in non-GPL software, if desired. | |
29 | (In contrast, use of RCU is permitted only in software licensed under | |
30 | GPL. Sorry!!!) | |
31 | ||
32 | In 1990, Pugh [Pugh90] noted that explicitly tracking which threads | |
33 | were reading a given data structure permitted deferred free to operate | |
34 | in the presence of non-terminating threads. However, this explicit | |
35 | tracking imposes significant read-side overhead, which is undesirable | |
36 | in read-mostly situations. This algorithm does take pains to avoid | |
37 | write-side contention and parallelize the other write-side overheads by | |
38 | providing a fine-grained locking design, however, it would be interesting | |
39 | to see how much of the performance advantage reported in 1990 remains | |
40 | in 2004. | |
41 | ||
42 | At about this same time, Adams [Adams91] described ``chaotic relaxation'', | |
43 | where the normal barriers between successive iterations of convergent | |
44 | numerical algorithms are relaxed, so that iteration $n$ might use | |
45 | data from iteration $n-1$ or even $n-2$. This introduces error, | |
46 | which typically slows convergence and thus increases the number of | |
47 | iterations required. However, this increase is sometimes more than made | |
48 | up for by a reduction in the number of expensive barrier operations, | |
49 | which are otherwise required to synchronize the threads at the end | |
50 | of each iteration. Unfortunately, chaotic relaxation requires highly | |
51 | structured data, such as the matrices used in scientific programs, and | |
52 | is thus inapplicable to most data structures in operating-system kernels. | |
53 | ||
54 | In 1993, Jacobson [Jacobson93] verbally described what is perhaps the | |
55 | simplest deferred-free technique: simply waiting a fixed amount of time | |
56 | before freeing blocks awaiting deferred free. Jacobson did not describe | |
57 | any write-side changes he might have made in this work using SGI's Irix | |
58 | kernel. Aju John published a similar technique in 1995 [AjuJohn95]. | |
59 | This works well if there is a well-defined upper bound on the length of | |
60 | time that reading threads can hold references, as there might well be in | |
61 | hard real-time systems. However, if this time is exceeded, perhaps due | |
62 | to preemption, excessive interrupts, or larger-than-anticipated load, | |
63 | memory corruption can ensue, with no reasonable means of diagnosis. | |
64 | Jacobson's technique is therefore inappropriate for use in production | |
65 | operating-system kernels, except when such kernels can provide hard | |
66 | real-time response guarantees for all operations. | |
67 | ||
68 | Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's | |
69 | read-side-tracking to permit replugging of algorithms within a commercial | |
70 | Unix operating system. However, this replugging permitted only a single | |
71 | reader at a time. The following year, this same group of researchers | |
72 | extended their technique to allow for multiple readers [Cowan96a]. | |
73 | Their approach requires memory barriers (and thus pipeline stalls), | |
74 | but reduces memory latency, contention, and locking overheads. | |
75 | ||
76 | 1995 also saw the first publication of DYNIX/ptx's RCU mechanism | |
77 | [Slingwine95], which was optimized for modern CPU architectures, | |
78 | and was successfully applied to a number of situations within the | |
79 | DYNIX/ptx kernel. The corresponding conference paper appeared in 1998 | |
80 | [McKenney98]. | |
81 | ||
82 | In 1999, the Tornado and K42 groups described their "generations" | |
83 | mechanism, which quite similar to RCU [Gamsa99]. These operating systems | |
84 | made pervasive use of RCU in place of "existence locks", which greatly | |
85 | simplifies locking hierarchies. | |
86 | ||
87 | 2001 saw the first RCU presentation involving Linux [McKenney01a] | |
88 | at OLS. The resulting abundance of RCU patches was presented the | |
89 | following year [McKenney02a], and use of RCU in dcache was first | |
90 | described that same year [Linder02a]. | |
91 | ||
92 | Also in 2002, Michael [Michael02b,Michael02a] presented techniques | |
93 | that defer the destruction of data structures to simplify non-blocking | |
94 | synchronization (wait-free synchronization, lock-free synchronization, | |
95 | and obstruction-free synchronization are all examples of non-blocking | |
96 | synchronization). In particular, this technique eliminates locking, | |
97 | reduces contention, reduces memory latency for readers, and parallelizes | |
98 | pipeline stalls and memory latency for writers. However, these | |
99 | techniques still impose significant read-side overhead in the form of | |
100 | memory barriers. Researchers at Sun worked along similar lines in the | |
101 | same timeframe [HerlihyLM02,HerlihyLMS03]. | |
102 | ||
103 | In 2003, the K42 group described how RCU could be used to create | |
104 | hot-pluggable implementations of operating-system functions. Later that | |
105 | year saw a paper describing an RCU implementation of System V IPC | |
106 | [Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a]. | |
107 | ||
108 | 2004 has seen a Linux-Journal article on use of RCU in dcache | |
109 | [McKenney04a], a performance comparison of locking to RCU on several | |
110 | different CPUs [McKenney04b], a dissertation describing use of RCU in a | |
111 | number of operating-system kernels [PaulEdwardMcKenneyPhD], and a paper | |
112 | describing how to make RCU safe for soft-realtime applications [Sarma04c]. | |
113 | ||
114 | ||
115 | Bibtex Entries | |
116 | ||
117 | @article{Kung80 | |
118 | ,author="H. T. Kung and Q. Lehman" | |
119 | ,title="Concurrent Maintenance of Binary Search Trees" | |
120 | ,Year="1980" | |
121 | ,Month="September" | |
122 | ,journal="ACM Transactions on Database Systems" | |
123 | ,volume="5" | |
124 | ,number="3" | |
125 | ,pages="354-382" | |
126 | } | |
127 | ||
128 | @techreport{Manber82 | |
129 | ,author="Udi Manber and Richard E. Ladner" | |
130 | ,title="Concurrency Control in a Dynamic Search Structure" | |
131 | ,institution="Department of Computer Science, University of Washington" | |
132 | ,address="Seattle, Washington" | |
133 | ,year="1982" | |
134 | ,number="82-01-01" | |
135 | ,month="January" | |
136 | ,pages="28" | |
137 | } | |
138 | ||
139 | @article{Manber84 | |
140 | ,author="Udi Manber and Richard E. Ladner" | |
141 | ,title="Concurrency Control in a Dynamic Search Structure" | |
142 | ,Year="1984" | |
143 | ,Month="September" | |
144 | ,journal="ACM Transactions on Database Systems" | |
145 | ,volume="9" | |
146 | ,number="3" | |
147 | ,pages="439-455" | |
148 | } | |
149 | ||
150 | @techreport{Hennessy89 | |
151 | ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" | |
152 | ,title="Passive Serialization in a Multitasking Environment" | |
153 | ,institution="US Patent and Trademark Office" | |
154 | ,address="Washington, DC" | |
155 | ,year="1989" | |
156 | ,number="US Patent 4,809,168 (lapsed)" | |
157 | ,month="February" | |
158 | ,pages="11" | |
159 | } | |
160 | ||
161 | @techreport{Pugh90 | |
162 | ,author="William Pugh" | |
163 | ,title="Concurrent Maintenance of Skip Lists" | |
164 | ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" | |
165 | ,address="College Park, Maryland" | |
166 | ,year="1990" | |
167 | ,number="CS-TR-2222.1" | |
168 | ,month="June" | |
169 | } | |
170 | ||
171 | @Book{Adams91 | |
172 | ,Author="Gregory R. Adams" | |
173 | ,title="Concurrent Programming, Principles, and Practices" | |
174 | ,Publisher="Benjamin Cummins" | |
175 | ,Year="1991" | |
176 | } | |
177 | ||
178 | @unpublished{Jacobson93 | |
179 | ,author="Van Jacobson" | |
180 | ,title="Avoid Read-Side Locking Via Delayed Free" | |
181 | ,year="1993" | |
182 | ,month="September" | |
183 | ,note="Verbal discussion" | |
184 | } | |
185 | ||
186 | @Conference{AjuJohn95 | |
187 | ,Author="Aju John" | |
188 | ,Title="Dynamic vnodes -- Design and Implementation" | |
189 | ,Booktitle="{USENIX Winter 1995}" | |
190 | ,Publisher="USENIX Association" | |
191 | ,Month="January" | |
192 | ,Year="1995" | |
193 | ,pages="11-23" | |
194 | ,Address="New Orleans, LA" | |
195 | } | |
196 | ||
197 | @techreport{Slingwine95 | |
198 | ,author="John D. Slingwine and Paul E. McKenney" | |
199 | ,title="Apparatus and Method for Achieving Reduced Overhead Mutual | |
200 | Exclusion and Maintaining Coherency in a Multiprocessor System | |
201 | Utilizing Execution History and Thread Monitoring" | |
202 | ,institution="US Patent and Trademark Office" | |
203 | ,address="Washington, DC" | |
204 | ,year="1995" | |
205 | ,number="US Patent 5,442,758 (contributed under GPL)" | |
206 | ,month="August" | |
207 | } | |
208 | ||
209 | @techreport{Slingwine97 | |
210 | ,author="John D. Slingwine and Paul E. McKenney" | |
211 | ,title="Method for maintaining data coherency using thread | |
212 | activity summaries in a multicomputer system" | |
213 | ,institution="US Patent and Trademark Office" | |
214 | ,address="Washington, DC" | |
215 | ,year="1997" | |
216 | ,number="US Patent 5,608,893 (contributed under GPL)" | |
217 | ,month="March" | |
218 | } | |
219 | ||
220 | @techreport{Slingwine98 | |
221 | ,author="John D. Slingwine and Paul E. McKenney" | |
222 | ,title="Apparatus and method for achieving reduced overhead | |
223 | mutual exclusion and maintaining coherency in a multiprocessor | |
224 | system utilizing execution history and thread monitoring" | |
225 | ,institution="US Patent and Trademark Office" | |
226 | ,address="Washington, DC" | |
227 | ,year="1998" | |
228 | ,number="US Patent 5,727,209 (contributed under GPL)" | |
229 | ,month="March" | |
230 | } | |
231 | ||
232 | @Conference{McKenney98 | |
233 | ,Author="Paul E. McKenney and John D. Slingwine" | |
234 | ,Title="Read-Copy Update: Using Execution History to Solve Concurrency | |
235 | Problems" | |
236 | ,Booktitle="{Parallel and Distributed Computing and Systems}" | |
237 | ,Month="October" | |
238 | ,Year="1998" | |
239 | ,pages="509-518" | |
240 | ,Address="Las Vegas, NV" | |
241 | } | |
242 | ||
243 | @Conference{Gamsa99 | |
244 | ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" | |
245 | ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory | |
246 | Multiprocessor Operating System" | |
247 | ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on | |
248 | Operating System Design and Implementation}" | |
249 | ,Month="February" | |
250 | ,Year="1999" | |
251 | ,pages="87-100" | |
252 | ,Address="New Orleans, LA" | |
253 | } | |
254 | ||
255 | @techreport{Slingwine01 | |
256 | ,author="John D. Slingwine and Paul E. McKenney" | |
257 | ,title="Apparatus and method for achieving reduced overhead | |
258 | mutual exclusion and maintaining coherency in a multiprocessor | |
259 | system utilizing execution history and thread monitoring" | |
260 | ,institution="US Patent and Trademark Office" | |
261 | ,address="Washington, DC" | |
262 | ,year="2001" | |
263 | ,number="US Patent 5,219,690 (contributed under GPL)" | |
264 | ,month="April" | |
265 | } | |
266 | ||
267 | @Conference{McKenney01a | |
268 | ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and | |
269 | Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" | |
270 | ,Title="Read-Copy Update" | |
271 | ,Booktitle="{Ottawa Linux Symposium}" | |
272 | ,Month="July" | |
273 | ,Year="2001" | |
274 | ,note="Available: | |
275 | \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} | |
276 | \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} | |
277 | [Viewed June 23, 2004]" | |
278 | annotation=" | |
279 | Described RCU, and presented some patches implementing and using it in | |
280 | the Linux kernel. | |
281 | " | |
282 | } | |
283 | ||
284 | @Conference{Linder02a | |
285 | ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" | |
286 | ,Title="Scalability of the Directory Entry Cache" | |
287 | ,Booktitle="{Ottawa Linux Symposium}" | |
288 | ,Month="June" | |
289 | ,Year="2002" | |
290 | ,pages="289-300" | |
291 | } | |
292 | ||
293 | @Conference{McKenney02a | |
294 | ,Author="Paul E. McKenney and Dipankar Sarma and | |
295 | Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" | |
296 | ,Title="Read-Copy Update" | |
297 | ,Booktitle="{Ottawa Linux Symposium}" | |
298 | ,Month="June" | |
299 | ,Year="2002" | |
300 | ,pages="338-367" | |
301 | ,note="Available: | |
302 | \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} | |
303 | [Viewed June 23, 2004]" | |
304 | } | |
305 | ||
306 | @article{Appavoo03a | |
307 | ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and | |
308 | D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and | |
309 | B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and | |
310 | B. Rosenburg and M. Stumm and J. Xenidis" | |
311 | ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" | |
312 | ,Year="2003" | |
313 | ,Month="January" | |
314 | ,journal="IBM Systems Journal" | |
315 | ,volume="42" | |
316 | ,number="1" | |
317 | ,pages="60-76" | |
318 | } | |
319 | ||
320 | @Conference{Arcangeli03 | |
321 | ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and | |
322 | Dipankar Sarma" | |
323 | ,Title="Using Read-Copy Update Techniques for {System V IPC} in the | |
324 | {Linux} 2.5 Kernel" | |
325 | ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference | |
326 | (FREENIX Track)" | |
327 | ,Publisher="USENIX Association" | |
328 | ,year="2003" | |
329 | ,month="June" | |
330 | ,pages="297-310" | |
331 | } | |
332 | ||
333 | @article{McKenney03a | |
334 | ,author="Paul E. McKenney" | |
335 | ,title="Using {RCU} in the {Linux} 2.5 Kernel" | |
336 | ,Year="2003" | |
337 | ,Month="October" | |
338 | ,journal="Linux Journal" | |
339 | ,volume="1" | |
340 | ,number="114" | |
341 | ,pages="18-26" | |
342 | } | |
343 | ||
344 | @article{McKenney04a | |
345 | ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" | |
346 | ,title="Scaling dcache with {RCU}" | |
347 | ,Year="2004" | |
348 | ,Month="January" | |
349 | ,journal="Linux Journal" | |
350 | ,volume="1" | |
351 | ,number="118" | |
352 | ,pages="38-46" | |
353 | } | |
354 | ||
355 | @Conference{McKenney04b | |
356 | ,Author="Paul E. McKenney" | |
357 | ,Title="{RCU} vs. Locking Performance on Different {CPUs}" | |
358 | ,Booktitle="{linux.conf.au}" | |
359 | ,Month="January" | |
360 | ,Year="2004" | |
361 | ,Address="Adelaide, Australia" | |
362 | ,note="Available: | |
363 | \url{http://www.linux.org.au/conf/2004/abstracts.html#90} | |
364 | \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} | |
365 | [Viewed June 23, 2004]" | |
366 | } | |
367 | ||
368 | @phdthesis{PaulEdwardMcKenneyPhD | |
369 | ,author="Paul E. McKenney" | |
370 | ,title="Exploiting Deferred Destruction: | |
371 | An Analysis of Read-Copy-Update Techniques | |
372 | in Operating System Kernels" | |
373 | ,school="OGI School of Science and Engineering at | |
374 | Oregon Health and Sciences University" | |
375 | ,year="2004" | |
376 | } | |
377 | ||
378 | @Conference{Sarma04c | |
379 | ,Author="Dipankar Sarma and Paul E. McKenney" | |
380 | ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" | |
381 | ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference | |
382 | (FREENIX Track)" | |
383 | ,Publisher="USENIX Association" | |
384 | ,year="2004" | |
385 | ,month="June" | |
386 | ,pages="182-191" | |
387 | } |