Synchronization โ€” Easy Exam Guide Unit u07 (critical sections, semaphores, classic problems). This is the highest-value topic (~5 pts of code every exam). ๐Ÿ”ด = comes a lot.

Written in simple (B1) English. Read it from top to bottom before the exam.

0How "synchronization" comes in the exam

This topic gives the most points. There is almost always a write-a-concurrent-program task (~5 points) plus one or two true/false questions. Three shapes:

The question you will seeHow oftenSection
๐Ÿ”ด Write a program with semaphores (turn a precedence graph into code, or build a primitive)almost every exam (~5 pts)ยง4
๐Ÿ”ด "Which outputs are possible?" โ€” trace threads that use semaphoresoftenยง3 + drills
๐Ÿ”ด True/false: critical section / TestAndSet / spinlock; or analyse a reader-writer / producer-consumer schemeoftenยง2, ยง5

1The critical section problem ๐Ÿ”ด

When two threads/processes touch the same shared data, the result can depend on the timing โ€” this is a race condition. Example: n++ is really "read n, add 1, write n". If two threads do it together, one update can be lost.

A critical section is the part of the code that uses the shared data. To be safe, only one thread may be inside it at a time = mutual exclusion.

A correct solution must have all three:
  1. Mutual exclusion โ€” only one thread in the critical section at a time.
  2. Progress โ€” if the section is free and someone wants in, one of them gets in (no deadlock). A thread outside the section must not block others.
  3. Bounded waiting โ€” a thread cannot be made to wait forever (no starvation).
while (TRUE) {
   entry code      // lock / prologue
   CRITICAL SECTION
   exit code       // unlock / epilogue
   non-critical section   // NOT protected
}

2Software & hardware locks ๐Ÿ”ด

Software (Peterson)

Simple flag tricks fail: a naive "test then set" is two steps, and a context switch between them lets both threads in (no mutual exclusion). Strict turn alternation causes starvation. The correct two-thread software solution is Peterson's algorithm (a flag[] + a turn variable) โ€” it gives all three properties, but it still busy-waits.

Hardware (TestAndSet)

The hardware way uses one atomic instruction that reads and sets a lock in a single step:

char TestAndSet(char *lock){
   char val = *lock;   // read the OLD value
   *lock = TRUE;       // set it TRUE
   return val;         // return the OLD value
}
// use:
while (TestAndSet(&lock));   // spin until lock was FALSE
CRITICAL SECTION
lock = FALSE;
โœ— Trap sentences
  • "Busy waiting is efficient / good for battery devices." No โ€” it wastes CPU.
  • "TestAndSet guarantees no starvation." No โ€” it does not give bounded waiting by itself.
  • The atomic line must be *lock = TRUE (dereference) and must return val (the old value).

3Semaphores ๐Ÿ”ด

A semaphore is a shared counter managed by the OS. Unlike a spinlock, a blocked thread is put in a queue and uses no CPU. It has two atomic operations:

Two useful facts
The counter can go negative; then |counter| = number of waiting threads. And the init value = the maximum number of threads allowed at once (so init 1 = a normal lock / mutex).

Binary semaphore = 0/1 = a mutex (for mutual exclusion). Counting semaphore = any value โ‰ฅ 0 (for counting resources or ordering).

POSIX API

sem_t s;
sem_init(&s, 0, value);   // value = initial counter; 0 = shared between threads
sem_wait(&s);             // P
sem_post(&s);             // V
sem_destroy(&s);
๐ŸŽฏ In the exam โ€” "which outputs are possible?"
You get 2โ€“3 threads with wait/signal on shared semaphores. Method: find which threads can start (their semaphore is > 0), then follow each signal to see who it unblocks. A semaphore that starts at 0 forces an order: the wait side must come after the matching signal.

4Precedence graphs โ€” the key write-code skill ๐Ÿ”ด the ~5-point task

