## 3 RCU-Style Non-Blocking Synchronous Algorithms
### Multi-Version Read Log Update (MV-RLU)
#### 3.3.2 Use of MV-RLU APIs  
MV-RLU's API is almost identical to RLU, so it is compatible with most applications without modification. The main APIs of MV-RLU are as follows.  
Figure 3: Example of updating a node in a linked list with MV-RLU. The assumptions and notations of Figure 1 are followed in the same way.  
* **mvrlu_reader_lock0**, **mvrlu_reader_unlock()**: APIs used by threads to enter/exit a critical section. mvrlu_reader_lock() begins a MV-RLU section and reads global clock and stores it as local clock in the thread's metadata. mvrlu_reader_unlock() commits an update of a shared object and finishes an MV-RLU section.
* **mvrlu_try_lock0**: An API that acquires exclusive rights to modify an object and creates a version in the log.
* **mvrlu_try_lock_const0**: An optimized form of **mvrlu_try_lock0** API for objects to be deleted. Objects to be deleted do not need to create a new version in the log, so MV-RLU only has exclusive rights to modify the object.
* **mvrlu_assign_pointer() or MV-RLU_assign_ptr0**: An API where a write thread performs pointer mutation operations on shared objects.
* **mvrlu_dereference0 or mvrlu_deref0**: An API that traverses for the latest valid version based on local clock on each thread (MV-RLU searches the version with the latest write clock based on local clock while traversing the version chain of Figure 3a).
* **mvrlu_free0**: An API that performs the logical deletion of objects.  
Figure 3b shows a relationship between the threads of API usages required in the process of Figure 3a. In order to access the data structure synchronized with MV-RLU, each thread needs to enter the MV-RLU section, and the thread reads the latest valid version based on the time it enters the MV-RLU section (local clock). Thread W1 calls mvrlu_reader_lock() to begin the MV-RLU section to access shared data. Then, to modify node \(B\), the thread calls try_lock(B) to get exclusive modification rights. Thread W1 creates version \(B^{\prime}\) in its log, adds it to the front of node \(B^{\prime}\)s version chain, and releases node \(B^{\prime}\)s mutation right. Then, the thread modifies the pointer of the target node using mvrlu_assign_pointer() and stores the update clock of version \(B^{\prime}\) with global clock + 1 (stored in the write clock ). Thread R1 enters the MV-RLU section after thread W1's modification, so it reads \(B^{\prime}\), which is the latest valid version for node \(B\), through mvrlu_deref(B). While thread R1 reads \(B^{\prime}\), thread W2 creates a new version \(B^{\prime\prime}\) to update node B once more using try_lock(B) and mvrlu_assign_pointer(). Then, the thread records the write clock of version \(B^{\prime\prime}\) () and completes the modification. After the update of thread W2 is completed, thread R2 enters the MV-RLU section and reads the copied node (version) \(B^{\prime\prime}\), as \(B^{\prime\prime}\) is the most recent valid version that the R2 can read. Similar to RCU and RLU, each thread safely releases versions that has passed the Grace Period to recycle the log. Log reclamation of MV-RLU takes a certain amount of time regardless of the number of execution threads because all threads execute their logs in parallel when the log usage exceeds a certain threshold.