Documentation/RCU/RTFP.txt

   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 has
  29 lapsed, so this approach may be used in non-GPL software, if desired.
  30 (In contrast, use of RCU is permitted only in software licensed under
  31 GPL.  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 Bibtex Entries
 154
 155 @article{Kung80
 156 ,author="H. T. Kung and Q. Lehman"
 157 ,title="Concurrent Maintenance of Binary Search Trees"
 158 ,Year="1980"
 159 ,Month="September"
 160 ,journal="ACM Transactions on Database Systems"
 161 ,volume="5"
 162 ,number="3"
 163 ,pages="354-382"
 164 }
 165
 166 @techreport{Manber82
 167 ,author="Udi Manber and Richard E. Ladner"
 168 ,title="Concurrency Control in a Dynamic Search Structure"
 169 ,institution="Department of Computer Science, University of Washington"
 170 ,address="Seattle, Washington"
 171 ,year="1982"
 172 ,number="82-01-01"
 173 ,month="January"
 174 ,pages="28"
 175 }
 176
 177 @article{Manber84
 178 ,author="Udi Manber and Richard E. Ladner"
 179 ,title="Concurrency Control in a Dynamic Search Structure"
 180 ,Year="1984"
 181 ,Month="September"
 182 ,journal="ACM Transactions on Database Systems"
 183 ,volume="9"
 184 ,number="3"
 185 ,pages="439-455"
 186 }
 187
 188 @techreport{Hennessy89
 189 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
 190 ,title="Passive Serialization in a Multitasking Environment"
 191 ,institution="US Patent and Trademark Office"
 192 ,address="Washington, DC"
 193 ,year="1989"
 194 ,number="US Patent 4,809,168 (lapsed)"
 195 ,month="February"
 196 ,pages="11"
 197 }
 198
 199 @techreport{Pugh90
 200 ,author="William Pugh"
 201 ,title="Concurrent Maintenance of Skip Lists"
 202 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
 203 ,address="College Park, Maryland"
 204 ,year="1990"
 205 ,number="CS-TR-2222.1"
 206 ,month="June"
 207 }
 208
 209 @Book{Adams91
 210 ,Author="Gregory R. Adams"
 211 ,title="Concurrent Programming, Principles, and Practices"
 212 ,Publisher="Benjamin Cummins"
 213 ,Year="1991"
 214 }
 215
 216 @phdthesis{HMassalinPhD
 217 ,author="H. Massalin"
 218 ,title="Synthesis: An Efficient Implementation of Fundamental Operating
 219 System Services"
 220 ,school="Columbia University"
 221 ,address="New York, NY"
 222 ,year="1992"
 223 ,annotation="
 224         Mondo optimizing compiler.
 225         Wait-free stuff.
 226         Good advice: defer work to avoid synchronization.
 227 "
 228 }
 229
 230 @unpublished{Jacobson93
 231 ,author="Van Jacobson"
 232 ,title="Avoid Read-Side Locking Via Delayed Free"
 233 ,year="1993"
 234 ,month="September"
 235 ,note="Verbal discussion"
 236 }
 237
 238 @Conference{AjuJohn95
 239 ,Author="Aju John"
 240 ,Title="Dynamic vnodes -- Design and Implementation"
 241 ,Booktitle="{USENIX Winter 1995}"
 242 ,Publisher="USENIX Association"
 243 ,Month="January"
 244 ,Year="1995"
 245 ,pages="11-23"
 246 ,Address="New Orleans, LA"
 247 }
 248
 249 @conference{Pu95a,
 250 Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and
 251 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and
 252 Ke Zhang",
 253 Title = "Optimistic Incremental Specialization: Streamlining a Commercial
 254 Operating System",
 255 Booktitle = "15\textsuperscript{th} ACM Symposium on
 256 Operating Systems Principles (SOSP'95)",
 257 address = "Copper Mountain, CO",
 258 month="December",
 259 year="1995",
 260 pages="314-321",
 261 annotation="
 262         Uses a replugger, but with a flag to signal when people are
 263         using the resource at hand.  Only one reader at a time.
 264 "
 265 }
 266
 267 @conference{Cowan96a,
 268 Author = "Crispin Cowan and Tito Autrey and Charles Krasic and
 269 Calton Pu and Jonathan Walpole",
 270 Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System",
 271 Booktitle = "International Conference on Configurable Distributed Systems
 272 (ICCDS'96)",
 273 address = "Annapolis, MD",
 274 month="May",
 275 year="1996",
 276 pages="108",
 277 isbn="0-8186-7395-8",
 278 annotation="
 279         Uses a replugger, but with a counter to signal when people are
 280         using the resource at hand.  Allows multiple readers.
 281 "
 282 }
 283
 284 @techreport{Slingwine95
 285 ,author="John D. Slingwine and Paul E. McKenney"
 286 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual
 287 Exclusion and Maintaining Coherency in a Multiprocessor System
 288 Utilizing Execution History and Thread Monitoring"
 289 ,institution="US Patent and Trademark Office"
 290 ,address="Washington, DC"
 291 ,year="1995"
 292 ,number="US Patent 5,442,758 (contributed under GPL)"
 293 ,month="August"
 294 }
 295
 296 @techreport{Slingwine97
 297 ,author="John D. Slingwine and Paul E. McKenney"
 298 ,title="Method for maintaining data coherency using thread
 299 activity summaries in a multicomputer system"
 300 ,institution="US Patent and Trademark Office"
 301 ,address="Washington, DC"
 302 ,year="1997"
 303 ,number="US Patent 5,608,893 (contributed under GPL)"
 304 ,month="March"
 305 }
 306
 307 @techreport{Slingwine98
 308 ,author="John D. Slingwine and Paul E. McKenney"
 309 ,title="Apparatus and method for achieving reduced overhead
 310 mutual exclusion and maintaining coherency in a multiprocessor
 311 system utilizing execution history and thread monitoring"
 312 ,institution="US Patent and Trademark Office"
 313 ,address="Washington, DC"
 314 ,year="1998"
 315 ,number="US Patent 5,727,209 (contributed under GPL)"
 316 ,month="March"
 317 }
 318
 319 @Conference{McKenney98
 320 ,Author="Paul E. McKenney and John D. Slingwine"
 321 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency
 322 Problems"
 323 ,Booktitle="{Parallel and Distributed Computing and Systems}"
 324 ,Month="October"
 325 ,Year="1998"
 326 ,pages="509-518"
 327 ,Address="Las Vegas, NV"
 328 }
 329
 330 @Conference{Gamsa99
 331 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
 332 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
 333 Multiprocessor Operating System"
 334 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
 335 Operating System Design and Implementation}"
 336 ,Month="February"
 337 ,Year="1999"
 338 ,pages="87-100"
 339 ,Address="New Orleans, LA"
 340 }
 341
 342 @techreport{Slingwine01
 343 ,author="John D. Slingwine and Paul E. McKenney"
 344 ,title="Apparatus and method for achieving reduced overhead
 345 mutual exclusion and maintaining coherency in a multiprocessor
 346 system utilizing execution history and thread monitoring"
 347 ,institution="US Patent and Trademark Office"
 348 ,address="Washington, DC"
 349 ,year="2001"
 350 ,number="US Patent 5,219,690 (contributed under GPL)"
 351 ,month="April"
 352 }
 353
 354 @Conference{McKenney01a
 355 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
 356 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
 357 ,Title="Read-Copy Update"
 358 ,Booktitle="{Ottawa Linux Symposium}"
 359 ,Month="July"
 360 ,Year="2001"
 361 ,note="Available:
 362 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
 363 \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
 364 [Viewed June 23, 2004]"
 365 annotation="
 366 Described RCU, and presented some patches implementing and using it in
 367 the Linux kernel.
 368 "
 369 }
 370
 371 @Conference{Linder02a
 372 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
 373 ,Title="Scalability of the Directory Entry Cache"
 374 ,Booktitle="{Ottawa Linux Symposium}"
 375 ,Month="June"
 376 ,Year="2002"
 377 ,pages="289-300"
 378 }
 379
 380 @Conference{McKenney02a
 381 ,Author="Paul E. McKenney and Dipankar Sarma and
 382 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
 383 ,Title="Read-Copy Update"
 384 ,Booktitle="{Ottawa Linux Symposium}"
 385 ,Month="June"
 386 ,Year="2002"
 387 ,pages="338-367"
 388 ,note="Available:
 389 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
 390 [Viewed June 23, 2004]"
 391 }
 392
 393 @conference{Michael02a
 394 ,author="Maged M. Michael"
 395 ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
 396 Reads and Writes"
 397 ,Year="2002"
 398 ,Month="August"
 399 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
 400 Symposium on Principles of Distributed Computing}"
 401 ,pages="21-30"
 402 ,annotation="
 403         Each thread keeps an array of pointers to items that it is
 404         currently referencing.  Sort of an inside-out garbage collection
 405         mechanism, but one that requires the accessing code to explicitly
 406         state its needs.  Also requires read-side memory barriers on
 407         most architectures.
 408 "
 409 }
 410
 411 @conference{Michael02b
 412 ,author="Maged M. Michael"
 413 ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
 414 ,Year="2002"
 415 ,Month="August"
 416 ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
 417 Symposium on Parallel
 418 Algorithms and Architecture}"
 419 ,pages="73-82"
 420 ,annotation="
 421         Like the title says...
 422 "
 423 }
 424
 425 @InProceedings{HerlihyLM02
 426 ,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
 427 ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
 428 Lock-Free Data Structures"
 429 ,booktitle={Proceedings of 16\textsuperscript{th} International
 430 Symposium on Distributed Computing}
 431 ,year=2002
 432 ,month="October"
 433 ,pages="339-353"
 434 }
 435
 436 @article{Appavoo03a
 437 ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
 438 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
 439 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
 440 B. Rosenburg and M. Stumm and J. Xenidis"
 441 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
 442 ,Year="2003"
 443 ,Month="January"
 444 ,journal="IBM Systems Journal"
 445 ,volume="42"
 446 ,number="1"
 447 ,pages="60-76"
 448 }
 449
 450 @Conference{Arcangeli03
 451 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
 452 Dipankar Sarma"
 453 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the
 454 {Linux} 2.5 Kernel"
 455 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
 456 (FREENIX Track)"
 457 ,Publisher="USENIX Association"
 458 ,year="2003"
 459 ,month="June"
 460 ,pages="297-310"
 461 }
 462
 463 @article{McKenney03a
 464 ,author="Paul E. McKenney"
 465 ,title="Using {RCU} in the {Linux} 2.5 Kernel"
 466 ,Year="2003"
 467 ,Month="October"
 468 ,journal="Linux Journal"
 469 ,volume="1"
 470 ,number="114"
 471 ,pages="18-26"
 472 }
 473
 474 @techreport{Friedberg03a
 475 ,author="Stuart A. Friedberg"
 476 ,title="Lock-Free Wild Card Search Data Structure and Method"
 477 ,institution="US Patent and Trademark Office"
 478 ,address="Washington, DC"
 479 ,year="2003"
 480 ,number="US Patent 6,662,184 (contributed under GPL)"
 481 ,month="December"
 482 ,pages="112"
 483 }
 484
 485 @article{McKenney04a
 486 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
 487 ,title="Scaling dcache with {RCU}"
 488 ,Year="2004"
 489 ,Month="January"
 490 ,journal="Linux Journal"
 491 ,volume="1"
 492 ,number="118"
 493 ,pages="38-46"
 494 }
 495
 496 @Conference{McKenney04b
 497 ,Author="Paul E. McKenney"
 498 ,Title="{RCU} vs. Locking Performance on Different {CPUs}"
 499 ,Booktitle="{linux.conf.au}"
 500 ,Month="January"
 501 ,Year="2004"
 502 ,Address="Adelaide, Australia"
 503 ,note="Available:
 504 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
 505 \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
 506 [Viewed June 23, 2004]"
 507 }
 508
 509 @phdthesis{PaulEdwardMcKenneyPhD
 510 ,author="Paul E. McKenney"
 511 ,title="Exploiting Deferred Destruction:
 512 An Analysis of Read-Copy-Update Techniques
 513 in Operating System Kernels"
 514 ,school="OGI School of Science and Engineering at
 515 Oregon Health and Sciences University"
 516 ,year="2004"
 517 ,note="Available:
 518 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
 519 [Viewed October 15, 2004]"
 520 }
 521
 522 @Conference{Sarma04c
 523 ,Author="Dipankar Sarma and Paul E. McKenney"
 524 ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
 525 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
 526 (FREENIX Track)"
 527 ,Publisher="USENIX Association"
 528 ,year="2004"
 529 ,month="June"
 530 ,pages="182-191"
 531 }
 532
 533 @unpublished{JamesMorris04b
 534 ,Author="James Morris"
 535 ,Title="Recent Developments in {SELinux} Kernel Performance"
 536 ,month="December"
 537 ,year="2004"
 538 ,note="Available:
 539 \url{http://www.livejournal.com/users/james_morris/2153.html}
 540 [Viewed December 10, 2004]"
 541 }
 542
 543 @unpublished{PaulMcKenney05a
 544 ,Author="Paul E. McKenney"
 545 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress"
 546 ,month="May"
 547 ,year="2005"
 548 ,note="Available:
 549 \url{http://lkml.org/lkml/2005/5/9/185}
 550 [Viewed May 13, 2005]"
 551 ,annotation="
 552         First publication of working lock-based deferred free patches
 553         for the CONFIG_PREEMPT_RT environment.
 554 "
 555 }
 556
 557 @conference{PaulMcKenney05b
 558 ,Author="Paul E. McKenney and Dipankar Sarma"
 559 ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
 560 ,Booktitle="linux.conf.au 2005"
 561 ,month="April"
 562 ,year="2005"
 563 ,address="Canberra, Australia"
 564 ,note="Available:
 565 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf}
 566 [Viewed May 13, 2005]"
 567 ,annotation="
 568         Realtime turns into making RCU yet more realtime friendly.
 569 "
 570 }
 571
 572 @conference{ThomasEHart2006a
 573 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
 574 ,Title="Making Lockless Synchronization Fast: Performance Implications
 575 of Memory Reclamation"
 576 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and
 577 Distributed Processing Symposium"
 578 ,month="April"
 579 ,year="2006"
 580 ,day="25-29"
 581 ,address="Rhodes, Greece"
 582 ,annotation="
 583         Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
 584         reference counting.
 585 "
 586 }
 587
 588 @Conference{PaulEMcKenney2006b
 589 ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
 590 Suparna Bhattacharya"
 591 ,Title="Extending RCU for Realtime and Embedded Workloads"
 592 ,Booktitle="{Ottawa Linux Symposium}"
 593 ,Month="July"
 594 ,Year="2006"
 595 ,pages="v2 123-138"
 596 ,note="Available:
 597 \url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
 598 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
 599 [Viewed January 1, 2007]"
 600 ,annotation="
 601         Described how to improve the -rt implementation of realtime RCU.
 602 "
 603 }
 604
 605 @unpublished{PaulEMcKenney2006c
 606 ,Author="Paul E. McKenney"
 607 ,Title="Sleepable {RCU}"
 608 ,month="October"
 609 ,day="9"
 610 ,year="2006"
 611 ,note="Available:
 612 \url{http://lwn.net/Articles/202847/}
 613 Revised:
 614 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf}
 615 [Viewed August 21, 2006]"
 616 ,annotation="
 617         LWN article introducing SRCU.
 618 "
 619 }
 620
 621 @unpublished{RobertOlsson2006a
 622 ,Author="Robert Olsson and Stefan Nilsson"
 623 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
 624 ,month="August"
 625 ,day="18"
 626 ,year="2006"
 627 ,note="Available:
 628 \url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf}
 629 [Viewed February 24, 2007]"
 630 ,annotation="
 631         RCU-protected dynamic trie-hash combination.
 632 "
 633 }
 634
 635 @unpublished{ThomasEHart2007a
 636 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
 637 ,Title="Performance of memory reclamation for lockless synchronization"
 638 ,journal="J. Parallel Distrib. Comput."
 639 ,year="2007"
 640 ,note="To appear in J. Parallel Distrib. Comput.
 641        \url{doi=10.1016/j.jpdc.2007.04.010}"
 642 ,annotation={
 643         Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free
 644         reference counting.  Journal version of ThomasEHart2006a.
 645 }
 646 }
 647
 648 @unpublished{PaulEMcKenney2007QRCUspin
 649 ,Author="Paul E. McKenney"
 650 ,Title="Using Promela and Spin to verify parallel algorithms"
 651 ,month="August"
 652 ,day="1"
 653 ,year="2007"
 654 ,note="Available:
 655 \url{http://lwn.net/Articles/243851/}
 656 [Viewed September 8, 2007]"
 657 ,annotation="
 658         LWN article describing Promela and spin, and also using Oleg
 659         Nesterov's QRCU as an example (with Paul McKenney's fastpath).
 660 "
 661 }
 662
 663 @unpublished{PaulEMcKenney2007PreemptibleRCU
 664 ,Author="Paul E. McKenney"
 665 ,Title="The design of preemptible read-copy-update"
 666 ,month="October"
 667 ,day="8"
 668 ,year="2007"
 669 ,note="Available:
 670 \url{http://lwn.net/Articles/253651/}
 671 [Viewed October 25, 2007]"
 672 ,annotation="
 673         LWN article describing the design of preemptible RCU.
 674 "
 675 }
 676
 677 ########################################################################
 678 #
 679 #       "What is RCU?" LWN series.
 680 #
 681
 682 @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
 683 ,Author="Paul E. McKenney and Jonathan Walpole"
 684 ,Title="What is {RCU}, Fundamentally?"
 685 ,month="December"
 686 ,day="17"
 687 ,year="2007"
 688 ,note="Available:
 689 \url{http://lwn.net/Articles/262464/}
 690 [Viewed December 27, 2007]"
 691 ,annotation="
 692         Lays out the three basic components of RCU: (1) publish-subscribe,
 693         (2) wait for pre-existing readers to complete, and (2) maintain
 694         multiple versions.
 695 "
 696 }
 697
 698 @unpublished{PaulEMcKenney2008WhatIsRCUUsage
 699 ,Author="Paul E. McKenney"
 700 ,Title="What is {RCU}? Part 2: Usage"
 701 ,month="January"
 702 ,day="4"
 703 ,year="2008"
 704 ,note="Available:
 705 \url{http://lwn.net/Articles/263130/}
 706 [Viewed January 4, 2008]"
 707 ,annotation="
 708         Lays out six uses of RCU:
 709         1. RCU is a Reader-Writer Lock Replacement
 710         2. RCU is a Restricted Reference-Counting Mechanism
 711         3. RCU is a Bulk Reference-Counting Mechanism
 712         4. RCU is a Poor Man's Garbage Collector
 713         5. RCU is a Way of Providing Existence Guarantees
 714         6. RCU is a Way of Waiting for Things to Finish
 715 "
 716 }
 717
 718 @unpublished{PaulEMcKenney2008WhatIsRCUAPI
 719 ,Author="Paul E. McKenney"
 720 ,Title="{RCU} part 3: the {RCU} {API}"
 721 ,month="January"
 722 ,day="17"
 723 ,year="2008"
 724 ,note="Available:
 725 \url{http://lwn.net/Articles/264090/}
 726 [Viewed January 10, 2008]"
 727 ,annotation="
 728         Gives an overview of the Linux-kernel RCU API and a brief annotated RCU
 729         bibliography.
 730 "
 731 }
 732
 733 @article{DinakarGuniguntala2008IBMSysJ
 734 ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
 735 ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
 736 ,Year="2008"
 737 ,Month="April"
 738 ,journal="IBM Systems Journal"
 739 ,volume="47"
 740 ,number="2"
 741 ,pages="@@-@@"
 742 ,annotation="
 743         RCU, realtime RCU, sleepable RCU, performance.
 744 "
 745 }
 746
 747 @article{PaulEMcKenney2008RCUOSR
 748 ,author="Paul E. McKenney and Jonathan Walpole"
 749 ,title="Introducing technology into the {Linux} kernel: a case study"
 750 ,Year="2008"
 751 ,journal="SIGOPS Oper. Syst. Rev."
 752 ,volume="42"
 753 ,number="5"
 754 ,pages="4--17"
 755 ,issn="0163-5980"
 756 ,doi={http://doi.acm.org/10.1145/1400097.1400099}
 757 ,publisher="ACM"
 758 ,address="New York, NY, USA"
 759 ,annotation={
 760         Linux changed RCU to a far greater degree than RCU has changed Linux.
 761 }
 762 }
 763
 764 @unpublished{PaulEMcKenney2008HierarchicalRCU
 765 ,Author="Paul E. McKenney"
 766 ,Title="Hierarchical {RCU}"
 767 ,month="November"
 768 ,day="3"
 769 ,year="2008"
 770 ,note="Available:
 771 \url{http://lwn.net/Articles/305782/}
 772 [Viewed November 6, 2008]"
 773 ,annotation="
 774         RCU with combining-tree-based grace-period detection,
 775         permitting it to handle thousands of CPUs.
 776 "
 777 }
 778
 779 @conference{PaulEMcKenney2009MaliciousURCU
 780 ,Author="Paul E. McKenney"
 781 ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
 782 ,Booktitle="linux.conf.au 2009"
 783 ,month="January"
 784 ,year="2009"
 785 ,address="Hobart, Australia"
 786 ,note="Available:
 787 \url{http://www.rdrop.com/users/paulmck/RCU/urcutorture.2009.01.22a.pdf}
 788 [Viewed February 2, 2009]"
 789 ,annotation="
 790         Realtime RCU and torture-testing RCU uses.
 791 "
 792 }
 793
 794 @unpublished{MathieuDesnoyers2009URCU
 795 ,Author="Mathieu Desnoyers"
 796 ,Title="[{RFC} git tree] Userspace {RCU} (urcu) for {Linux}"
 797 ,month="February"
 798 ,day="5"
 799 ,year="2009"
 800 ,note="Available:
 801 \url{http://lkml.org/lkml/2009/2/5/572}
 802 \url{git://lttng.org/userspace-rcu.git}
 803 [Viewed February 20, 2009]"
 804 ,annotation="
 805         Mathieu Desnoyers's user-space RCU implementation.
 806         git://lttng.org/userspace-rcu.git
 807 "
 808 }
 809
 810 @unpublished{PaulEMcKenney2009BloatWatchRCU
 811 ,Author="Paul E. McKenney"
 812 ,Title="{RCU}: The {Bloatwatch} Edition"
 813 ,month="March"
 814 ,day="17"
 815 ,year="2009"
 816 ,note="Available:
 817 \url{http://lwn.net/Articles/323929/}
 818 [Viewed March 20, 2009]"
 819 ,annotation="
 820         Uniprocessor assumptions allow simplified RCU implementation.
 821 "
 822 }