Based on kernel version 2.6.25. Page generated on 2008-04-18 21:22 EST.
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 1993, Jacobson [Jacobson93] verbally described what is perhaps the 56 simplest deferred-free technique: simply waiting a fixed amount of time 57 before freeing blocks awaiting deferred free. Jacobson did not describe 58 any write-side changes he might have made in this work using SGI's Irix 59 kernel. Aju John published a similar technique in 1995 [AjuJohn95]. 60 This works well if there is a well-defined upper bound on the length of 61 time that reading threads can hold references, as there might well be in 62 hard real-time systems. However, if this time is exceeded, perhaps due 63 to preemption, excessive interrupts, or larger-than-anticipated load, 64 memory corruption can ensue, with no reasonable means of diagnosis. 65 Jacobson's technique is therefore inappropriate for use in production 66 operating-system kernels, except when such kernels can provide hard 67 real-time response guarantees for all operations. 68 69 Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's 70 read-side-tracking to permit replugging of algorithms within a commercial 71 Unix operating system. However, this replugging permitted only a single 72 reader at a time. The following year, this same group of researchers 73 extended their technique to allow for multiple readers [Cowan96a]. 74 Their approach requires memory barriers (and thus pipeline stalls), 75 but reduces memory latency, contention, and locking overheads. 76 77 1995 also saw the first publication of DYNIX/ptx's RCU mechanism 78 [Slingwine95], which was optimized for modern CPU architectures, 79 and was successfully applied to a number of situations within the 80 DYNIX/ptx kernel. The corresponding conference paper appeared in 1998 81 [McKenney98]. 82 83 In 1999, the Tornado and K42 groups described their "generations" 84 mechanism, which quite similar to RCU [Gamsa99]. These operating systems 85 made pervasive use of RCU in place of "existence locks", which greatly 86 simplifies locking hierarchies. 87 88 2001 saw the first RCU presentation involving Linux [McKenney01a] 89 at OLS. The resulting abundance of RCU patches was presented the 90 following year [McKenney02a], and use of RCU in dcache was first 91 described that same year [Linder02a]. 92 93 Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer" 94 techniques that defer the destruction of data structures to simplify 95 non-blocking synchronization (wait-free synchronization, lock-free 96 synchronization, and obstruction-free synchronization are all examples of 97 non-blocking synchronization). In particular, this technique eliminates 98 locking, reduces contention, reduces memory latency for readers, and 99 parallelizes pipeline stalls and memory latency for writers. However, 100 these techniques still impose significant read-side overhead in the 101 form of memory barriers. Researchers at Sun worked along similar lines 102 in the same timeframe [HerlihyLM02]. These techniques can be thought 103 of as inside-out reference counts, where the count is represented by the 104 number of hazard pointers referencing a given data structure (rather than 105 the more conventional counter field within the data structure itself). 106 107 By the same token, RCU can be thought of as a "bulk reference count", 108 where some form of reference counter covers all reference by a given CPU 109 or thread during a set timeframe. This timeframe is related to, but 110 not necessarily exactly the same as, an RCU grace period. In classic 111 RCU, the reference counter is the per-CPU bit in the "bitmask" field, 112 and each such bit covers all references that might have been made by 113 the corresponding CPU during the prior grace period. Of course, RCU 114 can be thought of in other terms as well. 115 116 In 2003, the K42 group described how RCU could be used to create 117 hot-pluggable implementations of operating-system functions [Appavoo03a]. 118 Later that year saw a paper describing an RCU implementation of System 119 V IPC [Arcangeli03], and an introduction to RCU in Linux Journal 120 [McKenney03a]. 121 122 2004 has seen a Linux-Journal article on use of RCU in dcache 123 [McKenney04a], a performance comparison of locking to RCU on several 124 different CPUs [McKenney04b], a dissertation describing use of RCU in a 125 number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper 126 describing how to make RCU safe for soft-realtime applications [Sarma04c], 127 and a paper describing SELinux performance with RCU [JamesMorris04b]. 128 129 2005 brought further adaptation of RCU to realtime use, permitting 130 preemption of RCU realtime critical sections [PaulMcKenney05a, 131 PaulMcKenney05b]. 132 133 2006 saw the first best-paper award for an RCU paper [ThomasEHart2006a], 134 as well as further work on efficient implementations of preemptible 135 RCU [PaulEMcKenney2006b], but priority-boosting of RCU read-side critical 136 sections proved elusive. An RCU implementation permitting general 137 blocking in read-side critical sections appeared [PaulEMcKenney2006c], 138 Robert Olsson described an RCU-protected trie-hash combination 139 [RobertOlsson2006a]. 140 141 142 Bibtex Entries 143 144 @article{Kung80 145 ,author="H. T. Kung and Q. Lehman" 146 ,title="Concurrent Maintenance of Binary Search Trees" 147 ,Year="1980" 148 ,Month="September" 149 ,journal="ACM Transactions on Database Systems" 150 ,volume="5" 151 ,number="3" 152 ,pages="354-382" 153 } 154 155 @techreport{Manber82 156 ,author="Udi Manber and Richard E. Ladner" 157 ,title="Concurrency Control in a Dynamic Search Structure" 158 ,institution="Department of Computer Science, University of Washington" 159 ,address="Seattle, Washington" 160 ,year="1982" 161 ,number="82-01-01" 162 ,month="January" 163 ,pages="28" 164 } 165 166 @article{Manber84 167 ,author="Udi Manber and Richard E. Ladner" 168 ,title="Concurrency Control in a Dynamic Search Structure" 169 ,Year="1984" 170 ,Month="September" 171 ,journal="ACM Transactions on Database Systems" 172 ,volume="9" 173 ,number="3" 174 ,pages="439-455" 175 } 176 177 @techreport{Hennessy89 178 ,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" 179 ,title="Passive Serialization in a Multitasking Environment" 180 ,institution="US Patent and Trademark Office" 181 ,address="Washington, DC" 182 ,year="1989" 183 ,number="US Patent 4,809,168 (lapsed)" 184 ,month="February" 185 ,pages="11" 186 } 187 188 @techreport{Pugh90 189 ,author="William Pugh" 190 ,title="Concurrent Maintenance of Skip Lists" 191 ,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" 192 ,address="College Park, Maryland" 193 ,year="1990" 194 ,number="CS-TR-2222.1" 195 ,month="June" 196 } 197 198 @Book{Adams91 199 ,Author="Gregory R. Adams" 200 ,title="Concurrent Programming, Principles, and Practices" 201 ,Publisher="Benjamin Cummins" 202 ,Year="1991" 203 } 204 205 @unpublished{Jacobson93 206 ,author="Van Jacobson" 207 ,title="Avoid Read-Side Locking Via Delayed Free" 208 ,year="1993" 209 ,month="September" 210 ,note="Verbal discussion" 211 } 212 213 @Conference{AjuJohn95 214 ,Author="Aju John" 215 ,Title="Dynamic vnodes -- Design and Implementation" 216 ,Booktitle="{USENIX Winter 1995}" 217 ,Publisher="USENIX Association" 218 ,Month="January" 219 ,Year="1995" 220 ,pages="11-23" 221 ,Address="New Orleans, LA" 222 } 223 224 @conference{Pu95a, 225 Author = "Calton Pu and Tito Autrey and Andrew Black and Charles Consel and 226 Crispin Cowan and Jon Inouye and Lakshmi Kethana and Jonathan Walpole and 227 Ke Zhang", 228 Title = "Optimistic Incremental Specialization: Streamlining a Commercial 229 Operating System", 230 Booktitle = "15\textsuperscript{th} ACM Symposium on 231 Operating Systems Principles (SOSP'95)", 232 address = "Copper Mountain, CO", 233 month="December", 234 year="1995", 235 pages="314-321", 236 annotation=" 237 Uses a replugger, but with a flag to signal when people are 238 using the resource at hand. Only one reader at a time. 239 " 240 } 241 242 @conference{Cowan96a, 243 Author = "Crispin Cowan and Tito Autrey and Charles Krasic and 244 Calton Pu and Jonathan Walpole", 245 Title = "Fast Concurrent Dynamic Linking for an Adaptive Operating System", 246 Booktitle = "International Conference on Configurable Distributed Systems 247 (ICCDS'96)", 248 address = "Annapolis, MD", 249 month="May", 250 year="1996", 251 pages="108", 252 isbn="0-8186-7395-8", 253 annotation=" 254 Uses a replugger, but with a counter to signal when people are 255 using the resource at hand. Allows multiple readers. 256 " 257 } 258 259 @techreport{Slingwine95 260 ,author="John D. Slingwine and Paul E. McKenney" 261 ,title="Apparatus and Method for Achieving Reduced Overhead Mutual 262 Exclusion and Maintaining Coherency in a Multiprocessor System 263 Utilizing Execution History and Thread Monitoring" 264 ,institution="US Patent and Trademark Office" 265 ,address="Washington, DC" 266 ,year="1995" 267 ,number="US Patent 5,442,758 (contributed under GPL)" 268 ,month="August" 269 } 270 271 @techreport{Slingwine97 272 ,author="John D. Slingwine and Paul E. McKenney" 273 ,title="Method for maintaining data coherency using thread 274 activity summaries in a multicomputer system" 275 ,institution="US Patent and Trademark Office" 276 ,address="Washington, DC" 277 ,year="1997" 278 ,number="US Patent 5,608,893 (contributed under GPL)" 279 ,month="March" 280 } 281 282 @techreport{Slingwine98 283 ,author="John D. Slingwine and Paul E. McKenney" 284 ,title="Apparatus and method for achieving reduced overhead 285 mutual exclusion and maintaining coherency in a multiprocessor 286 system utilizing execution history and thread monitoring" 287 ,institution="US Patent and Trademark Office" 288 ,address="Washington, DC" 289 ,year="1998" 290 ,number="US Patent 5,727,209 (contributed under GPL)" 291 ,month="March" 292 } 293 294 @Conference{McKenney98 295 ,Author="Paul E. McKenney and John D. Slingwine" 296 ,Title="Read-Copy Update: Using Execution History to Solve Concurrency 297 Problems" 298 ,Booktitle="{Parallel and Distributed Computing and Systems}" 299 ,Month="October" 300 ,Year="1998" 301 ,pages="509-518" 302 ,Address="Las Vegas, NV" 303 } 304 305 @Conference{Gamsa99 306 ,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" 307 ,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory 308 Multiprocessor Operating System" 309 ,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on 310 Operating System Design and Implementation}" 311 ,Month="February" 312 ,Year="1999" 313 ,pages="87-100" 314 ,Address="New Orleans, LA" 315 } 316 317 @techreport{Slingwine01 318 ,author="John D. Slingwine and Paul E. McKenney" 319 ,title="Apparatus and method for achieving reduced overhead 320 mutual exclusion and maintaining coherency in a multiprocessor 321 system utilizing execution history and thread monitoring" 322 ,institution="US Patent and Trademark Office" 323 ,address="Washington, DC" 324 ,year="2001" 325 ,number="US Patent 5,219,690 (contributed under GPL)" 326 ,month="April" 327 } 328 329 @Conference{McKenney01a 330 ,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and 331 Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" 332 ,Title="Read-Copy Update" 333 ,Booktitle="{Ottawa Linux Symposium}" 334 ,Month="July" 335 ,Year="2001" 336 ,note="Available: 337 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 338 \url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} 339 [Viewed June 23, 2004]" 340 annotation=" 341 Described RCU, and presented some patches implementing and using it in 342 the Linux kernel. 343 " 344 } 345 346 @Conference{Linder02a 347 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 348 ,Title="Scalability of the Directory Entry Cache" 349 ,Booktitle="{Ottawa Linux Symposium}" 350 ,Month="June" 351 ,Year="2002" 352 ,pages="289-300" 353 } 354 355 @Conference{McKenney02a 356 ,Author="Paul E. McKenney and Dipankar Sarma and 357 Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" 358 ,Title="Read-Copy Update" 359 ,Booktitle="{Ottawa Linux Symposium}" 360 ,Month="June" 361 ,Year="2002" 362 ,pages="338-367" 363 ,note="Available: 364 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 365 [Viewed June 23, 2004]" 366 } 367 368 @conference{Michael02a 369 ,author="Maged M. Michael" 370 ,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic 371 Reads and Writes" 372 ,Year="2002" 373 ,Month="August" 374 ,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM 375 Symposium on Principles of Distributed Computing}" 376 ,pages="21-30" 377 ,annotation=" 378 Each thread keeps an array of pointers to items that it is 379 currently referencing. Sort of an inside-out garbage collection 380 mechanism, but one that requires the accessing code to explicitly 381 state its needs. Also requires read-side memory barriers on 382 most architectures. 383 " 384 } 385 386 @conference{Michael02b 387 ,author="Maged M. Michael" 388 ,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets" 389 ,Year="2002" 390 ,Month="August" 391 ,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM 392 Symposium on Parallel 393 Algorithms and Architecture}" 394 ,pages="73-82" 395 ,annotation=" 396 Like the title says... 397 " 398 } 399 400 @InProceedings{HerlihyLM02 401 ,author={Maurice Herlihy and Victor Luchangco and Mark Moir} 402 ,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, 403 Lock-Free Data Structures" 404 ,booktitle={Proceedings of 16\textsuperscript{th} International 405 Symposium on Distributed Computing} 406 ,year=2002 407 ,month="October" 408 ,pages="339-353" 409 } 410 411 @article{Appavoo03a 412 ,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and 413 D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and 414 B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and 415 B. Rosenburg and M. Stumm and J. Xenidis" 416 ,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" 417 ,Year="2003" 418 ,Month="January" 419 ,journal="IBM Systems Journal" 420 ,volume="42" 421 ,number="1" 422 ,pages="60-76" 423 } 424 425 @Conference{Arcangeli03 426 ,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and 427 Dipankar Sarma" 428 ,Title="Using Read-Copy Update Techniques for {System V IPC} in the 429 {Linux} 2.5 Kernel" 430 ,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference 431 (FREENIX Track)" 432 ,Publisher="USENIX Association" 433 ,year="2003" 434 ,month="June" 435 ,pages="297-310" 436 } 437 438 @article{McKenney03a 439 ,author="Paul E. McKenney" 440 ,title="Using {RCU} in the {Linux} 2.5 Kernel" 441 ,Year="2003" 442 ,Month="October" 443 ,journal="Linux Journal" 444 ,volume="1" 445 ,number="114" 446 ,pages="18-26" 447 } 448 449 @techreport{Friedberg03a 450 ,author="Stuart A. Friedberg" 451 ,title="Lock-Free Wild Card Search Data Structure and Method" 452 ,institution="US Patent and Trademark Office" 453 ,address="Washington, DC" 454 ,year="2003" 455 ,number="US Patent 6,662,184 (contributed under GPL)" 456 ,month="December" 457 ,pages="112" 458 } 459 460 @article{McKenney04a 461 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" 462 ,title="Scaling dcache with {RCU}" 463 ,Year="2004" 464 ,Month="January" 465 ,journal="Linux Journal" 466 ,volume="1" 467 ,number="118" 468 ,pages="38-46" 469 } 470 471 @Conference{McKenney04b 472 ,Author="Paul E. McKenney" 473 ,Title="{RCU} vs. Locking Performance on Different {CPUs}" 474 ,Booktitle="{linux.conf.au}" 475 ,Month="January" 476 ,Year="2004" 477 ,Address="Adelaide, Australia" 478 ,note="Available: 479 \url{http://www.linux.org.au/conf/2004/abstracts.html#90} 480 \url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} 481 [Viewed June 23, 2004]" 482 } 483 484 @phdthesis{PaulEdwardMcKenneyPhD 485 ,author="Paul E. McKenney" 486 ,title="Exploiting Deferred Destruction: 487 An Analysis of Read-Copy-Update Techniques 488 in Operating System Kernels" 489 ,school="OGI School of Science and Engineering at 490 Oregon Health and Sciences University" 491 ,year="2004" 492 ,note="Available: 493 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} 494 [Viewed October 15, 2004]" 495 } 496 497 @Conference{Sarma04c 498 ,Author="Dipankar Sarma and Paul E. McKenney" 499 ,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" 500 ,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 501 (FREENIX Track)" 502 ,Publisher="USENIX Association" 503 ,year="2004" 504 ,month="June" 505 ,pages="182-191" 506 } 507 508 @unpublished{JamesMorris04b 509 ,Author="James Morris" 510 ,Title="Recent Developments in {SELinux} Kernel Performance" 511 ,month="December" 512 ,year="2004" 513 ,note="Available: 514 \url{http://www.livejournal.com/users/james_morris/2153.html} 515 [Viewed December 10, 2004]" 516 } 517 518 @unpublished{PaulMcKenney05a 519 ,Author="Paul E. McKenney" 520 ,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" 521 ,month="May" 522 ,year="2005" 523 ,note="Available: 524 \url{http://lkml.org/lkml/2005/5/9/185} 525 [Viewed May 13, 2005]" 526 ,annotation=" 527 First publication of working lock-based deferred free patches 528 for the CONFIG_PREEMPT_RT environment. 529 " 530 } 531 532 @conference{PaulMcKenney05b 533 ,Author="Paul E. McKenney and Dipankar Sarma" 534 ,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware" 535 ,Booktitle="linux.conf.au 2005" 536 ,month="April" 537 ,year="2005" 538 ,address="Canberra, Australia" 539 ,note="Available: 540 \url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} 541 [Viewed May 13, 2005]" 542 ,annotation=" 543 Realtime turns into making RCU yet more realtime friendly. 544 " 545 } 546 547 @conference{ThomasEHart2006a 548 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown" 549 ,Title="Making Lockless Synchronization Fast: Performance Implications 550 of Memory Reclamation" 551 ,Booktitle="20\textsuperscript{th} {IEEE} International Parallel and 552 Distributed Processing Symposium" 553 ,month="April" 554 ,year="2006" 555 ,day="25-29" 556 ,address="Rhodes, Greece" 557 ,annotation=" 558 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free 559 reference counting. 560 " 561 } 562 563 @Conference{PaulEMcKenney2006b 564 ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and 565 Suparna Bhattacharya" 566 ,Title="Extending RCU for Realtime and Embedded Workloads" 567 ,Booktitle="{Ottawa Linux Symposium}" 568 ,Month="July" 569 ,Year="2006" 570 ,pages="v2 123-138" 571 ,note="Available: 572 \url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} 573 \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} 574 [Viewed January 1, 2007]" 575 ,annotation=" 576 Described how to improve the -rt implementation of realtime RCU. 577 " 578 } 579 580 @unpublished{PaulEMcKenney2006c 581 ,Author="Paul E. McKenney" 582 ,Title="Sleepable {RCU}" 583 ,month="October" 584 ,day="9" 585 ,year="2006" 586 ,note="Available: 587 \url{http://lwn.net/Articles/202847/} 588 Revised: 589 \url{http://www.rdrop.com/users/paulmck/RCU/srcu.2007.01.14a.pdf} 590 [Viewed August 21, 2006]" 591 ,annotation=" 592 LWN article introducing SRCU. 593 " 594 } 595 596 @unpublished{RobertOlsson2006a 597 ,Author="Robert Olsson and Stefan Nilsson" 598 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" 599 ,month="August" 600 ,day="18" 601 ,year="2006" 602 ,note="Available: 603 \url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf} 604 [Viewed February 24, 2007]" 605 ,annotation=" 606 RCU-protected dynamic trie-hash combination. 607 " 608 } 609 610 @unpublished{ThomasEHart2007a 611 ,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" 612 ,Title="Performance of memory reclamation for lockless synchronization" 613 ,journal="J. Parallel Distrib. Comput." 614 ,year="2007" 615 ,note="To appear in J. Parallel Distrib. Comput. 616 \url{doi=10.1016/j.jpdc.2007.04.010}" 617 ,annotation={ 618 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free 619 reference counting. Journal version of ThomasEHart2006a. 620 } 621 } 622 623 @unpublished{PaulEMcKenney2007QRCUspin 624 ,Author="Paul E. McKenney" 625 ,Title="Using Promela and Spin to verify parallel algorithms" 626 ,month="August" 627 ,day="1" 628 ,year="2007" 629 ,note="Available: 630 \url{http://lwn.net/Articles/243851/} 631 [Viewed September 8, 2007]" 632 ,annotation=" 633 LWN article describing Promela and spin, and also using Oleg 634 Nesterov's QRCU as an example (with Paul McKenney's fastpath). 635 " 636 }