Root/
1 | Read the F-ing Papers! |
2 | |
3 | |
4 | This document describes RCU-related publications, and is followed by |
5 | the corresponding bibtex entries. A number of the publications may |
6 | be found at http://www.rdrop.com/users/paulmck/RCU/. |
7 | |
8 | The first thing resembling RCU was published in 1980, when Kung and Lehman |
9 | [Kung80] recommended use of a garbage collector to defer destruction |
10 | of nodes in a parallel binary search tree in order to simplify its |
11 | implementation. This works well in environments that have garbage |
12 | collectors, but most production garbage collectors incur significant |
13 | overhead. |
14 | |
15 | In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring |
16 | destruction until all threads running at that time have terminated, again |
17 | for a parallel binary search tree. This approach works well in systems |
18 | with short-lived threads, such as the K42 research operating system. |
19 | However, Linux has long-lived tasks, so more is needed. |
20 | |
21 | In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive |
22 | serialization, which is an RCU-like mechanism that relies on the presence |
23 | of "quiescent states" in the VM/XA hypervisor that are guaranteed not |
24 | to be referencing the data structure. However, this mechanism was not |
25 | optimized for modern computer systems, which is not surprising given |
26 | that these overheads were not so expensive in the mid-80s. Nonetheless, |
27 | passive serialization appears to be the first deferred-destruction |
28 | mechanism to be used in production. Furthermore, the relevant patent |
29 | has lapsed, so this approach may be used in non-GPL software, if desired. |
30 | (In contrast, implementation of RCU is permitted only in software licensed |
31 | under either GPL or LGPL. Sorry!!!) |
32 | |
33 | In 1990, Pugh [Pugh90] noted that explicitly tracking which threads |
34 | were reading a given data structure permitted deferred free to operate |
35 | in the presence of non-terminating threads. However, this explicit |
36 | tracking imposes significant read-side overhead, which is undesirable |
37 | in read-mostly situations. This algorithm does take pains to avoid |
38 | write-side contention and parallelize the other write-side overheads by |
39 | providing a fine-grained locking design, however, it would be interesting |
40 | to see how much of the performance advantage reported in 1990 remains |
41 | in 2004. |
42 | |
43 | At about this same time, Adams [Adams91] described ``chaotic relaxation'', |
44 | where the normal barriers between successive iterations of convergent |
45 | numerical algorithms are relaxed, so that iteration $n$ might use |
46 | data from iteration $n-1$ or even $n-2$. This introduces error, |
47 | which typically slows convergence and thus increases the number of |
48 | iterations required. However, this increase is sometimes more than made |
49 | up for by a reduction in the number of expensive barrier operations, |
50 | which are otherwise required to synchronize the threads at the end |
51 | of each iteration. Unfortunately, chaotic relaxation requires highly |
52 | structured data, such as the matrices used in scientific programs, and |
53 | is thus inapplicable to most data structures in operating-system kernels. |
54 | |
55 | In 1992, Henry (now Alexia) Massalin completed a dissertation advising |
56 | parallel programmers to defer processing when feasible to simplify |
57 | synchronization. RCU makes extremely heavy use of this advice. |
58 | |
59 | In 1993, Jacobson [Jacobson93] verbally described what is perhaps the |
60 | simplest deferred-free technique: simply waiting a fixed amount of time |
61 | before freeing blocks awaiting deferred free. Jacobson did not describe |
62 | any write-side changes he might have made in this work using SGI's Irix |
63 | kernel. Aju John published a similar technique in 1995 [AjuJohn95]. |
64 | This works well if there is a well-defined upper bound on the length of |
65 | time that reading threads can hold references, as there might well be in |
66 | hard real-time systems. However, if this time is exceeded, perhaps due |
67 | to preemption, excessive interrupts, or larger-than-anticipated load, |
68 | memory corruption can ensue, with no reasonable means of diagnosis. |
69 | Jacobson's technique is therefore inappropriate for use in production |
70 | operating-system kernels, except when such kernels can provide hard |
71 | real-time response guarantees for all operations. |
72 | |
73 | Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's |
74 | read-side-tracking to permit replugging of algorithms within a commercial |
75 | Unix operating system. However, this replugging permitted only a single |
76 | reader at a time. The following year, this same group of researchers |
77 | extended their technique to allow for multiple readers [Cowan96a]. |
78 | Their approach requires memory barriers (and thus pipeline stalls), |
79 | but reduces memory latency, contention, and locking overheads. |
80 | |
81 | 1995 also saw the first publication of DYNIX/ptx's RCU mechanism |
82 | [Slingwine95], which was optimized for modern CPU architectures, |
83 | and was successfully applied to a number of situations within the |
84 | DYNIX/ptx kernel. The corresponding conference paper appeared in 1998 |
85 | [McKenney98]. |
86 | |
87 | In 1999, the Tornado and K42 groups described their "generations" |
88 | mechanism, which quite similar to RCU [Gamsa99]. These operating systems |
89 | made pervasive use of RCU in place of "existence locks", which greatly |
90 | simplifies locking hierarchies. |
91 | |
92 | 2001 saw the first RCU presentation involving Linux [McKenney01a] |
93 | at OLS. The resulting abundance of RCU patches was presented the |
94 | following year [McKenney02a], and use of RCU in dcache was first |
95 | described that same year [Linder02a]. |
96 | |
97 | Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer" |
98 | techniques that defer the destruction of data structures to simplify |
99 | non-blocking synchronization (wait-free synchronization, lock-free |
100 | synchronization, and obstruction-free synchronization are all examples of |
101 | non-blocking synchronization). In particular, this technique eliminates |
102 | locking, reduces contention, reduces memory latency for readers, and |
103 | parallelizes pipeline stalls and memory latency for writers. However, |
104 | these techniques still impose significant read-side overhead in the |
105 | form of memory barriers. Researchers at Sun worked along similar lines |
106 | in the same timeframe [HerlihyLM02]. These techniques can be thought |
107 | of as inside-out reference counts, where the count is represented by the |
108 | number of hazard pointers referencing a given data structure (rather than |
109 | the more conventional counter field within the data structure itself). |
110 | |
111 | By the same token, RCU can be thought of as a "bulk reference count", |
112 | where some form of reference counter covers all reference by a given CPU |
113 | or thread during a set timeframe. This timeframe is related to, but |
114 | not necessarily exactly the same as, an RCU grace period. In classic |
115 | RCU, the reference counter is the per-CPU bit in the "bitmask" field, |
116 | and each such bit covers all references that might have been made by |
117 | the corresponding CPU during the prior grace period. Of course, RCU |
118 | can be thought of in other terms as well. |
119 | |
120 | In 2003, the K42 group described how RCU could be used to create |
121 | hot-pluggable implementations of operating-system functions [Appavoo03a]. |
122 | Later that year saw a paper describing an RCU implementation of System |
123 | V IPC [Arcangeli03], and an introduction to RCU in Linux Journal |
124 | [McKenney03a]. |
125 | |
126 | 2004 has seen a Linux-Journal article on use of RCU in dcache |
127 | [McKenney04a], a performance comparison of locking to RCU on several |
128 | different CPUs [McKenney04b], a dissertation describing use of RCU in a |
129 | number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper |
130 | describing how to make RCU safe for soft-realtime applications [Sarma04c], |
131 | and a paper describing SELinux performance with RCU [JamesMorris04b]. |
132 | |
133 | 2005 brought further adaptation of RCU to realtime use, permitting |
134 | preemption of RCU realtime critical sections [PaulMcKenney05a, |
135 | PaulMcKenney05b]. |
136 | |
137 | 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a], |
138 | as well as further work on efficient implementations of preemptible |
139 | RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical |
140 | sections proved elusive. An RCU implementation permitting general |
141 | blocking in read-side critical sections appeared [PaulEMcKenney2006c], |
142 | Robert Olsson described an RCU-protected trie-hash combination |
143 | [RobertOlsson2006a]. |
144 | |
145 | 2007 saw the journal version of the award-winning RCU paper from 2006 |
146 | [ThomasEHart2007a], as well as a paper demonstrating use of Promela |
147 | and Spin to mechanically verify an optimization to Oleg Nesterov's |
148 | QRCU [PaulEMcKenney2007QRCUspin], a design document describing |
149 | preemptible RCU [PaulEMcKenney2007PreemptibleRCU], and the three-part |
150 | LWN "What is RCU?" series [PaulEMcKenney2007WhatIsRCUFundamentally, |
151 | PaulEMcKenney2008WhatIsRCUUsage, and PaulEMcKenney2008WhatIsRCUAPI]. |
152 | |
153 | 2008 saw a journal paper on real-time RCU [DinakarGuniguntala2008IBMSysJ], |
154 | a history of how Linux changed RCU more than RCU changed Linux |
155 | [PaulEMcKenney2008RCUOSR], and a design overview of hierarchical RCU |
156 | [PaulEMcKenney2008HierarchicalRCU]. |
157 | |
158 | 2009 introduced user-level RCU algorithms [PaulEMcKenney2009MaliciousURCU], |
159 | which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU] |
160 | [MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made |
161 | its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU]. |
162 | The problem of resizeable RCU-protected hash tables may now be on a path |
163 | to a solution [JoshTriplett2009RPHash]. |
164 | |
165 | Bibtex Entries |
166 | |
167 | @article{Kung80 |
168 | ,author="H. T. Kung and Q. Lehman" |
169 | ,title="Concurrent Maintenance of Binary Search Trees" |
170 | ,Year="1980" |
171 | ,Month="September" |
172 | ,journal="ACM Transactions on Database Systems" |
173 | ,volume="5" |
174 | ,number="3" |
175 | ,pages="354-382" |
176 | } |
177 | |
178 | @techreport{Manber82 |
179 | ,author="Udi Manber and Richard E. Ladner" |
180 | ,title="Concurrency Control in a Dynamic Search Structure" |
181 | ,institution="Department of Computer Science, University of Washington" |
182 | ,address="Seattle, Washington" |
183 | ,year="1982" |
184 | ,number="82-01-01" |
185 | ,month="January" |
186 | ,pages="28" |
187 | } |
188 | |
189 | @article{Manber84 |
190 | ,author="Udi Manber and Richard E. Ladner" |
191 | ,title="Concurrency Control in a Dynamic Search Structure" |
192 | ,Year="1984" |
193 | ,Month="September" |
194 | ,journal="ACM Transactions on Database Systems" |
195 | ,volume="9" |
196 | ,number="3" |
197 | ,pages="439-455" |
198 | } |
199 | |
200 | @techreport{Hennessy89 |
201 | ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" |
202 | ,title="Passive Serialization in a Multitasking Environment" |
203 | ,institution="US Patent and Trademark Office" |
204 | ,address="Washington, DC" |
205 | ,year="1989" |
206 | ,number="US Patent 4,809,168 (lapsed)" |
207 | ,month="February" |
208 | ,pages="11" |
209 | } |
210 | |
211 | @techreport{Pugh90 |
212 | ,author="William Pugh" |
213 | ,title="Concurrent Maintenance of Skip Lists" |
214 | ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" |
215 | ,address="College Park, Maryland" |
216 | ,year="1990" |
217 | ,number="CS-TR-2222.1" |
218 | ,month="June" |
219 | } |
220 | |
221 | @Book{Adams91 |
222 | ,Author="Gregory R. Adams" |
223 | ,title="Concurrent Programming, Principles, and Practices" |
224 | ,Publisher="Benjamin Cummins" |
225 | ,Year="1991" |
226 | } |
227 | |
228 | @phdthesis{HMassalinPhD |
229 | ,author="H. Massalin" |
230 | ,title="Synthesis: An Efficient Implementation of Fundamental Operating |
231 | System Services" |
232 | ,school="Columbia University" |
233 | ,address="New York, NY" |
234 | ,year="1992" |
235 | ,annotation=" |
236 | Mondo optimizing compiler. |
237 | Wait-free stuff. |
238 | Good advice: defer work to avoid synchronization. |
239 | " |
240 | } |
241 | |
242 | @unpublished{Jacobson93 |
243 | ,author="Van Jacobson" |
244 | ,title="Avoid Read-Side Locking Via Delayed Free" |
245 | ,year="1993" |
246 | ,month="September" |
247 | ,note="Verbal discussion" |
248 | } |
249 | |
250 | @Conference{AjuJohn95 |
251 | ,Author="Aju John" |
252 | ,Title="Dynamic vnodes -- Design and Implementation" |
253 | ,Booktitle="{USENIX Winter 1995}" |
254 | ,Publisher="USENIX Association" |
255 | ,Month="January" |
256 | ,Year="1995" |
257 | ,pages="11-23" |
258 | ,Address="New Orleans, LA" |
259 | } |
260 | |
261 | @conference{Pu95a, |
262 | Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and |
263 | Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and |
264 | Ke Zhang", |
265 | Title = "Optimistic Incremental Specialization: Streamlining a Commercial |
266 | Operating System", |
267 | Booktitle = "15\textsuperscript{th} ACM Symposium on |
268 | Operating Systems Principles (SOSP'95)", |
269 | address = "Copper Mountain, CO", |
270 | month="December", |
271 | year="1995", |
272 | pages="314-321", |
273 | annotation=" |
274 | Uses a replugger, but with a flag to signal when people are |
275 | using the resource at hand. Only one reader at a time. |
276 | " |
277 | } |
278 | |
279 | @conference{Cowan96a, |
280 | Author = "Crispin Cowan and Tito Autrey and Charles Krasic and |
281 | Calton Pu and Jonathan Walpole", |
282 | Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System", |
283 | Booktitle = "International Conference on Configurable Distributed Systems |
284 | (ICCDS'96)", |
285 | address = "Annapolis, MD", |
286 | month="May", |
287 | year="1996", |
288 | pages="108", |
289 | isbn="0-8186-7395-8", |
290 | annotation=" |
291 | Uses a replugger, but with a counter to signal when people are |
292 | using the resource at hand. Allows multiple readers. |
293 | " |
294 | } |
295 | |
296 | @techreport{Slingwine95 |
297 | ,author="John D. Slingwine and Paul E. McKenney" |
298 | ,title="Apparatus and Method for Achieving Reduced Overhead Mutual |
299 | Exclusion and Maintaining Coherency in a Multiprocessor System |
300 | Utilizing Execution History and Thread Monitoring" |
301 | ,institution="US Patent and Trademark Office" |
302 | ,address="Washington, DC" |
303 | ,year="1995" |
304 | ,number="US Patent 5,442,758 (contributed under GPL)" |
305 | ,month="August" |
306 | } |
307 | |
308 | @techreport{Slingwine97 |
309 | ,author="John D. Slingwine and Paul E. McKenney" |
310 | ,title="Method for maintaining data coherency using thread |
311 | activity summaries in a multicomputer system" |
312 | ,institution="US Patent and Trademark Office" |
313 | ,address="Washington, DC" |
314 | ,year="1997" |
315 | ,number="US Patent 5,608,893 (contributed under GPL)" |
316 | ,month="March" |
317 | } |
318 | |
319 | @techreport{Slingwine98 |
320 | ,author="John D. Slingwine and Paul E. McKenney" |
321 | ,title="Apparatus and method for achieving reduced overhead |
322 | mutual exclusion and maintaining coherency in a multiprocessor |
323 | system utilizing execution history and thread monitoring" |
324 | ,institution="US Patent and Trademark Office" |
325 | ,address="Washington, DC" |
326 | ,year="1998" |
327 | ,number="US Patent 5,727,209 (contributed under GPL)" |
328 | ,month="March" |
329 | } |
330 | |
331 | @Conference{McKenney98 |
332 | ,Author="Paul E. McKenney and John D. Slingwine" |
333 | ,Title="Read-Copy Update: Using Execution History to Solve Concurrency |
334 | Problems" |
335 | ,Booktitle="{Parallel and Distributed Computing and Systems}" |
336 | ,Month="October" |
337 | ,Year="1998" |
338 | ,pages="509-518" |
339 | ,Address="Las Vegas, NV" |
340 | } |
341 | |
342 | @Conference{Gamsa99 |
343 | ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" |
344 | ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory |
345 | Multiprocessor Operating System" |
346 | ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on |
347 | Operating System Design and Implementation}" |
348 | ,Month="February" |
349 | ,Year="1999" |
350 | ,pages="87-100" |
351 | ,Address="New Orleans, LA" |
352 | } |
353 | |
354 | @techreport{Slingwine01 |
355 | ,author="John D. Slingwine and Paul E. McKenney" |
356 | ,title="Apparatus and method for achieving reduced overhead |
357 | mutual exclusion and maintaining coherency in a multiprocessor |
358 | system utilizing execution history and thread monitoring" |
359 | ,institution="US Patent and Trademark Office" |
360 | ,address="Washington, DC" |
361 | ,year="2001" |
362 | ,number="US Patent 5,219,690 (contributed under GPL)" |
363 | ,month="April" |
364 | } |
365 | |
366 | @Conference{McKenney01a |
367 | ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and |
368 | Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" |
369 | ,Title="Read-Copy Update" |
370 | ,Booktitle="{Ottawa Linux Symposium}" |
371 | ,Month="July" |
372 | ,Year="2001" |
373 | ,note="Available: |
374 | \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} |
375 | \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} |
376 | [Viewed June 23, 2004]" |
377 | annotation=" |
378 | Described RCU, and presented some patches implementing and using it in |
379 | the Linux kernel. |
380 | " |
381 | } |
382 | |
383 | @Conference{Linder02a |
384 | ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" |
385 | ,Title="Scalability of the Directory Entry Cache" |
386 | ,Booktitle="{Ottawa Linux Symposium}" |
387 | ,Month="June" |
388 | ,Year="2002" |
389 | ,pages="289-300" |
390 | } |
391 | |
392 | @Conference{McKenney02a |
393 | ,Author="Paul E. McKenney and Dipankar Sarma and |
394 | Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" |
395 | ,Title="Read-Copy Update" |
396 | ,Booktitle="{Ottawa Linux Symposium}" |
397 | ,Month="June" |
398 | ,Year="2002" |
399 | ,pages="338-367" |
400 | ,note="Available: |
401 | \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} |
402 | [Viewed June 23, 2004]" |
403 | } |
404 | |
405 | @conference{Michael02a |
406 | ,author="Maged M. Michael" |
407 | ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic |
408 | Reads and Writes" |
409 | ,Year="2002" |
410 | ,Month="August" |
411 | ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM |
412 | Symposium on Principles of Distributed Computing}" |
413 | ,pages="21-30" |
414 | ,annotation=" |
415 | Each thread keeps an array of pointers to items that it is |
416 | currently referencing. Sort of an inside-out garbage collection |
417 | mechanism, but one that requires the accessing code to explicitly |
418 | state its needs. Also requires read-side memory barriers on |
419 | most architectures. |
420 | " |
421 | } |
422 | |
423 | @conference{Michael02b |
424 | ,author="Maged M. Michael" |
425 | ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets" |
426 | ,Year="2002" |
427 | ,Month="August" |
428 | ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM |
429 | Symposium on Parallel |
430 | Algorithms and Architecture}" |
431 | ,pages="73-82" |
432 | ,annotation=" |
433 | Like the title says... |
434 | " |
435 | } |
436 | |
437 | @InProceedings{HerlihyLM02 |
438 | ,author={Maurice Herlihy and Victor Luchangco and Mark Moir} |
439 | ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, |
440 | Lock-Free Data Structures" |
441 | ,booktitle={Proceedings of 16\textsuperscript{th} International |
442 | Symposium on Distributed Computing} |
443 | ,year=2002 |
444 | ,month="October" |
445 | ,pages="339-353" |
446 | } |
447 | |
448 | @article{Appavoo03a |
449 | ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and |
450 | D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and |
451 | B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and |
452 | B. Rosenburg and M. Stumm and J. Xenidis" |
453 | ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" |
454 | ,Year="2003" |
455 | ,Month="January" |
456 | ,journal="IBM Systems Journal" |
457 | ,volume="42" |
458 | ,number="1" |
459 | ,pages="60-76" |
460 | } |
461 | |
462 | @Conference{Arcangeli03 |
463 | ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and |
464 | Dipankar Sarma" |
465 | ,Title="Using Read-Copy Update Techniques for {System V IPC} in the |
466 | {Linux} 2.5 Kernel" |
467 | ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference |
468 | (FREENIX Track)" |
469 | ,Publisher="USENIX Association" |
470 | ,year="2003" |
471 | ,month="June" |
472 | ,pages="297-310" |
473 | } |
474 | |
475 | @article{McKenney03a |
476 | ,author="Paul E. McKenney" |
477 | ,title="Using {RCU} in the {Linux} 2.5 Kernel" |
478 | ,Year="2003" |
479 | ,Month="October" |
480 | ,journal="Linux Journal" |
481 | ,volume="1" |
482 | ,number="114" |
483 | ,pages="18-26" |
484 | } |
485 | |
486 | @techreport{Friedberg03a |
487 | ,author="Stuart A. Friedberg" |
488 | ,title="Lock-Free Wild Card Search Data Structure and Method" |
489 | ,institution="US Patent and Trademark Office" |
490 | ,address="Washington, DC" |
491 | ,year="2003" |
492 | ,number="US Patent 6,662,184 (contributed under GPL)" |
493 | ,month="December" |
494 | ,pages="112" |
495 | } |
496 | |
497 | @article{McKenney04a |
498 | ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" |
499 | ,title="Scaling dcache with {RCU}" |
500 | ,Year="2004" |
501 | ,Month="January" |
502 | ,journal="Linux Journal" |
503 | ,volume="1" |
504 | ,number="118" |
505 | ,pages="38-46" |
506 | } |
507 | |
508 | @Conference{McKenney04b |
509 | ,Author="Paul E. McKenney" |
510 | ,Title="{RCU} vs. Locking Performance on Different {CPUs}" |
511 | ,Booktitle="{linux.conf.au}" |
512 | ,Month="January" |
513 | ,Year="2004" |
514 | ,Address="Adelaide, Australia" |
515 | ,note="Available: |
516 | \url{http://www.linux.org.au/conf/2004/abstracts.html#90} |
517 | \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} |
518 | [Viewed June 23, 2004]" |
519 | } |
520 | |
521 | @phdthesis{PaulEdwardMcKenneyPhD |
522 | ,author="Paul E. McKenney" |
523 | ,title="Exploiting Deferred Destruction: |
524 | An Analysis of Read-Copy-Update Techniques |
525 | in Operating System Kernels" |
526 | ,school="OGI School of Science and Engineering at |
527 | Oregon Health and Sciences University" |
528 | ,year="2004" |
529 | ,note="Available: |
530 | \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} |
531 | [Viewed October 15, 2004]" |
532 | } |
533 | |
534 | @Conference{Sarma04c |
535 | ,Author="Dipankar Sarma and Paul E. McKenney" |
536 | ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" |
537 | ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference |
538 | (FREENIX Track)" |
539 | ,Publisher="USENIX Association" |
540 | ,year="2004" |
541 | ,month="June" |
542 | ,pages="182-191" |
543 | } |
544 | |
545 | @unpublished{JamesMorris04b |
546 | ,Author="James Morris" |
547 | ,Title="Recent Developments in {SELinux} Kernel Performance" |
548 | ,month="December" |
549 | ,year="2004" |
550 | ,note="Available: |
551 | \url{http://www.livejournal.com/users/james_morris/2153.html} |
552 | [Viewed December 10, 2004]" |
553 | } |
554 | |
555 | @unpublished{PaulMcKenney05a |
556 | ,Author="Paul E. McKenney" |
557 | ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" |
558 | ,month="May" |
559 | ,year="2005" |
560 | ,note="Available: |
561 | \url{http://lkml.org/lkml/2005/5/9/185} |
562 | [Viewed May 13, 2005]" |
563 | ,annotation=" |
564 | First publication of working lock-based deferred free patches |
565 | for the CONFIG_PREEMPT_RT environment. |
566 | " |
567 | } |
568 | |
569 | @conference{PaulMcKenney05b |
570 | ,Author="Paul E. McKenney and Dipankar Sarma" |
571 | ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware" |
572 | ,Booktitle="linux.conf.au 2005" |
573 | ,month="April" |
574 | ,year="2005" |
575 | ,address="Canberra, Australia" |
576 | ,note="Available: |
577 | \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} |
578 | [Viewed May 13, 2005]" |
579 | ,annotation=" |
580 | Realtime turns into making RCU yet more realtime friendly. |
581 | " |
582 | } |
583 | |
584 | @conference{ThomasEHart2006a |
585 | ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" |
586 | ,Title="Making Lockless Synchronization Fast: Performance Implications |
587 | of Memory Reclamation" |
588 | ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and |
589 | Distributed Processing Symposium" |
590 | ,month="April" |
591 | ,year="2006" |
592 | ,day="25-29" |
593 | ,address="Rhodes, Greece" |
594 | ,annotation=" |
595 | Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free |
596 | reference counting. |
597 | " |
598 | } |
599 | |
600 | @Conference{PaulEMcKenney2006b |
601 | ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and |
602 | Suparna Bhattacharya" |
603 | ,Title="Extending RCU for Realtime and Embedded Workloads" |
604 | ,Booktitle="{Ottawa Linux Symposium}" |
605 | ,Month="July" |
606 | ,Year="2006" |
607 | ,pages="v2 123-138" |
608 | ,note="Available: |
609 | \url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} |
610 | \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} |
611 | [Viewed January 1, 2007]" |
612 | ,annotation=" |
613 | Described how to improve the -rt implementation of realtime RCU. |
614 | " |
615 | } |
616 | |
617 | @unpublished{PaulEMcKenney2006c |
618 | ,Author="Paul E. McKenney" |
619 | ,Title="Sleepable {RCU}" |
620 | ,month="October" |
621 | ,day="9" |
622 | ,year="2006" |
623 | ,note="Available: |
624 | \url{http://lwn.net/Articles/202847/} |
625 | Revised: |
626 | \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf} |
627 | [Viewed August 21, 2006]" |
628 | ,annotation=" |
629 | LWN article introducing SRCU. |
630 | " |
631 | } |
632 | |
633 | @unpublished{RobertOlsson2006a |
634 | ,Author="Robert Olsson and Stefan Nilsson" |
635 | ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" |
636 | ,month="August" |
637 | ,day="18" |
638 | ,year="2006" |
639 | ,note="Available: |
640 | \url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf} |
641 | [Viewed February 24, 2007]" |
642 | ,annotation=" |
643 | RCU-protected dynamic trie-hash combination. |
644 | " |
645 | } |
646 | |
647 | @unpublished{ThomasEHart2007a |
648 | ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" |
649 | ,Title="Performance of memory reclamation for lockless synchronization" |
650 | ,journal="J. Parallel Distrib. Comput." |
651 | ,year="2007" |
652 | ,note="To appear in J. Parallel Distrib. Comput. |
653 | \url{doi=10.1016/j.jpdc.2007.04.010}" |
654 | ,annotation={ |
655 | Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free |
656 | reference counting. Journal version of ThomasEHart2006a. |
657 | } |
658 | } |
659 | |
660 | @unpublished{PaulEMcKenney2007QRCUspin |
661 | ,Author="Paul E. McKenney" |
662 | ,Title="Using Promela and Spin to verify parallel algorithms" |
663 | ,month="August" |
664 | ,day="1" |
665 | ,year="2007" |
666 | ,note="Available: |
667 | \url{http://lwn.net/Articles/243851/} |
668 | [Viewed September 8, 2007]" |
669 | ,annotation=" |
670 | LWN article describing Promela and spin, and also using Oleg |
671 | Nesterov's QRCU as an example (with Paul McKenney's fastpath). |
672 | " |
673 | } |
674 | |
675 | @unpublished{PaulEMcKenney2007PreemptibleRCU |
676 | ,Author="Paul E. McKenney" |
677 | ,Title="The design of preemptible read-copy-update" |
678 | ,month="October" |
679 | ,day="8" |
680 | ,year="2007" |
681 | ,note="Available: |
682 | \url{http://lwn.net/Articles/253651/} |
683 | [Viewed October 25, 2007]" |
684 | ,annotation=" |
685 | LWN article describing the design of preemptible RCU. |
686 | " |
687 | } |
688 | |
689 | ######################################################################## |
690 | # |
691 | # "What is RCU?" LWN series. |
692 | # |
693 | |
694 | @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally |
695 | ,Author="Paul E. McKenney and Jonathan Walpole" |
696 | ,Title="What is {RCU}, Fundamentally?" |
697 | ,month="December" |
698 | ,day="17" |
699 | ,year="2007" |
700 | ,note="Available: |
701 | \url{http://lwn.net/Articles/262464/} |
702 | [Viewed December 27, 2007]" |
703 | ,annotation=" |
704 | Lays out the three basic components of RCU: (1) publish-subscribe, |
705 | (2) wait for pre-existing readers to complete, and (2) maintain |
706 | multiple versions. |
707 | " |
708 | } |
709 | |
710 | @unpublished{PaulEMcKenney2008WhatIsRCUUsage |
711 | ,Author="Paul E. McKenney" |
712 | ,Title="What is {RCU}? Part 2: Usage" |
713 | ,month="January" |
714 | ,day="4" |
715 | ,year="2008" |
716 | ,note="Available: |
717 | \url{http://lwn.net/Articles/263130/} |
718 | [Viewed January 4, 2008]" |
719 | ,annotation=" |
720 | Lays out six uses of RCU: |
721 | 1. RCU is a Reader-Writer Lock Replacement |
722 | 2. RCU is a Restricted Reference-Counting Mechanism |
723 | 3. RCU is a Bulk Reference-Counting Mechanism |
724 | 4. RCU is a Poor Man's Garbage Collector |
725 | 5. RCU is a Way of Providing Existence Guarantees |
726 | 6. RCU is a Way of Waiting for Things to Finish |
727 | " |
728 | } |
729 | |
730 | @unpublished{PaulEMcKenney2008WhatIsRCUAPI |
731 | ,Author="Paul E. McKenney" |
732 | ,Title="{RCU} part 3: the {RCU} {API}" |
733 | ,month="January" |
734 | ,day="17" |
735 | ,year="2008" |
736 | ,note="Available: |
737 | \url{http://lwn.net/Articles/264090/} |
738 | [Viewed January 10, 2008]" |
739 | ,annotation=" |
740 | Gives an overview of the Linux-kernel RCU API and a brief annotated RCU |
741 | bibliography. |
742 | " |
743 | } |
744 | |
745 | # |
746 | # "What is RCU?" LWN series. |
747 | # |
748 | ######################################################################## |
749 | |
750 | @article{DinakarGuniguntala2008IBMSysJ |
751 | ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" |
752 | ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" |
753 | ,Year="2008" |
754 | ,Month="April" |
755 | ,journal="IBM Systems Journal" |
756 | ,volume="47" |
757 | ,number="2" |
758 | ,pages="@@-@@" |
759 | ,annotation=" |
760 | RCU, realtime RCU, sleepable RCU, performance. |
761 | " |
762 | } |
763 | |
764 | @article{PaulEMcKenney2008RCUOSR |
765 | ,author="Paul E. McKenney and Jonathan Walpole" |
766 | ,title="Introducing technology into the {Linux} kernel: a case study" |
767 | ,Year="2008" |
768 | ,journal="SIGOPS Oper. Syst. Rev." |
769 | ,volume="42" |
770 | ,number="5" |
771 | ,pages="4--17" |
772 | ,issn="0163-5980" |
773 | ,doi={http://doi.acm.org/10.1145/1400097.1400099} |
774 | ,publisher="ACM" |
775 | ,address="New York, NY, USA" |
776 | ,annotation={ |
777 | Linux changed RCU to a far greater degree than RCU has changed Linux. |
778 | } |
779 | } |
780 | |
781 | @unpublished{PaulEMcKenney2008HierarchicalRCU |
782 | ,Author="Paul E. McKenney" |
783 | ,Title="Hierarchical {RCU}" |
784 | ,month="November" |
785 | ,day="3" |
786 | ,year="2008" |
787 | ,note="Available: |
788 | \url{http://lwn.net/Articles/305782/} |
789 | [Viewed November 6, 2008]" |
790 | ,annotation=" |
791 | RCU with combining-tree-based grace-period detection, |
792 | permitting it to handle thousands of CPUs. |
793 | " |
794 | } |
795 | |
796 | @conference{PaulEMcKenney2009MaliciousURCU |
797 | ,Author="Paul E. McKenney" |
798 | ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms" |
799 | ,Booktitle="linux.conf.au 2009" |
800 | ,month="January" |
801 | ,year="2009" |
802 | ,address="Hobart, Australia" |
803 | ,note="Available: |
804 | \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf} |
805 | [Viewed February 2, 2009]" |
806 | ,annotation=" |
807 | Realtime RCU and torture-testing RCU uses. |
808 | " |
809 | } |
810 | |
811 | @unpublished{MathieuDesnoyers2009URCU |
812 | ,Author="Mathieu Desnoyers" |
813 | ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}" |
814 | ,month="February" |
815 | ,day="5" |
816 | ,year="2009" |
817 | ,note="Available: |
818 | \url{http://lkml.org/lkml/2009/2/5/572} |
819 | \url{git://lttng.org/userspace-rcu.git} |
820 | [Viewed February 20, 2009]" |
821 | ,annotation=" |
822 | Mathieu Desnoyers's user-space RCU implementation. |
823 | git://lttng.org/userspace-rcu.git |
824 | " |
825 | } |
826 | |
827 | @unpublished{PaulEMcKenney2009BloatWatchRCU |
828 | ,Author="Paul E. McKenney" |
829 | ,Title="{RCU}: The {Bloatwatch} Edition" |
830 | ,month="March" |
831 | ,day="17" |
832 | ,year="2009" |
833 | ,note="Available: |
834 | \url{http://lwn.net/Articles/323929/} |
835 | [Viewed March 20, 2009]" |
836 | ,annotation=" |
837 | Uniprocessor assumptions allow simplified RCU implementation. |
838 | " |
839 | } |
840 | |
841 | @unpublished{PaulEMcKenney2009expeditedRCU |
842 | ,Author="Paul E. McKenney" |
843 | ,Title="[{PATCH} -tip 0/3] expedited 'big hammer' {RCU} grace periods" |
844 | ,month="June" |
845 | ,day="25" |
846 | ,year="2009" |
847 | ,note="Available: |
848 | \url{http://lkml.org/lkml/2009/6/25/306} |
849 | [Viewed August 16, 2009]" |
850 | ,annotation=" |
851 | First posting of expedited RCU to be accepted into -tip. |
852 | " |
853 | } |
854 | |
855 | @unpublished{JoshTriplett2009RPHash |
856 | ,Author="Josh Triplett" |
857 | ,Title="Scalable concurrent hash tables via relativistic programming" |
858 | ,month="September" |
859 | ,year="2009" |
860 | ,note="Linux Plumbers Conference presentation" |
861 | ,annotation=" |
862 | RP fun with hash tables. |
863 | " |
864 | } |
865 | |
866 | @phdthesis{MathieuDesnoyersPhD |
867 | , title = "Low-Impact Operating System Tracing" |
868 | , author = "Mathieu Desnoyers" |
869 | , school = "Ecole Polytechnique de Montr\'{e}al" |
870 | , month = "December" |
871 | , year = 2009 |
872 | ,note="Available: |
873 | \url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} |
874 | [Viewed December 9, 2009]" |
875 | } |
876 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9