Lockfree

tags : Concurrency

Resources §

• An Introduction to Lock-Free Programming
• 1024cores - Introduction
• CppCon 2014: Herb Sutter “Lock-Free Programming (or, Juggling Razor Blades)
• CppCon 2017: Fedor Pikus “C++ atomics, from basic to advanced.""

FAQ §

What is Non-blocking algorithm? §

An algorithm is non-blocking if the delay of some threads cannot delay other threads indefinitely

What is Lockless? §

	Lock less	Lock based
Blocking	X	Mutexes and Friends
Non-blocking	Atomics and friends	X

• I don’t know what is lockless. It’s a confusing term. I’ll not use this term.
• Locking is how you implement for blocking
• Atomicity is how you implement non-blocking

Why Non-blocking algorithms? §

• You usually don’t need non-blocking algorithms. Locking/blocking algorithms are just fine for most cases.
• What non-blocking algorithms primarily offer is varying range of forward progress guarantees.
• As a side effect of it, there might be some performance gains. In general lockfree algorithms are slower than analogous algorithms not burdened with forward progress guarantees
• So, you want to look at Non-blocking algorithms if your system requires the forward progress gurantees these algorithms provide.

Termination safety/Forward progress guarantees of Non-blocking algorithms §

• wait-free, loсk-free etc. are theoretical properties that consider kind of corner cases.

// forward progress gurantees
|<-less gurantee--------------------------------more gurantee->|
lock based algorithms < obstruction-free < lock-free < wait-free
|------blocking-------|-------------- non-blocking ------------|

Wait-free §

• Guaranteed per-thread progress (strongest guarantee)
• No computation can ever be blocked by another computation
• Hard to implement

Lock-free §

• Guaranteed system-wide progress
• Some thread can be blocked by other thread but CPU can continue doing other useful work without stalls

Obstruction-free §

• Thread makes forward progress only if it does not encounter contention from other threads
• Does not block other threads
• Livelock is possible

Primitives §

Atomics §

• Atomic operations are ones which manipulate memory in a way that appears indivisible: No thread can observe the operation half-complete.
• Different primitives allow different levels of forward progress gurantees.
  • Eg. CAS can’t be used to implement wait-free but can be used to implement lock-free.

Read-modify-write (RMW) §

• Compare-And-Swap Loops (CAS)

  It guarantees that: no other thread wrote to the memory location in between the "compare" and the "swap"

  • Its more of an idea of an operation. Different systems implement it differently.

  • How it’s actually implemented

    • CPU architectures

      • always-succeed
        • Some architectures simply lock that memory location (or cache line) during the operation so that other writes are impossible.
      • might-fail
        • On other architectures (so-called LL/SC), the core doing the CAS may simply monitor the memory location, and if another write occurs at the wrong time, the CAS will not do its write and indicate failure instead.

    • OS/Libraries

      • In some cases the mutex(in OS/lang library) is probably implemented using a CAS or similar atomic operation
      • Linux: Lockless patterns: an introduction to compare-and-swap [LWN.net]​
      • single-core
        • Usually, single-core systems where atomicity is not a concern
          • The language’s CAS function may be implemented in a simpler and cheaper way without needing such special instructions.
        • single-core systems still need atomicity with respect to interrupts. CAS SHOULD BE an uninterruptible operation and single core CPUs perform virtualized parallelization (context switches)

    • Object stores/other system

      • These apply the idea of CAS using whatever underlying premitive is available, we just need to ensure the atomicity gurantee that CAS provides
      • See Object Store (eg. S3) Consistency in object stores can be provided via CAS

  • Resources

    • See ABA problem - Wikiwand

• fetch-and-add (FAA)

Load and Stores (LAS) §

• load-and-store vs compare-and-swap : Lockless patterns: an introduction to compare-and-swap [LWN.net]​