Concurrency

The canonical lost update

count = 5;  // two threads each run count++

Thread A                    Thread B                 count
mov eax, [count]   → 5                                    5
                             mov eax, [count]   → 5       5
                             add eax, 1         → 6       5
                             mov [count], eax             6
add eax, 1         → 6   // A's stale copy!          6
mov [count], eax                                          6

Two increments, one result. The interleaving above is one of several; the
bug appears only for some of them, which is why races are intermittent and
why "it works on my machine" is meaningless. Add more cores and the window
gets wider, not narrower.

What a correct solution must guarantee

Any critical-section mechanism has to satisfy all three. Interviewers ask for these by name:

1. Mutual exclusion. At most one thread inside the critical section at a time.
2. Progress. If nobody is inside and someone wants in, one of the waiting threads must get in — no mutual blocking, no deadlock.
3. Bounded waiting. A thread can be overtaken only a bounded number of times before it gets its turn — no starvation.

A fourth, implicit requirement: no assumptions about relative speed. A solution that only works if threads run at similar rates is not a solution.

Why you can't just do it in software

Peterson's algorithm solves it for two threads using only loads and stores, and is worth knowing as proof that it's possible — but it doesn't generalise cleanly to N threads and it breaks under modern memory reordering unless you add barriers. Real implementations use a hardware atomic instruction:

test-and-set    atomically read a word and set it to 1, return the old value
compare-and-swap (CAS)
                atomically: if *addr == expected, store new; return success
fetch-and-add   atomically add and return the previous value

The point is ATOMICITY AT THE HARDWARE LEVEL: the CPU guarantees no other
core can observe or modify the location mid-instruction, by locking the
cache line. Every lock, semaphore, and lock-free structure in existence is
built on one of these three. CAS is the most general — you can build the
others from it.

Semaphore semantics

wait(S)   /  P(S)  /  acquire():
    S--;  if (S < 0) block this thread on S's queue

signal(S) /  V(S)  /  release():
    S++;  if (S <= 0) wake one thread from S's queue

Both operations are atomic — that's the entire contract.
A negative S means |S| threads are waiting.

Initial value tells you what it IS:
  1  → mutual exclusion (lock)
  0  → signalling / rendezvous ("wait for me to finish")
  N  → N interchangeable resources (pool of N connections)

Condition variables, and the rule nobody remembers

mutex_lock(&m);
while (queue_is_empty())        // WHILE, never IF
    cond_wait(&cv, &m);        // atomically unlocks m and sleeps;
                                  // re-locks m before returning
item = dequeue();
mutex_unlock(&m);

Spin or sleep?

Producer–consumer (bounded buffer)

Producers add, consumers remove, the buffer is size N. Producers must block when full, consumers when empty, and the buffer itself needs mutual exclusion.

semaphore empty = N;    // free slots
semaphore full  = 0;    // filled slots
mutex     m;

Producer                       Consumer
wait(empty);   // a slot?       wait(full);    // an item?
  wait(m);                        wait(m);
    buffer[in] = item;              item = buffer[out];
    in = (in+1) % N;                out = (out+1) % N;
  signal(m);                      signal(m);
signal(full);  // +1 item       signal(empty); // +1 slot

Two things to get right, and both are asked:

1. ORDER MATTERS. Acquiring the mutex BEFORE the counting semaphore
   deadlocks: a producer holding m blocks on a full buffer, and the
   consumer that would drain it can never get m. Resource semaphore
   first, then the mutex. Always.

2. The counting semaphores do double duty — they enforce the bound AND
   they are the blocking mechanism. No polling anywhere.

Readers–writers

Many readers may read simultaneously; a writer needs exclusive access. The interesting part is who gets priority, because you cannot have all three of reader concurrency, no reader starvation, and no writer starvation.

// Reader-priority (shows the mechanism; note it starves writers)
int readcount = 0;  mutex rc_mutex;  semaphore rw = 1;

Reader                              Writer
wait(rc_mutex);                       wait(rw);
  readcount++;                          ... write ...
  if (readcount == 1) wait(rw); // 1st  signal(rw);
signal(rc_mutex);                       // simple, and starvable
  ... read ...
wait(rc_mutex);
  readcount--;
  if (readcount == 0) signal(rw); // last one out unlocks
signal(rc_mutex);

The trick: only the FIRST reader acquires rw and only the LAST releases it.
Readers in between just adjust the count.
Real-world note: this is why RWLocks often lose to a plain mutex — the
counter itself is a contended cache line, and under heavy read load the
bookkeeping can cost more than the exclusion you avoided.

Dining philosophers

Five philosophers, five forks between them, each needs both neighbours' forks to eat. If all five simultaneously pick up their left fork, all five hold one fork and wait forever for the right. That's a textbook circular wait — and the four standard fixes map exactly onto the four ways to break deadlock:

The four necessary conditions (Coffman)

