## 3 RCU-Style Non-Blocking Synchronous Algorithms
### Read Copy Update (RCU)
#### 3.1.2 Use of RCU APIs  
We introduce the main APIs of RCU and show examples of their use. RCU consists of various functions depending on the implementation, and the main APIs are as follows.  
* **rcu_read_lock()**, **rcu_read_unlock0**: APIs that notify the entry and exit of a critical section of reading threads, respectively.
* **rcu_assign_pointer() or **rcu_assign_ptr0**: Used by write threads to apply changes to a node. Used when changing the next pointer of node A to node B' in the example of Figure 1a ().
* **rcu_deference()** or **rcu_deref0**: An API used by threads to read shared data in a critical section. It guarantees the order of operations through memory barriers, compiler directives, etc., to ensure that appropriate values of changed shared data can be read.
* **rcu_synchronize0**: An API that waits for a critical section of the currently reading threads to exit before safely releasing an original node of the copied node.
* **rcu_call0**: Non-blocking type API of **rcu_synchronize0**. An API that releases nodes in a non-blocking manner by registering nodes to be freed and a call back function instead of directly calling **rcu_synchronize0** if an application does not allow the write thread to be blocked. Frequent calls of **rcu_call0** may cause memory management problems due to the accumulation of a large number of nodes to be freed [53; 54].  
Figure 1: Example of updating a node in a linked list with RCU. (**a**) assumes that multiple threads concurrently access the linked list consisting of three nodes: A, B, and C. (**b**) shows the API usage for the operation example of (**a**) for each thread.  
Through Figure 1b, we explain a relationship between the threads and API usage required in the process of Figure 1a. Thread R1 enters the critical section through rcu_read_lock(). Thread R1 reads node B using rcu_deref() in critical section ( ). Thread W acquires the mutual exclusive lock for write operations, creates B', which is a copy of node B ( ), and performs an update through pointer assignment operation using rcu_assign_pointer() ( ). Then, thread W releases the lock (at the end of the Write Lock region in Figure 1b). While thread W updates node B, R1 still reads node B without interruption. R1 reads node B (denoted as rcu_deref(B) in the figure) because it reads the A's next node through rcu_deref() before the rcu_assign_ptr() of thread W ( ). R2 reads node B' (denoted as rcu_deref(B') in the figure), because it reads the A's next node through rcu_deref() after the rcu_assign_ptr() of thread W ( ). The rcu_assign_pointer() and rcu_deref() prevent instruction reordering through memory barriers, compiler directives, etc., so that appropriate nodes can be read before or after the change of the nodes. Thread W calls rcu_synchronize() to wait until [PERSON] finishes reading to node B, and then, it releases the original node (denoted as free in Figure 1b). The waiting period is referred to as the Grace Period of thread W in Figure 1b. The quiescent state means a state in which threads are not accessing shared data. The area on thread R1's timeline in Figure 1b represents the period following [PERSON]'s completion of reading node B. The Grace Period ends when all read threads have passed the Quiescent State[37; 55]. To summarize RCU, read threads access nodes without any lock, and a write thread releases a node when all the readers in the critical section pass the Quiescent State after the node is modified.