High-level C++ Implementation of the

Read-Copy-Update Pattern
Gábor Márton Imre Szekeres Zoltán Porkoláb
Eötvös Loránd University, Budapest University of Technology Eötvös Loránd University,
Faculty of Informatics and Economics Faculty of Informatics
Dept. of Programming Languages Budapest, Hungary Dept. of Programming Languages
and Compilers Email: iszekeres.x@[Link] and Compilers
H-1117 Pázmány Péter sétány 1/C H-1117 Pázmány Péter sétány 1/C
Budapest, Hungary Budapest, Hungary
Email: martongabesz@[Link] Email: gsd@[Link]

Abstract—Concurrent programming with classical mutex/lock SPINLOCK(lock);

techniques does not scale well when reads are way more frequent
than writes. Such situation happens in operating system kernels Value lookup(List list, Key key) {
Node* node;
among other performance critical multithreaded applications. Value local_value;
Read copy update (RCU) is a well know technique for solving the rcu_read_lock();
// iterate over the list and return the value
problem. RCU guarantees minimal overhead for read operations // of the found element
and allows them to occur concurrently with write operations. if (node = find(list, key)) {
RCU is a favourite concurrent pattern in low level, performance local_value = node->value
rcu_read_unlock();
critical applications, like the Linux kernel. Currently there is return local_value;
no high-level abstraction for RCU for the C++ programming }
rcu_read_unlock();
language. In this paper, we present our C++ RCU class library return not_found;
to support efficient concurrent programming for the read-copy- }
update pattern. The library has been carefully designed to void remove (List list, Key key) {
optimise performance in a heavily multithreaded environment, Node* node;
in the same time providing high-level abstractions, like smart spin_lock(lock);
// iterate over the list and find the key
pointers and other C++11/14/17 features. if (node = find(list, key)) {
remove_node(list, node);
I. I NTRODUCTION spin_unlock(lock);
synchronize_rcu();
Read-copy-update is a concurrent design pattern [1], [2] free(node);
return;
which allows extremely low overhead for readers. Updates }
spin_unlock(lock);
can happen concurrently with reads as they leave the old }
versions of the data structure intact; this way the already
existing readers can finish their work. Thus, updates might Fig. 1. Usage of RCU in a linked list
require more overhead than reads and their effect might be
delayed. In contrast to readers-writers lock [3] RCU does not
block the writers if there are concurrent readers. rcu_read_unlock() we indicate the reader side critical
Classical RCU first appeared in the Linux kernel in 2002 section. In this read side critical section we traverse through
[4], [5]. It provides the following reader side primitives: the list (find()) and once we found the key we return with
rcu_read_lock() and rcu_read_unlock(). Read- the associated value. In the implementation of find() we
side critical sections may use rcu_dereference() to have to use rcu_dereference() to access the elements
access RCU protected pointers. in the list. It might happen that the key is not in the list, in
On the update side we may use the that case we again close the critical section and then return
synchronize_rcu() primitive and with a special value indicating the element is not in the list.
rcu_assign_pointer() to assign values to protected In remove() we have to use a spin lock in order to
pointer. Pointers stored by rcu_assign_pointer() protect the list from concurrent write operations. The block
can be fetched from within read-side critical sections by which is protected by the spin lock is the write-side critical
rcu_dereference(). section. We iterate over the list trying to find the key and
The pseudo code in Figure 1 demonstrates how these if we found it then we unlink (remove_node()) it from
primitives can be used to implement the lookup and the remove the list. In the realization of the remove_node() we have
operations on a simple linked list of key-value pairs. This to use the rcu_assign_pointer() primitive. After the
implementation is a simplified excerpt of McKenney’s pre- removal, with the synchronize_rcu() primitive we wait
BSD routing table example. With rcu_read_lock() and all pre-existing RCU read-side critical sections to completely
finish. Then we can deallocate the list node which is no longer class X {
needed and this way can close the write-side critical section std::vector<int> v;
mutable std::mutex m;
by releasing the lock.
public:
Classic RCU requires that read-side critical sections obey int sum() const { // read operation
the same rules obeyed by the critical sections of pure spin- std::lock_guard<std::mutex> lock{m};
return std::accumulate([Link](), [Link](),
locks: blocking or sleeping of any sort is strictly prohibited. 0);
}
Since 2002 many different RCU flavours have appeared in void add(int i) { // write operation
the Linux kernel which relax this strict requirement. Using std::lock_guard<std::mutex> lock{m};
v.push_back(i);
realtime RCU [6]–[8] read-side critical sections may be pre- }
};
empted and may block while acquiring spinlocks. Sleepable
RCU allows more, it permits arbitrary sleeping (or blocking)
Fig. 2. A shared collection
within RCU read-side critical sections [9], [10].
The different RCU flavours in the Linux kernel are nat-
urally dependent on the kernel internals, for example on class X {
std::shared_ptr<std::vector<int>> v;
the scheduler. Obviously they cannot be used in user space. mutable std::mutex m;
Userspace RCU (URCU) [11], [12] was created in 2009 public:
and has a similar API to the kernel space RCU flavours. X()
: v(std::make_shared<
Userspace RCU has different variants and implementations. std::vector<int>>()) {}
int sum() const { // read operation
For instance the Quiescent-State-Based Reclamation RCU std::shared_ptr<std::vector<int>>
(QSBR) provides near-zero read-side overhead but the price local_copy;
{
of minimal overhead is that each thread in an application is std::lock_guard<std::mutex> lock{m};
local_copy = v;
required to periodically invoke rcu_quiescent_state() }
to announce that it resides in a quiescent state [13]. The // assume processing the data takes longer
// than copying it
general-purpose user space realization can be used in appli- return std::accumulate(local_copy->begin(),
local_copy->end(),
cations where we cannot guarantee that each threads will in- 0);
voke rcu_quiescent_state() sufficiently often. How- }
void add(int i) { // write operation
ever, this versatility has its own price, general-purpose RCU std::shared_ptr<std::vector<int>>
local_copy;
has to use memory barriers in the read-side. A third variant {
std::lock_guard<std::mutex> lock{m};
uses POSIX signals to eliminate these barriers, obviously this local_copy = v;
flavour cannot be used on non-POSIX systems. }
local_copy->push_back(i);
URCU provides a low level C API, therefore it is more {
std::lock_guard<std::mutex> lock{m};
prone to errors in C++ programs than a well established high- v = local_copy;
level C++ API can be. For instance, it is easy to forget to call }
}
rcu_read_unlock() on all return paths. In URCU there };
is no automatic memory reclamation; to deallocate memory,
first we have to use the synchronize_rcu() primitive. Fig. 3. Using a shared pointer in the collection
In this paper we present an alternative implementation for
user space RCU as a C++ smart pointer, thus there is no
need to manually deallocate memory. Our realization provides reads are way more frequent than writes [5]. Instead of a
a high-level abstraction C++ API to the users, so they can simple lock_guard we could use a readers-writers lock [3],
use a simple construct which is not prone to errors, still its but that would scale badly as well, especially when we have
performance is satisfying for most of the use cases. Our paper multiple concurrent writers [5].
is organized as follows. In section II we present the steps The first idea to make it better is to have a shared pointer
which lead from using a mutex to the concept of a high-level and hold the lock only until that is copied by the reader or
smart pointer for the RCU semantics. We describe the details updated by the writer (Figure 3). Now we have a race on the
and difficulties with the implementation of the smart pointer in pointee itself during the write. So we need to have a deep
III. Section IV contains the description of our testing methods. copy (Figure 4). The copy construction of the underlying data
We write about ongoing and future work in section V. Our (vector<int>) is thread safe, since the copy constructor
paper concludes in VI. parameter is a constant reference to vector<int>.
Still, there is one more problem: if there are two concurrent
II. T OWARDS A H IGHER L EVEL A BSTRACTION FOR RCU write operations then we might miss one of them. We should
Let us suppose we have a collection that is shared among check whether the other writer had done an update after the
multiple readers and writers in a concurrent manner (Figure actual writer has loaded the local copy. If it did then we should
2). It is a common way to make the collection thread safe load the data again and try to do the update again. This leads
by holding a lock until the iteration is finished (on the reader to the idea of using an atomic_compare_exchange in
thread). This approach does not scale well, especially when a while loop. We could use an atomic_shared_ptr if
 void add(int i) { // write operation class X {
std::shared_ptr<std::vector<int>> local_copy; rcu_ptr<std::vector<int>> v;
{
std::lock_guard<std::mutex> lock{m}; public:
local_copy = v; X()
} : v(std::make_shared<
auto local_deep_copy = std::vector<int>>()) {}
std::make_shared<std::vector<int>>( int sum() const { // read operation
*local_copy); std::shared_ptr<const std::vector<int>>
local_deep_copy->push_back(i); local_copy = [Link]();
{ return std::accumulate(local_copy->begin(),
std::lock_guard<std::mutex> lock{m}; local_copy->end(),
v = local_deep_copy; 0);
} }
} void add(int i) { // write operation
v.copy_update([i](std::vector<int> *copy) {
copy->push_back(i);
Fig. 4. Deep copy });
}
};
1 class X {
2 std::shared_ptr<std::vector<int>> v; Fig. 6. Usage of rcu ptr
3
4 public:
5 X()
6 : v(std::make_shared<
7 std::vector<int>>()) {} of the member.
8 int sum() const { // read operation We might notice that we can move construct the third pa-
9 auto local_copy = std::atomic_load(&v);
10 return std::accumulate(local_copy->begin(), rameter of atomic_compare_exchange_strong, there-
11 local_copy->end(),
12 0); fore we can spare a reference count increment and decrement:
13 }
14 void add(int i) { // write operation exchange_result =
15 auto local_copy = std::atomic_load(&v); std::atomic_compare_exchange_strong(
16 auto exchange_result = false; &v, &local_copy,
17 while (!exchange_result) { std::move(local_deep_copy));
18 // we need a deep copy
19 auto local_deep_copy = Regarding the write operation, since we are
20 std::make_shared<std::vector<int>>(
21 *local_copy); already in a while loop we could replace
22 local_deep_copy->push_back(i); atomic_compare_exchange_strong with
23 exchange_result =
24 std::atomic_compare_exchange_strong( atomic_compare_exchange_weak. That can result in
25 &v, &local_copy, local_deep_copy);
26 } a performance gain on some platforms [15], [16]. However,
27 } atomic_compare_exchange_weak can fail spuriously1 .
28 };
Consequently, we might do the deep copy more often than
Fig. 5. Using atomic shared pointer needed if we used the weak counterpart.
In the current form of class X nothing stops an other
programmer (e.g. a naive maintainer of the code years later)
that was included in the current C++ standard, but until then to add a new reader operation, like this:
we have to be satisfied with the free function overloads for int another_sum() const {
shared_ptr (Figure 5). These free function overloads take a return std::accumulate(v->begin(), v->end(),
0);
simple shared_ptr as a parameter and perform the specific }
atomic operations: This is definitely a race condition and a problem. To avoid
template <class T> this user error and to hide the sensitive technical details
std::shared_ptr<T> atomic_load(
const std::shared_ptr<T> *p); we created a smart pointer which we named as rcu_ptr.
template <class T> This smart pointer provides a general higher level abstraction
bool atomic_compare_exchange_strong( above atomic_shared_ptr. Figure 6 represents how can
std::shared_ptr<T> * p,
std::shared_ptr<T> * expected, we use rcu_ptr in our running example. The read()
std::shared_ptr<T> desired);
method of rcu_ptr returns a shared_ptr<const T>
Note, atomic_shared_ptr class template which would by value, therefore it is thread safe. The existence of the
replace these free functions might be included in the C++20 shared_ptr in the scope enforces that the read object will
standard [14]. Since both during the read operation and the live at least until this read operation finishes. By using the
write operation we do not modify the pointee the element shared pointer this way, we are free from the ABA problem
type of the member shared_ptr can be changed to be a [17], [18] since the memory address associated with the object
constant: cannot be reused until the object itself is reclaimed [19]. The
class X { copy_update() method receives a lambda. This lambda is
std::shared_ptr<const std::vector<int>> v; called whenever an update needs to be done, i.e. it will be
// ...
}; called continuously until the update is successful. The lambda
In the write operation we do the update on the copy of the 1 Spurious failure enables implementation of compare-and-exchange on a
original pointee (line 22 of Figure 5) and not on the pointee broader class of machines, e.g., load-locked store-conditional machines [15]
 1 template <typename T> class rcu_ptr { member shared_ptr. There is no need to make these
2 std::shared_ptr<const T> sp; constructors thread safe, because the construction can be done
3
4 public: only by one thread.
5 rcu_ptr() = default;
6 ˜rcu_ptr() = default; Lines 24-33 is the realization of the reset() methods
7
8 rcu_ptr(const rcu_ptr &rhs) = delete; which receive a shared_ptr<const T> as an lvalue or
9 rcu_ptr & rvalue reference parameter. We can use it to reset the wrapped
10 operator=(const rcu_ptr &rhs) = delete;
11 rcu_ptr(rcu_ptr &&) = delete; data to a new value independent from the old value (e.g.
12 rcu_ptr &operator=(rcu_ptr &&) = delete;
13 [Link]() ). Actually, with the parameter we over-
14 rcu_ptr(const std::shared_ptr<const T> &sp_) write the currently contained shared_ptr. The overwrite
15 : sp(sp_) {}
16 rcu_ptr(std::shared_ptr<const T> &&sp_) has to be an atomic operation in order to protect the member
17 : sp(std::move(sp_)) {}
18 from concurrent reset() calls.
19 std::shared_ptr<const T> read() const {
20 return std::atomic_load_explicit( In lines 19-22, the read() method atomically loads the
21 &sp, std::memory_order_consume); member shared_ptr and returns with a copy of that. The
22 }
23 copy_update() function template (lines 35-60) receives
24 void
25 reset(const std::shared_ptr<const T> &r) { an rvalue reference to an instance of a callable type. First
26 std::atomic_store_explicit(
27 &sp, r, std::memory_order_release); we create a local copy of the member as sp_l (lines 38-
28 } 40). If this local copy is set (i.e the rcu_ptr instance is
29 void reset(std::shared_ptr<const T> &&r) {
30 std::atomic_store_explicit( initialized) then we create a deep copy, that is we copy the
31 &sp, std::move(r),
32 std::memory_order_release); pointee itself and we create a new shared_ptr<T> (denoted
33 } as r) pointing to the copy (lines 44-47). Note, that this is a
34
35 template <typename R> non-constant shared pointer. On line 50 we call the callable
36 void copy_update(R &&fun) {
37 and we pass a non-constant pointer to the new copy as a
38 std::shared_ptr<const T> sp_l =
39 std::atomic_load_explicit( parameter. Then in lines 53-59 we exchange the member
40 &sp, std::memory_order_consume); shared pointer with a shared_ptr to the deep copy if we
41
42 std::shared_ptr<T> r; find that the member still points to the same object of which
43 do {
44 if (sp_l) { we created the copy. If it turns out that is not the case (i.e.
45 // deep copy another thread was faster), then we repeat the whole deep
46 r = std::make_shared<T>(*sp_l);
47 } copy update sequence until we succeed (line 43). The callers
48
49 // update of the copy_update() function must be aware that in case
50 std::forward<R>(fun)([Link]());
51 of an unset (or default initialized) rcu_ptr the callable will
52 } while ( be called with a null pointer as an argument. Also, a call
53 !std::
54 atomic_compare_exchange_strong_explicit( expression with this function is invalid, if the wrapped data
55 &sp, &sp_l,
56 std::shared_ptr<const T>( type (T) is a non-copyable type.
57 std::move(r)),
58 std::memory_order_release,
59 std::memory_order_consume)); A. Memory Ordering
60 }
61 }; A memory_order_release store is said to synchro-
nize with a memory_order_acquire load if that load
Fig. 7. The rcu ptr class template returns the value stored or in some special cases, some later
value [15], [22]. When a memory_order_release store
synchronizes with a memory_order_acquire load, any
receives a T* for the copy of the actual data. We can modify memory reference preceding the memory_order_release
the copy of the actual data inside the lambda. store will happen before any memory reference following
the memory_order_acquire load [15], [22]. This prop-
III. S MART P OINTER FOR RCU SEMANTICS erty allows a linked structure to be locklessly traversed
In Figure 7 we present the implementation of the rcu_ptr by using memory_order_release stores when updat-
class template. We provide a default constructor and a de- ing pointers to reference new data elements and by us-
fault destructor (lines 5 and 6). The move and copy oper- ing memory_order_acquire loads when loading point-
ations are deleted (lines 8-12) because rcu_ptr is essen- ers while locklessly traversing the data structure [22]. A
tially a wrapper around an atomic type (we plan to support memory_order_release store is dependency ordered be-
atomic_shared_ptr as soon as it is included in the fore a memory_order_consume load when that load re-
standard). And all atomic types are neither copyable nor turns the value stored, or in some special cases, some later
movable (because there is no sense to assign meaning for an value [15], [22]. Then, if the load carries a dependency to some
operation spanning two separately atomic objects) [20], [21]. later memory reference, any memory reference preceding the
We can create an rcu_ptr from an lvalue or rvalue memory_order_release store will happen before that
reference of shared_ptr<const T> (lines 14-17). These later memory reference [15], [22]. This means that when there
functions just simply copy or move their parameter into the is dependency ordering, memory_order_consume gives
the same guarantees that memory_order_acquire does, B. Lock Free atomic shared ptr
but at lower cost [22]. Our rcu_ptr relies on the free functions over-
In the classical RCU, the rcu_dereference() primitive loads with the atomic_ prefix [15, section [Link]]
implements the notion of a dependency ordered load, which for std::shared_ptr. It would be nice to use an
suppresses aggressive code-motion compiler optimizations and atomic_shared_ptr [14], but currently that is still in
generates a simple load on any system other than DEC Alpha, experimental phase. We use atomic shared_ptr opera-
where it generates a load followed by a memory-barrier tions which are implemented in terms of a spinlock (that
instruction. The rcu_assign_pointer() primitive im- is how it is implemented in the currently available stan-
plements the notion of store release, which on sequentially dard libraries). Having a lock-free atomic_shared_ptr
consistent and total-store-ordered systems compiles to a simple would be really beneficial. However, implementing a lock-free
assignment [11]. atomic_shared_ptr in a portable way can have extreme
difficulties [24]. Though, it might be easier on architectures
In our implementation of rcu_ptr::copy_update() where the double word CAS operation is available as a
function we can also use the release and consume seman- CPU instruction as we can see that with Anthony Williams
tics. We cannot use relaxed ordering because in case of implementation [25].
that if the fun is inlined and fun itself is not an or-
IV. C ORRECTNESS AND T ESTING
dering operation or it does not contain any fences then
the load or the compare exchange might be reordered To validate the correctness of our data structure we used
into the middle of fun. Also we need to ”see” the lat- different testing methods. We executed unit tests in a se-
est updates so we can copy and update the ”most re- quential manner (i.e. no parallel execution) to validate the
cent” version. Though, there is a data dependency chain: basic behaviour of the class template. We used oriented stress
sp_l->r->compare_exchange(...,r). So if all the testing [26] and sanitizers from the LLVM/Clang infrastructure
architectures were preserving data dependency ordering, than [27] to verify behaviour during concurrent execution. During
we would be fine with relaxed. However, some architec- our stress tests we focused on pairs of public methods of
tures do not preserve data dependency ordering (e.g. DEC rcu_ptr and we executed these functions from different
Alpha), therefore we need to explicitly state that we rely threads. We executed the operations in a loop on each thread
on that neither the CPU nor the compiler will reorder and we added random delays in between each calls. This way
data dependent operations. This is what we express with we tested different execution timings and we could make race
the consume-release semantics. Consequently, during all the windows slightly larger.
atomic load operations in the rcu_ptr class template we
V. F UTURE W ORK
can use memory_order_consume and during all atomic
store operations (including the read-modify-write operation) It is our ongoing work to create concrete and precise perfor-
we use memory_order_release. If the definition of the mance measurements. We aim to measure the performance of
fun callable is unseen by the compiler (i.e. it is defined in an our rcu_ptr on a weekly ordered architecture like ARMv7.
other translation unit) then the user have to annotate the decla- Our target is to do measurements on different dimensions
ration of the callable with the [[carries_dependency]] because the performance may depend on the architecture,
attribute [15]. Otherwise, the compiler may assume that the the number of reader or writer threads, the ratio of the
dependency chain is broken during the call and consequently it readers/writers, the size of the wrapped data, etc. Also, we
would fall back to the safer but less efficient acquire semantics plan to compare our implementation with URCU and readers-
[15]. writers lock in different use cases. The complexity and the
huge variegation of possible measurements drive us to publish
Unfortunately the consume memory order is temporarily the future results in a different paper.
deprecated in C++17. It is widely accepted that the current
definition of memory_order_consume in the C++11/14 VI. C ONCLUSION
standard is not useful. All current compilers essentially map RCU is a technique in concurrent programming which is
it to memory_order_acquire. The difficulties appear to getting used more and more often nowadays. It has been
stem both from the high implementation complexity and introduced in the Linux kernel first, but the efficiency of
from the fact that the current definition uses a fairly general the technique became proven so people demanded an im-
definition of ”dependency” [22], [23]. As such, the consume plementation which could be used in user space too. The
ordering has to be redefined. While this work is in progress, current available user space RCU solutions do not provide
hopefully ready for the next revision of C++, users are a mechanism for automatic memory reclamation, also they
encouraged to not use this ordering and instead use acquire provide a low level C API, which may be prone to errors.
ordering, so as to not be exposed to a breaking change in the In this paper we presented a high-level C++ implementation
future. As for our rcu_ptr, in order to reach the consume for the read-copy-update pattern, which provides automatic
semantics we plan to use hardware specific instructions in the memory deallocation while providing a safer and hard-to-
future to overcome the mentioned problem. misuse API.
 ACKNOWLEDGMENT [21] [Link], “Why are std::atomic objects not copyable?” 2017.
[Online]. Available: [Link]
The authors would like to thank to Péter Bolla for having [22] P. E. McKenney, T. Riegel, J. Preshing, H. Boehm, C. Nelson,
valuable discussions about the implementation, and the public O. Giroux, and L. Crowl, “Towards implementation and use of mem-
ory order consume,” ISO/IEC JTC 1, Information Technology, Subcom-
interface. We would like to thank also to for Máté Cserna, for mittee SC 22, Programming Language C++, Tech. Rep. P0098R0, 2015.
his really helpful comments on the library implementation. [23] H.-J. Boehm, “Temporarily deprecate memory order consume,”
ISO/IEC JTC 1, Information Technology, Subcommittee SC 22,
R EFERENCES Programming Language C++, Tech. Rep. P0371R0, May 2016.
[24] M. McCarty, “Implementing a lock-free atomic shared ptr,” 2016,
[1] P. E. McKenney and J. D. Slingwine, “Read-copy update: Using execu- cppNow 2016. [Online]. Available: [Link]
tion history to solve concurrency problems,” in Parallel and Distributed [25] A. Williams, “Implementation of a lock-free atomic shared ptr
Computing and Systems, 1998, pp. 509–518. class template as described in n4162,” 2016. [Online]. Available:
[2] P. E. McKenney, J. Appavoo, A. Kleen, O. Krieger, R. Russell, D. Sarma, [Link] shared ptr
and M. Soni, “Read-copy update,” in AUUG Conference Proceedings. [26] M. Desnoyers, “Proving the correctness of nonblocking data structures,”
AUUG, Inc., 2001, p. 175. Communications of the ACM, vol. 56, no. 7, pp. 62–69, 2013.
[3] J. M. Mellor-Crummey and M. L. Scott, “Scalable reader-writer [27] [Link]. (2017) clang: a c language family frontend for llvm. [Online].
synchronization for shared-memory multiprocessors,” SIGPLAN Not., Available: [Link]
vol. 26, no. 7, pp. 106–113, Apr. 1991. [Online]. Available:
[Link]
[4] P. E. McKenney and J. Walpole, “What is RCU, fundamentally?”
December 2007, available: [Link] [Viewed De-
cember 27, 2007].
[5] P. E. McKenney, Is Parallel Programming Hard, And,
If So, What Can You Do About It? Corvallis,
OR, USA: [Link], 2010. [Online]. Available:
[Link]
[6] P. McKenney, “The design of preemptible read-copy-update,” October
2007, available: [Link] [Viewed October 25,
2007].
[7] P. E. McKenney, D. Sarma, I. Molnar, and S. Bhattacharya, “Extending
rcu for realtime and embedded workloads,” in Ottawa Linux Symposium,
pages v2, 2006, pp. 123–138.
[8] P. E. McKenney and D. Sarma, “Adapting rcu for real-time operating
system usage,” Oct. 23 2007, uS Patent 7,287,135.
[9] P. E. McKenney, “Sleepable RCU,” October 2006,
available: [Link] Revised:
[Link]
[Viewed August 21, 2006].
[10] D. Guniguntala, P. E. McKenney, J. Triplett, and J. Walpole, “The read-
copy-update mechanism for supporting real-time applications on shared-
memory multiprocessor systems with Linux,” IBM Systems Journal,
vol. 47, no. 2, pp. 221–236, May 2008.
[11] M. Desnoyers, P. E. McKenney, A. S. Stern, M. R. Dagenais, and
J. Walpole, “User-level implementations of read-copy update,” IEEE
Transactions on Parallel and Distributed Systems, vol. 23, no. 2, pp.
375–382, 2012.
[12] M. Desnoyers, “[RFC git tree] userspace RCU (urcu) for Linux,”
February 2009, [Link]
[13] T. E. Hart, P. E. McKenney, A. D. Brown, and J. Walpole, “Performance
of memory reclamation for lockless synchronization,” J. Parallel Distrib.
Comput., vol. 67, no. 12, pp. 1270–1285, 2007.
[14] H. Sutter, “Atomic smart pointers, rev. 1,” ISO/IEC JTC 1, Information
Technology, Subcommittee SC 22, Programming Language C++, Tech.
Rep. n4162, Oct. 2014.
[15] ISO, ISO/IEC 14882:2014 Information technology — Programming
languages — C++. Geneva, Switzerland: International Organization
for Standardization, 2014.
[16] [Link], “Understanding
std::atomic::compare exchange weak() in c++11,” 2017. [Online].
Available: [Link]
[17] R. K. Treiber, Systems programming: Coping with parallelism. Inter-
national Business Machines Incorporated, Thomas J. Watson Research
Center, 1986.
[18] D. Dechev, P. Pirkelbauer, and B. Stroustrup, “Understanding and
effectively preventing the aba problem in descriptor-based lock-free
designs,” in Object/Component/Service-Oriented Real-Time Distributed
Computing (ISORC), 2010 13th IEEE International Symposium on.
IEEE, 2010, pp. 185–192.
[19] A. Williams, “Why do we need atomic shared ptr?” August
2015, available: [Link]
do-we-need-atomic shared [Link].
[20] Anthony Williams, C++ concurrency in action: practical multithread-
ing. Manning Publ., 2012.