The core logic of lockless programming is the CAS operation brought by processor. CAS can compare and exchange value between two number in a single instruction. From the perspective of CPU synchronization primitive, CAS instruction like “cmpxchg” is expensive. but from the view of application programmer, the lockfree data structure is really attractive for its free user from using more expensive operation system “mutex locks” which will switch the worker thread from background back and forth.
LockFree data-structure always comes with ABA problem, according herb sutter. for example, We need to resolve the deletion issue: we can’t delete a node if a concurrent reader/writer might be pointing to it.
there are 4 options to solve the problem:
- Option1: Use lazy garbage collection. solve the problem because memory cannot be reused while any pointers to it exist, However, destruction of nodes becomes nondeterministic.
- Option2: Use reference counting ( garbage collection). solve the problem in cases without cycles.
- Option3: Never actually delete a node ( only logically delete) , can work when deleting is rare.
- Option4: Put auxiliary nodes in between actual nodes. Contains a next pointer only, no data. These links don’t move. Enables operations on adjacent nodes to run without interference.