Here's an interesting, practical and more memory efficient way alternative to the Read Copy Update (RCU) Algo. These algos assume far more reads than writes. Instead of copying the data structure for writing (essentially creating a new version), you maintain two copies of your data structures where both sides are eventually consistent. Strictly, writers will modify the opposite (say left) side of what the current readers are reading (right) and then point new readers to the modified side (left) while waiting for old readers to finish up before modifying the other side (right). When another write comes in, the same process occurs starting with the right side.
Simple concurrent algorithm too and there is no reason to use heavy synchronization mechanisms here. A counter (Array of counters is better because contention is bad) for each side and an index for where the reads are going. It is pretty novel for me.
Links
- Video: https://www.youtube.com/watch?v=FtaD0maxwec&index=73&list=PLHTh1InhhwT75gykhs7pqcR_uSiG601oh
- CF: http://concurrencyfreaks.blogspot.com/2013/12/left-right-concurrency-control.html