All four must hold simultaneously. Break any one and deadlock is impossible — which is exactly how every prevention strategy works.

The four strategies

Banker's algorithm, worked

Avoidance: before granting a request, check whether some ordering of the remaining processes could all finish. If yes the state is safe; if not, make the requester wait even though the resource is free.

Total resources:  A=10  B=5  C=7

        Allocated      Max         Need = Max − Allocated
        A  B  C      A  B  C          A  B  C
P0      0  1  0      7  5  3          7  4  3
P1      2  0  0      3  2  2          1  2  2
P2      3  0  2      9  0  2          6  0  0
P3      2  1  1      2  2  2          0  1  1
P4      0  0  2      4  3  3          4  3  1
       ---------
sum     7  2  5   →  Available = (10,5,7) − (7,2,5) = (3,3,2)

Find a safe sequence:
Available (3,3,2)
  P0 needs (7,4,3) → 7>3, can't run yet
  P1 needs (1,2,2) → fits! run P1, it finishes and frees its allocation
                     Available = (3,3,2) + (2,0,0) = (5,3,2)
  P3 needs (0,1,1) → fits! Available = (5,3,2) + (2,1,1) = (7,4,3)
  P0 needs (7,4,3) → fits exactly! Available = (7,4,3) + (0,1,0) = (7,5,3)
  P2 needs (6,0,0) → fits! Available = (7,5,3) + (3,0,2) = (10,5,5)
  P4 needs (4,3,1) → fits! Available = (10,5,5) + (0,0,2) = (10,5,7)

SAFE. Sequence: P1 → P3 → P0 → P2 → P4

Now: P1 requests (1,0,2). Grant it tentatively —
     Available becomes (2,3,0), P1's Need becomes (0,2,0).
     Re-run the safety check: P1 needs (0,2,0), Available (2,3,0) → fits.
     Still safe, so the request is GRANTED.

Why nobody uses this: it needs each process's MAXIMUM future demand up
front, it assumes a fixed resource count, and it is O(n²m) per request.
Know it because it is examined; say why it isn't used because that is
what distinguishes understanding from memorisation.

Compare-and-swap and the retry loop

// Atomic increment without any lock
do {
    old = counter;                       // read
    new = old + 1;                       // compute
} while (!CAS(&counter, old, new));  // swap only if unchanged

If another thread changed counter in between, CAS fails and we retry with
the fresh value. No update is ever lost.

The guarantees you can offer, weakest to strongest:
  BLOCKING     a stalled thread can block others indefinitely (locks)
  LOCK-FREE    at least one thread makes progress system-wide
               (a single thread might retry forever — that's allowed)
  WAIT-FREE    EVERY thread completes in a bounded number of steps
               (strongest, rarest, usually needs fetch-and-add not CAS)

Cost: under heavy contention the CAS loop wastes work — many threads spin,
one wins. A well-implemented lock can beat lock-free code when contention
is high, because the losers sleep instead of burning cycles.

Memory ordering — why your code isn't what runs

Compilers reorder instructions; CPUs execute out of order and buffer stores. Both preserve single-threaded semantics and neither preserves what another thread observes. So this famously fails:

Thread A              Thread B
data = 42;             while (!ready) ;
ready = true;          print(data);   // may print 0!

B can observe ready==true before it observes data==42, because the two
stores may become visible in either order. Nothing is "wrong" —
neither thread violated its own sequential semantics.

Orderings, weakest to strongest:
  relaxed              atomicity only, no ordering. Fine for counters.
  acquire / release    release-store publishes everything before it;
                       acquire-load sees everything the releaser published.
                       This pairing is what you almost always want.
  seq_cst              a single total order all threads agree on.
                       Default in C++/Java/Rust. Safest, slowest.

This is why volatile in C/C++ does not make code thread-safe — it prevents compiler caching in a register but emits no memory barriers and provides no atomicity. (Java's volatile is different: it does imply ordering.) It's also why the classic double-checked locking singleton was broken for years: another thread could see a non-null pointer to a partially-constructed object.

Priority inversion

Low-priority task L takes a lock.
High-priority task H needs it and blocks.
Medium-priority task M — needing nothing — preempts L.
  → H waits on L, L waits on M, M runs freely.
  → A high-priority task is effectively blocked by a MEDIUM one.

Fixes:
  priority inheritance  L is temporarily boosted to H's priority while
                        it holds a lock H wants. (Needs OWNERSHIP —
                        which is why mutexes can do it and semaphores can't.)
  priority ceiling      any lock holder immediately runs at the highest
                        priority of any task that could take that lock.

This is not academic: it nearly lost the Mars Pathfinder mission in 1997.
The rover kept resetting because a high-priority bus task was blocked by a
low-priority meteorological task through a shared mutex, and the watchdog
fired. NASA fixed it by enabling priority inheritance — remotely.