sdlc.dev

Computer science fundamentals for working engineers path · Running programs · Topic 8 of 13

Concurrency: races, locks, deadlock and atomics

Not started

Concurrency means more than one sequence of work is in progress at once: threads on several cores, or tasks taking turns on one thread, as in JavaScript. The result is only well defined if every possible interleaving of their steps is acceptable. A **race condition** is a case where some interleavings give a wrong answer. Races are hard to find because the bad interleaving may happen once in a million runs, and adding a log line can make it disappear.

Why it matters: Lost updates, double bookings, counters that drift and services that freeze under load all come from shared state touched by more than one thread or task.

  1. 1A race needs three things

    Shared data, at least one writer, and no ordering between the accesses. Remove any one and the race is gone.

  2. 2Read-modify-write is not one step

    x = x + 1 reads, adds and writes. Another thread or task can run in between, and one update is lost.

  3. 3Locks make sections exclusive

    A mutex lets one thread at a time into a critical section. Hold it briefly, and never across slow I/O if you can avoid it.

  4. 4Deadlock needs four conditions

    Mutual exclusion, hold and wait, no preemption, and a circular wait. Taking locks in one global order breaks the circle.

1

How it works

The explanation, with examples you can run.

JavaScript runs one piece of code at a time, but an await is a point where other tasks can run. That is enough for a lost update. In the lesson below, two withdrawals each read the balance, pause (as a database call would), then write their result.

2

Watch it run

Play it or step through. Every step says what just happened.

let balance = 100;const pause = () => new Promise(resolve => setTimeout(resolve, 0));async function withdraw(amount) {  const seen = balance;  await pause();  balance = seen - amount;}Promise.all([withdraw(30), withdraw(50)]).then(() => console.log(balance));

Task A: withdraw(30)

What A has read or written

empty

Task B: withdraw(50)

What B has read or written

empty

Shared balance

empty

Timer queue

Paused tasks waiting to resume

empty

Console0 lines

    Step 0 of 8

    Nothing has run yet. Two withdrawals of 30 and 50 should leave 20.

    Real threads can interleave between any two machine instructions, not only at await, so the same bug is even easier to hit.

    3

    Try it yourself

    Change the code, predict the order, then run it for real in your browser.

    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    4

    Check yourself

    3 questions. Get them all right to finish this topic.

    1. 1.In the trace, two withdrawals of 30 and 50 from 100 leave a balance of 50. Which change fixes it without a lock?
    2. 2.Thread 1 holds lock A and waits for lock B. Thread 2 holds lock B and waits for lock A. What is the standard prevention?
    3. 3.What does an atomic compare-and-swap (CAS) do?

    0 of 3 right so far. Get all three to finish this topic.

    Fixing it

    There are three families of fixes, in every language:

    1. Don't share. Give each piece of state one owner, and send it messages (actors, channels, a single-writer queue).
    2. Make the critical section exclusive. A lock (mutex) lets only one thread at a time run the read-modify-write. In JavaScript, the simplest fix here is to remove the await between read and write: balance -= amount runs in one uninterrupted step. Across processes or machines, the database does this for you with a transaction, SELECT … FOR UPDATE, or a conditional UPDATE … WHERE balance >= 30.
    3. Use an atomic operation. CPUs provide instructions that read, modify and write a memory location in one indivisible step: atomic add, exchange and compare-and-swap (CAS). Java's AtomicLong, C#'s Interlocked, Go's sync/atomic and JavaScript's Atomics on a SharedArrayBuffer expose them.
    ⌘/Ctrl + Enter
    OutputNot run yet

    Press Run to see what your code prints, in order.

    Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

    This prints 20: the second withdrawal can't start its read until the first has written.

    Deadlock

    Locks bring their own failure. Coffman and colleagues showed in 1971 that deadlock requires four conditions at once: mutual exclusion (a resource can be held by one party), hold and wait (a party holds one resource while waiting for another), no preemption (nobody can take a resource away), and circular wait (A waits for B, which waits for A). Break any one and deadlock can't happen. In practice: acquire locks in one global order, hold as few as possible for as short as possible, use timeouts, and never call unknown code (callbacks, I/O) while holding a lock.

    Go deeper