Concurrency, Synchronisation and Deadlocks

Race conditions, critical sections, mutexes and semaphores, producer–consumer, and deadlock conditions, prevention, and detection.

Est. 45 min Updated Suggest a fix
// Part 01 — Interleaving

Concurrency Makes Operation Order Observable

Concurrent tasks can interleave instructions. The source expression counter += 1 is conceptually a read, add, and write; two threads can both read 7, both calculate 8, and both store 8. One increment is lost. A race condition occurs when the result depends on timing or interleaving in a way the program has not safely controlled. A data race is a particular unsynchronized conflict over shared memory; language memory models can make its consequences more serious than just a lost update.

A critical section accesses shared state. Correct synchronization aims for mutual exclusion where necessary, progress, and bounded waiting under stated assumptions. Protect the invariant, not merely one line that looks suspicious: all reads and writes that depend on the invariant need a consistent protocol.

⚠️ Important
Adding a sleep is not synchronization. It changes timing and may hide a bug on one run while leaving the race intact.
// Part 02 — Mutexes

Use a Mutex to Protect an Invariant

A mutex has ownership: one thread locks it, performs a short critical section, then unlocks it. Other threads wait until they can acquire it. Keep the protected work small, avoid I/O while holding a lock where practical, and use a consistent lock order when several mutexes are needed.

counter.c
c
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

enum { THREADS = 4, ITERATIONS = 100000 };
static long counter = 0;
static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

