Condition Variables, Semaphores and Deadlock

A mutex answers “Who may access this data now?” It does not answer “Has the work finished?” To wait for an event, a thread needs a record of the event and a way to sleep until that record changes.

Why spinning is a poor wait

The loop while (done == 0) ; spends CPU time repeatedly checking a flag. On one CPU, that work delays the child that must set the flag. In C, an unsynchronized read of an ordinary variable while another thread writes it is also a data race. The compiler need not reload the flag on each iteration.

A condition variable gives threads a waiting queue. POSIX provides pthread_cond_t, initialized with PTHREAD_COND_INITIALIZER or pthread_cond_init(). The queue is separate from the state being tested: done records completion; the condition variable provides somewhere to sleep.

Keep the check and the wait together

pthread_cond_wait(&c, &m) requires the caller to hold mutex m. It atomically releases that mutex and starts waiting. Before returning, it reacquires the mutex. This closes the dangerous gap in which another thread could change the state and signal before the waiter has actually started waiting.

Here is a parent waiting for a child's completion. The names lock, wait, signal, and unlock shorten the corresponding thread-library calls.

/* Parent */
lock(&m);
while (done == 0)
    wait(&c, &m);
unlock(&m);

/* Child */
lock(&m);
done = 1;
signal(&c);
unlock(&m);

Initially done is 0. If the parent runs first, it locks, finds unfinished work, and waits. Waiting releases m, allowing the child to lock it, set done, and signal. The parent eventually reacquires m, checks done again, and continues.

If the child runs first, it records completion before the parent arrives. Its signal wakes nobody, but the later parent sees done == 1 and skips the wait. Correctness must survive both orders.

Signals do not store events

pthread_cond_signal(&c) unblocks at least one waiter when there are waiters; POSIX permits more than one to wake. With no waiters it has no effect. pthread_cond_broadcast(&c) wakes all current waiters. Neither call deposits a saved notification for future threads.

Leaving out done therefore breaks the join pattern: a child can signal before its parent waits, after which the parent sleeps with no future signal coming. This is a lost wakeup. Checking done outside the mutex creates another lost-wakeup window: the parent checks false, the child sets true and signals, then the parent starts waiting.

Protect the state check and every state change with the same mutex. Hold it from the check through the call to wait. A straightforward signaling path changes the state and signals while still holding that mutex. POSIX permits signaling without holding it, but the shared-state protocol must still prevent a lost wakeup.

Returning from wait means the thread may try again. It does not mean the condition it needs is still true. This distinction matters whenever several threads compete for the same data.

Mesa and Hoare semantics

POSIX, Java, C++ condition variables, and Python conditions follow Mesa behavior. Hoare's monitors introduced the stronger handoff model; Mesa's approach is the common practical choice.

Suppose C1 waits for a one-slot buffer to become nonempty. A producer fills it and signals C1. C1 is now ready, but C2 can acquire the mutex first and take the item. When C1 finally reacquires the mutex, the buffer is empty again.

lock(&m);
while (count == 0)
    wait(&filled, &m);
v = get();
unlock(&m);

The while repeats the test after every return. An if tests only before the first wait and would let C1 call get() on an empty buffer. Even with one producer and one consumer, use while: POSIX also allows spurious wakeups, where wait returns without a matching signal.

Wake one thread or all of them?

A signal is suitable when the waiters need the same condition and any one can use the change. A broadcast is useful when several can proceed, or when different waiters need different amounts and the signaler cannot select the right one.

Consider an allocator with 0 bytes free. Ta needs 100 bytes and Tb needs 10. Another thread releases 50 bytes. A signal might wake Ta, which still cannot proceed, leaving Tb asleep even though its request fits. Broadcasting wakes both. They reacquire the mutex one at a time; Tb can allocate, while Ta waits again. This is a covering condition: the notification covers every potentially eligible waiter.

Broadcast can cause extra wakeups, context switches, and competition for the mutex. Separate condition variables for distinct predicates can make signaling more selective. In a buffer, producers and consumers should not share one undifferentiated signal queue.

The monitor connection

A monitor bundles shared data with operations that admit one thread at a time and condition variables for waiting. Java objects supply a lock and a wait set. Inside synchronized, a thread can call wait(), notify(), or notifyAll(); calling them without owning that object's monitor throws IllegalMonitorStateException.

Waiting releases only the associated mutex or Java object's lock. If a thread also holds another lock, that second lock stays held. A producer that needs it may be unable to make the condition true. Check all locks held at a wait, not just the one named in the call.

