View source for McKenney, Slingwine - Read-Copy Update; Using Execution History to Solve Concurrency Problems

==Algorithm Description==
RCU is derived directly from hazard pointers.  If you've implemented hazard pointers, you will most likely have already have seen RCU and figured it out for yourself.  If OTOH you've only read the hazard pointer paper, you may well not have figured it out.

The essence of hazard pointers is that each thread, when it needs to ensure data structure elements are not deallocated, points pointers at those elements; and other threads, when they come to try to deallocate elements, will check those pointers.

Having implemented this, what you immediately observe is that threads only care about elements ''during an operation on the data structure''.  So if you're say adding an element to a linked list, you start caring from the point you set your hazard pointers to pointer at the insertion element and the following element, and you stop caring once your element has been linked in.

If a thread currently doesn't care about any elements in the data structure (all hazard pointers are currently set to NULL; the thread isn't doing any operations on the data structure), then as far as that thread is concerned, all deallocation candidate elements can be deallocated.

RCU is the step on from this; the observation that if, for a given deallocation candidate element (e.g. an element removed from the data structure, which therefore can no longer have new references), we knew every thread had reached a point where it no longer cares about elements in the data structure, ''then it must be safe to deallocate that element''.

Genius!  saves all that messing around with hazard pointer checking.

==See Also==
* [[White Papers]]