Load Linked Store Conditional

There are 2 best known ways to create lock free thread safe data structures:

1. LL/SC (Load Linked/Store Conditional)
2. CAS (Compare And Swap)

A lock-free thread-safe data-structure is a data structure that can be used multithreaded environments (hence thread-safe) that uses no locks (or uses very small locks, like CAS and LL/SC, hence lock-free).

LL/SC is a techinique that uses 2 instructions: LL and SC. LL sets a value and has a "counter" that is used for the thread to remember who did the change, so that when SC is used to set that value again (over the same memory location), if the value has changed in the mean time (by another thread typically), the "counter" would not be the same and the operation would fail (hence "condition").

It works the following way. First a copy of the data structure is made and the old pointer value is marked "reserved for update" using LL. Once the whole lock-free algorithm finishes, it is time to set the pointer value to its new location using SC. As you can imagine this means both LL and SC must be atomic (they are usually atomic and implemented as single CPU instructions).

In the case of CAS, there is only one CPU instruction called conveniently CAS, receiving 2 parameters to be exchanged atomically.

CAS can be implemented using LL/SC and LL/SC can be implemented using CAS.

The whole idea of lock-free synchronization is that critical sections can be reduced so much that the whole algorithm may execute in parallel. The only disadvantage is that the thread needs to copy the part of the data structure that is being modified, and that the algorithm must be prepared for failure (in case that some thread modified the same data before it did). Since modifying a pointer can be done atomically, magically we have several threads doing its magic at the same time.