A precedence graph says "task A must finish before task B starts". You turn each arrow into semaphores. The rule:

  1. Use one semaphore per arrow (or one per node), all init 0.
  2. After a task finishes, signal the semaphore of each outgoing arrow.
  3. Before a task starts, wait on the semaphore of each incoming arrow (so a node with 3 parents does 3 waits).
  4. The very first task has nothing before it โ†’ its semaphore is init 1 (so it can start).
  5. For a cyclic version (tasks loop forever), close the loop: the last node signals the first.
โ–ถ Example: P1 โ†’ {P2,P3,P4}; P2,P3,P6 โ†’ P5; P4 โ†’ P6; P5 โ†’ P1 (cyclic)
init(p1,1); init(p2,0); ... init(p6,0);   // only the start = 1

P1: wait(p1); ...; signal(p2); signal(p3); signal(p4);   // 3 children
P2: wait(p2); ...; signal(p5);
P3: wait(p3); ...; signal(p5);
P4: wait(p4); ...; signal(p6);
P6: wait(p6); ...; signal(p5);
P5: wait(p5); wait(p5); wait(p5); ...; signal(p1);   // 3 parents = 3 waits
Note: an arrow that is already implied by a path (e.g. P6โ†’P1 when P6โ†’P5โ†’P1 exists) is superfluous โ€” drop it.

5Classic problems ๐Ÿ”ด

Producer / Consumer (bounded buffer)

init(empty, SIZE); init(full, 0); init(mutex, 1);
Producer: wait(empty); wait(mutex); put(); signal(mutex); signal(full);
Consumer: wait(full);  wait(mutex); get(); signal(mutex); signal(empty);

Readers / Writers

Many readers can read together; a writer needs exclusive access. The first reader locks the writers out, the last reader unlocks them. Key trap: whichever group has precedence, the other group can starve (reader-precedence starves writers; writer-precedence starves readers).

Dining philosophers

5 philosophers, 5 forks; each needs 2 forks. If everyone grabs their left fork at once โ†’ deadlock (circular wait). Fixes: make one philosopher grab in the opposite order (break the symmetry), allow only 4 at the table, or add an extra fork instance.

6Common semaphore bugs (spot them!) ๐Ÿ”ด

MistakeResult
signal before the CS / missing wait / extra signalmutual exclusion broken (others get in)
two wait in a row with no signal betweendeadlock
missing signal after the CSdeadlock (others blocked forever)
two threads take two locks in different orderdeadlock (circular wait โ€” fix: same order everywhere)
๐ŸŽฏ In the exam โ€” analyse a scheme (2024-02-07 reader/writer, 2025-09-17 prod/cons, 2025-01-28 philosophers)
Check: is mutual exclusion kept? can a wait-order cause deadlock? is one group starving? Remember: swapping two signals is harmless; swapping two waits can deadlock.

7One-page trap sheet

  • Three rules: mutual exclusion + progress (no deadlock) + bounded waiting (no starvation).
  • Naive flag fails ME (test+set not atomic). Peterson = correct software. Both still busy-wait.
  • TestAndSet: atomic, reads old value & sets TRUE โ†’ gives ME; it is a spinlock (wastes CPU) and does NOT stop starvation.
  • Semaphore: wait = down/block, signal = up/wake. No busy wait (uses a queue). Counter can be negative; |counter| = waiters. init value = max threads allowed in.
  • Mutex = binary semaphore (init 1). init 0 = used for ordering.
  • Precedence graph: one semaphore per arrow, init 0 (start node init 1); signal after, wait before; a join needs one wait per incoming arrow.
  • Producer/consumer: empty/full counting + mutex; counting wait BEFORE mutex wait, or deadlock. Two signals order is free.
  • Readers/writers: the group WITHOUT precedence can starve.
  • Dining philosophers: all grab same side โ†’ deadlock; break symmetry to fix.
  • Two waits in a row / missing signal / inconsistent lock order โ†’ deadlock. Extra/early signal / missing wait โ†’ ME broken.