Concurrency questions in coding rounds

A concurrency question in a coding round asks for code that stays correct while several threads or tasks run at the same time. Four tasks come up again and again: make threads take turns in a fixed order, pass work through a bounded buffer, make a shared structure such as a counter or a cache safe to use from many threads, and run many tasks with at most k running at once. Whichever task you get, the interviewer is checking whether you can see three failures coming. In a race, the steps of two threads interleave and an update is lost. In a deadlock, each thread waits for something another one holds. In starvation, one thread keeps losing its turn while the rest go ahead. This lesson reproduces each failure in a program that runs, shows Go’s race detector catching one, and sorts out where threads can run at all: the Python in your browser cannot start a thread, but asyncio runs there, and the same three failures happen with async tasks.

The four kinds of task

Each of the four tasks has a small piece of shared state, and all of the difficulty lies in keeping one rule about it true while threads interleave.

• Threads in a fixed order. Three workers start in any order, and their log lines must still come out as connect, load, serve; or two threads take turns printing the next number of a shared sequence. What is shared is whose turn it is, and the usual tool is one signal per hand-off: a semaphore, an event, a condition variable, or a channel in Go.
• A bounded buffer. Producers add jobs to a queue that holds at most k jobs, and consumers take them out. Producers wait while it is full, consumers while it is empty, and everything stops cleanly at the end. What is shared is the queue and its count, kept with a lock and two condition variables, or in a ready-made blocking queue such as queue.Queue(maxsize), ArrayBlockingQueue or a buffered channel.
• A thread-safe structure. Make this counter, cache or rate limiter safe when many threads call it. What is shared is the structure’s fields: start with one lock around every operation, use an atomic for a lone counter, and reach for finer locks only once a measurement asks for them.
• Limited parallelism. Run n tasks with at most k running at once, and return the results in input order. What is shared is the index of the next task and the free slots, handed out by a semaphore with k permits or by k workers that take tasks from one queue; in JavaScript, by a pool of k promises.

The rest of this module takes the tasks one at a time: running tasks with a limit, bounded buffers and threads that take turns, then safe counters, caches and aggregation.

The code for any of them fits on one screen, and the reasoning is what the interviewer is listening to. Whatever the task, a strong answer does four things:

1. It states the rule the shared state must keep: “no more seats are sold than the show has”, “the queue never holds more than k jobs”.
2. It picks the smallest tool that keeps the rule, and says why: a lock for a few lines that must not interleave, a condition variable or a channel when a thread must wait for something, an atomic for a lone counter.
3. It walks through one bad interleaving aloud, before the fix and after it: “thread A reads 41, then thread B reads 41, then…”.
4. It says how to test the code: run it under a race detector, repeat it many times under load, and give every wait a time limit, so that a hang turns into a failure you can see.

Three ways concurrent code goes wrong

Races: two increments, one lost

counter += 1 looks like one step, but it is three: read the counter, add one, write the result back. The addition happens inside the thread, so another thread can step in only between the read and the write, and that is enough. If threads A and B both read 41 before either of them writes, both write 42, and one of the two increments is gone. This is a lost update.

How likely is that? This program tries every order in which the threads’ reads and writes can run, and counts how each order ends. It is the brute force of concurrency: instead of hoping that a test happens to hit the bad order, it runs all of them.

"""Every order in which threads can run the steps of counter += 1, tried and counted.

counter += 1 is a read of counter, then a write of the value read plus one. The
addition happens inside the thread, so only the reads and the writes can interleave
with the other threads' steps.
"""
from collections import Counter


def orders(threads):
    """Every interleaving of the threads' steps that keeps each thread's own order."""
    if not any(threads):
        yield []
        return
    for i, steps in enumerate(threads):
        if steps:
            rest = threads[:i] + [steps[1:]] + threads[i + 1:]
            for tail in orders(rest):
                yield [steps[0]] + tail


def run(order):
    """Runs one interleaving from counter = 0 and returns the final counter."""
    counter = 0
    seen = {}                        # what each thread read last
    for thread, step in order:
        if step == "read":
            seen[thread] = counter
        elif step == "write":        # stores what it read, plus one
            counter = seen[thread] + 1
        else:                        # "add": a read and a write that nothing can split
            counter += 1
    return counter


def report(n_threads, increments, steps=("read", "write")):
    names = "ABC"[:n_threads]
    threads = [[(name, step) for _ in range(increments) for step in steps] for name in names]
    finals = Counter(run(order) for order in orders(threads))
    total, right = sum(finals.values()), n_threads * increments
    spread = ", ".join(f"{value} in {finals[value]}" for value in sorted(finals))
    print(f"{n_threads} threads x {increments} increment(s), {'+'.join(steps)}: {total} orders; "
          f"final counter {spread}; right in {finals[right]} of {total}")


report(2, 1)
report(2, 2)
report(3, 1)
report(2, 2, steps=("add",))

losing = [("A", "read"), ("B", "read"), ("A", "write"), ("B", "write")]
steps_shown = ", ".join(f"{thread} {step}s" for thread, step in losing)
print("one losing order:", steps_shown, "->", run(losing))