Producers add items to a fixed-size buffer; consumers remove them. A correct bounded buffer prevents overwriting a full buffer, removing from an empty one, and concurrent changes to its bookkeeping. A web server's request queue and the pipe between grep error log.txt and wc -l both fit this pattern.

Follow the ring indices

A ring buffer uses an array and two indices. fill_ptr marks the next write; use_ptr marks the next read. Both advance modulo MAX. A separate count distinguishes empty from full, even when the two indices are equal.

void put(int v) {
    buffer[fill_ptr] = v;
    fill_ptr = (fill_ptr + 1) % MAX;
    count++;
}
int get(void) {
    int v = buffer[use_ptr];
    use_ptr = (use_ptr + 1) % MAX;
    count--;
    return v;
}

Start with capacity 3 and both indices at 0. Putting 7, 8, and 9 fills slots 0, 1, and 2. The write index wraps to 0 and count reaches 3. Getting returns 7 and advances the read index to 1. Putting 10 reuses slot 0. The array is now [10, 8, 9], but FIFO removal follows the read index: 8 comes next, then 9, then 10.

Match each signal to the opposite role

Use one mutex, empty for producers waiting for space, and fill for consumers waiting for an item. Initialize both condition variables and the mutex before starting threads.

/* Producer: repeat for each item v */
lock(&m);
while (count == MAX)
    wait(&empty, &m);
put(v);
signal(&fill);
unlock(&m);

/* Consumer */
lock(&m);
while (count == 0)
    wait(&fill, &m);
v = get();
signal(&empty);
unlock(&m);

The check and buffer update stay in one critical section. Otherwise two producers could both see one free slot and overwrite each other's work. Waiting releases m, so the opposite role can change the buffer.

Why one queue can stall

With one condition variable and signals, producers and consumers can wake the wrong role. For capacity 1, C1 and C2 first sleep on empty. P inserts an item, wakes C1, then waits because the buffer is full. C1 removes the item and signals, but the signal may wake C2 instead of P. C1 waits again; C2 also finds empty and waits. P stays asleep although space is available. Two queues route each signal to the role that can now proceed. Broadcasting on a shared queue can avoid that selection problem, at the cost of extra wakeups.

A larger capacity absorbs bursts and allows producing and consuming work outside the buffer's short critical section to overlap. The buffer updates themselves remain serialized. Capacity 1 forces every insertion and removal to alternate.

For clean shutdown, first wait for every producer to finish its real items. Then enqueue one reserved end-of-data item per consumer, such as -1 when real items are nonnegative. Each consumer exits after taking one. Sending those markers while producers are still active can leave real items with no consumer.

A semaphore holds an integer changed by atomic wait and post operations. Dijkstra introduced it in the 1960s as P and V; POSIX names the operations sem_wait() and sem_post(). Atomic means two threads cannot partially perform the same counter operation at once.

Available units determine the initial value

sem_init(&s, 0, X) creates an unnamed semaphore with value X. The second argument 0 selects sharing among threads in one process. For sharing between processes, a nonzero argument requires the semaphore to live in shared memory.

A binary semaphore used as a lock surrounds a critical section with wait and post. Starting it at 0 blocks the first entrant. Starting it at 2 allows two entrants and fails to provide mutual exclusion.

Two equivalent counting models

In Dijkstra's definition, the value stays nonnegative: wait sleeps until it can decrement without going below zero, and post adds a unit. Linux follows this nonnegative convention.

For hand traces, use the signed-counter model: wait decrements and blocks if the new value is negative; post increments and wakes a waiter when one is blocked. A negative value's magnitude counts blocked waiters in this model. It is a reasoning convention, not a negative value to expect from Linux's semaphore API.

Trace a lock initialized to 1:

1. T0 waits: 1 becomes 0, so T0 enters.
2. T1 waits: 0 becomes −1, so T1 blocks.
3. T0 posts: −1 becomes 0, allowing T1 to continue.
4. T1 finishes and posts: 0 becomes 1.

The wakeup transfers the existing permit to T1; another wait is not needed before T1 enters its critical section.

A post is remembered

With no waiter, a post increases the available count. A future wait can consume that permit. This is useful when one thread finishes before the thread waiting for it has started. A condition-variable signal has no such memory.

Semaphores have no owner: one thread may wait and another may post. A mutex belongs to its locking thread; unlocking a default POSIX mutex from another thread is undefined behavior. The ownerless semaphore supports signaling, but also makes an extra post harder to diagnose.

