Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Classic synchronisation problems

Classic synchronization problems (producer-consumer, readers-writers, dining philosophers) show how to coordinate concurrent processes/threads to avoid races, ensure mutual exclusion, progress and bounded waiting; engineers use these patterns to design correct concurrent systems and pick appropriate

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Concurrent threads and processes share resources in modern operating systems and embedded devices. Classic synchronization problems are canonical examples engineers use to design, test and explain synchronization mechanisms (mutexes, semaphores, monitors). Understanding them helps you avoid race conditions, deadlocks and starvation in real systems.

Key ideas

  • Critical section — a section of code in which a thread accesses shared resources (shared variables, buffers, devices) that must not be concurrently accessed by other threads. Always define the critical section precisely when designing a solution.

  • Mutual exclusion — the property that at most one thread is executing its critical section at any time. Formal requirement: for any time instant t, the number of threads executing their critical section must be ≤ 1.

  • Progress — if no thread is in its critical section and some threads wish to enter, the selection of the thread that will enter next cannot be postponed indefinitely (system must make progress). Only threads that are trying to enter their critical section may participate in the decision (threads in their remainder section do not influence it).

  • Bounded waiting (no starvation) — there exists a bound on the number of times other threads are allowed to enter their critical section after a thread has made a request to enter, before that request is granted.

  • Semaphore — an abstract integer variable supporting two atomic operations: wait(P) (also called P or down) and signal(V) (also called V or up). A semaphore is either counting (integer may be >1) or binary (restricted to 0 or 1). Semantics (Dijkstra): wait atomically decrements; if the resulting value < 0, the caller blocks. signal atomically increments and, if there are waiters (i.e., resulting value ≤ 0), wakes one waiting thread. In POSIX, sem_wait blocks when the value is 0 and otherwise decrements; both models are equivalent in effect for correct solutions.

  • Monitor — a high-level synchronization construct that groups shared data and procedures with automatic mutual exclusion; condition variables inside monitors allow threads to wait and be signalled. In most real systems (Mesa semantics), calling wait on a condition releases the monitor lock; signal marks a waiter ready while the signaller keeps the lock, so the awakened thread must re-acquire the lock and re-check the condition predicate.

Classic problems (each: statement, assumptions, common solution sketch):

  1. Producer–Consumer (bounded-buffer)
  • Statement: Producers create data items and put them into a fixed-size buffer; consumers remove items from the buffer. Constraint: producers must not put into a full buffer and consumers must not remove from an empty buffer. Goal: synchronize so that no race occurs on buffer indices and buffer capacity is respected.
  • Assumptions: buffer of size N, atomic semaphore operations, producers/consumers run concurrently, shared buffer and indices require mutual exclusion.
  • Canonical solution uses three synchronization objects: a mutex for buffer access, a counting semaphore full (items available) initial 0, and a counting semaphore empty (free slots) initial N.
  • Draw: draw a rectangle labelled "buffer" with N slots, arrows from Producer to buffer (with label wait(empty)), arrows from buffer to Consumer (with label wait(full)), and a small lock symbol on buffer labelled mutex.
  1. Readers–Writers
  • Statement: Shared data can be read by multiple readers simultaneously but writing requires exclusive access. Two classical variants: first readers-preference (readers may starve writers) and writers-preference (writers prioritized, readers may be delayed).
  • Assumptions: atomic counters for number of readers, semaphores/mutexes for exclusive access, fairness not automatic unless added.
  • First readers-writers solution (readers-preference) uses a mutex protecting a reader count and a semaphore wrt (initial 1) to block writers. When first reader enters it does wait(wrt); last reader leaving does signal(wrt).
  • Diagram: show shared data box; multiple reader arrows labelled concurrent; writer arrow labelled exclusive (blocked by wrt semaphore).
  1. Dining Philosophers
  • Statement: N philosophers sit around a round table with N forks (one between each pair). Each philosopher needs two forks (left and right) to eat. Goal: allow eating without deadlock and ideally without starvation.
  • Assumptions: each fork is a lock/semaphore; philosophers alternate thinking and hungry states.
  • Common solutions: (a) resource hierarchy (number forks 1..N; each philosopher picks lower-numbered fork first then higher-numbered — breaks cycle and prevents deadlock); (b) allow at most N-1 philosophers to try to pick forks using a semaphore with initial value N-1 (prevents circular wait); (c) use a waiter or arbiter that grants forks only when both available.
  • Diagram: circle of 5 philosophers labelled P0..P4 with forks F0..F4 between them; arrows from philosopher to forks when eating.

