RCU, this barrier-based mechanism, allows for simple epoch-based reclamation of the old copies, and the mechanism as a whole eliminates many of the atomic read-modify-write instructions, memory barriers, and cache misses that are so expensive on modern multicore systems.
- Novel extension of RCU framework that support read-only traverals concurrently with multiple updates.
- In a semi-automated way.
- Removes from the programmer the burder of handcrafting the concurrent copy management using only single pointer manipulations.
- Can be API-compatible with RCU.
- Clock-based logging mechanism.
- Object-level write-log per thread.
// For all operations:
The writer’s modifications are:
- hidden from concurrent reads,
- avoid conflicts with concurrent writes.
In the following figure, the order of updating new value, 23, at write-clock and global-clock is important. Because all new object copies of the write-log become visible at once to all concurrent RLU protected section after the increment of global clock.
Many of the lock mentioned is not really calling
pthread_mutex_lock() but just performing a update at a specific filed in data.
- Execute writers serially.
- Fine-grained locks.
Using a global lock for each writer is simplicity of the code and the concurrency that does exist between read-only and write operations.
But the drawback is a lack of scalability.
Each object that a writer modifies is logged and locked (as shown in the former figure) by the RLU mechanism.
RLU locks can be used as a fine-grained locking mechanism.
For standard lock, it is necessary to execute post-lock customized verifications to ensure that the state of the object is still the same as it was before locking. This action is unnecessary for RLU locks.
- a global clock
- a global array of threads
- two write-logs: new object copies
- a thread indentifier
- a pointer: point to the actual object
- the object size
- a special pointer value that indicates this is a copy (constant)
- a run counter: the thread is active or not
- a local clock: stealing mechanism
- write clock for each thread: stealing mechanism
- write clock of a thread is initially $\infty$ and write clock is updated first (than global clock), so stealing from a thread is only possible when is updates the write clock during the commit
- a pointer: points to the copy of this object in a write-log
Note: The actually code is the way of much more complex than previously mentioned. But these code are also nice course of programming in C.
- Read-Log-Update: A Lightweight Synchronization Mechanism for Concurrent Programming, Alexander Matveev, Nir Shavit, Pascal Felber, Patrick Marlier