A semaphore can be built from a mutex, condition variable, and nonnegative integer. Wait locks, loops while value <= 0, waits, decrements, and unlocks. Post locks, increments, signals, and unlocks. The mutex makes the counter operations atomic; the loop handles wakeups that do not leave a unit available. Locks with condition variables and semaphores can implement one another, although a correct condition-variable implementation from semaphores is more involved.

The same wait/post pair can represent an event or a limited supply. Decide what a permit means before choosing the initial count and where each operation belongs.

Make completion precede use

For a parent waiting for a child, initialize finished to 0. The child posts after finishing its work. The parent waits before using the result.

/* Child */
produce_result();
sem_post(&finished);

/* Parent */
sem_wait(&finished);
use_result();

If the parent arrives first, the signed value changes from 0 to −1 and it sleeps. The child's post returns the value to 0 and wakes it. If the child arrives first, its post changes 0 to 1; the later wait changes 1 to 0 without blocking. One completed event permits one successful wait.

Count a resource pool

A pool of four database connections uses a semaphore initialized to 4. Each client waits before borrowing a connection and posts after returning it. A fifth simultaneous borrower sleeps. The semaphore counts admission; a separate mutex still protects the shared list that identifies which connection is free. Two admitted threads must not remove the same list entry.

Throttling applies the same idea to an expensive phase. Suppose 100 threads each need 500 MB during processing. Together they could need 50,000 MB. A machine with 8 GB has 8,000 MB under decimal SI units. Admitting at most 12 workers limits this phase to 6,000 MB and leaves 2,000 MB for other use.

sem_wait(&processing_slots);
run_memory_heavy_phase();
sem_post(&processing_slots);

Every path after a successful wait must return its permit, including an error path. Forgetting a post gradually reduces capacity. Posting twice creates an extra permit and allows more simultaneous users than intended.

Meet at a rendezvous

A rendezvous requires two threads to arrive before either continues. Initialize a_arrived and b_arrived to 0.

/* A */
sem_post(&a_arrived);
sem_wait(&b_arrived);

/* B */
sem_post(&b_arrived);
sem_wait(&a_arrived);

If A arrives first, it records its arrival and blocks for B. B records its arrival and can consume A's saved permit. A can then consume B's permit. Reversing both sequences to wait before post leaves each thread asleep before it announces anything.

These two semaphores implement one meeting. Reusing synchronization across repeated rounds requires keeping rounds from consuming each other's arrivals; one successful trace is not a reusable barrier design.

A semaphore fits a count or a simple event well. A condition variable fits a richer predicate, such as waiting until a queue contains several items of a required type. In that case the mutex protects the state from which the condition is computed.

A semaphore buffer separates two questions: “Is an item or slot available?” and “Who may update the array now?” Two counting semaphores answer the first question, and a mutex answers the second.

Set up three distinct controls

For capacity MAX, initialize empty to MAX, full to 0, and the mutex to unlocked. Here empty and full are semaphores, not condition variables. A permit from empty reserves one slot; a permit from full reserves one item.

/* Producer */
sem_wait(&empty);
lock(&mutex);
put(v);
unlock(&mutex);
sem_post(&full);

/* Consumer */
sem_wait(&full);
lock(&mutex);
v = get();
unlock(&mutex);
sem_post(&empty);

The producer acquires space before touching the ring, then publishes the completed item by posting full. The consumer acquires an item, removes it under the mutex, and returns space with a post to empty. A successful semaphore wait already reserves the resource, so these calls do not need a condition-variable-style predicate loop around them.

Trace one slot

Initially empty is 1 and full is 0. A consumer waits on full, changing it to −1 in the signed model, and sleeps. The producer waits on empty, taking it from 1 to 0. It locks, inserts, unlocks, and posts full, taking −1 to 0 and releasing the consumer.

The producer's next wait on empty changes 0 to −1 and blocks. The consumer takes the item under the mutex and posts empty, taking −1 to 0 and releasing the producer. The semaphore counts carry the handoff; no separate count is required for synchronization.

With a larger buffer, several producers can pass the space semaphore. Without the mutex, both might read the same fill_ptr and write the same slot. A reservation is not exclusive access to the array's indices.

Why locking first can deadlock

Suppose the consumer locks mutex before waiting on full. On an empty buffer it sleeps while still owning the mutex. The producer needs that mutex to insert the item whose post would release the consumer. Neither can finish.