2 threads x 1 increment(s), read+write: 6 orders; final counter 1 in 4, 2 in 2; right in 2 of 6
2 threads x 2 increment(s), read+write: 70 orders; final counter 2 in 32, 3 in 32, 4 in 6; right in 6 of 70
3 threads x 1 increment(s), read+write: 90 orders; final counter 1 in 48, 2 in 36, 3 in 6; right in 6 of 90
2 threads x 2 increment(s), add: 6 orders; final counter 4 in 6; right in 6 of 6
one losing order: A reads, B reads, A writes, B writes -> 1

Two threads with one increment each have 6 possible orders, and 4 of them lose an update. With two increments each, only 6 of the 70 orders give the right total of 4, and 32 of them end at 2, as if half the work never happened. Three threads with one increment each are right in 6 orders out of 90. The fourth line shows the way out: when the read and the write are one step that nothing can split, as with an atomic add or a lock held around both, every order gives the right total.

Two terms for this are often mixed up, and keeping them apart is part of a good answer:

• A data race is two accesses to the same memory from different threads, at least one of them a write, with nothing in the program that orders one before the other. That is how the Go memory model defines it, and the C++ standard says that any data race results in undefined behaviour.
• A race condition is any bug in which the result depends on how threads or tasks happen to interleave. Every data race can cause one, but a race condition needs no data race at all. Suppose a booking reads the number of free seats while it holds a lock, releases the lock, and then sells the seats under the lock again. Every access is protected, and seats are still oversold, because another booking can run between the two locked steps.

The difference matters when you choose a tool: race detectors find data races, not race conditions in general.

Deadlocks: everyone waits

A deadlock is a group of threads in which each one waits for something that only another member of the group can give, so that none of them ever moves again. The classic case is two locks taken in opposite orders. A transfer from account A to account B locks A and then B, a transfer from B to A locks B and then A, and if each takes its first lock before the other takes its second, both wait forever. Coffman, Elphick and Shoshani’s survey of deadlocks named the four conditions that must all hold for one to happen:

• Mutual exclusion: a resource, such as a lock, is held by one thread at a time.
• Hold and wait: a thread keeps what it holds while it waits for more.
• No preemption: nothing takes a resource away from the thread that holds it.
• Circular wait: there is a cycle of threads, each waiting for a resource that the next one holds.

Remove any one of them and the deadlock cannot happen. In code, the usual ways are one fixed order in which every thread takes its locks, so that no cycle can form; taking all the locks a step needs in a single call, which C++’s std::scoped_lock does with a deadlock-avoidance algorithm; and a time limit on every wait, which turns a silent hang into an error you can handle. A thread can even deadlock on its own. Python’s threading.Lock blocks every further attempt to acquire it until it is released, attempts by the thread that holds it included, while a threading.RLock lets its holder acquire it again.

Starvation: always someone else’s turn

Starvation happens when a thread is ready to run and could run, but keeps losing its turn to others for as long as they keep coming. Unlike a deadlock, the program as a whole makes progress, which is why starvation hides from tests: the totals come out right, and one kind of work simply never happens. The usual causes are a lock that makes no promise about who goes next, readers that keep a writer out (one of the quiz snippets below), and, with async tasks, a task that never reaches an await. Locks differ in what they promise about the order of waiters:

• Python’s threading.Lock promises nothing: when several threads wait, its documentation says that which one proceeds is not defined and may vary between implementations.
• Java’s ReentrantLock takes a fairness flag. Created with true, it favours the thread that has waited longest, which its documentation says guarantees lack of starvation, at the price of lower throughput.
• asyncio.Lock is fair: the first task that started waiting is the next one to get the lock.

A close relative is livelock: the threads keep running and reacting to each other, for instance by backing off and retrying in step, but none of them gets anywhere.

A lost update in Go, caught by the race detector

Go makes the failure easy to see, because goroutines can run in parallel on every core. Four goroutines each add 1 to a shared counter a million times:

// Four goroutines each add 1 to a shared counter a million times, with nothing to
// coordinate them.
package main

import (
	"fmt"
	"sync"
)

func main() {
	const workers, rounds = 4, 1_000_000
	for run := 1; run <= 5; run++ {
		counter := 0
		var wg sync.WaitGroup
		for range workers {
			wg.Go(func() { // Go 1.25+: starts a goroutine that wg.Wait() waits for
				for range rounds {
					counter++ // a read, an add and a write: others can step in between
				}
			})
		}
		wg.Wait()
		total := workers * rounds
		fmt.Printf("run %d: %d of %d, lost %d\n", run, counter, total, total-counter)
	}
}

from session import session

session(("go build -trimpath -o lost lost.go && ./lost", 0))

# go version go1.27.1 darwin/arm64
$ go build -trimpath -o lost lost.go && ./lost
run 1: 1554342 of 4000000, lost 2445658
run 2: 1495411 of 4000000, lost 2504589
run 3: 1313926 of 4000000, lost 2686074
run 4: 1385874 of 4000000, lost 2614126
run 5: 1840501 of 4000000, lost 2159499

