Documentation/RCU/RTFP.txt

Read the F-ing Papers!


This document describes RCU-related publications, and is followed by
the corresponding bibtex entries.

The first thing resembling RCU was published in 1980, when Kung and Lehman
[Kung80] recommended use of a garbage collector to defer destruction
of nodes in a parallel binary search tree in order to simplify its
implementation.  This works well in environments that have garbage
collectors, but current production garbage collectors incur significant
read-side overhead.

In 1982, Manber and Ladner [Manber82,Manber84] recommended deferring
destruction until all threads running at that time have terminated, again
for a parallel binary search tree.  This approach works well in systems
with short-lived threads, such as the K42 research operating system.
However, Linux has long-lived tasks, so more is needed.

In 1986, Hennessy, Osisek, and Seigh [Hennessy89] introduced passive
serialization, which is an RCU-like mechanism that relies on the presence
of "quiescent states" in the VM/XA hypervisor that are guaranteed not
to be referencing the data structure.  However, this mechanism was not
optimized for modern computer systems, which is not surprising given
that these overheads were not so expensive in the mid-80s.  Nonetheless,
passive serialization appears to be the first deferred-destruction
mechanism to be used in production.  Furthermore, the relevant patent has
lapsed, so this approach may be used in non-GPL software, if desired.
(In contrast, use of RCU is permitted only in software licensed under
GPL.  Sorry!!!)

In 1990, Pugh [Pugh90] noted that explicitly tracking which threads
were reading a given data structure permitted deferred free to operate
in the presence of non-terminating threads.  However, this explicit
tracking imposes significant read-side overhead, which is undesirable
in read-mostly situations.  This algorithm does take pains to avoid
write-side contention and parallelize the other write-side overheads by
providing a fine-grained locking design, however, it would be interesting
to see how much of the performance advantage reported in 1990 remains
in 2004.

At about this same time, Adams [Adams91] described ``chaotic relaxation'',
where the normal barriers between successive iterations of convergent
numerical algorithms are relaxed, so that iteration $n$ might use
data from iteration $n-1$ or even $n-2$.  This introduces error,
which typically slows convergence and thus increases the number of
iterations required.  However, this increase is sometimes more than made
up for by a reduction in the number of expensive barrier operations,
which are otherwise required to synchronize the threads at the end
of each iteration.  Unfortunately, chaotic relaxation requires highly
structured data, such as the matrices used in scientific programs, and
is thus inapplicable to most data structures in operating-system kernels.

In 1993, Jacobson [Jacobson93] verbally described what is perhaps the
simplest deferred-free technique: simply waiting a fixed amount of time
before freeing blocks awaiting deferred free.  Jacobson did not describe
any write-side changes he might have made in this work using SGI's Irix
kernel.  Aju John published a similar technique in 1995 [AjuJohn95].
This works well if there is a well-defined upper bound on the length of
time that reading threads can hold references, as there might well be in
hard real-time systems.  However, if this time is exceeded, perhaps due
to preemption, excessive interrupts, or larger-than-anticipated load,
memory corruption can ensue, with no reasonable means of diagnosis.
Jacobson's technique is therefore inappropriate for use in production
operating-system kernels, except when such kernels can provide hard
real-time response guarantees for all operations.

Also in 1995, Pu et al. [Pu95a] applied a technique similar to that of Pugh's
read-side-tracking to permit replugging of algorithms within a commercial
Unix operating system.  However, this replugging permitted only a single
reader at a time.  The following year, this same group of researchers
extended their technique to allow for multiple readers [Cowan96a].
Their approach requires memory barriers (and thus pipeline stalls),
but reduces memory latency, contention, and locking overheads.

1995 also saw the first publication of DYNIX/ptx's RCU mechanism
[Slingwine95], which was optimized for modern CPU architectures,
and was successfully applied to a number of situations within the
DYNIX/ptx kernel.  The corresponding conference paper appeared in 1998
[McKenney98].

In 1999, the Tornado and K42 groups described their "generations"
mechanism, which quite similar to RCU [Gamsa99].  These operating systems
made pervasive use of RCU in place of "existence locks", which greatly
simplifies locking hierarchies.

2001 saw the first RCU presentation involving Linux [McKenney01a]
at OLS.  The resulting abundance of RCU patches was presented the
following year [McKenney02a], and use of RCU in dcache was first
described that same year [Linder02a].

