Concurrency

A process owns an isolated address space and OS resources; threads are execution contexts inside one process that share that memory. Each thread has its own stack, registers and program counter. Separate processes cannot touch each other's memory and must use explicit inter-process communication.

Under preemptive scheduling a timer interrupt lets the scheduler suspend a task at almost any instruction and run another. Under cooperative scheduling a task runs until it voluntarily yields. Preemption guarantees progress for everyone; cooperation is cheaper and predictable but one non-yielding task blocks all others.

Three mappings of program threads onto kernel-scheduled threads. 1:1 — each program thread is a kernel thread: real parallelism, but costly. N:1 — many on one: cheap, but no multicore and one blocking call stalls all. M:N — both benefits, at the price of a complex two-level scheduler.

Joining means one thread blocks until another finishes. Starting a thread only launches it; the starter keeps running and has no idea when the work is done or whether it succeeded. Join gives you completion timing and a safe point to read results.

The kernel saves the running thread's registers and program counter, picks another runnable thread, and restores its state; a switch to a different process also swaps page tables. The direct cost is small. The larger, indirect cost is cold caches, branch predictors and address-translation entries when the new thread starts running.

A latch is created with the count N. Each worker decrements it once when done; the coordinator blocks in await until the count reaches zero, then continues. The count never resets, so any wait after zero returns immediately instead of blocking.

A monitor is a lock protecting shared state plus a condition variable to wait on. The consumer locks, and while the queue is empty calls wait, which atomically releases the lock and sleeps. A producer adds an item under the lock and signals. Polling wastes CPU and adds latency; waiting costs nothing until woken.

At most one thread holds a given mutex, so critical sections guarded by that same lock never overlap, and a holder's writes become visible to the next holder. It promises nothing about acquisition order, fairness, deadlock freedom, or data guarded by another lock.

It has two modes: many threads may hold it in shared (read) mode at once, but exclusive (write) mode admits one holder and excludes all readers. It only beats a plain mutex when reads greatly outnumber writes and critical sections are long enough to repay its higher bookkeeping cost.

A semaphore is a counter of permits with two atomic operations: acquire, which takes a permit and blocks while none are free, and release, which returns one. A counting semaphore starts with N permits; a binary semaphore holds at most one.

That one statement is three machine steps: read the value, add one, write it back. Two threads can read the same old value, both add one to it, and both write the same new value — so two increments produce one. Updates are lost whenever the steps interleave.

Deadlock is a set of threads permanently blocked, each waiting for a resource another one in the set holds. It requires four conditions at once: mutual exclusion, hold-and-wait, no preemption, circular wait.

A data race is a memory-model property: two threads access the same location concurrently, at least one writes, with no ordering between them. A race condition is a correctness property: the result depends on timing. You can have a race condition with zero data races (all accesses properly synchronized, but the logic assumes state cannot change between steps) and a data race that never produces a wrong-looking answer.

Transfer(A,B) and transfer(B,A) take the two locks in opposite orders and can each hold one while waiting for the other. Fix: define one total order over all lockable objects, such as a unique id, and always acquire in that order.

Both are liveness failures: no useful work completes. In deadlock the threads are blocked forever waiting on each other, so their states are frozen. In livelock the threads stay runnable and keep changing state (retry, back off, yield) but the pattern repeats and nobody finishes.

The statement is three steps: read, add one, write back. Two threads can read the same old value and both write the same new value, so one increment is lost. An atomic read-modify-write performs all three steps as one indivisible hardware operation that no other thread can interleave with.

Nothing orders the write against the read, so the reader has no obligation to observe it. The compiler may load the variable once into a register and loop on that copy, and the write may sit in the writer's store buffer. Publish the flag through a synchronization edge.

That is the ABA problem. Between the read and the compare-and-swap, other threads changed the value to B and back to A. Compare-and-swap only checks that the word is equal now, not that nothing happened meanwhile, so anything the thread inferred from its first read may be stale.

Compare-and-swap atomically writes a new value only if the location still equals the value you expected, reporting success or failure. You read, compute a new value, attempt the swap, and loop on failure with a fresh read. A loop iterates when another thread updated the location first; a persistently unlucky thread can starve, though the system as a whole always progresses.

False sharing. Coherence tracks whole cache lines, so both counters live in one line; each write must take exclusive ownership and invalidates the other core's copy, so the line ping-pongs between caches. Confirm with coherence-miss counters or by separating the fields; fix by padding or aligning them onto different lines, or by accumulating per thread.

A coroutine is a function that can pause partway through and resume later. Suspending saves its state, hands control back to a scheduler, and frees the underlying thread for other work. A blocked thread keeps its whole stack and OS slot while doing nothing.

An event loop is a single thread cycling forever: wait for ready events, take the next task from a queue, run its handler to completion, repeat. No handler is ever interrupted mid-way by another handler, so loop-owned state needs no locks — but a slow handler delays everything behind it.

A future is the read side of a result that is not ready yet: you await it or attach a continuation. A promise is the write side: the producer completes it once, with a value or an error. Splitting them stops consumers from completing results.

Mapping applies a synchronous function to the value. Chaining applies a function that returns another future and flattens it, so the result completes when the inner work finishes. Mapping with an async function yields a future of a future: the outer completes early, before the real work is done.

A future completes with either a value or an error, and an error short-circuits the downstream transforms until a handler that accepts errors is reached. A try/catch at the call site only sees synchronous failures, because the function returns a pending handle long before the failure exists.

