11da177e4SLinus TorvaldsRead the F-ing Papers! 21da177e4SLinus Torvalds 31da177e4SLinus Torvalds 41da177e4SLinus TorvaldsThis document describes RCU-related publications, and is followed by 5*dd81eca8SPaul E. McKenneythe corresponding bibtex entries. A number of the publications may 6*dd81eca8SPaul E. McKenneybe found at http://www.rdrop.com/users/paulmck/RCU/. 71da177e4SLinus Torvalds 81da177e4SLinus TorvaldsThe first thing resembling RCU was published in 1980, when Kung and Lehman 91da177e4SLinus Torvalds[Kung80] recommended use of a garbage collector to defer destruction 101da177e4SLinus Torvaldsof nodes in a parallel binary search tree in order to simplify its 111da177e4SLinus Torvaldsimplementation. This works well in environments that have garbage 121da177e4SLinus Torvaldscollectors, but current production garbage collectors incur significant 131da177e4SLinus Torvaldsread-side overhead. 141da177e4SLinus Torvalds 151da177e4SLinus TorvaldsIn 1982, Manber and Ladner [Manber82,Manber84] recommended deferring 161da177e4SLinus Torvaldsdestruction until all threads running at that time have terminated, again 171da177e4SLinus Torvaldsfor a parallel binary search tree. This approach works well in systems 181da177e4SLinus Torvaldswith short-lived threads, such as the K42 research operating system. 191da177e4SLinus TorvaldsHowever, Linux has long-lived tasks, so more is needed. 201da177e4SLinus Torvalds 211da177e4SLinus TorvaldsIn 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive 221da177e4SLinus Torvaldsserialization, which is an RCU-like mechanism that relies on the presence 231da177e4SLinus Torvaldsof "quiescent states" in the VM/XA hypervisor that are guaranteed not 241da177e4SLinus Torvaldsto be referencing the data structure. However, this mechanism was not 251da177e4SLinus Torvaldsoptimized for modern computer systems, which is not surprising given 261da177e4SLinus Torvaldsthat these overheads were not so expensive in the mid-80s. Nonetheless, 271da177e4SLinus Torvaldspassive serialization appears to be the first deferred-destruction 281da177e4SLinus Torvaldsmechanism to be used in production. Furthermore, the relevant patent has 291da177e4SLinus Torvaldslapsed, so this approach may be used in non-GPL software, if desired. 301da177e4SLinus Torvalds(In contrast, use of RCU is permitted only in software licensed under 311da177e4SLinus TorvaldsGPL. Sorry!!!) 321da177e4SLinus Torvalds 331da177e4SLinus TorvaldsIn 1990, Pugh [Pugh90] noted that explicitly tracking which threads 341da177e4SLinus Torvaldswere reading a given data structure permitted deferred free to operate 351da177e4SLinus Torvaldsin the presence of non-terminating threads. However, this explicit 361da177e4SLinus Torvaldstracking imposes significant read-side overhead, which is undesirable 371da177e4SLinus Torvaldsin read-mostly situations. This algorithm does take pains to avoid 381da177e4SLinus Torvaldswrite-side contention and parallelize the other write-side overheads by 391da177e4SLinus Torvaldsproviding a fine-grained locking design, however, it would be interesting 401da177e4SLinus Torvaldsto see how much of the performance advantage reported in 1990 remains 411da177e4SLinus Torvaldsin 2004. 421da177e4SLinus Torvalds 431da177e4SLinus TorvaldsAt about this same time, Adams [Adams91] described ``chaotic relaxation'', 441da177e4SLinus Torvaldswhere the normal barriers between successive iterations of convergent 451da177e4SLinus Torvaldsnumerical algorithms are relaxed, so that iteration $n$ might use 461da177e4SLinus Torvaldsdata from iteration $n-1$ or even $n-2$. This introduces error, 471da177e4SLinus Torvaldswhich typically slows convergence and thus increases the number of 481da177e4SLinus Torvaldsiterations required. However, this increase is sometimes more than made 491da177e4SLinus Torvaldsup for by a reduction in the number of expensive barrier operations, 501da177e4SLinus Torvaldswhich are otherwise required to synchronize the threads at the end 511da177e4SLinus Torvaldsof each iteration. Unfortunately, chaotic relaxation requires highly 521da177e4SLinus Torvaldsstructured data, such as the matrices used in scientific programs, and 531da177e4SLinus Torvaldsis thus inapplicable to most data structures in operating-system kernels. 541da177e4SLinus Torvalds 551da177e4SLinus TorvaldsIn 1993, Jacobson [Jacobson93] verbally described what is perhaps the 561da177e4SLinus Torvaldssimplest deferred-free technique: simply waiting a fixed amount of time 571da177e4SLinus Torvaldsbefore freeing blocks awaiting deferred free. Jacobson did not describe 581da177e4SLinus Torvaldsany write-side changes he might have made in this work using SGI's Irix 591da177e4SLinus Torvaldskernel. Aju John published a similar technique in 1995 [AjuJohn95]. 601da177e4SLinus TorvaldsThis works well if there is a well-defined upper bound on the length of 611da177e4SLinus Torvaldstime that reading threads can hold references, as there might well be in 621da177e4SLinus Torvaldshard real-time systems. However, if this time is exceeded, perhaps due 631da177e4SLinus Torvaldsto preemption, excessive interrupts, or larger-than-anticipated load, 641da177e4SLinus Torvaldsmemory corruption can ensue, with no reasonable means of diagnosis. 651da177e4SLinus TorvaldsJacobson's technique is therefore inappropriate for use in production 661da177e4SLinus Torvaldsoperating-system kernels, except when such kernels can provide hard 671da177e4SLinus Torvaldsreal-time response guarantees for all operations. 681da177e4SLinus Torvalds 691da177e4SLinus TorvaldsAlso in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's 701da177e4SLinus Torvaldsread-side-tracking to permit replugging of algorithms within a commercial 711da177e4SLinus TorvaldsUnix operating system. However, this replugging permitted only a single 721da177e4SLinus Torvaldsreader at a time. The following year, this same group of researchers 731da177e4SLinus Torvaldsextended their technique to allow for multiple readers [Cowan96a]. 741da177e4SLinus TorvaldsTheir approach requires memory barriers (and thus pipeline stalls), 751da177e4SLinus Torvaldsbut reduces memory latency, contention, and locking overheads. 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds1995 also saw the first publication of DYNIX/ptx's RCU mechanism 781da177e4SLinus Torvalds[Slingwine95], which was optimized for modern CPU architectures, 791da177e4SLinus Torvaldsand was successfully applied to a number of situations within the 801da177e4SLinus TorvaldsDYNIX/ptx kernel. The corresponding conference paper appeared in 1998 811da177e4SLinus Torvalds[McKenney98]. 821da177e4SLinus Torvalds 831da177e4SLinus TorvaldsIn 1999, the Tornado and K42 groups described their "generations" 841da177e4SLinus Torvaldsmechanism, which quite similar to RCU [Gamsa99]. These operating systems 851da177e4SLinus Torvaldsmade pervasive use of RCU in place of "existence locks", which greatly 861da177e4SLinus Torvaldssimplifies locking hierarchies. 871da177e4SLinus Torvalds 881da177e4SLinus Torvalds2001 saw the first RCU presentation involving Linux [McKenney01a] 891da177e4SLinus Torvaldsat OLS. The resulting abundance of RCU patches was presented the 901da177e4SLinus Torvaldsfollowing year [McKenney02a], and use of RCU in dcache was first 911da177e4SLinus Torvaldsdescribed that same year [Linder02a]. 921da177e4SLinus Torvalds 931da177e4SLinus TorvaldsAlso in 2002, Michael [Michael02b,Michael02a] presented techniques 941da177e4SLinus Torvaldsthat defer the destruction of data structures to simplify non-blocking 951da177e4SLinus Torvaldssynchronization (wait-free synchronization, lock-free synchronization, 961da177e4SLinus Torvaldsand obstruction-free synchronization are all examples of non-blocking 971da177e4SLinus Torvaldssynchronization). In particular, this technique eliminates locking, 981da177e4SLinus Torvaldsreduces contention, reduces memory latency for readers, and parallelizes 991da177e4SLinus Torvaldspipeline stalls and memory latency for writers. However, these 1001da177e4SLinus Torvaldstechniques still impose significant read-side overhead in the form of 1011da177e4SLinus Torvaldsmemory barriers. Researchers at Sun worked along similar lines in the 1021da177e4SLinus Torvaldssame timeframe [HerlihyLM02,HerlihyLMS03]. 1031da177e4SLinus Torvalds 1041da177e4SLinus TorvaldsIn 2003, the K42 group described how RCU could be used to create 1051da177e4SLinus Torvaldshot-pluggable implementations of operating-system functions. Later that 1061da177e4SLinus Torvaldsyear saw a paper describing an RCU implementation of System V IPC 1071da177e4SLinus Torvalds[Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a]. 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds2004 has seen a Linux-Journal article on use of RCU in dcache 1101da177e4SLinus Torvalds[McKenney04a], a performance comparison of locking to RCU on several 1111da177e4SLinus Torvaldsdifferent CPUs [McKenney04b], a dissertation describing use of RCU in a 112a83f1fe2SPaul E. McKenneynumber of operating-system kernels [PaulEdwardMcKenneyPhD], a paper 113a83f1fe2SPaul E. McKenneydescribing how to make RCU safe for soft-realtime applications [Sarma04c], 114a83f1fe2SPaul E. McKenneyand a paper describing SELinux performance with RCU [JamesMorris04b]. 1151da177e4SLinus Torvalds 1161da177e4SLinus Torvalds 117*dd81eca8SPaul E. McKenney2005 has seen further adaptation of RCU to realtime use, permitting 118*dd81eca8SPaul E. McKenneypreemption of RCU realtime critical sections [PaulMcKenney05a, 119*dd81eca8SPaul E. McKenneyPaulMcKenney05b]. 120*dd81eca8SPaul E. McKenney 1211da177e4SLinus TorvaldsBibtex Entries 1221da177e4SLinus Torvalds 1231da177e4SLinus Torvalds@article{Kung80 1241da177e4SLinus Torvalds,author="H. T. Kung and Q. Lehman" 1251da177e4SLinus Torvalds,title="Concurrent Maintenance of Binary Search Trees" 1261da177e4SLinus Torvalds,Year="1980" 1271da177e4SLinus Torvalds,Month="September" 1281da177e4SLinus Torvalds,journal="ACM Transactions on Database Systems" 1291da177e4SLinus Torvalds,volume="5" 1301da177e4SLinus Torvalds,number="3" 1311da177e4SLinus Torvalds,pages="354-382" 1321da177e4SLinus Torvalds} 1331da177e4SLinus Torvalds 1341da177e4SLinus Torvalds@techreport{Manber82 1351da177e4SLinus Torvalds,author="Udi Manber and Richard E. Ladner" 1361da177e4SLinus Torvalds,title="Concurrency Control in a Dynamic Search Structure" 1371da177e4SLinus Torvalds,institution="Department of Computer Science, University of Washington" 1381da177e4SLinus Torvalds,address="Seattle, Washington" 1391da177e4SLinus Torvalds,year="1982" 1401da177e4SLinus Torvalds,number="82-01-01" 1411da177e4SLinus Torvalds,month="January" 1421da177e4SLinus Torvalds,pages="28" 1431da177e4SLinus Torvalds} 1441da177e4SLinus Torvalds 1451da177e4SLinus Torvalds@article{Manber84 1461da177e4SLinus Torvalds,author="Udi Manber and Richard E. Ladner" 1471da177e4SLinus Torvalds,title="Concurrency Control in a Dynamic Search Structure" 1481da177e4SLinus Torvalds,Year="1984" 1491da177e4SLinus Torvalds,Month="September" 1501da177e4SLinus Torvalds,journal="ACM Transactions on Database Systems" 1511da177e4SLinus Torvalds,volume="9" 1521da177e4SLinus Torvalds,number="3" 1531da177e4SLinus Torvalds,pages="439-455" 1541da177e4SLinus Torvalds} 1551da177e4SLinus Torvalds 1561da177e4SLinus Torvalds@techreport{Hennessy89 1571da177e4SLinus Torvalds,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}" 1581da177e4SLinus Torvalds,title="Passive Serialization in a Multitasking Environment" 1591da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 1601da177e4SLinus Torvalds,address="Washington, DC" 1611da177e4SLinus Torvalds,year="1989" 1621da177e4SLinus Torvalds,number="US Patent 4,809,168 (lapsed)" 1631da177e4SLinus Torvalds,month="February" 1641da177e4SLinus Torvalds,pages="11" 1651da177e4SLinus Torvalds} 1661da177e4SLinus Torvalds 1671da177e4SLinus Torvalds@techreport{Pugh90 1681da177e4SLinus Torvalds,author="William Pugh" 1691da177e4SLinus Torvalds,title="Concurrent Maintenance of Skip Lists" 1701da177e4SLinus Torvalds,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland" 1711da177e4SLinus Torvalds,address="College Park, Maryland" 1721da177e4SLinus Torvalds,year="1990" 1731da177e4SLinus Torvalds,number="CS-TR-2222.1" 1741da177e4SLinus Torvalds,month="June" 1751da177e4SLinus Torvalds} 1761da177e4SLinus Torvalds 1771da177e4SLinus Torvalds@Book{Adams91 1781da177e4SLinus Torvalds,Author="Gregory R. Adams" 1791da177e4SLinus Torvalds,title="Concurrent Programming, Principles, and Practices" 1801da177e4SLinus Torvalds,Publisher="Benjamin Cummins" 1811da177e4SLinus Torvalds,Year="1991" 1821da177e4SLinus Torvalds} 1831da177e4SLinus Torvalds 1841da177e4SLinus Torvalds@unpublished{Jacobson93 1851da177e4SLinus Torvalds,author="Van Jacobson" 1861da177e4SLinus Torvalds,title="Avoid Read-Side Locking Via Delayed Free" 1871da177e4SLinus Torvalds,year="1993" 1881da177e4SLinus Torvalds,month="September" 1891da177e4SLinus Torvalds,note="Verbal discussion" 1901da177e4SLinus Torvalds} 1911da177e4SLinus Torvalds 1921da177e4SLinus Torvalds@Conference{AjuJohn95 1931da177e4SLinus Torvalds,Author="Aju John" 1941da177e4SLinus Torvalds,Title="Dynamic vnodes -- Design and Implementation" 1951da177e4SLinus Torvalds,Booktitle="{USENIX Winter 1995}" 1961da177e4SLinus Torvalds,Publisher="USENIX Association" 1971da177e4SLinus Torvalds,Month="January" 1981da177e4SLinus Torvalds,Year="1995" 1991da177e4SLinus Torvalds,pages="11-23" 2001da177e4SLinus Torvalds,Address="New Orleans, LA" 2011da177e4SLinus Torvalds} 2021da177e4SLinus Torvalds 2031da177e4SLinus Torvalds@techreport{Slingwine95 2041da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 2051da177e4SLinus Torvalds,title="Apparatus and Method for Achieving Reduced Overhead Mutual 2061da177e4SLinus TorvaldsExclusion and Maintaining Coherency in a Multiprocessor System 2071da177e4SLinus TorvaldsUtilizing Execution History and Thread Monitoring" 2081da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 2091da177e4SLinus Torvalds,address="Washington, DC" 2101da177e4SLinus Torvalds,year="1995" 2111da177e4SLinus Torvalds,number="US Patent 5,442,758 (contributed under GPL)" 2121da177e4SLinus Torvalds,month="August" 2131da177e4SLinus Torvalds} 2141da177e4SLinus Torvalds 2151da177e4SLinus Torvalds@techreport{Slingwine97 2161da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 2171da177e4SLinus Torvalds,title="Method for maintaining data coherency using thread 2181da177e4SLinus Torvaldsactivity summaries in a multicomputer system" 2191da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 2201da177e4SLinus Torvalds,address="Washington, DC" 2211da177e4SLinus Torvalds,year="1997" 2221da177e4SLinus Torvalds,number="US Patent 5,608,893 (contributed under GPL)" 2231da177e4SLinus Torvalds,month="March" 2241da177e4SLinus Torvalds} 2251da177e4SLinus Torvalds 2261da177e4SLinus Torvalds@techreport{Slingwine98 2271da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 2281da177e4SLinus Torvalds,title="Apparatus and method for achieving reduced overhead 2291da177e4SLinus Torvaldsmutual exclusion and maintaining coherency in a multiprocessor 2301da177e4SLinus Torvaldssystem utilizing execution history and thread monitoring" 2311da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 2321da177e4SLinus Torvalds,address="Washington, DC" 2331da177e4SLinus Torvalds,year="1998" 2341da177e4SLinus Torvalds,number="US Patent 5,727,209 (contributed under GPL)" 2351da177e4SLinus Torvalds,month="March" 2361da177e4SLinus Torvalds} 2371da177e4SLinus Torvalds 2381da177e4SLinus Torvalds@Conference{McKenney98 2391da177e4SLinus Torvalds,Author="Paul E. McKenney and John D. Slingwine" 2401da177e4SLinus Torvalds,Title="Read-Copy Update: Using Execution History to Solve Concurrency 2411da177e4SLinus TorvaldsProblems" 2421da177e4SLinus Torvalds,Booktitle="{Parallel and Distributed Computing and Systems}" 2431da177e4SLinus Torvalds,Month="October" 2441da177e4SLinus Torvalds,Year="1998" 2451da177e4SLinus Torvalds,pages="509-518" 2461da177e4SLinus Torvalds,Address="Las Vegas, NV" 2471da177e4SLinus Torvalds} 2481da177e4SLinus Torvalds 2491da177e4SLinus Torvalds@Conference{Gamsa99 2501da177e4SLinus Torvalds,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm" 2511da177e4SLinus Torvalds,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory 2521da177e4SLinus TorvaldsMultiprocessor Operating System" 2531da177e4SLinus Torvalds,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on 2541da177e4SLinus TorvaldsOperating System Design and Implementation}" 2551da177e4SLinus Torvalds,Month="February" 2561da177e4SLinus Torvalds,Year="1999" 2571da177e4SLinus Torvalds,pages="87-100" 2581da177e4SLinus Torvalds,Address="New Orleans, LA" 2591da177e4SLinus Torvalds} 2601da177e4SLinus Torvalds 2611da177e4SLinus Torvalds@techreport{Slingwine01 2621da177e4SLinus Torvalds,author="John D. Slingwine and Paul E. McKenney" 2631da177e4SLinus Torvalds,title="Apparatus and method for achieving reduced overhead 2641da177e4SLinus Torvaldsmutual exclusion and maintaining coherency in a multiprocessor 2651da177e4SLinus Torvaldssystem utilizing execution history and thread monitoring" 2661da177e4SLinus Torvalds,institution="US Patent and Trademark Office" 2671da177e4SLinus Torvalds,address="Washington, DC" 2681da177e4SLinus Torvalds,year="2001" 2691da177e4SLinus Torvalds,number="US Patent 5,219,690 (contributed under GPL)" 2701da177e4SLinus Torvalds,month="April" 2711da177e4SLinus Torvalds} 2721da177e4SLinus Torvalds 2731da177e4SLinus Torvalds@Conference{McKenney01a 2741da177e4SLinus Torvalds,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and 2751da177e4SLinus TorvaldsOrran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni" 2761da177e4SLinus Torvalds,Title="Read-Copy Update" 2771da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 2781da177e4SLinus Torvalds,Month="July" 2791da177e4SLinus Torvalds,Year="2001" 2801da177e4SLinus Torvalds,note="Available: 2811da177e4SLinus Torvalds\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 2821da177e4SLinus Torvalds\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} 2831da177e4SLinus Torvalds[Viewed June 23, 2004]" 2841da177e4SLinus Torvaldsannotation=" 2851da177e4SLinus TorvaldsDescribed RCU, and presented some patches implementing and using it in 2861da177e4SLinus Torvaldsthe Linux kernel. 2871da177e4SLinus Torvalds" 2881da177e4SLinus Torvalds} 2891da177e4SLinus Torvalds 2901da177e4SLinus Torvalds@Conference{Linder02a 2911da177e4SLinus Torvalds,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 2921da177e4SLinus Torvalds,Title="Scalability of the Directory Entry Cache" 2931da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 2941da177e4SLinus Torvalds,Month="June" 2951da177e4SLinus Torvalds,Year="2002" 2961da177e4SLinus Torvalds,pages="289-300" 2971da177e4SLinus Torvalds} 2981da177e4SLinus Torvalds 2991da177e4SLinus Torvalds@Conference{McKenney02a 3001da177e4SLinus Torvalds,Author="Paul E. McKenney and Dipankar Sarma and 3011da177e4SLinus TorvaldsAndrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell" 3021da177e4SLinus Torvalds,Title="Read-Copy Update" 3031da177e4SLinus Torvalds,Booktitle="{Ottawa Linux Symposium}" 3041da177e4SLinus Torvalds,Month="June" 3051da177e4SLinus Torvalds,Year="2002" 3061da177e4SLinus Torvalds,pages="338-367" 3071da177e4SLinus Torvalds,note="Available: 3081da177e4SLinus Torvalds\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 3091da177e4SLinus Torvalds[Viewed June 23, 2004]" 3101da177e4SLinus Torvalds} 3111da177e4SLinus Torvalds 3121da177e4SLinus Torvalds@article{Appavoo03a 3131da177e4SLinus Torvalds,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and 3141da177e4SLinus TorvaldsD. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and 3151da177e4SLinus TorvaldsB. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and 3161da177e4SLinus TorvaldsB. Rosenburg and M. Stumm and J. Xenidis" 3171da177e4SLinus Torvalds,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping" 3181da177e4SLinus Torvalds,Year="2003" 3191da177e4SLinus Torvalds,Month="January" 3201da177e4SLinus Torvalds,journal="IBM Systems Journal" 3211da177e4SLinus Torvalds,volume="42" 3221da177e4SLinus Torvalds,number="1" 3231da177e4SLinus Torvalds,pages="60-76" 3241da177e4SLinus Torvalds} 3251da177e4SLinus Torvalds 3261da177e4SLinus Torvalds@Conference{Arcangeli03 3271da177e4SLinus Torvalds,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and 3281da177e4SLinus TorvaldsDipankar Sarma" 3291da177e4SLinus Torvalds,Title="Using Read-Copy Update Techniques for {System V IPC} in the 3301da177e4SLinus Torvalds{Linux} 2.5 Kernel" 3311da177e4SLinus Torvalds,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference 3321da177e4SLinus Torvalds(FREENIX Track)" 3331da177e4SLinus Torvalds,Publisher="USENIX Association" 3341da177e4SLinus Torvalds,year="2003" 3351da177e4SLinus Torvalds,month="June" 3361da177e4SLinus Torvalds,pages="297-310" 3371da177e4SLinus Torvalds} 3381da177e4SLinus Torvalds 3391da177e4SLinus Torvalds@article{McKenney03a 3401da177e4SLinus Torvalds,author="Paul E. McKenney" 3411da177e4SLinus Torvalds,title="Using {RCU} in the {Linux} 2.5 Kernel" 3421da177e4SLinus Torvalds,Year="2003" 3431da177e4SLinus Torvalds,Month="October" 3441da177e4SLinus Torvalds,journal="Linux Journal" 3451da177e4SLinus Torvalds,volume="1" 3461da177e4SLinus Torvalds,number="114" 3471da177e4SLinus Torvalds,pages="18-26" 3481da177e4SLinus Torvalds} 3491da177e4SLinus Torvalds 350a83f1fe2SPaul E. McKenney@techreport{Friedberg03a 351a83f1fe2SPaul E. McKenney,author="Stuart A. Friedberg" 352a83f1fe2SPaul E. McKenney,title="Lock-Free Wild Card Search Data Structure and Method" 353a83f1fe2SPaul E. McKenney,institution="US Patent and Trademark Office" 354a83f1fe2SPaul E. McKenney,address="Washington, DC" 355a83f1fe2SPaul E. McKenney,year="2003" 356a83f1fe2SPaul E. McKenney,number="US Patent 6,662,184 (contributed under GPL)" 357a83f1fe2SPaul E. McKenney,month="December" 358a83f1fe2SPaul E. McKenney,pages="112" 359a83f1fe2SPaul E. McKenney} 360a83f1fe2SPaul E. McKenney 3611da177e4SLinus Torvalds@article{McKenney04a 3621da177e4SLinus Torvalds,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni" 3631da177e4SLinus Torvalds,title="Scaling dcache with {RCU}" 3641da177e4SLinus Torvalds,Year="2004" 3651da177e4SLinus Torvalds,Month="January" 3661da177e4SLinus Torvalds,journal="Linux Journal" 3671da177e4SLinus Torvalds,volume="1" 3681da177e4SLinus Torvalds,number="118" 3691da177e4SLinus Torvalds,pages="38-46" 3701da177e4SLinus Torvalds} 3711da177e4SLinus Torvalds 3721da177e4SLinus Torvalds@Conference{McKenney04b 3731da177e4SLinus Torvalds,Author="Paul E. McKenney" 3741da177e4SLinus Torvalds,Title="{RCU} vs. Locking Performance on Different {CPUs}" 3751da177e4SLinus Torvalds,Booktitle="{linux.conf.au}" 3761da177e4SLinus Torvalds,Month="January" 3771da177e4SLinus Torvalds,Year="2004" 3781da177e4SLinus Torvalds,Address="Adelaide, Australia" 3791da177e4SLinus Torvalds,note="Available: 3801da177e4SLinus Torvalds\url{http://www.linux.org.au/conf/2004/abstracts.html#90} 3811da177e4SLinus Torvalds\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} 3821da177e4SLinus Torvalds[Viewed June 23, 2004]" 3831da177e4SLinus Torvalds} 3841da177e4SLinus Torvalds 3851da177e4SLinus Torvalds@phdthesis{PaulEdwardMcKenneyPhD 3861da177e4SLinus Torvalds,author="Paul E. McKenney" 3871da177e4SLinus Torvalds,title="Exploiting Deferred Destruction: 3881da177e4SLinus TorvaldsAn Analysis of Read-Copy-Update Techniques 3891da177e4SLinus Torvaldsin Operating System Kernels" 3901da177e4SLinus Torvalds,school="OGI School of Science and Engineering at 3911da177e4SLinus TorvaldsOregon Health and Sciences University" 3921da177e4SLinus Torvalds,year="2004" 393a83f1fe2SPaul E. McKenney,note="Available: 394a83f1fe2SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} 395a83f1fe2SPaul E. McKenney[Viewed October 15, 2004]" 3961da177e4SLinus Torvalds} 3971da177e4SLinus Torvalds 3981da177e4SLinus Torvalds@Conference{Sarma04c 3991da177e4SLinus Torvalds,Author="Dipankar Sarma and Paul E. McKenney" 4001da177e4SLinus Torvalds,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" 4011da177e4SLinus Torvalds,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 4021da177e4SLinus Torvalds(FREENIX Track)" 4031da177e4SLinus Torvalds,Publisher="USENIX Association" 4041da177e4SLinus Torvalds,year="2004" 4051da177e4SLinus Torvalds,month="June" 4061da177e4SLinus Torvalds,pages="182-191" 4071da177e4SLinus Torvalds} 408a83f1fe2SPaul E. McKenney 409a83f1fe2SPaul E. McKenney@unpublished{JamesMorris04b 410a83f1fe2SPaul E. McKenney,Author="James Morris" 411a83f1fe2SPaul E. McKenney,Title="Recent Developments in {SELinux} Kernel Performance" 412a83f1fe2SPaul E. McKenney,month="December" 413a83f1fe2SPaul E. McKenney,year="2004" 414a83f1fe2SPaul E. McKenney,note="Available: 415a83f1fe2SPaul E. McKenney\url{http://www.livejournal.com/users/james_morris/2153.html} 416a83f1fe2SPaul E. McKenney[Viewed December 10, 2004]" 417a83f1fe2SPaul E. McKenney} 418*dd81eca8SPaul E. McKenney 419*dd81eca8SPaul E. McKenney@unpublished{PaulMcKenney05a 420*dd81eca8SPaul E. McKenney,Author="Paul E. McKenney" 421*dd81eca8SPaul E. McKenney,Title="{[RFC]} {RCU} and {CONFIG\_PREEMPT\_RT} progress" 422*dd81eca8SPaul E. McKenney,month="May" 423*dd81eca8SPaul E. McKenney,year="2005" 424*dd81eca8SPaul E. McKenney,note="Available: 425*dd81eca8SPaul E. McKenney\url{http://lkml.org/lkml/2005/5/9/185} 426*dd81eca8SPaul E. McKenney[Viewed May 13, 2005]" 427*dd81eca8SPaul E. McKenney,annotation=" 428*dd81eca8SPaul E. McKenney First publication of working lock-based deferred free patches 429*dd81eca8SPaul E. McKenney for the CONFIG_PREEMPT_RT environment. 430*dd81eca8SPaul E. McKenney" 431*dd81eca8SPaul E. McKenney} 432*dd81eca8SPaul E. McKenney 433*dd81eca8SPaul E. McKenney@conference{PaulMcKenney05b 434*dd81eca8SPaul E. McKenney,Author="Paul E. McKenney and Dipankar Sarma" 435*dd81eca8SPaul E. McKenney,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware" 436*dd81eca8SPaul E. McKenney,Booktitle="linux.conf.au 2005" 437*dd81eca8SPaul E. McKenney,month="April" 438*dd81eca8SPaul E. McKenney,year="2005" 439*dd81eca8SPaul E. McKenney,address="Canberra, Australia" 440*dd81eca8SPaul E. McKenney,note="Available: 441*dd81eca8SPaul E. McKenney\url{http://www.rdrop.com/users/paulmck/RCU/realtimeRCU.2005.04.23a.pdf} 442*dd81eca8SPaul E. McKenney[Viewed May 13, 2005]" 443*dd81eca8SPaul E. McKenney,annotation=" 444*dd81eca8SPaul E. McKenney Realtime turns into making RCU yet more realtime friendly. 445*dd81eca8SPaul E. McKenney" 446*dd81eca8SPaul E. McKenney} 447