TRT
Sign in

Expert · Module 25

Concurrent data structures

Share structures between threads safely: locks, atomics and lock-free designs.

Start the modulePro5 lessons · about 70 minutes

Locks are the default answer to sharing data between threads, and this module takes them apart before it builds the alternatives: what a data race actually is and what a mutex promises to do about it, how atomics and compare-and-swap exchange exclusion for detection, a lock-free stack and then a queue, and the ABA problem that appears the moment a pointer stops telling you when it was written. It ends with the bill that comes with all of it: a node can be removed while another thread is still reading it, so reclamation schemes decide when a free is safe. By the end you should be able to read a concurrent structure and say where its ordering assumptions live, what its worst case costs, and which guarantee it does not give you.

  1. 1Data races and locksPro — members onlyTwo threads incrementing one counter can both be correct line by line and still lose updates. This lesson defines a data race, shows what a mutex fixes, and prices the lock: fast path, futex slow path, contention, convoying and spinlocks.13 min
  2. 2Atomics and compare-and-swapPro — members onlyAtomic loads, stores and read-modify-write operations let two threads update one value without a lock. This lesson traces a CAS loop whose swap fails and retries, and picks the weakest memory ordering that is still correct.14 min
  3. 3A lock-free stackPro — members onlyThe Treiber stack links a node's next field and then CASes the head, for both push and pop. This lesson verifies every pointer through both operations, shows why the classic pop turns unsafe once a node can be freed, and states the progress guarantees exactly.14 min
  4. 4Lock-free queues and the ABA problemPro — members onlyA queue has two live ends, so it needs a dummy node, two CASes per operation and a rule for finishing work another thread left half-done. Then the ABA problem: a CAS that compares values can succeed on a node that left and came back.15 min
  5. 5Memory reclamationPro — members onlyA lock-free structure can outlive the thread that is reading it: another thread removes a node while the reader is descheduled, and freeing it then is a use-after-free. Hazard pointers, epochs, RCU and garbage collection each answer when a free is safe.14 min