A semaphore wait releases no mutex. A condition-variable wait deliberately releases its associated mutex. The order in this buffer therefore matters: reserve first, lock second, change the buffer, unlock, then publish the opposite permit.

The broader rule is to avoid blocking while holding a lock needed by the operation that can unblock you. That rule explains why the readers–writers algorithm can have a different safe arrangement: its writer does not need the reader-counter lock to release its resource.

The mutex may itself be a binary semaphore initialized to 1. Its role remains mutual exclusion; the other two semaphores count resources.

Read-heavy structures can allow several readers at once because reading does not change the data. A readers–writers lock admits either a group of readers or one writer. Every change to the protected data requires write access.

Build the reader group

Use readers = 0, a semaphore lock initialized to 1 to protect that counter, and writelock initialized to 1 to protect the shared resource.

/* Acquire read access */
sem_wait(&lock);
readers++;
if (readers == 1)
    sem_wait(&writelock);
sem_post(&lock);

/* Release read access */
sem_wait(&lock);
readers--;
if (readers == 0)
    sem_post(&writelock);
sem_post(&lock);

A writer waits on writelock, changes the data, then posts writelock. It does not acquire the counter lock. The first reader takes writelock for the group, and the last reader returns it. A semaphore suits that handoff because its posting thread need not be the thread that originally waited.

Trace R1 entering: it raises readers to 1 and takes writelock. R2 raises the count to 2 without taking another permit. Writer W now blocks on writelock. R1 leaves and lowers the count to 1. R2 leaves, lowers it to 0, and posts, allowing W to write alone.

The first reader may wait for writelock while holding lock. This does not create the bounded-buffer deadlock: the current writer needs no counter lock to finish and post writelock.

Fairness is a separate property

This design prefers readers. While the reader count stays positive, another reader can join the group ahead of a waiting writer. A steady stream of overlapping readers can keep the writer waiting indefinitely: writer starvation.

The basic design provides safety but no bound on how long a writer waits. More reader throughput is not the same as fair service.

Use the correct mode

A read lock cannot protect a write from other readers. Updating even a cache counter under read access can race with another reader. To upgrade in this basic design, release read access, acquire write access, and recheck the condition. Waiting for write access while still counted as a reader can make the thread wait for itself forever.

POSIX provides pthread_rwlock_t, pthread_rwlock_rdlock(), pthread_rwlock_wrlock(), and pthread_rwlock_unlock(). Java offers ReentrantReadWriteLock; C++17 offers std::shared_mutex. These locks cost more bookkeeping than a plain mutex. Measure the workload: short sections or frequent writes can make a simple mutex as fast or faster.

An atomicity violation occurs when code relies on a group of accesses being indivisible, but another thread can act between them. Each individual access can look reasonable while the combined operation fails.

Find the gap after the check

Consider a shared log buffer:

/* T1 */
if (log->buf != NULL)
    write_out(log->buf);

/* T2 */
log->buf = NULL;

T1 can check a non-null pointer, pause, and resume after T2 clears it. T1 then passes null to write_out(). The intended guarantee was not just a valid check; it was that the checked value stayed usable through the call.

Protect the check and use together, and protect the competing assignment with the same mutex:

/* T1 */
lock(&m);
if (log->buf != NULL)
    write_out(log->buf);
unlock(&m);

/* T2 */
lock(&m);
log->buf = NULL;
unlock(&m);

T2 now runs either before or after T1's whole operation. Giving each thread its own lock does not help: both could hold their separate locks simultaneously. Locking only T1 leaves T2 free to enter the gap.

A valid test can still lead to an invalid balance

Start with balance 50. Two threads each intend to withdraw 30 only if enough remains. Both can read 50 and pass balance >= 30 before either acts. If the withdrawals are then applied, the balance can become −10. Protecting the test and subtraction together lets the first withdrawal leave 20; the next thread sees 20 and refuses.

Even atomic loads and atomic subtractions do not make that pair one transaction. Another thread can act between the atomic check and the atomic change. One lock around the entire decision and change enforces the required boundary.

The same issue appears in count++: loading, adding, and storing are separate stages. Two threads can load the same old value and store the same incremented value, losing an update. A lock around the increment or an atomic fetch-and-add performs the required update safely.

Use evidence without overgeneralizing