"""Builds and runs the Go programs of this folder as you would in a terminal, and
prints the whole session.

Each command is printed after "$ ", followed by everything it printed (standard output
and standard error together, in the order a terminal shows them) and, when it exits
with a status other than 0, "[exit status N]". Every command states the status it
should end with: the race detector ends a program with status 66 when it found a race.
A command that ends any other way stops the session with status 1.

The Go is 1.27.1, from the installation beside the Python that runs this file; the
programs use no network.
"""

import os
import subprocess
import sys
from pathlib import Path

# .../installs/python/3.14.8/bin/python3 -> .../installs/go/1.27.1/bin
GO_BIN = Path(sys.executable).resolve().parents[3] / "go" / "1.27.1" / "bin"


def _shell(command):
    env = dict(os.environ)
    env["PATH"] = os.pathsep.join([str(GO_BIN), env.get("PATH", "")])
    env["GOTOOLCHAIN"] = "local"   # never download another Go
    env["GOTELEMETRY"] = "off"
    return subprocess.run(command, shell=True, env=env, text=True,
                          stdout=subprocess.PIPE, stderr=subprocess.STDOUT)


def session(*steps):
    """Runs (command, expected exit status) pairs and prints them as a terminal would."""
    version = _shell("go version")
    if version.returncode != 0:
        sys.exit("go version did not run: Go 1.27.1 is missing")
    print("#", version.stdout.strip())
    for command, expected in steps:
        print(f"$ {command}")
        done = _shell(command)
        print(done.stdout, end="")
        if done.returncode != 0:
            print(f"[exit status {done.returncode}]")
        if done.returncode != expected:
            sys.exit(f"{command} ended with status {done.returncode}, not {expected}")

Every run lost more than 100,000 of its 4,000,000 increments, and the shortfall changes from one run to the next. A test that checks the total catches a race this loud, but most races are quiet: they lose one update in a million calls, and only under load.

That is what Go’s race detector is for. Build or run a program with -race, and it watches the program’s memory accesses while it runs and reports any two that conflict with nothing to order them. The next program has the race in its quietest form: a sleep keeps the two increments 100 milliseconds apart, so no update is lost and the total is right.

// Two goroutines each add 1 to a shared counter. A sleep keeps them apart in time,
// so no update is lost in this run, but nothing in the program orders the increments.
package main

import (
	"fmt"
	"sync"
	"time"
)

func main() {
	counter := 0
	var wg sync.WaitGroup
	wg.Add(2)
	go func() { // the first goroutine
		defer wg.Done()
		counter++
	}()
	time.Sleep(100 * time.Millisecond) // the first one has finished; a sleep orders nothing
	go func() { // the second goroutine
		defer wg.Done()
		counter++
	}()
	wg.Wait() // orders both increments before the read below
	fmt.Println("counter:", counter)
}

from session import session

# The same program twice: built as usual, then with the race detector (-race).
# -trimpath keeps folder names out of the report, so it names files as written here.
session(
    ("go build -trimpath -o race race.go && ./race", 0),
    ("go build -race -trimpath -o race race.go && ./race", 66),
)

# go version go1.27.1 darwin/arm64
$ go build -trimpath -o race race.go && ./race
counter: 2
$ go build -race -trimpath -o race race.go && ./race
==================
WARNING: DATA RACE
Read at 0x00c000116038 by goroutine 9:
  main.main.func2()
      race.go:22 +0x68

Previous write at 0x00c000116038 by goroutine 7:
  main.main.func1()
      race.go:17 +0x78

Goroutine 9 (running) created at:
  main.main()
      race.go:20 +0x1a0

Goroutine 7 (finished) created at:
  main.main()
      race.go:15 +0xfc
==================
counter: 2
Found 1 data race(s)
[exit status 66]

The plain build printed counter: 2 and nothing else. The build with -race printed the same right answer and reported the race in the same run, because the detector checks whether the program orders the two accesses, not whether they happened to collide. Nothing orders them here. The Go memory model says that the end of a goroutine is not guaranteed to be synchronised with anything else in the program, and a sleep is not among the operations it lists as synchronising. The report reads from the top:

• Read at … by goroutine 9 is the access that found the conflict, with its stack: the second goroutine’s function, main.main.func2, at race.go:22, its counter++.
• Previous write at … by goroutine 7 is the access it conflicts with: the first goroutine’s counter++, at line 17.
• The two created at stacks say where each goroutine was started, lines 20 and 15, and (finished) confirms that the first one had already ended.
• Found 1 data race(s) closes the report, and the program ends with exit status 66, the detector’s default, so a script or a test run that uses it fails.

The fix is to order the accesses, and there are two usual ways:

// The same four goroutines and a million rounds each, made safe in two ways:
// a mutex, and an atomic counter.
package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

const workers, rounds = 4, 1_000_000

func withMutex() int {
	counter := 0
	var mu sync.Mutex
	var wg sync.WaitGroup
	for range workers {
		wg.Go(func() {
			for range rounds {
				mu.Lock() // one goroutine at a time runs the read, the add, the write
				counter++
				mu.Unlock()
			}
		})
	}
	wg.Wait() // also orders every goroutine's writes before the read below
	return counter
}

