In
multithreaded computing
Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes, and development of both hardware and software. Computing has scientific, e ...
, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.
The ABA problem occurs when multiple
threads (or
processes) accessing shared data interleave. Below is a sequence of events that illustrates the ABA problem:
# Process
reads value A from some shared memory location,
#
is
preempted, allowing process
to run,
#
writes value B to the shared memory location
#
writes value A to the shared memory location
#
is preempted, allowing process
to run,
#
reads value A from the shared memory location,
#
determines that the shared memory value has not changed and continues.
Although
can continue executing, it is possible that the behavior will not be correct due to the "hidden" modification in shared memory.
A common case of the ABA problem is encountered when implementing a
lock-free
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object due to
MRU memory allocation. A pointer to the new item is thus often equal to a pointer to the old item, causing an ABA problem.
Examples
Consider a software example (written in C++) of ABA using a
lock-free
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
stack
Stack may refer to:
Places
* Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group
* Blue Stack Mountains, in Co. Donegal, Ireland
People
* Stack (surname) (including a list of people ...
:
/* Naive lock-free stack which suffers from ABA problem.*/
class Stack ;
This code can normally prevent problems from concurrent access, but suffers from ABA problems. Consider the following sequence:
Stack initially contains ''top'' → A → B → C
Thread 1 starts running pop:
ret = A;
next = B;
Thread 1 gets interrupted just before the
compare_exchange_weak
...
// Now the stack is top → B → C
// Now the stack is top → C
delete B;
Now the stack is ''top'' → A → C
When Thread 1 resumes:
compare_exchange_weak(A, B)
This instruction succeeds because it finds ''top'' ret (both are A), so it sets top to next (which is B). As B has been deleted the program will access freed memory when it tries to look at the first element on the stack. In C++, as shown here, accessing freed memory is
undefined behavior
In computer programming, undefined behavior (UB) is the result of executing a program whose behavior is prescribed to be unpredictable, in the language specification to which the computer code adheres. This is different from unspecified behavior, ...
: this may result in crashes, data corruption or even just silently appear to work correctly. ABA bugs such as this can be difficult to debug.
Workarounds
Tagged state reference
A common workaround is to add extra "tag" or "stamp" bits to the quantity being considered. For example, an algorithm using
compare and swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of th ...
on a pointer might use the low bits of the address to indicate how many times the pointer has been successfully modified. Because of this, the next compare-and-swap will fail, even if the addresses are the same, because the tag bits will not match. This is sometimes called ABAʹ since the second A is made slightly different from the first. Such tagged state references are also used in
transactional memory In computer science and engineering, transactional memory attempts to simplify concurrent programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transa ...
. Although a
tagged pointer In computer science, a tagged pointer is a pointer (concretely a memory address) with additional data associated with it, such as an indirection bit or reference count. This additional data is often "folded" into the pointer, meaning stored inline ...
can be used for implementation, a separate tag field is preferred if double-width CAS is available.
If "tag" field wraps around, guarantees against ABA do not stand anymore. However, it has been observed that on currently existing CPUs, and using 60-bit tags, no wraparound is possible as long as the program lifetime (that is, without restarting the program) is limited to 10 years; in addition, it was argued that for practical purposes it is usually sufficient to have 40-48 bits of tag to guarantee against wrapping around. As modern CPUs (in particular, all modern x64 CPUs) tend to support 128-bit CAS operations, this can allow firm guarantees against ABA.
Intermediate nodes
A correct but expensive approach is to use intermediate nodes that are not data elements and thus assure invariants as elements are inserted and removed
alois
Alois (Latinized ''Aloysius'') is an Old Occitan form of the name Louis. Modern variants include ''Aloïs'' (French), ''Aloys'' (German), ''Alois'' (Czech), '' Alojz'' ( Slovak, Slovenian), ''Alojzy'' ( Polish), ''Aloísio'' (Portuguese, Spanish ...
Deferred reclamation
Another approach is to defer reclamation of removed data elements. One way to defer reclamation is to run the algorithm in an environment featuring an
automatic garbage collector; a problem here however is that if the GC is not lock-free, then the overall system is not lock-free, even though the data structure itself is.
Another way to defer reclamation is to use one or more
hazard pointer
In a multithreaded computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a lock-free data structure. These problems generally arise only in environments that don't have a ...
s, which are pointers to locations that otherwise cannot appear in the list. Each hazard pointer represents an intermediate state of an in-progress change; the presence of the pointer assures further synchronization
oug Lea Hazard pointers are lock-free, but can only track at most a fixed number of elements per thread as being in-use.
Yet another way to defer reclamation is to use
read-copy update (RCU), which involves enclosing the update in an RCU read-side critical section and then waiting for an RCU grace period before freeing any removed data elements. Using RCU in this way guarantees that any data element removed cannot reappear until all currently executing operations have completed. RCU is lock-free, but isn't suitable for all workloads.
Alternate instructions
Rather than using a single pointer-wide compare-and-swap instructions,
some processors have other instructions
intended to be more resistant or immune to the ABA problem.
Some architectures provide "larger" atomic operations such that, as example, both forward and backward links in a doubly linked list can be updated atomically; while this feature is architecture-dependent, it, in particular, is available for x86/x64 architectures (x86 allows for 64-bit CAS, and all modern x64 CPUs allow for 128-bit CAS) and IBM's
z/Architecture
z/Architecture, initially and briefly called ESA Modal Extensions (ESAME), is IBM's 64-bit complex instruction set computer (CISC) instruction set architecture, implemented by its mainframe computers. IBM introduced its first z/Architecture-b ...
(which allows for up to 128-bit CAS).
Some architectures provide a
load linked, store conditional instruction in which the store is performed only when there are no other stores of the indicated location. This effectively separates the notion of "storage contains value" from "storage has been changed". Examples include
DEC Alpha
Alpha (original name Alpha AXP) is a 64-bit reduced instruction set computer (RISC) instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). Alpha was designed to replace 32-bit VAX complex instruction set computers ...
,
MIPS,
PowerPC
PowerPC (with the backronym Performance Optimization With Enhanced RISC – Performance Computing, sometimes abbreviated as PPC) is a reduced instruction set computer (RISC) instruction set architecture (ISA) created by the 1991 Apple Inc., App ...
,
RISC-V
RISC-V (pronounced "risk-five" where five refers to the number of generations of RISC architecture that were developed at the University of California, Berkeley since 1981) is an open standard instruction set architecture (ISA) based on estab ...
and
ARM
In human anatomy, the arm refers to the upper limb in common usage, although academically the term specifically means the upper arm between the glenohumeral joint (shoulder joint) and the elbow joint. The distal part of the upper limb between th ...
(v6 and later).
Since these instructions provide atomicity using the address rather than the value, routines using these instructions are immune to the ABA problem.
[
John Goodacre and Andrew N. Sloss]
"Parallelism and the ARM Instruction Set Architecture"
p. 46.
See also
*
Readers–writers problem
In computer science, the readers–writers problems are examples of a common computing problem in concurrency. There are at least three variations of the problems, which deal with situations in which many concurrent threads of execution try to a ...
References
*
*
{{DEFAULTSORT:Aba Problem
Concurrency (computer science)