Lu and colleagues examined 105 fixed concurrency bugs in MySQL, Apache, Mozilla, and OpenOffice in a 2008 study. Of these, 74 were non-deadlock bugs and 31 were deadlocks. Atomicity and order violations accounted for 97% of the non-deadlock sample. These are findings about that studied sample, not a percentage guaranteed for every codebase.

About 92% of the studied bugs could be triggered by controlling the order of at most four memory accesses. A small interleaving table can therefore be more revealing than thousands of successful ordinary runs. ThreadSanitizer helps find executed data races, but a logical atomicity bug can remain even when every individual access is synchronized. Test the whole operation's invariant, such as “a successful withdrawal never overdraws the balance.”

An order violation means operation A must happen before operation B, but the program provides no synchronization that guarantees it. Mutual exclusion alone cannot choose which operation goes first.

A thread can run immediately

Suppose a creator stores a newly created worker record in a shared pointer, while the worker starts by using that pointer:

/* Creator */
worker = thread_create(worker_main);

/* New worker */
use(worker->state);

The worker may run before thread_create() returns and before the assignment completes. The creator's source-code order says nothing about when the new thread gets CPU time. A successful run simply means the creator happened to win that race.

Publish readiness after initialization

Add ready = 0, mutex m, and condition variable c. The creator keeps the mutex while it assigns the pointer and publishes readiness:

/* Creator */
lock(&m);
worker = thread_create(worker_main);
ready = 1;
signal(&c);
unlock(&m);

/* Worker, before using worker */
lock(&m);
while (ready == 0)
    wait(&c, &m);
unlock(&m);
use(worker->state);

If the worker reaches the mutex first, it cannot pass the readiness test until the creator has published the record. If it arrives later, ready remembers that initialization finished. Keep the record alive while the worker uses it, and synchronize any later changes.

A semaphore initialized to 0 offers a shorter handoff: the creator posts after assigning the pointer, and the worker waits before using it. For a result that exists only after a thread finishes, joining that thread before reading its result establishes the needed order. Freeing an object likewise must wait until its users finish, for example through joins or a correctly synchronized reference count.

Why timing changes do not fix it

Adding sleep(1) or sched_yield() only changes the chance of the desired schedule. A slower or loaded system can still let the consumer proceed too early. A mutex around each operation prevents overlap but still allows the use to acquire the mutex before initialization.

In Lu and colleagues' study, about one third of the non-deadlock bugs were order violations, and about 73% of the non-deadlock bugs were not fixed by merely adding or changing locks. Before choosing a primitive, name the operation that must finish and the operation that must wait. That dependency determines where the post, signal, or join belongs.

A set of threads is deadlocked when each waits for something only another thread in the set can provide. No member can continue and perform the action that releases the others. The program may work in many schedules before one unlucky ordering exposes the cycle.

Build the two-lock failure

T1 acquires L1 and next requests L2. T2 acquires L2 and next requests L1. If T1 takes L1, then T2 takes L2, both second acquisitions block. Each thread holds exactly the resource its partner needs.

This can hide inside ordinary functions. If transfer(a, b) locks a and then b, simultaneous calls transfer(x, y) and transfer(y, x) can acquire the account locks in opposite orders. Encapsulation makes a call convenient but can conceal the locks it takes.

Identify all four conditions

All four conditions are necessary. Designing out any one of them prevents resource deadlock. The presence of exclusive locks and nested acquisition alone does not establish that a particular execution has reached a cycle.

Read a wait-for graph

Draw a node per thread. Draw T → U when T waits for a resource U holds. With single-instance resources such as exclusive locks, a cycle identifies deadlock.

For T1 holding A and waiting for B, T2 holding B and waiting for C, and T3 holding C and waiting for A, the graph is T1 → T2 → T3 → T1. All three are stuck. If T3 instead requests a free lock D, it can finish and release C, allowing T2 and then T1 to proceed. A chain is not a cycle.

When resource types have multiple interchangeable instances, a cycle alone is insufficient: an additional instance may become available. Use resource counts and outstanding requests to assess that case.

Dining philosophers and related failures

Five philosophers share five forks arranged in a circle. Each needs both neighboring forks. If all pick up their left fork first, all can wait for their right fork forever. Reversing one philosopher's acquisition order breaks the cycle. Limiting admission to four philosophers also prevents the all-five holding pattern; at least one admitted philosopher can obtain both forks.

Starvation means one thread waits indefinitely while others progress. Livelock means threads run and react but repeatedly fail to make progress. A deadlocked set is blocked. One thread can even deadlock itself by locking a normal, non-recursive mutex it already holds. Semaphores and condition variables can create dependencies too: a waiter holding a lock needed by its signaler can close a cycle without a second explicit lock acquisition.

