## 3 RCU-Style Non-Blocking Synchronous Algorithms
### Read Copy Update (RCU)  
RCU [52] is a synchronization scheme that allows multiple read threads and one write thread to simultaneously access shared data. The advantage of RCU is that reading threads can perform concurrently without blocking while the writing thread is updating shared data. The reason RCU can increase the level of concurrency in the read operation is that it does not block existing read operations by creating a copy before updating the data. RCU overcomes the limitation of RW-lock where all other threads are blocked by a single writing thread in this way. The previous data need to be freed for memory management once all threads reading the previous data have been completed. RCU is a scheme suitable for synchronizing pointer-based data structures such as linked lists, but when updating, updates are applied by a single atomic pointer assignment, so there is a limit to its use in data structures that require multiple pointer assignment. This is because the data must be atomically distinct for the reading thread to distinguish it unambiguously before and after the update. Therefore, applying RCU to a data structure such as a doubly linked list or tree that requires multiple pointer assignment has limitations in programming complexity and operations [22; 24; 26]. The core of the RCU synchronization scheme is an algorithm that detects the completion of reading the previous data. The algorithm for detecting the read completion is closely related to the operating system's scheduler, interrupt handler, etc., so the algorithm is selected according to performance optimization and requirements of applications [19]. There are several algorithms for reclamation, including quiescent-state-based reclamation (QSBR), epoch-based reclamation (EBR), hazard-pointer-based reclamation (HPR), and lock-free reference counting (LFRC). QSBR and EBR are the most frequently used due to their performance [19; 38]. We introduce the algorithms we used and analyze its performance in Sections 4 and 5.2. Performance degradation owing to sequential execution between write threads and API usage complexity due to an atomic single pointer assignment update are both disadvantages of RCU [24]. \begin{table}
\begin{tabular}{l l l l l} \hline \hline  & **RW-Lock [51]** & **RCU [38]** & **RLU [24]** & **MV-RLU [25]** \\ \hline Policy & & lock-based & lock and non-blocking & non-blocking & non-blocking \\ \hline \multirow{3}{*}{Concurrency} & R-R & \(\bullet\) & \(\bullet\) & \(\bullet\) & \(\bullet\) \\ \cline{2-5}  & R-W & \(\times\) & \(\bullet\) & \(\bullet\) & \(\bullet\) \\ \cline{2-5}  & W-W & \(\times\) & \(\times\) & \(\blacktriangle\) & \(\blacktriangle\) \\ \hline \multirow{3}{*}{Design factor} & concurrent R, mutual exclusive W & concurrent R, single W & concurrent R, multiple W & concurrent R, multiple W \\ \cline{2-5}  & & & & \\ \cline{2-5} API usage difficulty & low & high & medium & medium \\ \hline Main & lock and unlock, mutual exclusion & serialized execution & & \\ \cline{2-5}  & & & & \\ \cline{2-5}  & & & & \\ \cline{2-5}  & & & & \\ \hline \end{tabular} NOTE. R: reader; W: writer; \(\times\): no parallelism; \(\bullet\): full parallelism; \(\blacktriangle\): write–write conflict for the same data.  
\end{table} 
Table 1: High-level comparison of blocking and non-blocking synchronization mechanisms. Depending on the design, each mechanisms features concurrent execution parallelism, major design factors, main performance overheads, and difficulty in API usage. RW-lock lock allows concurrent access for read-only operations, while write operations require exclusive access. RCU and RLU are designed for read-mostly workloads. In the case of RCU, read operations are non-blocking, since concurrent reads are allowed whereas write operations are blocking, because write executions are serialized. In the case of RLU, concurrent writes are allowed unless there is a write conflict of the same data. Therefore, RLU supports non-blocking for both read and write operations.