static void *increment(void *unused) {
    (void)unused;
    for (int i = 0; i < ITERATIONS; ++i) {
        pthread_mutex_lock(&lock);
        ++counter;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t threads[THREADS];
    for (int i = 0; i < THREADS; ++i)
        if (pthread_create(&threads[i], NULL, increment, NULL) != 0) return 1;
    for (int i = 0; i < THREADS; ++i)
        if (pthread_join(threads[i], NULL) != 0) return 1;
    printf("counter=%ld
", counter);
    pthread_mutex_destroy(&lock);
    return 0;
}

Compile on a POSIX platform with a C compiler and its pthread support, for example cc counter.c -pthread -o counter. Production code should also handle every lock and thread API error, including cleanup if thread creation fails partway through.

// Part 03 — Semaphores

A Semaphore Counts Available Permits

A semaphore maintains a count. A wait operation consumes a permit or blocks; a post operation makes one available and may wake a waiter. A binary semaphore can coordinate access, but unlike a mutex it generally does not express ownership in the same way. Use a mutex for exclusive ownership of an invariant and a counting semaphore when the count itself models available resources or queued work.

PrimitiveModelsTypical use
MutexExclusive ownershipProtect a shared data invariant
Counting semaphoreNumber of available permitsBounded resource pool or queued items
Condition variableA predicate may have changedWait for state while releasing a mutex
🎯 Pro Tip
With a condition variable, wait in a loop that checks the predicate while holding the mutex. A wakeup is a reason to check again, not proof the condition is true.
// Part 04 — Producer–consumer

Coordinate a Bounded Buffer

For a buffer of capacity N, a producer must wait when it is full and a consumer when it is empty. A standard semaphore design starts with empty=N, full=0, and a mutex for the buffer indexes and contents. Producer order is wait(empty), lock, insert, unlock, post(full); consumer order is wait(full), lock, remove, unlock, post(empty). Reversing the permit logic can deadlock or corrupt the queue.

producer_consumer.py
python
from queue import Queue
from threading import Thread

work = Queue(maxsize=3)

def produce():
    for item in range(5):
        work.put(item)       # blocks while the bounded queue is full
    work.put(None)           # sentinel ends the single consumer

def consume():
    while True:
        item = work.get()    # blocks while empty
        try:
            if item is None:
                return
            print("processed", item)
        finally:
            work.task_done()

producer = Thread(target=produce)
consumer = Thread(target=consume)
consumer.start()
producer.start()
producer.join()
consumer.join()

Remove the accidental leading space before def produce when copying into a Python file. The standard Queue encapsulates synchronization; production pipelines also need shutdown, cancellation, error propagation, and a policy for overload.

// Part 05 — Deadlock

The Four Coffman Conditions

A deadlock is a set of tasks permanently waiting for resources held by one another. The classic Coffman conditions are all necessary for a resource-allocation deadlock: mutual exclusion (a resource is non-shareable), hold and wait (a task holds one resource while waiting for another), no preemption (resources cannot be forcibly taken), and circular wait (a cycle of dependencies exists).

Prevention breaks at least one necessary condition. Examples include imposing a global lock order to prevent cycles, requesting all needed resources before proceeding to avoid hold-and-wait, or making a resource shareable where the resource permits it. Each technique has costs: global ordering can constrain design, and preemption may be impossible for some resources.

📌 Real World Example
Thread A owns lock L1 and waits for L2; thread B owns L2 and waits for L1. The wait-for graph contains A → B → A. A global order requiring L1 before L2 prevents this cycle if every path follows the rule.
// Part 06 — Avoidance and diagnosis

Banker's Algorithm and Practical Lock Design

Avoidance differs from prevention: a system examines a proposed allocation and grants it only if the resulting state is safe—there exists an order in which every process can finish with available resources plus resources released by earlier finishers. Banker's algorithm models maximum claims and is a classic teaching method. It requires known resource types and maximum demands, assumptions often unsuitable for general-purpose application locks.

For one resource type, let Available=3; remaining Need be P0=4, P1=2, P2=3; and current Allocation be P0=2, P1=2, P2=3. P1 can finish with the available units and release its allocation of 2, so Work becomes 5. P2 can then finish and release 3, so Work becomes 8; P0 can finish afterward. Thus P1 → P2 → P0 is a safe sequence. A request larger than available is delayed; a request within available is still denied if tentatively granting it leaves no safe sequence. Real Banker examples track vectors for several resource types and compare each Need vector with the Work vector component by component.

Banker's safety check: the process order is a witness that resources can be returned without deadlock.
CheckQuestionDecision
1. Request boundsDoes request exceed declared remaining Need?Reject an invalid claim
2. AvailabilityIs request no greater than Available?Otherwise the process waits
3. Tentative allocationSubtract from Available; add to Allocation; reduce NeedDo not commit yet
4. Safety testCan some unfinished process satisfy Need ≤ Work?Pretend it finishes and returns its allocation
5. Commit or roll backCan all processes finish in some order?Grant if safe; otherwise restore prior state

Deadlock is not the same as starvation (a task keeps losing access) or livelock (tasks keep reacting but do not make useful progress). For application code, timeouts, lock-order discipline, narrow critical sections, and diagnostic stacks are practical defenses. A timeout detects a prolonged wait; it does not automatically make recovery safe.

bash
# Find process/thread state and inspect a hang when permitted
ps -eLo pid,tid,stat,wchan:24,comm | head -n 25
top -H

# A debugger can show thread stacks for a process you own
# gdb -p <pid> then: thread apply all bt
  1. List each resource and its current owner.
  2. Draw a wait-for edge from each waiting task to the task holding the resource.
  3. Look for a cycle and verify the four Coffman assumptions.
  4. Choose prevention, safe-state avoidance, timeout, or recovery based on the resource and failure model.
// Part 07 — Pitfalls

Answer with Precision

Giving a memorized slogan without assumptions

Why: A scheduling or replacement answer changes with the workload and model.

Fix: State arrivals, frame count, preemption, and tie-breaking before calculating.

Confusing two neighboring concepts

Why: Similar terms describe different layers or guarantees.

Fix: Define each concept and provide one contrast before adding detail.

Treating an observation as a universal guarantee

Why: A command samples one system at one moment.

Fix: Describe the observation limits and what additional evidence is needed.

Ignoring trade-offs and failure modes

Why: An idealized definition omits the engineering constraints.

Fix: Name one cost, edge case, or recovery path for every mechanism.

// Part 08 — Practice

Apply It to a Small System

Practice

Trace, calculate, and explain

  1. Draw the state, resource, or address transitions for a realistic workload, including a wait or failure path.
  2. Run a relevant Linux observation command from this lesson and explain what it can and cannot prove.
  3. Implement the small C or Python exercise, change one input, and predict the result before executing it.
  4. Explain one design choice with a precise invariant, a concrete example, and a trade-off.

Hint: Write assumptions first, then use a trace or calculation to support your explanation.

🎯 Key Takeaways

  • ✓Concurrent execution permits interleavings; shared-state invariants need explicit synchronization.
  • ✓A mutex expresses ownership and mutual exclusion; semaphores model counted permits or queued work.
  • ✓Producer–consumer requires coordinated full/empty state and safe access to the buffer.
  • ✓Deadlock requires mutual exclusion, hold-and-wait, no preemption, and circular wait together.
  • ✓Prevention breaks a necessary condition; avoidance grants only allocations that preserve a safe state.
  • ✓Starvation and livelock are distinct progress failures, and a timeout is detection rather than automatic repair.

Next

What comes next

Once threads coordinate safely, see how the OS gives them isolated, efficient memory.

Lesson 06 · Memory Management and Virtual Memory →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...