Prevention changes the design so a necessary deadlock condition cannot arise. Lock ordering is often the clearest approach because it attacks the circular dependency directly.

Give every lock an order

Assign unique keys to locks and always acquire lower keys before higher ones. For account transfers, sort the account identifiers before locking. Both transfer(x, y) and transfer(y, x) then acquire the same account first. If the identifiers name the same account, acquire its lock once.

A cycle would require the keys to keep increasing around the circle and return to the starting key, which is impossible. Every acquisition path must follow the rule. One helper that reverses the order restores the risk. Linux's lockdep tracks observed locking dependencies and reports potentially unsafe orders.

Acquire all or acquire none

A strict way to remove hold-and-wait is to grant a thread its complete resource set in one step, or grant nothing. It never holds a partial set while waiting for the remainder. This requires knowing the needed resources in advance and can reduce concurrency.

A related protocol serializes acquisition sequences with a global prevention lock:

lock(&prevention);
lock(&L1);
lock(&L2);
unlock(&prevention);
/* use L1 and L2, then release them */

All threads must finish acquiring their full set under that global lock, and resource release must not require acquiring it. One thread may still hold L1 while waiting for L2, so this does not literally remove hold-and-wait. It prevents other threads from starting a competing partial acquisition. No holder can be midway through a second competing acquisition sequence. Holding locks earlier and serializing acquisition are the costs.

Give up and retry

pthread_mutex_trylock() returns immediately with EBUSY when a lock is unavailable. A thread can acquire L1, try L2, and release L1 if the attempt fails. It must undo other partial acquisitions before retrying too.

Two threads can repeatedly collide, back off, and retry together. That is livelock: both execute, but neither finishes. Random backoff reduces repeated collisions; it does not turn the retry loop into a fairness guarantee.

Replace a lock with an atomic operation

Compare-and-swap (CAS) changes a location only if it still matches an expected value. Conceptually, an atomic-add retry loop reads the old value, attempts to replace it with old plus the increment, and retries if another thread changed it first. Actual C implementations use atomic types and atomic operations for the read as well as the update.

Removing lock acquisition removes lock deadlock from that operation. A lock-free algorithm guarantees system-wide progress, but one thread may keep losing its retries. General lock-free structures also need careful memory-lifetime design.

Avoidance checks whether a proposed request leaves a way for every thread to finish. It permits the usual resource-use patterns, but delays requests that destroy the remaining safe completion orders.

Safe is a promise of a possible order

A safe sequence orders threads so each can obtain its remaining maximum demand from the resources currently free plus those earlier threads release. An unsafe state lacks such a guaranteed order. It need not already be deadlocked: threads might request less than their maximum or release resources early.

Scheduling can also avoid dangerous overlap by ensuring two conflicting tasks do not enter their resource-use phases together. Simply placing both on one CPU is insufficient because they can still be preempted and interleave while holding resources. The required guarantee is nonoverlap of the conflicting phases.

Set up the banker's tables

For each resource type, track Available. For each thread, track Max, Allocation, and Need = Max - Allocation. Compare vectors component by component, never by their summed totals.

Use resource totals (7, 5, 6):

Allocations total (4, 3, 4), leaving Available = (3, 2, 2).

Work through the safety test

Set Work to Available. Choose an unfinished thread whose Need fits Work, pretend it finishes, and add its Allocation back to Work.

1. T1 fits (3, 2, 2). Returning (2, 0, 1) gives Work (5, 2, 3).
2. T0 fits. Returning (1, 1, 0) gives (6, 3, 3).
3. T2 fits. Returning (1, 1, 2) gives (7, 4, 5).
4. T3 fits. Returning (0, 1, 1) gives (7, 5, 6).

Every thread finishes in this simulation, so the state is safe. Work increases by Allocation, not Max: the extra resources temporarily granted for completion are returned as well, giving a net gain equal to what the thread originally held.

Pretend to grant, then test again

A request must fit both the thread's Need and Available. Then subtract it from Available, add it to Allocation, subtract it from Need, and run the safety test on that tentative state.

From the original table, T2 requesting (1, 0, 1) leaves Available (2, 2, 1). T1 can still go first, followed by T0, T2, and T3, so it is safe.

