CSE Roadmap

Level 4 of 12 · about 3 weeks

Concurrency and synchronisation

How threads share data safely: the critical-section problem, atomic instructions, mutexes, condition variables, semaphores, the classic problems and the tools that find bugs.

Modules

Core: everyone needs it. Common: most jobs use it. Specialist: optional depth, safe to skip on a first read.

  1. 1

    The critical-section problem

    What mutual exclusion must guarantee, why simple attempts fail, and why even a correct algorithm needs hardware care

    Core 7 parts · about 5 hours

  2. 2

    Atomic instructions and spinlocks

    The hardware step that makes locks possible, the simplest locks built from it, and what they cost

    Core 7 parts · about 5 hours

  3. 3

    Mutexes and futexes

    The lock that puts waiters to sleep, how Linux builds it, and the rules for using it well

    Core 7 parts · about 5 hours

  4. 4

    Condition variables and monitors

    Waiting until something becomes true, without polling, and the pattern that makes it safe

    Core 7 parts · about 5 hours

  5. 5

    Semaphores

    A counter that makes threads wait, for exclusion, for limited resources and for ordering

    Core 7 parts · about 5 hours

  6. 6

    Producer-consumer and the bounded buffer

    The most common coordination pattern, solved with semaphores and with condition variables, and tested

    Core 7 parts · about 6 hours

  7. 7

    Readers-writers and dining philosophers

    Two classic problems that show how to share data among readers, and how to avoid a deadlock over several locks

    Core 7 parts · about 5 hours

  8. 8

    Concurrency bugs and the tools that find them

    Atomicity and order violations, data races and the compiler, and ThreadSanitizer and Helgrind in use

    Core 7 parts · about 5 hours

  9. 9

    Case study, a scalable counter and a hash table

    Making shared data structures fast with threads, measured step by step

    Core 7 parts · about 6 hours