func withAtomic() int64 {
	var counter atomic.Int64
	var wg sync.WaitGroup
	for range workers {
		wg.Go(func() {
			for range rounds {
				counter.Add(1) // the read, the add and the write as one step
			}
		})
	}
	wg.Wait()
	return counter.Load()
}

func main() {
	fmt.Printf("mutex:  %d of %d\n", withMutex(), workers*rounds)
	fmt.Printf("atomic: %d of %d\n", withAtomic(), workers*rounds)
}

from session import session

# Built with the race detector: it watches every access to both counters, and reports
# nothing.
session(("go build -race -trimpath -o fixed fixed.go && ./fixed", 0))

# go version go1.27.1 darwin/arm64
$ go build -race -trimpath -o fixed fixed.go && ./fixed
mutex:  4000000 of 4000000
atomic: 4000000 of 4000000

Both versions were built with -race, and the detector reported nothing. The mutex turns the read, the add and the write into a critical section that one goroutine runs at a time. atomic.Int64’s Add does the read, the add and the write as one indivisible step. In both, wg.Wait() orders every goroutine’s work before the final read. An atomic suits a lone counter; once two values must change together, such as a balance and the list of its transactions, you need the lock.

In an interview, what the detector cannot do matters as much as what it can:

• It only sees what runs. The Go documentation says it cannot find races in code paths that are not executed, so a clean run of tests that never take the racy path proves nothing.
• It finds data races, not race conditions. The booking that checks and sells under two separate locks passes it cleanly and still oversells.
• It costs time and memory. For a typical program the Go documentation gives 5 to 10 times the memory and 2 to 20 times the running time, so it belongs in tests and staging rather than in production.

C and C++ have the same kind of tool in Clang’s ThreadSanitizer, switched on with -fsanitize=thread, plus -g for file names and line numbers in its reports and -O1 or higher for reasonable speed. Its reports open with WARNING: ThreadSanitizer: data race and show the two conflicting accesses the way Go’s do, and its documentation gives a typical slowdown of 5 to 15 times and a memory overhead of 5 to 10 times.

Where threads can run

Not every runtime gives you threads, and that matters in a round: if the editor runs Python in the browser, a threaded answer cannot run there at all.

• CPython 3.14, the usual build: threads, with threading, queue, concurrent.futures and asyncio. The GIL lets one thread run Python code at a time, but threads can switch between bytecode instructions, so races still happen.
• CPython 3.14, the free-threaded build: threads that run in parallel, with the same modules. It is officially supported since 3.14 and still optional. Built-in types such as dict and list lock themselves, but a read-then-write sequence of yours does not.
• Pyodide 314.0.7, in a browser: no threads. threading imports, but starting a thread raises RuntimeError; asyncio works.
• JavaScript, in a browser page or Node.js: one thread runs your code, and an async function lets other code run only at an await. Web Workers and Node.js’s worker_threads add threads for parallel work, and those share memory only through a SharedArrayBuffer.
• Java 25: platform threads and virtual threads, with synchronized and java.util.concurrent. Virtual threads, final since Java 21, make a thread per task cheap, and the races stay the same.
• Go 1.27: goroutines that run in parallel, with channels, sync and sync/atomic; go run -race and go test -race look for races.
• C++23: std::thread and std::jthread, with std::mutex, std::atomic, std::condition_variable and std::counting_semaphore; -fsanitize=thread looks for races.

This program asks the Python that runs it whether it can start a thread:

"""Can this Python start a thread? Press Run to ask the Python in your browser, then
run the file on your computer to compare."""
import sys
import threading

print("Python", sys.version.split()[0], "on", sys.platform)
# False only on a free-threaded build running with the GIL switched off.
print("GIL enabled:", sys._is_gil_enabled())


def greet():
    print("a second thread says hello")


try:
    worker = threading.Thread(target=greet)
    worker.start()
    worker.join()
    print("threads: yes")
except RuntimeError as error:
    print("threads: no,", error)

Python 3.14.8 on darwin
GIL enabled: True
a second thread says hello
threads: yes

Python 3.14.2 on emscripten
GIL enabled: True
threads: no, can't start new thread

Pyodide can import threading but cannot start a thread, and its documentation says that it does not support threading or multiprocessing. That is why the browser exercises of this module use asyncio, which does run in Pyodide, while their thread versions in Java, Go and C++ show recorded output.

Both runs print GIL enabled: True, and the GIL deserves a sentence of its own, because many candidates conclude from it that Python threads cannot race. The global interpreter lock lets only one thread run Python bytecode at a time in the usual build, but the interpreter can switch threads between bytecode instructions, and Python’s own FAQ lists D[x] = D[x] + 1 among the operations that are not atomic. Python 3.14 also made the free-threaded build officially supported (PEP 779): there, threads run truly in parallel, and its documentation still recommends threading.Lock over relying on the internal locks of built-in types. sys._is_gil_enabled() tells you which kind of run you are in.

The same failures with async tasks

