It is a common use case to read a data element, execute some logic, and update with a new value. For single-threaded programs, it bears no consequences, but for concurrent scenarios, the entire operation must be carried out in a lockstep as an atomic operation. This case is so common that many processors support this at the hardware level using a special Compare-and-swap (CAS) instruction, which is much cheaper than locking. On x86/x64 architectures, the instruction is called
CompareExchange (CMPXCHG
).
Unfortunately, it is possible that another thread updates the variable with the same value that the thread working on the atomic update is going to compare the old value against. This is known as the ABA problem. The set of instructions load-linked (LL) and store-conditional (SC), which are found in some other architectures, provide an alternative to CAS without the ABA problem. After the LL instruction reads the value from an address, the SC instruction to update...