The talk has several purposes:
- Introducing MESI cache coherence;
- Showing that lock-free algorithms aren't automatically faster than lock-based ones;
- Explaining why this happens (due to cache coherence dynamics);
- Introducing the idea of using non-failing atomic primitives instead of CAS as a way of speeding up lock-free algorithms.
The above goals are achieved by discussing the problem of designing a concurrent FIFO queue, starting from a simple lock-based algorithm, through a lock-free algorithm (that performs poorly), to the LCRQ algorithm, which is based on fetch-and-add (a non-failing primitive).
Download presentation