Concurrency, Synchronisation and Deadlocks
Race conditions, critical sections, mutexes and semaphores, producer–consumer, and deadlock conditions, prevention, and detection.
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.
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.
#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.
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.
| Primitive | Models | Typical use |
|---|---|---|
| Mutex | Exclusive ownership | Protect a shared data invariant |
| Counting semaphore | Number of available permits | Bounded resource pool or queued items |
| Condition variable | A predicate may have changed | Wait for state while releasing a mutex |
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.
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.
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.
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.
| Check | Question | Decision |
|---|---|---|
| 1. Request bounds | Does request exceed declared remaining Need? | Reject an invalid claim |
| 2. Availability | Is request no greater than Available? | Otherwise the process waits |
| 3. Tentative allocation | Subtract from Available; add to Allocation; reduce Need | Do not commit yet |
| 4. Safety test | Can some unfinished process satisfy Need ≤ Work? | Pretend it finishes and returns its allocation |
| 5. Commit or roll back | Can 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.
# 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- List each resource and its current owner.
- Draw a wait-for edge from each waiting task to the task holding the resource.
- Look for a cycle and verify the four Coffman assumptions.
- Choose prevention, safe-state avoidance, timeout, or recovery based on the resource and failure model.
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.
Apply It to a Small System
Practice
Trace, calculate, and explain
- Draw the state, resource, or address transitions for a realistic workload, including a wait or failure path.
- Run a relevant Linux observation command from this lesson and explain what it can and cannot prove.
- Implement the small C or Python exercise, change one input, and predict the result before executing it.
- 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.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
