Implementation of a wait-free simulation for a lock-free algorithm as described in the paper - A Practical Wait-Free Simulation for Lock-Free Data Structures.
- Normalized Lock Free Form
- Wait-free queue
- Contention Measure
- Cas Descriptor
- Wait-Free simulator
This section maybe a little convoluted. It is a WIP.
Say, the head of a linked list points to a node A
head -> A (@0x1)
We now want to insert node B.
insert B (@0x2); B.next = 0x1
We do this using a compare_and_swap primitive.
CAS(head, 0x1, 0x2) -> Succeed if A is still at the head -> fail if A is no longer at the head (maybe due to the insertion from another thread), because B.next would need to be different.
However, there is a possibilty of a problem.
Imagine someone else meanwhile
insert C (@0x3); C.next = 0x1
CAS(head, 0x1, 0x3)
Now lets imagine someone removes A
remove A
CAS(C.next, 0x1, 0x0)
Now if someone inserts a node D
insert D (@0x1); and D.next = 0x3
C is at the head
CAS(head, 0x3, 0x1)
So the final LL
head -> D -> C -> .
and now ...
insert of B continues.
CAS(head, 0x1, 0x2) -> this CAS should have failed ideally
head -> B -> A(@0x1) actually D(@0x1) -> C(@0x3)
Even though the last CAS happened to succeed since the values were same, but the thing we are pointing aren't really the same.
This is known as the ABA problem.