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 see | How often | Section |
|---|---|---|
| ๐ด 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 semaphores | often | ยง3 + drills |
| ๐ด True/false: critical section / TestAndSet / spinlock; or analyse a reader-writer / producer-consumer scheme | often | ยง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.
- Mutual exclusion โ only one thread in the critical section at a time.
- 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.
- 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;
- It works because read+set are one atomic step โ two threads cannot both see FALSE. That gives mutual exclusion.
- It is a spinlock: the waiting thread loops and wastes CPU (busy waiting). Use only for very short waits.
- Important: TestAndSet gives mutual exclusion and progress, but NOT bounded waiting โ starvation is possible. To add fairness you need an extra waiting array (more complex).
- "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 mustreturn 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:
wait(S)(also called P orsem_wait): decrease the counter; if it goes below 0, the thread blocks.signal(S)(also called V orsem_post): increase the counter; if a thread is waiting, wake one.
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);
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:
- Use one semaphore per arrow (or one per node), all init 0.
- After a task finishes,
signalthe semaphore of each outgoing arrow. - Before a task starts,
waiton the semaphore of each incoming arrow (so a node with 3 parents does 3 waits). - The very first task has nothing before it โ its semaphore is init 1 (so it can start).
- For a cyclic version (tasks loop forever), close the loop: the last node signals the first.
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 waitsNote: 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);
emptycounts free slots,fullcounts used slots,mutexprotects the buffer.- Order matters: the counting
wait(empty/full) must come before thewait(mutex). If you swap them, you can deadlock (you hold the mutex and then block). - The order of the two
signals at the end does not matter (signal never blocks).
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!) ๐ด
| Mistake | Result |
|---|---|
signal before the CS / missing wait / extra signal | mutual exclusion broken (others get in) |
two wait in a row with no signal between | deadlock |
missing signal after the CS | deadlock (others blocked forever) |
| two threads take two locks in different order | deadlock (circular wait โ fix: same order everywhere) |
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/fullcounting +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.