asyncio runs all of its tasks on one thread, and a task runs without interruption from one await to the next. There are no data races, then, but every await is a point at which any other task may run, and all three failures come back in a new form. The three programs below run in your browser.

First, a race. A hundred deposits, each of 10, read the balance, await a ledger write, then store the balance they read plus 10:

"""100 deposits of 10, run as asyncio tasks. asyncio switches tasks only at an await,
and one await between the read and the write is enough to lose updates."""
import asyncio


async def save_to_ledger():
    await asyncio.sleep(0)  # stands in for a database call: other tasks run meanwhile


async def deposit_racy(account, amount, lock):
    balance = account["balance"]            # read
    await save_to_ledger()                  # every other deposit reads the old balance
    account["balance"] = balance + amount   # write: overwrites the deposits made since


async def deposit_locked(account, amount, lock):
    async with lock:                        # one task at a time, from read to write
        balance = account["balance"]
        await save_to_ledger()
        account["balance"] = balance + amount


async def deposit_no_await_between(account, amount, lock):
    await save_to_ledger()
    account["balance"] += amount            # no await between the read and the write


async def main():
    for deposit in (deposit_racy, deposit_locked, deposit_no_await_between):
        account, lock = {"balance": 0}, asyncio.Lock()
        await asyncio.gather(*(deposit(account, 10, lock) for _ in range(100)))
        name, balance = deposit.__name__, account["balance"]
        print(f"{name:25} balance {balance:4} after 100 deposits of 10")


asyncio.run(main())

deposit_racy              balance   10 after 100 deposits of 10
deposit_locked            balance 1000 after 100 deposits of 10
deposit_no_await_between  balance 1000 after 100 deposits of 10

The racy version ends at 10, not 1,000: every deposit read 0 before any of them wrote, and the last write won. An asyncio.Lock held from the read to the write fixes it. So does moving the await so that nothing awaits between the read and the write, because asyncio never switches tasks there. The second fix is real but fragile: whoever later adds an await in between brings the race back, so in an interview, say which guarantee your code relies on.

Next, a deadlock. Two transfers each lock both of their accounts with an asyncio.Lock, in opposite orders:

"""Two transfers lock both of their accounts. Taken in opposite orders, each one waits
for the lock that the other holds."""
import asyncio


async def transfer(name, first, second, log):
    async with first["lock"]:
        log[name] = f"holds {first['name']}, waits for {second['name']}"
        await asyncio.sleep(0)          # the other transfer takes its first lock here
        async with second["lock"]:
            log[name] = "done"


def source_first(source, target):
    return source, target


def by_account_name(source, target):
    # One order for every transfer, whichever way the money goes.
    return sorted((source, target), key=lambda account: account["name"])


async def run_both(lock_order):
    a = {"name": "account A", "lock": asyncio.Lock()}
    b = {"name": "account B", "lock": asyncio.Lock()}
    log = {}
    tasks = [asyncio.create_task(transfer("A to B", *lock_order(a, b), log)),
             asyncio.create_task(transfer("B to A", *lock_order(b, a), log))]
    done, waiting = await asyncio.wait(tasks, timeout=0.5)
    for task in waiting:
        task.cancel()                   # stop the stuck transfers so that the program ends
    await asyncio.gather(*waiting, return_exceptions=True)
    stuck = len(waiting)
    print(f"{lock_order.__name__}: {stuck} of 2 transfers still waiting after 0.5 s")
    for name, state in log.items():
        print(f"  {name}: {state}")


async def main():
    await run_both(source_first)
    await run_both(by_account_name)


asyncio.run(main())

source_first: 2 of 2 transfers still waiting after 0.5 s
  A to B: holds account A, waits for account B
  B to A: holds account B, waits for account A
by_account_name: 0 of 2 transfers still waiting after 0.5 s
  A to B: done
  B to A: done

With the source account locked first, both transfers were still waiting after half a second, each holding one lock and waiting for the other’s. asyncio’s locks take no timeout of their own, so the program waits for both tasks with asyncio.wait(…, timeout=0.5), which returns the tasks that have not finished without stopping them, and then cancels those. Locking the two accounts in the same order for every transfer, here by name, lets both finish.

Last, starvation. A busy worker takes a lock 1,000 times in a row, and a reporter needs it once:

"""A busy worker takes a lock 1,000 times in a row, and a reporter needs it once.
Who goes next depends on the lock."""
import asyncio


class PollingLock:
    """A flag that waiting tasks check, sleep on and check again.

    There is no queue of waiters, so nothing decides who goes next.
    """

    def __init__(self):
        self.held = False

    async def acquire(self):
        while self.held:
            await asyncio.sleep(0)      # look again on the next turn
        self.held = True

    def release(self):
        self.held = False


class QueueLock:
    """asyncio.Lock behind the same two methods: waiters queue in arrival order."""

    def __init__(self):
        self.lock = asyncio.Lock()

    async def acquire(self):
        await self.lock.acquire()

    def release(self):
        self.lock.release()


