Workarounds
Going back to the previous example of Charlie and his briefcase, what could Charlie have done differently?
There are a number of ways that Charlie could have prevented this from happening, even though he can't open the briefcase. For one, he could've chained the real briefcase to the seat. That way, Albert would have to cut the chain to steal the briefcase, and Charlie would notice the cut chain and sound the alarm. This is what the LL/SC instruction on some processors attempts to do. Another solution would be for Charlie to write down the serial number of his real briefcase, and check it after every time he looks away from it. This is how Double-Word Compare-And-Swap Tagging works. Automatic Garbage Collection, 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. When Charlie, his boss, and whoever else cares about the briefcase don't need it anymore, it is destroyed. Then, and only then, is another briefcase that looks like his allowed to be created.
Below are examples of code mechanisms that implement the ideas above.
A common workaround is to add extra "tag" bits to the quantity being considered. For example, an algorithm using compare and swap 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 does not completely solve the problem, as the tag bits will eventually wrap around, but helps to avoid it. Some architectures provide a double-word compare and swap, which allows for a larger tag. This is sometimes called ABAŹ¹ since the second A is made slightly different from the first.
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 .
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. Another way to defer reclamation is to use one or more hazard pointers, 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 . 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.
Some architectures provide "larger" atomic operations such that, as example, both forward and backward links in a doubly linked list can be updated atomically.
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, MIPS, PowerPC and ARM (v6 and later). However no practical implementations of load linked will directly solve the ABA problem.
Read more about this topic: ABA Problem