Editing Read-copy-update (section)

==History==
{{prose|section|date=May 2014}}

Techniques and mechanisms resembling RCU have been independently invented multiple times:<ref>{{Cite thesis
  | last = McKenney
  | first = Paul E.
  | title = Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques
  | url = http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf
  | journal = OGI School of Science and Engineering at Oregon Health and Sciences University
  | date = July 2004
   }}</ref>
# [[H. T. Kung]] and Q. Lehman described use of garbage collectors to implement RCU-like access to a binary search tree.<ref>{{Cite journal
  | last1 = Kung
  | first1 = H. T.
  | last2 = Lehman
  | first2 = Q.
  | title = Concurrent Maintenance of Binary Search Trees
  | journal = ACM Transactions on Database Systems
  | volume = 5
  | date = September 1980
  | issue = 3
  | doi = 10.1145/320613.320619
  | page = 354
  | citeseerx = 10.1.1.639.8357
  | s2cid = 13007648
 }}</ref>
# [[Udi Manber]] and Richard Ladner extended Kung's and Lehman's work to non-garbage-collected environments by deferring reclamation until all threads running at removal time have terminated, which works in environments that do not have long-lived threads.<ref>{{Cite journal
  | last1 = Manber
  | first1 = Udi
  | last2 = Ladner
  | first2 = Richard E.
  | title = Concurrency Control in a Dynamic Search Structure
  | journal = ACM Transactions on Database Systems
  | volume = 9
  | date = September 1984
  | issue = 3
  }}</ref>
# [[Richard Rashid]] et al. described a lazy [[translation lookaside buffer]] (TLB) implementation that deferred reclaiming virtual-address space until all CPUs flushed their TLB, which is similar in spirit to some RCU implementations.<ref>{{Cite conference
  | last1 = Rashid
  | first1 = Richard
  | last2 = Tevanian
  | first2 = Avadis
  | last3 = Young
  | first3 = Michael
  | last4 = Golub
  | first4 = David
  | last5 = Baron
  | first5 = Robert
  | last6 = Bolosky
  | first6 = William
  | last7 = Chew
  | first7 = Jonathan
  | title = Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
  | url = http://citeseer.csail.mit.edu/cache/papers/cs/6535/http:zSzzSzwww.cs.cornell.eduzSzcs614-sp98zSzberkeley-262zSzmach-vm.pdf/rashid87machineindependent.pdf
  | journal = Second Symposium on Architectural Support for Programming Languages and Operating Systems
  | publisher = Association for Computing Machinery
  | date = October 1987
  }}</ref>
# James P. Hennessy, Damian L. Osisek, and Joseph W. Seigh, II were granted US Patent 4,809,168 in 1989 (since lapsed).  This patent describes an RCU-like mechanism that was apparently used in [[VM (Operating system)|VM/XA]] on [[IBM mainframe]]s.<ref>{{Cite patent
  | inventor1-last = Hennessy
  | inventor1-first = James P.
  | inventor2-last = Osisek
  | inventor2-first = Damian L.
  | inventor3-last = Seigh II
  | inventor3-first = Joseph W.
  | title = Passive Serialization in a Multitasking Environment
  | country = US
  | number = 4809168
  | pubdate = February 1989
  }}</ref>
# [[William Pugh (computer scientist)|William Pugh]] described an RCU-like mechanism that relied on explicit flag-setting by readers.<ref>{{Cite tech report
  | last = Pugh
  | first = William
  | title = Concurrent Maintenance of Skip Lists
  | url = http://portal.acm.org/citation.cfm?id=SERIES9310.93717
  | institution = Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland
  | number = CS-TR-2222.1
  | date = June 1990
   }}</ref>
# Aju John proposed an RCU-like implementation where updaters simply wait for a fixed period of time, under the assumption that readers would all complete within that fixed time, as might be appropriate in a hard real-time system.<ref>{{Cite conference
  | last = John
  | first = Aju
  | title = Dynamic vnodes &mdash; design and implementation
  | journal = USENIX Winter 1995
  | url = https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a
  | date = January 1995
   }}</ref>  [[Van Jacobson]] proposed a similar scheme in 1993 (verbal communication).
# J. Slingwine and P. E. McKenney received US Patent 5,442,758 in August 1995, which describes RCU as implemented in [[DYNIX/ptx]] and later in the Linux kernel.<ref>{{Cite patent
  | inventor1-last = Slingwine
  | inventor1-first = John D.
  | inventor2-last = McKenney
  | inventor2-first = Paul E.
  | title = Apparatus and Method for Achieving Reduced Overhead Mutual Exclusion and Maintaining Coherency in a Multiprocessor System
  | country = US
  | number = 5442758
  | pubdate = August 1995
  }}</ref>