async def busy_worker(lock, turns, log):
    for _ in range(turns):
        await lock.acquire()
        await asyncio.sleep(0)          # works for a moment while it holds the lock
        log.append("worker")
        lock.release()                  # then straight back to acquire() for its next turn


async def reporter(lock, log):
    await lock.acquire()
    log.append("reporter")
    lock.release()


async def main():
    for make_lock in (PollingLock, QueueLock):
        lock, log = make_lock(), []
        await asyncio.gather(busy_worker(lock, 1000, log), reporter(lock, log))
        waited = log.index("reporter")
        print(f"{make_lock.__name__:11} the reporter got the lock after {waited:4} "
              "of the worker's 1000 turns")


asyncio.run(main())

PollingLock the reporter got the lock after 1000 of the worker's 1000 turns
QueueLock   the reporter got the lock after    1 of the worker's 1000 turns

With the polling lock, the reporter waited through all 1,000 of the worker’s turns. Every time it looked, the worker had already taken the lock again, because releasing it and taking it back involved no await, so the reporter never ran in between. Had the worker run forever, the reporter would have waited forever while the program as a whole kept busy. asyncio.Lock is fair, as its documentation says: the task that started waiting first is the one that proceeds, so the reporter, which had been waiting since the worker’s first turn, went next.

JavaScript’s async functions follow the same rule: code runs without interruption from one await to the next, so a check and an update with an await between them can interleave with other calls. The exercise below has a JavaScript version too.

The tools in each language

Five needs cover most of the four tasks, and each has a standard tool in every language of this track:

• One thread at a time in a section. Python threads: threading.Lock. asyncio: asyncio.Lock. Java: synchronized or ReentrantLock. Go: sync.Mutex. C++: std::mutex, taken with std::scoped_lock.
• A counter that many update. Python threads: a lock around it. asyncio: no await between the read and the write. Java: AtomicInteger, or LongAdder under heavy contention. Go: atomic.Int64. C++: std::atomic<int>.
• Waiting until something is true. Python threads: threading.Condition or threading.Event. asyncio: asyncio.Condition or asyncio.Event. Java: a Condition or a CountDownLatch. Go: a channel, or sync.Cond. C++: std::condition_variable.
• At most k at once. Python threads: threading.Semaphore. asyncio: asyncio.Semaphore. Java: Semaphore. Go: a buffered channel of k tokens. C++: std::counting_semaphore.
• A bounded queue. Python threads: queue.Queue(maxsize=k). asyncio: asyncio.Queue(maxsize=k). Java: ArrayBlockingQueue. Go: make(chan T, k). C++ has none in its standard library: a std::deque, a mutex and two condition variables make one.

JavaScript on a single thread needs no lock for a check and an update with no await between them, because nothing interleaves there. A promise that every caller shares, or a count of the tasks in flight, covers most of the other jobs, and a later lesson of this module builds a promise pool from them.

Practise: sell the last seats

A ticket desk sells the seats of one show, and each of its bookings checks how many seats are free, awaits the payment, and only then takes the seats. Twelve bookings that arrive together for ten seats all pass the check. Fix it in Python or JavaScript, so that bookings are served in the order they arrive, nothing is oversold and a refused booking is never charged. The sample tests start many bookings at once and compare the result with serving them one by one.

desk = SeatDesk(10, pay)
await asyncio.gather(desk.book("dev", 4), desk.book("esha", 4), desk.book("farid", 4), desk.book("gita", 2))
# [True, True, False, True]: farid's 4 seats do not fit when farid's turn comes, gita's 2 do

class SeatDesk:
    """Sells the seats of one show. Many book() calls run at once, as asyncio tasks."""

    def __init__(self, seats, pay):
        self.seats_left = seats
        self.sold = {}      # buyer -> number of seats sold to them
        self.pay = pay      # async pay(buyer, count) charges the buyer; others run meanwhile

    async def book(self, buyer, count):
        """Sells count seats to buyer and returns True, or returns False when fewer
        than count seats are free.

        Fix it: it oversells when bookings overlap. Serve bookings in the order book()
        was called, charge every sale exactly once, and never charge a refused booking.
        """
        if self.seats_left < count:
            return False
        await self.pay(buyer, count)
        self.seats_left -= count
        self.sold[buyer] = self.sold.get(buyer, 0) + count
        return True

import asyncio
import random

from seats import SeatDesk


def recorder():
    """A pay() that records every charge and, like a real payment service, makes the
    caller wait."""
    charges = []

    async def pay(buyer, count):
        await asyncio.sleep(0)
        charges.append((buyer, count))

    return pay, charges


async def test_one_booking_on_its_own():
    """2 of 5 seats for one buyer"""
    pay, charges = recorder()
    desk = SeatDesk(5, pay)
    assert await desk.book("asha", 2) is True
    assert (desk.seats_left, desk.sold, charges) == (3, {"asha": 2}, [("asha", 2)])


async def test_a_booking_that_does_not_fit():
    """3 seats wanted and 2 free: refused, and nobody is charged"""
    pay, charges = recorder()
    desk = SeatDesk(2, pay)
    assert await desk.book("bala", 3) is False
    assert (desk.seats_left, desk.sold, charges) == (2, {}, [])