Also in 2002, Michael [Michael02b,Michael02a] presented techniques
that defer the destruction of data structures to simplify non-blocking
synchronization (wait-free synchronization, lock-free synchronization,
and obstruction-free synchronization are all examples of non-blocking
synchronization).  In particular, this technique eliminates locking,
reduces contention, reduces memory latency for readers, and parallelizes
pipeline stalls and memory latency for writers.  However, these
techniques still impose significant read-side overhead in the form of
memory barriers.  Researchers at Sun worked along similar lines in the
same timeframe [HerlihyLM02,HerlihyLMS03].

In 2003, the K42 group described how RCU could be used to create
hot-pluggable implementations of operating-system functions.  Later that
year saw a paper describing an RCU implementation of System V IPC
[Arcangeli03], and an introduction to RCU in Linux Journal [McKenney03a].

2004 has seen a Linux-Journal article on use of RCU in dcache
[McKenney04a], a performance comparison of locking to RCU on several
different CPUs [McKenney04b], a dissertation describing use of RCU in a
number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
describing how to make RCU safe for soft-realtime applications [Sarma04c],
and a paper describing SELinux performance with RCU [JamesMorris04b].


Bibtex Entries

@article{Kung80
,author="H. T. Kung and Q. Lehman"
,title="Concurrent Maintenance of Binary Search Trees"
,Year="1980"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="5"
,number="3"
,pages="354-382"
}

@techreport{Manber82
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,institution="Department of Computer Science, University of Washington"
,address="Seattle, Washington"
,year="1982"
,number="82-01-01"
,month="January"
,pages="28"
}

@article{Manber84
,author="Udi Manber and Richard E. Ladner"
,title="Concurrency Control in a Dynamic Search Structure"
,Year="1984"
,Month="September"
,journal="ACM Transactions on Database Systems"
,volume="9"
,number="3"
,pages="439-455"
}

@techreport{Hennessy89
,author="James P. Hennessy and Damian L. Osisek and Joseph W. {Seigh II}"
,title="Passive Serialization in a Multitasking Environment"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1989"
,number="US Patent 4,809,168 (lapsed)"
,month="February"
,pages="11"
}

@techreport{Pugh90
,author="William Pugh"
,title="Concurrent Maintenance of Skip Lists"
,institution="Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland"
,address="College Park, Maryland"
,year="1990"
,number="CS-TR-2222.1"
,month="June"
}

@Book{Adams91
,Author="Gregory R. Adams"
,title="Concurrent Programming, Principles, and Practices"
,Publisher="Benjamin Cummins"
,Year="1991"
}

@unpublished{Jacobson93
,author="Van Jacobson"
,title="Avoid Read-Side Locking Via Delayed Free"
,year="1993"
,month="September"
,note="Verbal discussion"
}

@Conference{AjuJohn95
,Author="Aju John"
,Title="Dynamic vnodes -- Design and Implementation"
,Booktitle="{USENIX Winter 1995}"
,Publisher="USENIX Association"
,Month="January"
,Year="1995"
,pages="11-23"
,Address="New Orleans, LA"
}

@techreport{Slingwine95
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and Method for Achieving Reduced Overhead Mutual
Exclusion and Maintaining Coherency in a Multiprocessor System
Utilizing Execution History and Thread Monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1995"
,number="US Patent 5,442,758 (contributed under GPL)"
,month="August"
}

@techreport{Slingwine97
,author="John D. Slingwine and Paul E. McKenney"
,title="Method for maintaining data coherency using thread
activity summaries in a multicomputer system"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1997"
,number="US Patent 5,608,893 (contributed under GPL)"
,month="March"
}

@techreport{Slingwine98
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and method for achieving reduced overhead
mutual exclusion and maintaining coherency in a multiprocessor
system utilizing execution history and thread monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="1998"
,number="US Patent 5,727,209 (contributed under GPL)"
,month="March"
}

@Conference{McKenney98
,Author="Paul E. McKenney and John D. Slingwine"
,Title="Read-Copy Update: Using Execution History to Solve Concurrency
Problems"
,Booktitle="{Parallel and Distributed Computing and Systems}"
,Month="October"
,Year="1998"
,pages="509-518"
,Address="Las Vegas, NV"
}