# B. Gamsa, O. Krieger, J. Appavoo, and M. Stumm described an RCU-like mechanism used in the [[University of Toronto]] [https://web.archive.org/web/20061010230626/http://www.eecg.toronto.edu/~tornado/ Tornado research operating system] and the closely related [[IBM Research]] [[K42]] research operating systems.<ref>{{Cite conference
  | last1 = Gamsa
  | first1 = Ben
  | last2 = Krieger
  | first2 = Orran
  | last3 = Appavoo
  | first3 = Jonathan
  | last4 = Stumm
  | first4 = Michael
  | title = Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System
  | journal = Proceedings of the Third Symposium on Operating System Design and Implementation
  | url = http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf
  | date = February 1999
   }}</ref>
# [[Rusty Russell]] and Phil Rumpf described RCU-like techniques for handling unloading of Linux kernel modules.<ref>{{cite web
  | last = Russell
  | first = Rusty
  | title = Re: modular net drivers
  | url = http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html
  | date = June 2000
  | access-date = 2010-10-01
  | archive-date = 2012-03-31
  | archive-url = https://web.archive.org/web/20120331044313/http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html
  | url-status = dead
  }}</ref><ref>{{cite web
  | last = Russell
  | first = Rusty
  | title = Re: modular net drivers
  | url = http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html
  | date = June 2000
  | access-date = 2010-10-01
  | archive-date = 2012-03-31
  | archive-url = https://web.archive.org/web/20120331044422/http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html
  | url-status = dead
  }}</ref>
# D. Sarma added RCU to [https://www.kernel.org/pub/linux/kernel/v2.5/ChangeLog-2.5.43 version 2.5.43 of the Linux kernel] in October 2002.
# Robert Colvin et al. formally verified a lazy concurrent list-based set algorithm that resembles RCU.<ref>{{Cite conference
 |last1        = Colvin
 |first1       = Robert
 |last2       = Groves
 |first2      = Lindsay
 |last3       = Luchangco
 |first3      = Victor
 |last4       = Moir
 |first4      = Mark
 |title       = Formal Verification of a Lazy Concurrent List-Based Set Algorithm
 |journal     = Computer Aided Verification
 |url         = http://research.sun.com/scalable/pubs/CAV2006.pdf
 |date        = August 2006
 |url-status     = dead
 |archive-url  = https://web.archive.org/web/20090717075757/http://research.sun.com/scalable/pubs/CAV2006.pdf
 |archive-date = 2009-07-17
}}</ref>
# M. Desnoyers et al. published a description of user-space RCU.<ref>{{Cite journal
  | last1 = Desnoyers
  | first1 = Mathieu
  | last2 = McKenney
  | first2 = Paul E.
  | last3 = Stern
  | first3 = Alan
  | last4 = Dagenais
  | first4 = Michel R.
  | last5 = Walpole
  | first5 = Jonathan
  | title = User-Level Implementations of Read-Copy Update
  | journal = IEEE Transactions on Parallel and Distributed Systems
  | date = February 2012
   | volume = 23
 | issue = 2
 | pages = 375–382
 | doi = 10.1109/TPDS.2011.159
  | s2cid = 832767
 | url = http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
  }}</ref><ref>{{cite web
  | last1 = McKenney
  | first1 = Paul E.
  | last2 = Desnoyers
  | first2 = Mathieu
  | last3 = Jiangshan
  | first3= Lai
  | title = User-space RCU
  | publisher = [[Linux Weekly News]]
  | date = November 13, 2013
  | url = https://lwn.net/Articles/573424/
  | access-date = November 17, 2013 }}</ref>
# A. Gotsman et al. derived formal semantics for RCU based on separation logic.<ref>{{Cite conference
  | last1 = Gotsman
  | first1 = Alexey
  | last2 = Rinetzky
  | first2 = Noam
  | last3 = Yang
  | first3 = Hongseok
  | title = Verifying concurrent memory reclamation algorithms with grace
  | journal = ESOP'13: European Symposium on Programming
  | url = http://software.imdea.org/~gotsman/papers/recycling-esop13.pdf
  | date = March 16–24, 2013
   }}</ref>
# Ilan Frenkel, Roman Geller, Yoram Ramberg, and Yoram Snir were granted US Patent 7,099,932 in 2006.  This patent describes an RCU-like mechanism for retrieving and storing quality of service policy management information using a directory service in a manner that enforces read/write consistency and enables read/write concurrency.<ref name="patent7099932" />