Data parallelism runs the same operation over different slices of one data set — its scaling limit is how finely you can split the data. Task parallelism runs different operations concurrently — its scaling limit is the number of independent tasks and their dependency graph. Resizing a million images is data parallel; fetching a user profile and their orders at once is task parallel.

A task checks whether its input is small enough to do directly. If not, it splits the input into independent pieces, forks them so they can run in parallel, then joins - waits for each piece to finish - and combines their results. Join gives completion and result visibility.

Map transforms each input record independently into key-value pairs. Shuffle regroups those pairs so that all values for the same key land together on one reducer. Reduce folds each key's group into a result. Without the regroup step a reducer would only see part of each key.

Split a repeated job into ordered steps called stages, each with its own worker and a queue in front of it. Different items sit in different stages at the same time, so all workers run at once. Steady-state throughput is one item per slowest stage's time.

Each split costs bookkeeping - creating, queueing and scheduling a task. Below some size that overhead exceeds the useful work, so the recursion would slow things down. Pick the threshold by measuring: choose the smallest size where parallel still beats sequential, comfortably above the break-even point.

New tasks wait in the queue instead of running. Throughput stays flat at what the workers can serve, so latency climbs as the backlog grows. An unbounded queue eats memory; a bounded one eventually refuses work or blocks the submitter.

Orderly shutdown stops accepting new submissions but drains the queue and lets running tasks finish. Immediate shutdown also refuses new work, discards the queue - returning the undone tasks - and signals running tasks to stop. Both requests return at once; termination happens later.

A delay is a lower bound, not an appointment: the task will not start before 100 ms, but it may start much later. The scheduler keeps pending tasks ordered by due time and can only run one when a worker is free and the clock has passed it.

Only 8 tasks can actually compute at once, so throughput is already capped by the cores. Extra workers add context switches, cache pollution, memory for stacks and more lock contention. Throughput flattens then dips, and per-task latency rises because more work is in flight.

The waiting parent still occupies a worker. If every worker is a blocked parent, no worker is left to run the queued children, so parents wait on children that can never start. It is a resource deadlock where the scarce resource is the worker thread.

Cancelling means asking a running task to stop early and release what it holds; the task must notice the request and wind down. Ignoring its result stops nothing: it keeps burning CPU, connections and memory, and its side effects still happen.

With no owner waiting, the error has nowhere to propagate: it ends that task and lands in a default handler, an unread log line, or a result object nobody inspects. The system keeps reporting healthy while the work silently is not being done.

Nobody owns it. Failures vanish silently, nobody waits for it, it can outlive the data and resources it borrowed, it cannot be cancelled or given a deadline, and shutdown can kill it mid-work. The leak stays invisible.

A checkpoint is a point where the task tests the cancellation signal and abandons the work if it is set. Blocking and awaiting operations usually provide them implicitly; a pure compute loop has none, so you poll the signal every N iterations. Cancellation latency is roughly the time between checkpoints plus cleanup time.

Forced termination stops a task at an arbitrary instruction, so invariants are half-updated, locks and buffers are left in unknown states, and no cleanup runs. Cooperative cancellation stops only at safe points. A thread interruption flag is the same idea at thread level: a bit that blocking operations honour by aborting early.

An actor is an isolated unit with private state, a mailbox, and behaviour. Actors never share memory; they only send each other asynchronous messages. Each actor processes its mailbox strictly one message at a time, so its state is never touched concurrently and needs no lock.

CSP models a program as independent sequential processes that share no memory and interact only by sending and receiving values on channels. The communication is itself the synchronization, so there is no shared mutable state to lock.

The message must be fully built before it is sent and never change afterwards, all the way down: nested objects, arrays and collections must be immutable too, and the sender must keep no reference it can mutate. Then every reader sees identical content regardless of timing.

Producers put work items into a shared fixed-size buffer; consumers take them out. A producer blocks when the buffer is full, a consumer blocks when it is empty. This decouples the two sides in time and rate while the fixed capacity stops a fast producer from exhausting memory.

Typically at-most-once delivery, with FIFO order preserved only per sender-receiver pair. There is no global ordering, no causal ordering through intermediaries, and no guaranteed delivery. So handlers must tolerate lost, delayed and interleaved messages, and be idempotent if you add retries.

A fixed sleep is a guess about duration. Too short and the test fails on a loaded machine; too long and the suite crawls. Wait on a real completion signal instead — a future, a latch, a callback, or a quiescence check — with a generous timeout.

A data race is two threads accessing the same memory location, at least one of them writing, with no synchronization ordering the accesses. A dynamic detector instruments every load, store and synchronization event at runtime and checks whether each pair of conflicting accesses is ordered.

A virtual clock is a time source the test controls: it only advances when the test says so. Injecting it lets you test timeouts, retry backoff, cache expiry, rate limiting, and scheduled jobs instantly and deterministically, with no real waiting.

Take several dumps a few seconds apart and compare. Near-zero processor use means nobody is running, so look for threads blocked on a lock (and who owns it), waiting on a condition or a remote response, and for whole worker pools stuck in the same stack — that shared frame is the culprit.

Shrink the code under test so the bad window is a large fraction of it, start all threads from a barrier so they collide instead of running sequentially, perturb timing with randomized delays and varied thread counts, check a real invariant rather than a crash, and record the seed and observed state so a failure is reproducible.