async def test_the_last_seats_exactly():
    """a booking for exactly the free seats is sold"""
    pay, charges = recorder()
    desk = SeatDesk(3, pay)
    assert await desk.book("chen", 3) is True
    assert desk.seats_left == 0


async def test_twelve_buyers_at_once_for_ten_seats():
    """12 bookings of 1 seat start together: the first 10 are sold, the last 2 refused"""
    pay, charges = recorder()
    desk = SeatDesk(10, pay)
    buyers = [f"buyer{i}" for i in range(12)]
    results = await asyncio.gather(*(desk.book(b, 1) for b in buyers))
    assert results == [True] * 10 + [False] * 2
    assert desk.seats_left == 0
    assert desk.sold == {b: 1 for b in buyers[:10]}
    assert sorted(charges) == sorted((b, 1) for b in buyers[:10])


async def test_mixed_sizes_at_once():
    """4, 4, 4 and 2 seats of 10, all at once: the third does not fit, the fourth does"""
    pay, charges = recorder()
    desk = SeatDesk(10, pay)
    results = await asyncio.gather(
        desk.book("dev", 4), desk.book("esha", 4), desk.book("farid", 4), desk.book("gita", 2)
    )
    assert results == [True, True, False, True]
    assert (desk.seats_left, desk.sold) == (0, {"dev": 4, "esha": 4, "gita": 2})
    assert ("farid", 4) not in charges


async def test_the_same_buyer_twice():
    """a buyer who books twice gets both bookings added up"""
    pay, charges = recorder()
    desk = SeatDesk(6, pay)
    assert await asyncio.gather(desk.book("hari", 2), desk.book("hari", 3)) == [True, True]
    assert (desk.seats_left, desk.sold) == (1, {"hari": 5})


async def test_against_one_booking_at_a_time():
    """300 random rounds of overlapping bookings, checked against serving them one by one"""
    rng = random.Random(31)
    for _ in range(300):
        seats = rng.randint(0, 12)
        wanted = [(f"b{i}", rng.randint(1, 4)) for i in range(rng.randint(1, 10))]
        left, expected, expected_sold = seats, [], {}
        for buyer, count in wanted:
            fits = count <= left
            expected.append(fits)
            if fits:
                left -= count
                expected_sold[buyer] = count
        pay, charges = recorder()
        desk = SeatDesk(seats, pay)
        results = await asyncio.gather(*(desk.book(b, c) for b, c in wanted))
        got = (results, desk.seats_left, desk.sold)
        assert got == (expected, left, expected_sold), (seats, wanted)
        assert sorted(charges) == sorted(expected_sold.items()), (seats, wanted)

export class SeatDesk {
  /**
   * Sells the seats of one show. Many book() calls run at the same time.
   * pay(buyer, count) is an async function that charges the buyer; other calls run
   * while it waits.
   */
  constructor(seats, pay) {
    this.seatsLeft = seats;
    this.sold = new Map(); // buyer -> number of seats sold to them
    this.pay = pay;
  }

  /**
   * Sells count seats to buyer and resolves to true, or to false when fewer than count
   * seats are free.
   * Fix it: it oversells when bookings overlap. Serve bookings in the order book() was
   * called, charge every sale exactly once, and never charge a refused booking.
   */
  async book(buyer, count) {
    if (this.seatsLeft < count) return false;
    await this.pay(buyer, count);
    this.seatsLeft -= count;
    this.sold.set(buyer, (this.sold.get(buyer) ?? 0) + count);
    return true;
  }
}

import { test, assert } from 'mysmartcopilot:test';
import { SeatDesk } from './seats.mjs';

// A pay() that records every charge and, like a real payment service, makes the caller
// wait.
function recorder() {
  const charges = [];
  const pay = async (buyer, count) => {
    await null;
    charges.push([buyer, count]);
  };
  return { pay, charges };
}

const byBuyer = (a, b) => (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : a[1] - b[1]);
const sorted = (pairs) => [...pairs].sort(byBuyer);

test('2 of 5 seats for one buyer', async () => {
  const { pay, charges } = recorder();
  const desk = new SeatDesk(5, pay);
  assert.equal(await desk.book('asha', 2), true);
  assert.deepEqual([desk.seatsLeft, [...desk.sold], charges], [3, [['asha', 2]], [['asha', 2]]]);
});

test('3 seats wanted and 2 free: refused, and nobody is charged', async () => {
  const { pay, charges } = recorder();
  const desk = new SeatDesk(2, pay);
  assert.equal(await desk.book('bala', 3), false);
  assert.deepEqual([desk.seatsLeft, [...desk.sold], charges], [2, [], []]);
});

test('a booking for exactly the free seats is sold', async () => {
  const { pay } = recorder();
  const desk = new SeatDesk(3, pay);
  assert.equal(await desk.book('chen', 3), true);
  assert.equal(desk.seatsLeft, 0);
});