For each solution, state correctness arguments briefly: e.g., resource hierarchy prevents circular wait because requests are strictly ordered; semaphore N-1 prevents all philosophers from holding one fork (so some philosopher can get both) — explain assumptions.

Formulas

wait(S) — atomic operation that decrements semaphore S; if resulting value < 0, the calling thread blocks. Symbol: S is a semaphore (unit: abstract, no SI unit). Applies when using counting semaphores.

signal(S) — atomic operation that increments semaphore S; if there are waiting threads, one is unblocked. Symbol: S is a semaphore.

mutex_lock(m) / mutex_unlock(m) — lock and unlock operations on a mutual exclusion lock (binary). Symbol: m is mutex.

initial(empty) = N — empty is a counting semaphore initialised to buffer capacity N (applies to producer–consumer bounded buffer).

initial(full) = 0 — full counts filled slots in buffer.

readers_count — integer counter (unit: count) used in readers–writers solutions; incremented/decremented under a protecting mutex.

Note: these are semantic operations; POSIX names are sem_wait, sem_post for semaphores, pthread_mutex_lock, pthread_mutex_unlock for mutexes.

Worked examples

Example 1 — Model answer: Explain and write the semaphore solution for producer–consumer and show why it preserves mutual exclusion, avoids overflow/underflow, and provides progress.

Model answer (theory):

  • Use semaphores empty = N, full = 0, and mutex = 1 (binary). Producer: wait(empty); wait(mutex); add item; signal(mutex); signal(full); Consumer: wait(full); wait(mutex); remove item; signal(mutex); signal(empty);
  • Mutual exclusion: protected by mutex around buffer update.
  • No overflow/underflow: wait(empty) blocks producer when no empty slot; wait(full) blocks consumer when no item.
  • Progress: when buffer neither full nor empty, semaphores allow at least one of producer/consumer to proceed; blocked threads are waiting on semaphores which reflect resource availability.

Example 2 — C program (Producer–Consumer using POSIX threads and semaphores)

Code (save as prodcons.c):

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>

#define BUFFER_SIZE 5
#define PRODUCE_COUNT 10

int buffer[BUFFER_SIZE];
int in = 0, out = 0;

sem_t empty; // counts empty slots
sem_t full;  // counts full slots
pthread_mutex_t mutex;

void *producer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < PRODUCE_COUNT; i++) {
        sem_wait(&empty);
        pthread_mutex_lock(&mutex);
        buffer[in] = i; // produce item i
        printf("Producer %d produced %d at index %d\n", id, i, in);
        in = (in + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&full);
        usleep(100000); // 0.1s to allow interleaving
    }
    return NULL;
}

void *consumer(void *arg) {
    int id = *(int *)arg;
    for (int i = 0; i < PRODUCE_COUNT; i++) {
        sem_wait(&full);
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        printf("Consumer %d consumed %d at index %d\n", id, item, out);
        out = (out + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);
        usleep(150000); // 0.15s
    }
    return NULL;
}

int main() {
    pthread_t p, c;
    int pid = 1, cid = 1;
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);
    pthread_mutex_init(&mutex, NULL);

    pthread_create(&p, NULL, producer, &pid);
    pthread_create(&c, NULL, consumer, &cid);

    pthread_join(p, NULL);
    pthread_join(c, NULL);

    pthread_mutex_destroy(&mutex);
    sem_destroy(&empty);
    sem_destroy(&full);
    return 0;
}