Instead, T3 requesting (2, 1, 1) leaves Available (1, 1, 1). T3's remaining Need is (2, 0, 1). No thread fits: T0 needs 4 of A, T1 needs 2 of B, T2 needs 2 of C, and T3 needs 2 of A. Delay this request despite the currently free resources.

Every later request needs the same test. Avoidance needs declared maximum demands and a known resource model, making it more suitable for predictable specialized systems than general application workloads.

A system can allow deadlock to form, detect it, and recover. This accepts occasional lost work in exchange for fewer restrictions on ordinary resource requests. Detection is useful only when there is a viable recovery action.

Find blocked cycles

For single-instance resources, maintain a wait-for graph and search for a cycle, for example with depth-first search. Suppose the edges are T1 → T2, T2 → T3, T3 → T1, and T4 → T2. T1, T2, and T3 are the cycle. T4 is blocked behind it; T4's own execution cannot release a resource that breaks that cycle.

With multiple instances, a cycle is insufficient. Use Available, Allocation, and each thread's current outstanding Request. Start Work at Available. Repeatedly find a request that fits, simulate completion, and add that thread's Allocation to Work. Unlike avoidance, this test uses what threads are waiting for now, not their possible future maximum demand.

The standard resource detector initially sets aside threads holding no resources: they cannot contribute held resources to a resource cycle. Among resource holders, those left unfinished by the test are deadlocked under the model. Other threads can still be unable to progress because they depend on that set. Keeping the cycle and its blocked dependents separate helps choose an effective recovery victim.

Recover without corrupting shared state

A system may terminate one or more processes, reclaim resources with rollback to a checkpoint, or restart. Choose victims by recovery cost, priority, work already done, and resources held. After removing one victim, check again: several independent cycles may require more than one recovery action.

Terminating an arbitrary thread is not enough if it leaves a mutex locked or a shared structure half changed. Recovery must release or reconstruct resources and restore valid state. Transaction systems can abort a deadlocked transaction because rollback is part of their design. An ordinary application often needs a controlled process restart instead.

Interpret timeouts carefully

pthread_mutex_timedlock() can return ETIMEDOUT after a deadline. A watchdog can reset a device that stops reporting progress. Both detect excessive waiting; a long wait can also come from slow I/O or scheduling. A timeout is evidence to investigate or recover from, not a unique diagnosis of a cycle.

Linux and Windows do not generally find and repair cycles among an application's own locks. The program must implement its chosen strategy. If recovery repeatedly selects the same work as a victim, that work may starve even though each individual deadlock is broken.

An event loop waits for events and dispatches short handlers on one thread. The program explicitly chooses which ready event to handle next. Node.js and nginx use event-based designs to serve many connections without assigning a dedicated thread to each connection.

while (1) {
    events = get_events();
    /* handle each ready event, then return to the loop */
}

Synchronous handlers on the same loop run one at a time. One handler's ordinary instructions are not interrupted by another handler on that loop. The loop still depends on handlers returning promptly.

Build and inspect select sets

select() accepts sets of descriptors to watch for reading, writing, and exceptional conditions, plus a timeout. Its nfds argument is one greater than the highest watched descriptor. Watching descriptors 3, 5, and 9 therefore needs nfds = 10, not 3.

FD_ZERO(&readset);
FD_SET(3, &readset);
FD_SET(5, &readset);
FD_SET(9, &readset);
int n = select(10, &readset, NULL, NULL, NULL);
/* If n > 0, test each watched descriptor with FD_ISSET. */

A null timeout waits for readiness; a zero timeout checks and returns immediately. select() overwrites the sets with the ready descriptors, so rebuild them before each call. Its positive return counts set bits across the returned sets; a descriptor ready in two sets counts twice. Zero means timeout; −1 means error.

Readiness is not data transfer. The program still calls read() or recv(). End of input can appear as readability; a read returning 0 means the peer has closed its sending side. Handle that result instead of repeatedly redispatching the same ended input.

Keep handlers short and non-blocking

Set sockets to O_NONBLOCK. When an operation cannot proceed, it returns −1 with errno set to EAGAIN or EWOULDBLOCK, allowing the handler to return to the loop. Readiness can change before the operation, so non-blocking mode also protects against an unexpected wait after a readiness report.

A blocking read inside a handler delays every queued event. With 100 queued requests and a 10 ms blocking disk read per handler, the last request waits about 990 ms before its own read begins; the batch takes about 1,000 ms. The thread spent most of that time waiting while ready work sat queued.

Choose a readiness interface

