A common problem in concurrency is the so-called ABA problem. That means you read a value twice and each time it returns the same value A. Therefore you conclude that nothing changed in between. But you forgot the B.
Let me first use a simple scenario to introduce the problem.
The scenario consists of you sitting in a car and waiting that the traffic light becomes green. Green stands in our case for B, and red for A. What’s happening?
- You look at the traffic light and it is red (A).
- Because you are bored, you begin to check the news on your smartphone and forget the time.
- You look once more at the traffic light. Damn, is still red (A).
Of course, the traffic light became green (B) between your two checks. Therefore, what seems to be one red phase was two.
What does this mean for threads (processes)? Now once more formal.
- Thread 1 reads a variable var with value A.
- Thread 1 is preempted, and thread 2 runs.
- Thread 2 changes the variable var from A to B to A.
- Thread 1 starts to execute and checks the value of variable var; because the value of variable var is the same, thread 1 continues with its work,
Often, that is a no-brainer. You can simply ignore it.
Have a look at it here. The function fetch_mult (1) multiplies a std::atomic<T>& shared by mult.
The key observation is that there is a small time window between the reading of the old value T oldValue = shared.load (2) and the comparison with the new value (3). Therefore, another thread can kick in and change the oldValue from oldValue to anotherValue to oldValue back. The anotherValue is the B in ABA.
Often it makes no difference if the first read value is in the second read operation the original value. But in a lock-free concurrent data structure, ABA may have a great impact.
A lock-free data structure
I will not present here in detail a lock-free data structure. I will use a lock-free stack implemented as a singly linked list. The stack supports only two operations.
- Pops the top object and returns a pointer to it.
- Pushes the object specified to stack.
Let me describe in pseudo-code the pop operation to get an idea of the ABA problem. The pop operation performs, in essence, the following steps in a loop until the operation was successful.
- Get the head node: head
- Get the subsequent node: headNext
- Make headNext to the new head if head is still the head of the stack
Here are the first two nodes of the stack:
Let’s construct the ABA problem.
ABA in action
Let’s start with the following stack:
Thread 1 is active and wants to pop the head of stack.
- Thread 1 stores
- head = A
- headNext = B
Before thread 1 finishes the pop algorithm, thread 2 kicks in.
- Thread 2 pops A
- Thread 2 pops B and deletes B
- Thread 2 pushes A back
Thread 1 is rescheduled, and check if A == head. Because A == head, headNext which is B becomes the new head. But B was already deleted. Therefore, the program has undefined behavior.
There are a few remedies for the ABA problem.
Remedy for ABA
The conceptual problem of ABA is relatively easy to get. A node such as B == headNext was deleted, although another node A == head was referring to it. The solution to our problem is to eliminate the premature deletion of the node. Here are a few remedies.
Tagged state reference
You can add a tag indicating how often the node has been successfully modified. The result is that compare and swap method will eventually fail, although the check returns true.
The next three techniques are based on the idea of deferred reclamation.
Garbage collection guarantees that the variables will only be deleted if it is not needed anymore. That sounds promising but has a big drawback. Most garbage collectors are not lock-free. Therefore, you have a lock-free data structure, but the overall system is not lock-free.
In a hazard-pointer system, each thread keeps a list of hazard pointers indicating which nodes the thread is accessing. (This “list” may be limited to only one or two elements in many systems.) Nodes on the hazard pointer list must not be modified or deallocated by any other thread. … When a thread wishes to remove a node, it places it on a list of nodes “to be freed later” but does not deallocate the node’s memory until no other thread’s hazard list contains the pointer. A dedicated garbage-collection thread can do this manual garbage collection (if the list “to be freed later” is shared by all the threads); alternatively, cleaning up the “to be freed” list can be done by each worker thread as part of an operation such as “pop”.
RCU stands for Read Copy Update and is a synchronization technique for almost read-only data structures. RCU was created by Paul McKenney and is used in the Linux Kernel since 2002.
The idea is quite simple and follows the acronym. To modify data, you make a copy of the data and modify that copy. On the contrary, all readers work with the original data. You can safely replace the data structure with the copy if there is no reader.
For more details about RCU, read the article What is RCU, Fundamentally? by Paul McKenney.
I’m not so sure. I have to go for the next big topic with the potential for at least 20 exciting posts. Let yourself be surprised.
Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, and Marco Parri Empoli.
Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.
|My special thanks to Embarcadero|
|My special thanks to PVS-Studio|
|My special thanks to Tipi.build|
|My special thanks to Take Up Code|
I’m happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.
- Embedded Programmierung mit modernem C++ 12.12.2023 – 14.12.2023 (Präsenzschulung, Termingarantie)
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
- C++ – The Core Language
- C++ – The Standard Library
- C++ – Compact
- C++11 and C++14
- Concurrency with Modern C++
- Design Pattern and Architectural Pattern with C++
- Embedded Programming with Modern C++
- Generic Programming (Templates) with C++
- Clean Code with Modern C++
- Phone: +49 7472 917441
- Mobil:: +49 176 5506 5086
- Mail: schulung@ModernesCpp.de
- German Seminar Page: www.ModernesCpp.de
- Mentoring Page: www.ModernesCpp.org
Modernes C++ Mentoring,