Editing Compare-and-swap (section)

===ABA problem===
{{main|ABA problem}}
Some CAS-based algorithms are affected by and must handle the problem of a [[Type I error#False negative vs. false positive|false positive]] match, or the [[ABA problem]]. It is possible that between the time the old value is read and the time CAS is attempted, some other processors or threads change the memory location two or more times such that it acquires a bit pattern which matches the old value. 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.

A general solution to this is to use a double-length CAS (DCAS). E.g., on a 32-bit system, a 64-bit CAS can be used. The second half is used to hold a counter.  The compare part of the operation compares the previously read value of the pointer ''and'' the counter, with the current pointer and counter.  If they match, the swap occurs - the new value is written - but the new value has an incremented 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<sup>32</sup> operations would have to have occurred, causing the counter to wrap and at that moment, the pointer value would have to also by chance be the same).

An alternative form of this (useful on CPUs which lack DCAS) is to use an index into a freelist, rather than a full pointer, e.g. with a 32-bit CAS, use a 16-bit index and a 16-bit counter.  However, the reduced counter lengths begin to make ABA possible at modern CPU speeds.

One simple technique which helps alleviate this problem is to store an ABA counter in each data structure element, rather than using a single ABA counter for the whole data structure.

A more complicated but more effective solution is to implement safe memory reclamation (SMR).  This is in effect lock-free garbage collection.  The advantage of using SMR is the assurance a given pointer will exist only once at any one time in the data structure, thus the ABA problem is completely solved.  (Without SMR, something like a freelist will be in use, to ensure that all data elements can be accessed safely (no memory access violations) even when they are no longer present in the data structure.  With SMR, only elements actually currently in the data structure will be accessed).