Overview
ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and the read value being the same twice is used to conclude that nothing has happened in the interim
The problem arises if this new value, which looks exactly like the old value, has a different meaning: for instance, it could be a recycled address, or a wrapped version counter
Lock-Free Data Structures
Workarounds
Tagged State Reference
Add extra âtagâ bits to the value. For example, when using Double-Width CAS 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
Tagged state references are also used in transactional memory
Alternate Instructions
Architectures that support SC are immune to the ABA problem, since the store to the location is performed only when there are no other stores of the indicated location and these instructions provide atomicity using the address rather than the value