ABA Problem

In multithreaded computing, 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 in to 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 memory interleave. Below is the sequence of events that will result in the ABA problem:

  • Process reads value A from shared memory,
  • is preempted, allowing process to run,
  • modifies the shared memory value A to value B and back to A before preemption,
  • begins execution again, sees 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 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 optimization. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem.

Read more about ABA Problem:  Examples, Workarounds

Other articles related to "aba problem, problem, aba":

ABA Problem - Workarounds
... along with other techniques like Hazard Pointers, deal with this problem by ensuring that there is no other briefcase in the world that looks like Charlie's briefcase ... This does not completely solve the problem, as the tag bits will eventually wrap around, but helps to avoid it ... This is sometimes called ABAสน since the second A is made slightly different from the first ...
Compare-and-swap - Usage - ABA Problem
... these algorithms are affected by and must handle the problem of a false positive match, or the ABA problem ... The problem arises if this new bit pattern, which looks exactly like the old value, has a different meaning for instance, it could be a recycled address, or a wrapped version counter ... This means that if ABA has occurred, although the pointer value will be the same, the counter is exceedingly unlikely to be the same (for a 32 bit value, a multiple of 2^32 ...

Famous quotes containing the word problem:

    Any solution to a problem changes the problem.
    —R.W. (Richard William)