Compile: gcc -pthread prodcons.c -o prodcons and run ./prodcons.

Sample output (one possible run):

Producer 1 produced 0 at index 0 Consumer 1 consumed 0 at index 0 Producer 1 produced 1 at index 1 Producer 1 produced 2 at index 2 Consumer 1 consumed 1 at index 1 Producer 1 produced 3 at index 3 Consumer 1 consumed 2 at index 2 Producer 1 produced 4 at index 4 Consumer 1 consumed 3 at index 3 Producer 1 produced 5 at index 0 Consumer 1 consumed 4 at index 4 Producer 1 produced 6 at index 1 Consumer 1 consumed 5 at index 0 Producer 1 produced 7 at index 2 Consumer 1 consumed 6 at index 1 Producer 1 produced 8 at index 3 Consumer 1 consumed 7 at index 2 Producer 1 produced 9 at index 4 Consumer 1 consumed 8 at index 3 Consumer 1 consumed 9 at index 4

(Note: actual interleaving may vary; the program preserves buffer bounds and mutual exclusion.)

Example 3 — Model answer: Readers–Writers (first readers-preference)

Model answer (theory):

  • Shared objects: mutex (protect readers_count), wrt (binary semaphore for writers). Initialize mutex = 1, wrt = 1, readers_count = 0.
  • Reader enters: wait(mutex); readers_count++; if (readers_count == 1) wait(wrt); signal(mutex); // read; wait(mutex); readers_count--; if (readers_count==0) signal(wrt); signal(mutex);
  • Writer: wait(wrt); // write; signal(wrt);
  • Explanation: First reader locks writers out by waiting on wrt. Additional readers do not block. Last reader signals wrt so writers can proceed. This gives readers priority and can starve writers.

C skeleton (readers/writers behaviour) — full runnable program omitted for brevity; in exams give the algorithm and correctness argument.

Example 4 — Dining Philosophers short model answer

  • Resource hierarchy: number forks 0..N-1; philosopher i picks fork min(i,(i+1)%N) first, then the other. This imposes an order on resource acquisition, preventing circular wait and so preventing deadlock. State assumptions and note this does not guarantee fairness.

Common mistakes

  • Claiming that mutual exclusion alone solves starvation — it does not; you must prove bounded waiting.
  • For dining philosophers: saying "pick the left fork then the right fork" without addressing circular wait — that naive solution deadlocks when all pick left fork.
  • Not stating initial values of semaphores (examiners often dock marks for missing initialisation).

For your exam

Question types: definitions (state constraints: mutual exclusion, progress, bounded waiting), derivations/proofs (show why a solution enforces properties or show deadlock freedom), short notes (compare semaphore vs monitor), pseudo-code (full algorithm for producer–consumer/readers–writers), C programs (small pthreads example), and diagrams (buffer, table of philosophers).

What full-mark answers include:

  • Precise problem statement and assumptions.
  • Correct initialization of synchronization primitives and their exact code lines in the protocol.
  • Proof sketch for mutual exclusion, progress and bounded waiting where required.
  • Drawings: for producer–consumer draw buffer slots, for dining philosophers draw circle and numbered forks, for readers–writers draw concurrency vs exclusivity boxes.

Quick check

  1. Name the three classical requirements for a correct critical-section solution.
  2. In the producer–consumer solution using semaphores, what are the initial values of empty and full for a buffer of size N?
  3. Give one simple way to prevent deadlock in the dining philosophers problem.

Answers: 1) Mutual exclusion, progress, bounded waiting. 2) empty = N, full = 0. 3) Enforce a resource hierarchy (pick lower-numbered fork first) or use a semaphore limiting to N-1 philosophers.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?