How can compare-and-swap be used for a wait-free mutual exclusion for any shared data structure?

Question

Being new to multi-threading and mutexes I was going through the wikipedia for starters. I came across this portion:

CAS can be used to achieve wait-free mutual exclusion for any shared data structure by creating a linked list where each node represents the desired operation to be performed. CAS is then used to change the pointers in the linked list during the insertion of a new node. Only one process can be successful in its CAS; all other processes attempting to add a node at the same time will have to try again. Each process can then keep a local copy of the data structure, and upon traversing the linked list, can perform each operation from the list on its local copy.

Now I understand the basic concept of CAS where we basically use an atomic operation that compares a value to a predetermined value and if it matches we swap them. But I was not able to follow what is the "linked-list of desired operations" mean here? And why would all processes follow the same linked list of operations?

Answer 1

The linked list holds operations on the shared data structure.

For example, if I have a stack, it will be manipulated with pushes and pops. The linked list would be a set of pushes and pops on the pseudo-shared stack. Each thread sharing that stack will actually have a local copy, and to get to the current shared state, it'll walk the linked list of operations, and apply each operation in order to its local copy of the stack. When it reaches the end of the linked list, its local copy holds the current state (though, of course, it's subject to becoming stale at any time).

In the traditional model, you'd have some sort of locks around each push and pop. Each thread would wait to obtain a lock, then do a push or pop, then release the lock.

In this model, each thread has a local snapshot of the stack, which it keeps synchronized with other threads' view of the stack by applying the operations in the linked list. When it wants to manipulate the stack, it doesn't try to manipulate it directly at all. Instead, it simply adds its push or pop operation to the linked list, so all the other threads can/will see that operation and they can all stay in sync. Then, of course, it applies the operations in the linked list, and when (for example) there's a pop it checks which thread asked for the pop. It uses the popped item if and only if it's the thread that requested this particular pop.