test('12 bookings of 1 seat start together: the first 10 are sold, the last 2 refused', async () => {
  const { pay, charges } = recorder();
  const desk = new SeatDesk(10, pay);
  const buyers = Array.from({ length: 12 }, (_, i) => `buyer${i}`);
  const results = await Promise.all(buyers.map((b) => desk.book(b, 1)));
  assert.deepEqual(results, [...Array(10).fill(true), false, false]);
  assert.equal(desk.seatsLeft, 0);
  const firstTen = buyers.slice(0, 10).map((b) => [b, 1]);
  assert.deepEqual(sorted([...desk.sold]), sorted(firstTen));
  assert.deepEqual(sorted(charges), sorted(firstTen));
});

test('4, 4, 4 and 2 seats of 10, all at once: the third does not fit, the fourth does', async () => {
  const { pay, charges } = recorder();
  const desk = new SeatDesk(10, pay);
  const results = await Promise.all([
    desk.book('dev', 4),
    desk.book('esha', 4),
    desk.book('farid', 4),
    desk.book('gita', 2),
  ]);
  assert.deepEqual(results, [true, true, false, true]);
  const sold = [['dev', 4], ['esha', 4], ['gita', 2]];
  assert.deepEqual([desk.seatsLeft, sorted([...desk.sold])], [0, sold]);
  assert.equal(charges.some(([buyer]) => buyer === 'farid'), false);
});

test('a buyer who books twice gets both bookings added up', async () => {
  const { pay } = recorder();
  const desk = new SeatDesk(6, pay);
  const results = await Promise.all([desk.book('hari', 2), desk.book('hari', 3)]);
  assert.deepEqual(results, [true, true]);
  assert.deepEqual([desk.seatsLeft, [...desk.sold]], [1, [['hari', 5]]]);
});

test('300 random rounds of overlapping bookings, checked against serving them one by one', async () => {
  let seed = 31;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const randInt = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
  for (let round = 0; round < 300; round++) {
    const seats = randInt(0, 12);
    const wanted = Array.from({ length: randInt(1, 10) }, (_, i) => [`b${i}`, randInt(1, 4)]);
    let left = seats;
    const expected = [];
    const expectedSold = [];
    for (const [buyer, count] of wanted) {
      const fits = count <= left;
      expected.push(fits);
      if (fits) {
        left -= count;
        expectedSold.push([buyer, count]);
      }
    }
    const { pay, charges } = recorder();
    const desk = new SeatDesk(seats, pay);
    const results = await Promise.all(wanted.map(([b, c]) => desk.book(b, c)));
    const where = JSON.stringify([seats, wanted]);
    const got = [results, desk.seatsLeft, sorted([...desk.sold])];
    assert.deepEqual(got, [expected, left, sorted(expectedSold)], where);
    assert.deepEqual(sorted(charges), sorted(expectedSold), where);
  }
});

Then find the failure in six short snippets, one of which is correct:

Interview questions

Warm-up (fresher to mid-level): How does a data race differ from a race condition?

A data race is a fact about memory: two threads access the same location, at least one of them writes, and nothing in the program orders the two accesses, such as a lock, an atomic operation or a channel. A race condition is a fact about behaviour: the result depends on how the threads happen to interleave. A data race usually causes a race condition, a lost update for instance, and in C++ any data race is undefined behaviour. But a race condition needs no data race. If a booking checks the free seats under a lock, releases it, and sells under the lock again, every access is synchronised and the code still oversells. Race detectors such as Go’s -race find data races only; race conditions are found by reasoning about the steps that must happen together, and by stress tests that check the end result.

Warm-up (fresher to mid-level): Name the four conditions for a deadlock, and say which one a global lock order removes.

Mutual exclusion: a resource is held by one thread at a time. Hold and wait: a thread keeps what it holds while it waits for more. No preemption: nothing takes a resource away from its holder. Circular wait: a cycle of threads, each waiting for a resource the next one holds. All four must hold at once, so removing any one prevents deadlock. A global lock order, such as always locking the account with the smaller number first, removes circular wait: every thread climbs the same order, so no thread can hold a later lock while waiting for an earlier one, and no cycle can form. Taking every lock a step needs in one call removes hold and wait instead, and a time limit on each wait turns a deadlock into an error the code can handle.

Key takeaways

• Coding rounds set four concurrency tasks: threads in a fixed order, bounded buffers, thread-safe structures and limited parallelism. For each, state the rule the shared state must keep before you write code.
• counter += 1 is a read and a write. Of the 6 orders in which two threads’ increments can run, 4 lose an update.
• A data race is unordered access to shared memory; a race condition is any timing-dependent bug, and it needs no data race.
• A deadlock needs mutual exclusion, hold and wait, no preemption and circular wait at once. One lock order for every thread, all locks in one call, or a time limit on each wait breaks it.
• Starvation leaves the program running and one thread waiting. Fair locks, such as asyncio.Lock and Java’s ReentrantLock(true), hand the lock to the waiter that has waited longest.
• Go’s -race and Clang’s ThreadSanitizer report data races that happen while the program runs, even when the answer comes out right, and nothing in code paths that never ran.
• Pyodide cannot start threads, but asyncio runs there. From one await to the next a task runs alone, so every await between a check and an update is a place where a race can happen.