## 2 Related Work  
In this section, we briefly summarize the synchronization mechanisms and efforts for improving scalability on manycore machines. Synchronization mechanisms have been developed in many different ways. There are two bifurcations of synchronization mechanisms: blocking and non-blocking synchronization mechanisms [7; 9; 20]. The typical and widely blocking algorithm is spinlock[9]. Blocking synchronization algorithms guarantee mutual exclusive access to shared data by blocking threads competing for the data. Although their behavior is simple and intuitive, since it blocks the thread, they are prone to deadlock and priority inversion [20]. When multiple threads are racing to access shared data simultaneously, the performance of a system degrades significantly because of cache line bouncing [6]. RW-lock was proposed in attempt to increase the concurrency level of lock-based algorithms [7; 9]. It allows a concurrent read of the shared data; however, it blocks all the threads from reading when a thread is writing to the shared data because it provides mutual exclusive write access to the data. Queued spinlock attacks the limits of spinlock by inserting competing threads in a queue to reduce the cache coherency traffic [10; 11; 31]. Although it effectively reduces the traffic, it showed that the queuing approach is not scalable. Recent manycore machines have NUMA architecture with multiple CPU sockets. A noteworthy characteristic of NUMA architecture is that the access speed of remote and local memory is different. There are a plethora of works that consider the characteristics of NUMA architecture [8; 12; 13; 32; 33]. Nevertheless, the lock-based synchronization algorithms have not successfully solved the performance issue originating from blocking. To address such an issue, non-blocking synchronization algorithms are proposed. Unlike blocking algorithms, non-blocking synchronization algorithms do not block a thread while it is competing for a shared data. Since the threads are not blocked in trying to access the data, they are guaranteed to be executed within a period of time [9; 20]. Non-blocking algorithms are also known as lock-free (lockless) algorithm because they tend not to use locks in controlling the access to the shared data [16; 20]. It is also categorized as wait-free because all threads are simultaneously accessing the shared data [20]. There are a number of that exploits lock-free synchronization algorithms to increase concurrency of accessing basic data structures [14; 17; 34]. Compared to the lock-based algorithms, the algorithms [14; 17; 34] improved the parallelism in accessing the data. However, the performance issue still remains when there is high contention in accessing shared data. When multiple threads access the shared data simultaneously, the system calls compare-and-swap (CAS) instructions frequently. Then, the performance drops because it leads to cache line bouncing. It is also reported that there is a performance bottleneck due to cost of memory recycling [35]. On top of that, it is not a easy task in writing a correct lock-free program because we have to consider the atomicity of an operation, reordering of command due to optimization, memory barriers, etc. [36]. RCU is a type of non-blocking algorithm that made in Linux kernel to increase the performance in manycore systems [21; 27; 37]. Its usage is increasing in many different environments. RCU increases concurrency by allowing multiple threads to read while a thread is writing a shared data [22; 38]. It increases the concurrency by making a copy of the shared data when a thread writes to it. As it is being updated, the rest of the threads are allowed to access the copied data, which effectively increases the concurrency. An update is reflected in the data structure with single atomic pointer assignment operation even while threads read the data. To not to interfere with reading threads, the write thread has to wait for the read threads to complete their requests before releasing the memory.