@Conference{Gamsa99
,Author="Ben Gamsa and Orran Krieger and Jonathan Appavoo and Michael Stumm"
,Title="Tornado: Maximizing Locality and Concurrency in a Shared Memory
Multiprocessor Operating System"
,Booktitle="{Proceedings of the 3\textsuperscript{rd} Symposium on
Operating System Design and Implementation}"
,Month="February"
,Year="1999"
,pages="87-100"
,Address="New Orleans, LA"
}

@techreport{Slingwine01
,author="John D. Slingwine and Paul E. McKenney"
,title="Apparatus and method for achieving reduced overhead
mutual exclusion and maintaining coherency in a multiprocessor
system utilizing execution history and thread monitoring"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2001"
,number="US Patent 5,219,690 (contributed under GPL)"
,month="April"
}

@Conference{McKenney01a
,Author="Paul E. McKenney and Jonathan Appavoo and Andi Kleen and
Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="July"
,Year="2001"
,note="Available:
\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
[Viewed June 23, 2004]"
annotation="
Described RCU, and presented some patches implementing and using it in
the Linux kernel.
"
}

@Conference{Linder02a
,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
,Title="Scalability of the Directory Entry Cache"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="289-300"
}

@Conference{McKenney02a
,Author="Paul E. McKenney and Dipankar Sarma and
Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
,Title="Read-Copy Update"
,Booktitle="{Ottawa Linux Symposium}"
,Month="June"
,Year="2002"
,pages="338-367"
,note="Available:
\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
[Viewed June 23, 2004]"
}

@article{Appavoo03a
,author="J. Appavoo and K. Hui and C. A. N. Soules and R. W. Wisniewski and
D. M. {Da Silva} and O. Krieger and M. A. Auslander and D. J. Edelsohn and
B. Gamsa and G. R. Ganger and P. McKenney and M. Ostrowski and
B. Rosenburg and M. Stumm and J. Xenidis"
,title="Enabling Autonomic Behavior in Systems Software With Hot Swapping"
,Year="2003"
,Month="January"
,journal="IBM Systems Journal"
,volume="42"
,number="1"
,pages="60-76"
}

@Conference{Arcangeli03
,Author="Andrea Arcangeli and Mingming Cao and Paul E. McKenney and
Dipankar Sarma"
,Title="Using Read-Copy Update Techniques for {System V IPC} in the
{Linux} 2.5 Kernel"
,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2003"
,month="June"
,pages="297-310"
}

@article{McKenney03a
,author="Paul E. McKenney"
,title="Using {RCU} in the {Linux} 2.5 Kernel"
,Year="2003"
,Month="October"
,journal="Linux Journal"
,volume="1"
,number="114"
,pages="18-26"
}

@techreport{Friedberg03a
,author="Stuart A. Friedberg"
,title="Lock-Free Wild Card Search Data Structure and Method"
,institution="US Patent and Trademark Office"
,address="Washington, DC"
,year="2003"
,number="US Patent 6,662,184 (contributed under GPL)"
,month="December"
,pages="112"
}

@article{McKenney04a
,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
,title="Scaling dcache with {RCU}"
,Year="2004"
,Month="January"
,journal="Linux Journal"
,volume="1"
,number="118"
,pages="38-46"
}

@Conference{McKenney04b
,Author="Paul E. McKenney"
,Title="{RCU} vs. Locking Performance on Different {CPUs}"
,Booktitle="{linux.conf.au}"
,Month="January"
,Year="2004"
,Address="Adelaide, Australia"
,note="Available:
\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
[Viewed June 23, 2004]"
}

@phdthesis{PaulEdwardMcKenneyPhD
,author="Paul E. McKenney"
,title="Exploiting Deferred Destruction:
An Analysis of Read-Copy-Update Techniques
in Operating System Kernels"
,school="OGI School of Science and Engineering at
Oregon Health and Sciences University"
,year="2004"
,note="Available:
\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
[Viewed October 15, 2004]"
}

@Conference{Sarma04c
,Author="Dipankar Sarma and Paul E. McKenney"
,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
(FREENIX Track)"
,Publisher="USENIX Association"
,year="2004"
,month="June"
,pages="182-191"
}

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