select() and poll() examine the supplied watched set on each call, so their work grows with its size. Linux offers epoll; FreeBSD and macOS offer kqueue. Watching only a few descriptors does not make a high descriptor value safe for a fixed-size fd_set.

Network readiness tells a loop when it can try I/O. Regular disk files are different: select() and poll() report them ready even when accessing their data still waits for storage. To keep serving other events, submit work asynchronously and handle its result later.

Submit, wait elsewhere, collect

POSIX asynchronous I/O stores a request in struct aiocb. Important fields are aio_fildes for the file descriptor, aio_offset for the file position, aio_buf for the destination, and aio_nbytes for the requested length.

/* cb describes a read request */
aio_read(&cb);
/* Return to other work. Later: */
int status = aio_error(&cb);
/* EINPROGRESS: still running; 0: succeeded; otherwise an error. */
/* After completion, aio_return(&cb) collects its result. */

aio_read() queues the request and returns. Completion is a separate event. When aio_error() indicates completion, aio_return() provides the result, such as bytes read after success. A request can fail, and a successful read can return fewer bytes than requested. The request record and its buffer must remain valid while the operation is outstanding.

Repeatedly scanning every request in a tight loop wastes CPU time. aio_sigevent can configure a completion signal or callback. Linux io_uring uses submission and completion queues; Windows I/O completion ports provide completion-based dispatch. These interfaces let the program act on completed work without constantly retrying every unfinished request.

Carry state across the gap

A blocked thread keeps its function's local variables on its stack. An event handler that submits I/O and returns must save what the later handler needs. This explicit bookkeeping is manual stack management; the saved state is a continuation.

Suppose a server reads file descriptor 12 for a client on socket 7. At submission it saves a record associating that read request with socket 7 and its response state. When completion arrives, the loop finds the record, checks the read result, and continues sending the response to the correct client. Separate records keep several outstanding requests from mixing up their destinations.

The continuation should be tied to the particular operation, not just an identifier that might later be reused. Keep the client reference valid until the completion is handled, and remove the record when the task finishes. Those lifetime details replace assumptions a straight-line blocking function could keep on its stack.

Readable syntax can hide a suspension

Callbacks, promises, and async/await automate much of this state saving. In JavaScript, const data = await readFile(path); suspends that function while its I/O is pending. Other loop work can run, and the function resumes later with its local state restored.

Asynchronous means the caller can continue before the operation completes. It does not mean that its handlers run on several CPU cores at once. It also does not make CPU-heavy code after an await yield automatically: that code still occupies its executing thread until it returns or suspends again.

An event loop is a good fit for many mostly idle connections with small bursts of work. A thread-based design keeps a task's control flow and stack together. The best choice depends on waiting time, CPU work, memory, and how the code will evolve.

Compare the work each design carries

A chat server with 50,000 mostly idle connections can benefit from event records instead of a dedicated thread stack per connection. An image processor doing heavy computation per request needs enough workers to use the available cores; one busy loop cannot make those computations parallel.

Hidden waits still matter

A handler can stall without an obvious blocking API call. Accessing a page that has been paged out may trigger a disk read. During that page fault, the loop thread waits. mlock() can keep needed pages resident when the system permits the requested locked-memory amount. Simply removing explicit blocking calls does not eliminate every source of delay.

Code changes can introduce another hidden wait. If a formerly immediate helper starts fetching data, an event-based caller must split its work around a continuation or offload the call. A blocking thread's stack already stores where to resume and the local state it needs.

Combine the strengths

A hybrid design keeps network readiness on the event loop and sends blocking or CPU-heavy tasks to a worker pool. Completions return to the loop for response handling. Node.js uses libuv's thread pool for file system operations, so an asynchronous interface can be implemented by background threads.

To use multiple cores, a server can run one event loop per core in separate threads or processes. If those loops share mutable data, they need the usual locks or another synchronization protocol. The no-lock benefit applies to synchronous handlers on one loop, not every part of an event-based server.

A task can interleave across await

Suppose one unit of stock remains. A handler checks availability, awaits payment, then subtracts stock. While it is suspended, another handler can check the same stock and also begin payment. Both checks may succeed before either subtraction. No two synchronous handlers run simultaneously, yet the overall check-and-update operation is not atomic.

Reserve stock as one synchronized state change before yielding, with a release path if payment fails, or recheck under a protocol that prevents a second sale. A mutex held across a long wait can create other progress problems, so design the state transition and its recovery explicitly. Event code still needs reasoning about which facts remain true across each suspension.