These are the notes for CS Fundamentals for Placements, episode 26. In episode 25 we built locks: a spinlock, which loops while it waits, and a mutex, which sleeps. A lock answers one question: is it free or taken? Today we hit two problems a lock cannot solve. What if three threads may be inside at once, because there are three copies of the resource? And what if a thread has to wait for something to happen (chai to be ready), not just for a lock? Solving them, you will invent the semaphore with its two operations wait (P) and signal (V), meet counting and binary semaphores, solve semaphore value numericals, build the blocking semaphore with a waiting queue, compare a mutex with a binary semaphore, and then invent the monitor, its condition variables with wait and signal, and the difference between Hoare and Mesa semantics. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.
All program outputs below are real: every C program was compiled with gcc 13.3 -O2 (the SyntaxPilot compiler's flags; with glibc 2.39 no extra -pthread flag is needed) and run on Linux x86-64 with 2 CPUs on 3 November 2026, three times each; every output shown was the same on every run. The Java program was run with OpenJDK 21.
Refresher: a thread is a flow of execution inside a process; threads of one process share global variables. pthread_create starts a thread running a function, and pthread_join waits for it to finish. A critical section is code that touches shared data, and mutual exclusion means at most one thread is inside it at a time (episode 24). An atomic operation happens as one unbreakable step: no other thread can see it half done (episode 25).
The six problems
| Problem | What it teaches |
|---|---|
| 3 machines, 1 key | Semaphore, wait (P), signal (V), counting semaphore |
| What's the value now? | Semaphore value numericals |
| Don't knock, sit down | Busy waiting vs blocking; the waiting queue; negative values |
| A semaphore as a lock | Binary semaphore; mutex vs binary semaphore; signalling |
| One mistake breaks it | Why semaphores are error-prone; the monitor; Java synchronized |
| Wait for the chai | Condition variables, wait / signal / broadcast; Hoare vs Mesa; while, not if |
Problem 1: 3 machines, 1 key (the counting semaphore)
A hostel laundry room has 3 washing machines, and on Sunday morning 6 students want to wash clothes. The machines are a shared resource, but there are three copies of it. The warden uses last episode's fix: one room key (a mutex). Only the key holder may wash. It is safe, but one student washes while two machines sit idle.
Each student is a thread; washing is sleep(1), a one-second pause.
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
pthread_mutex_t key = PTHREAD_MUTEX_INITIALIZER; // ONE room key
void *student(void *arg) {
pthread_mutex_lock(&key); // take the key
sleep(1); // wash clothes: 1 second
pthread_mutex_unlock(&key); // give the key back
return NULL;
}
int main(void) {
struct timespec a, b; pthread_t s[6];
clock_gettime(CLOCK_MONOTONIC, &a);
for (int i = 0; i < 6; i++) pthread_create(&s[i], NULL, student, NULL);
for (int i = 0; i < 6; i++) pthread_join(s[i], NULL);
clock_gettime(CLOCK_MONOTONIC, &b);
double t = (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
printf("6 students washed in %.1f seconds\n", t);
}
Output:
6 students washed in 6.0 seconds
clock_gettime(CLOCK_MONOTONIC, ...) reads a clock that only moves forward, so the difference of two readings is the time taken. Six seconds: one student at a time. A lock cannot count.
The fix: a box of 3 tokens
The warden puts a box with 3 tokens at the desk, one per machine. To enter, you take a token; if the box is empty, you wait. When you leave, you put the token back, and a waiting student can go in.
| At the laundry desk | In code |
|---|---|
| A box with 3 tokens | A semaphore S = 3 |
| Take a token to enter (box empty? wait) | wait(S), also written P(S): S = S - 1, wait if nothing was free |
| Put the token back | signal(S), also written V(S): S = S + 1, let a waiting thread continue |
A semaphore is an integer counter shared by threads that you may touch only through two atomic operations, wait and signal. In POSIX (the standard C threads interface on Linux), the type is sem_t from <semaphore.h>:
| Textbook | POSIX C | Meaning |
|---|---|---|
| initialise S to n | sem_init(&s, 0, n) |
the middle 0 = shared between threads of this process |
| wait(S) / P(S) | sem_wait(&s) |
take one; sleep if none free |
| signal(S) / V(S) | sem_post(&s) |
give one back; wake a waiter if any |
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <semaphore.h>
sem_t machines; // counts free machines
void *student(void *arg) {
sem_wait(&machines); // P: take a machine token
sleep(1); // wash clothes: 1 second
sem_post(&machines); // V: return the token
return NULL;
}
int main(void) {
struct timespec a, b; pthread_t s[6];
sem_init(&machines, 0, 3); // 3 machines, all free
clock_gettime(CLOCK_MONOTONIC, &a);
for (int i = 0; i < 6; i++) pthread_create(&s[i], NULL, student, NULL);
for (int i = 0; i < 6; i++) pthread_join(s[i], NULL);
clock_gettime(CLOCK_MONOTONIC, &b);
double t = (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
printf("6 students washed in %.1f seconds\n", t);
}
Output:
6 students washed in 2.0 seconds
Three students washed together, then the next three. A semaphore whose value can be any count from 0 up to N is a counting semaphore. Use one whenever you have N identical copies of something: 3 machines, 10 database connections, 4 printers, 50 parking spots.
The textbook definition
wait(S) { // P
while (S <= 0) ; // nothing free: wait
S--; // take one
}
signal(S) { // V
S++; // give one back
}
Both operations are atomic: the check and the decrement in wait happen as one step, so two threads can never take the same token (that was exactly the bug of episode 24's lock variable).
History. Edsger W. Dijkstra, the Dutch computer scientist, introduced the semaphore idea in 1962 (manuscript EWD 51), and his 1968 paper Cooperating Sequential Processes proposed the semaphore with its two operations P and V. V is from verhogen, Dutch for "raise"; P is from prolaag, a word Dijkstra made up, read as "try to lower". Sources: K. R. Apt, Edsger Wybe Dijkstra (1930-2002): A Portrait of a Genius (arXiv cs/0210001).
Problem 2: what's the value now? (semaphore value numericals)
Every P subtracts 1 and every V adds 1, so:
final S = initial value − (number of P operations) + (number of V operations)
(as long as every waiting thread eventually gets through; in the blocking version below, the value may go negative while threads wait).
| Question | Working | Answer |
|---|---|---|
| S = 10; 6 P and 4 V | 10 − 6 + 4 | 8 |
| S = 7; 20 P and 15 V | 7 − 20 + 15 | 2 |
| S = 5; 8 P, no V | first 5 pass, 3 wait | blocking version: S = −3 (3 threads waiting) |
| S = 0; 3 V then 2 P | 0 + 3 − 2 | 1 |
| S = 4; 9 P and 2 V (the video's quiz) | 4 − 9 + 2 | −3: 3 threads still asleep |
GATE-style variant: "A counting semaphore was initialised to 12. Then 10 P and 4 V operations were done. How many more P operations can complete without blocking?" Value = 12 − 10 + 4 = 6, so 6 more P operations succeed; the 7th blocks.
Problem 3: don't knock, sit down (blocking semaphore with a waiting queue)
Look at the while (S <= 0) ; loop in the textbook wait. A waiting thread keeps checking S again and again, like a patient knocking on the doctor's door every second: "Free yet? Free yet?" That is busy waiting (also called spinning): waiting in a loop that burns CPU time doing nothing useful. Episode 25's spinlock did exactly this. On one CPU it is worse than useless: the spinning thread uses up the time slice the token holder needs to finish.
A real clinic works better:
| At the clinic | In the OS |
|---|---|
| Knocking every second | busy waiting: while (S <= 0) ; |
| Take token 14, your name goes in the register | S--, add the thread to the semaphore's waiting queue |
| Doze on the bench | block(): the thread leaves the CPU and sleeps (state: waiting/blocked) |
| "Token 14, please!" | signal: S++, remove one thread from the queue, wakeup() it |
struct semaphore { int value; queue list; };
wait(S) {
S.value--;
if (S.value < 0) { add me to S.list; block(); }
}
signal(S) {
S.value++;
if (S.value <= 0) { T = take from S.list; wakeup(T); }
}
- block() takes the calling thread off the CPU and puts it to sleep; it uses no CPU until woken.
- wakeup(T) moves thread T from the waiting state to the ready queue (the line of threads ready to run, episode 21).
waitdecrements first, so the value can go negative. A negative value tells you how many threads are waiting:S.value = −3means 3 threads are asleep inS.list.- In
signal,value <= 0after the increment means someone was waiting. - If
S.listis FIFO (first in, first out), every waiter is eventually woken: bounded waiting (episode 24). waitandsignalthemselves must still be atomic; the kernel protects these few lines internally (briefly, with a spinlock or by disabling interrupts on one core), which is fine because they are very short.
Linux's sem_wait behaves like this: a thread that finds no token sleeps; it does not spin.
Problem 4: a semaphore as a lock (binary semaphore; mutex vs semaphore)
With one machine, start the semaphore at 1:
sem_init(&s, 0, 1); // 1 = free
sem_wait(&s); // 1 → 0: I'm in
critical section
sem_post(&s); // 0 → 1: free again
A semaphore that only ever holds 0 or 1 is a binary semaphore. It gives mutual exclusion, so it works as a lock.
Live: the lost counter, fixed (and one missing line)
First version, with #include <semaphore.h> left out:
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
sem_t s; // a binary semaphore: 1 or 0
...
Compiler output:
main.c:5:1: error: unknown type name 'sem_t'
5 | sem_t s; // a binary semaphore: 1 or 0
| ^~~~~
main.c: In function 'work':
main.c:10:9: warning: implicit declaration of function 'sem_wait' [-Wimplicit-function-declaration]
The semaphore type and functions are declared in <semaphore.h>. With the include:
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t s; // a binary semaphore: 1 or 0
int counter = 0; // shared by both threads
void *work(void *arg) {
for (int i = 0; i < 100000; i++) {
sem_wait(&s); // P: wait until free, take it
counter++; // critical section
sem_post(&s); // V: free it again
}
return NULL;
}
int main(void) {
pthread_t a, b;
sem_init(&s, 0, 1); // 1 = free
pthread_create(&a, NULL, work, NULL);
pthread_create(&b, NULL, work, NULL);
sleep(2); // look after 2 seconds
printf("after 2 s: counter = %d (expected 200000)\n", counter);
}
Output:
after 2 s: counter = 200000 (expected 200000)
Not one update lost. (Main simply looks after 2 seconds instead of joining, so the next bug can be shown with the same program.)
Live: the wrong initial value
Change one line to sem_init(&s, 0, 0); (0 = taken):
after 2 s: counter = 0 (expected 200000)
Both threads called sem_wait on a semaphore with no token, and nobody ever signals, so both sleep forever. The initial value is how many threads may enter at the start: 1 for a lock, N for N resources, 0 for "wait for an event".
Mutex vs binary semaphore
| At a hotel | In code |
|---|---|
| Room key card: only the guest who checked in checks out | Mutex: has an owner (the thread that locked it); only the owner may unlock |
| The kitchen's "order ready" bell: the cook rings, the waiter reacts | Semaphore: no owner; any thread may signal |
Ownership, live. A mutex created with type PTHREAD_MUTEX_ERRORCHECK checks who unlocks it. strerror turns an error number into words.
#include <stdio.h>
#include <string.h>
#include <pthread.h>
pthread_mutex_t m; // a mutex has an OWNER
void *other(void *arg) {
int err = pthread_mutex_unlock(&m); // not the owner!
printf("other thread unlocks: %s\n", strerror(err));
return NULL;
}
int main(void) {
pthread_mutexattr_t at; // ask for error checking
pthread_mutexattr_init(&at);
pthread_mutexattr_settype(&at, PTHREAD_MUTEX_ERRORCHECK);
pthread_mutex_init(&m, &at);
pthread_mutex_lock(&m); // main thread locks: owner
pthread_t t;
pthread_create(&t, NULL, other, NULL);
pthread_join(t, NULL);
printf("owner unlocks: %s\n", strerror(pthread_mutex_unlock(&m)));
}
Output:
other thread unlocks: Operation not permitted
owner unlocks: Success
"Operation not permitted" is the text of the error code EPERM. With a default (non-error-checking) mutex, unlocking from a non-owner is undefined behaviour: it may appear to work and silently break mutual exclusion.
Signalling, live. A semaphore starting at 0 means "the event hasn't happened yet". One thread waits; a different thread signals.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t ready; // starts at 0: chai not ready
void *cook(void *arg) {
sleep(1); // making chai...
printf("cook: chai is ready\n");
sem_post(&ready); // V: signal "ready"
return NULL;
}
int main(void) {
sem_init(&ready, 0, 0);
pthread_t c;
pthread_create(&c, NULL, cook, NULL);
printf("waiter: waiting for chai...\n");
sem_wait(&ready); // P: sleep until signalled
printf("waiter: serving chai\n");
pthread_join(c, NULL);
}
Output (always in this order):
waiter: waiting for chai...
cook: chai is ready
waiter: serving chai
Using a semaphore to make one event happen after another is called signalling (or ordering). A mutex cannot do this, because the thread that locks must be the one that unlocks.
| Mutex | Binary semaphore | |
|---|---|---|
| Values | locked / unlocked | 0 / 1 |
| Owner | yes: the locking thread | no |
| Who releases | only the owner | any thread |
| Main use | mutual exclusion (protect data) | exclusion and signalling between threads |
| POSIX | pthread_mutex_lock / unlock |
sem_wait / sem_post |
| Extra features | error checking, recursive and priority-inheritance types | can be counting (0..N) |
Rule of thumb: protect data with a mutex; count resources or signal events with a semaphore.
Problem 5: one mistake breaks it (the monitor)
Semaphores trust every programmer:
| Mistake | Effect |
|---|---|
signal(S); critical section; wait(S); (swapped) |
every thread walks in: no mutual exclusion |
wait(S); critical section; wait(S); (typo) |
the thread sleeps forever (like starting at 0) |
forgetting wait(S) |
no protection at all |
forgetting signal(S) |
everyone after you waits forever |
The calls are spread across the whole program, and a single wrong line breaks everything, only sometimes. We want the protection to be automatic.
A bank locker room with a guard
| At the bank | A monitor |
|---|---|
| The lockers are inside a room; you can't reach them from outside | the shared data is private to the monitor |
| Only a few allowed actions: open locker, deposit, withdraw | the procedures (functions/methods) are the only way to touch the data |
| A guard lets one customer in at a time; customers never lock the door | automatic mutual exclusion: at most one thread is active inside the monitor |
A monitor is a programming-language construct that bundles shared data with the procedures that use it, and guarantees that at most one thread is executing any of those procedures at a time. The locking is done for you, so you cannot forget it or swap it.
History. Per Brinch Hansen first described and implemented monitors (in his language Concurrent Pascal); C. A. R. (Tony) Hoare's 1974 paper Monitors: an operating system structuring concept developed the theory and showed that monitors are as powerful as semaphores (each can implement the other). Source: Wikipedia, Monitor (synchronization).
Java supports monitors through synchronized: every object has a built-in lock, and a synchronized method takes the object's lock when it starts and releases it when it ends, even if it throws an exception.
class Counter {
private int count = 0;
synchronized void add() { // lock taken for you
count++;
} // and released for you
}
C has no monitors, so we build one by hand: the shared data, one pthread_mutex_t, and functions that lock it on entry and unlock it on every exit.
Problem 6: wait for the chai (condition variables; Hoare vs Mesa)
A chai stall as a monitor. Shared data: cups, the number of ready cups. A customer enters the monitor and, if there is no chai yet, has to wait.
Attempt 1: loop inside the monitor (never works)
lock(m);
while (cups == 0) { } // wait for chai...
cups--;
unlock(m);
The customer loops while holding the monitor's lock. The cook must enter the monitor to add a cup, but the lock is never free. The customer waits for the cook, and the cook waits for the customer: stuck forever.
The customer must give up the lock and go to sleep, and these two must happen as one atomic step. If the lock were dropped first and the sleep came after, the cook could add a cup and signal in the gap, the signal would be missed, and the customer would then sleep forever.
Condition variables
| At the chai stall | Condition variable |
|---|---|
| "No chai yet": step away from the counter and sit on the bench | wait(cond): atomically release the monitor lock and sleep; on waking, take the lock back before continuing |
| "Chai ready!" to one person: the next on the bench gets up | signal(cond): wake one waiting thread |
| "Chai ready!" to everyone: the whole bench gets up | broadcast(cond): wake all waiting threads |
A condition variable is a named queue of threads, inside a monitor, waiting for some condition to become true ("chai is ready", "buffer not full"). It has no value. A signal with nobody waiting is simply lost, unlike a semaphore's V, which is remembered in the count.
POSIX: pthread_cond_t, pthread_cond_wait(&cond, &mutex), pthread_cond_signal(&cond), pthread_cond_broadcast(&cond). Java: every object is also a condition variable: wait(), notify(), notifyAll(), called inside synchronized.
Live: the chai stall with if
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; // monitor lock
pthread_cond_t ready = PTHREAD_COND_INITIALIZER; // "chai is ready"
int cups = 0; // shared state
void *customer(void *arg) {
pthread_mutex_lock(&m); // enter monitor
if (cups == 0) // no chai yet?
pthread_cond_wait(&ready, &m); // sleep, drop lock
cups--; printf("took a cup, cups left = %d\n", cups);
pthread_mutex_unlock(&m); // leave monitor
return NULL;
}
int main(void) {
pthread_t c[2]; // two customers
for (int i = 0; i < 2; i++) pthread_create(&c[i], NULL, customer, NULL);
for (int k = 0; k < 2; k++) { // cook: 1 cup a second
sleep(1); pthread_mutex_lock(&m); cups++;
pthread_cond_broadcast(&ready); // wake all waiters
pthread_mutex_unlock(&m);
}
for (int i = 0; i < 2; i++) pthread_join(c[i], NULL);
}
Output (same on every run):
took a cup, cups left = 0
took a cup, cups left = -1
Minus one cup is impossible. The broadcast after the first cup woke both customers. The first to get the lock took the cup (0 left). The second had already passed its if before sleeping, so after waking it went straight to cups-- and took a cup that wasn't there.
Hoare vs Mesa semantics
What exactly happens at signal?
| Hoare semantics | Mesa semantics | |
|---|---|---|
| On signal | the lock is handed immediately to the woken thread, which runs at once; the signaller waits | the woken thread is only made ready; the signaller keeps the lock and keeps running |
| When the waiter runs | the condition is guaranteed still true | the condition may be false again (another thread may have run first) |
| How to wait | if (!cond) wait(c); is enough |
while (!cond) wait(c); is required |
| Chai stall | the chaiwala puts the cup into your hand | he shouts "Chai ready!", someone may get there first |
| Used by | Hoare's 1974 monitors, textbooks | Mesa (Xerox), POSIX threads, Java, most real systems |
Mesa semantics come from Xerox's Mesa language, described by Butler Lampson and David Redell in Experience with Processes and Monitors in Mesa (Communications of the ACM, February 1980). Under Mesa semantics, "a call to notify is nothing more than a hint" (summary by M. Whittaker). Mesa is simpler and cheaper to implement, which is why almost everything uses it. Source: Lampson's abstract page, paper summary.
Live: the fix, while instead of if
while (cups == 0) // re-check on waking
pthread_cond_wait(&ready, &m); // sleep, drop lock
Output:
took a cup, cups left = 0
took a cup, cups left = 0
The second customer woke, found no cup, went back to sleep, and took the second cup a second later. With Mesa semantics, always wait in a while loop. (POSIX also allows a waiting thread to wake up occasionally without any signal at all, which the while loop handles too.)
The same monitor in Java
public class Main {
static class ChaiStall { // a monitor
private int cups = 0; // shared data, hidden inside
synchronized void take() throws InterruptedException {
while (cups == 0) wait(); // drop the lock, sleep
cups--;
System.out.println("took a cup, cups left = " + cups);
}
synchronized void make() {
cups++;
notifyAll(); // wake all waiters
}
}
public static void main(String[] args) throws Exception {
ChaiStall stall = new ChaiStall();
Runnable customer = () -> {
try { stall.take(); } catch (InterruptedException e) { }
};
Thread a = new Thread(customer), b = new Thread(customer);
a.start(); b.start();
for (int k = 0; k < 2; k++) { Thread.sleep(1000); stall.make(); }
a.join(); b.join();
}
}
Output:
took a cup, cups left = 0
took a cup, cups left = 0
Calling wait() outside synchronized is a runtime error, because the thread must hold the monitor lock to give it up:
Object lock = new Object();
lock.wait(); // not inside synchronized (lock)
Exception in thread "main" java.lang.IllegalMonitorStateException: current thread is not owner
at java.base/java.lang.Object.wait0(Native Method)
...
The whole chain
| Problem | Invention |
|---|---|
| A lock can't count 3 machines | Counting semaphore: wait (P), signal (V) |
| What is S after many P and V? | Numericals: S = initial − P + V |
| Busy waiting wastes the CPU | Blocking semaphore with a waiting queue; S < 0 = number of waiters |
| One machine | Binary semaphore as a lock; vs mutex (owner) and for signalling |
| Semaphore calls are easy to misuse | Monitor: data + procedures + automatic lock (Java synchronized) |
| Waiting for an event inside a monitor | Condition variable: wait / signal / broadcast; Mesa → while |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
sem_t without the header |
error: unknown type name 'sem_t' |
Declared in <semaphore.h> |
#include <semaphore.h> |
| A lock semaphore started at 0 | after 2 s: counter = 0 (expected 200000) |
No token: every sem_wait sleeps |
Start at 1 (or N for N resources) |
| Unlocking another thread's mutex | other thread unlocks: Operation not permitted (error-checking mutex) |
A mutex has an owner | Unlock in the owner, or use a semaphore for signalling |
if before pthread_cond_wait |
took a cup, cups left = -1 |
Mesa: signal is only a hint | while (!condition) pthread_cond_wait(...) |
Java wait() outside synchronized |
IllegalMonitorStateException: current thread is not owner |
Must hold the monitor lock to release it | Call it inside a synchronized method or block |
Swapping wait and signal |
wrong totals, sometimes | Mutual exclusion lost | Use a monitor / mutex wrapper |
| Signalling a condition variable before anyone waits | the waiter sleeps forever | Condition-variable signals are not remembered | Check a shared condition (state variable) under the lock, in a while |
Mini project: the parking lot
A mall parking lot has 5 spots and 12 cars arrive. Write a C program with a counting semaphore spots (initial value 5); each car thread does sem_wait, parks for a random 1-3 seconds (sleep(1 + rand_r(&seed) % 3)), then sem_post. Keep a shared parked counter protected by a mutex, and print car 7 parked, 5 inside on entry. Check that the number inside never goes above 5. Then add a display thread that waits on a second semaphore full (initial 0), which the 5th car to park posts, and prints LOT FULL. Which part is mutual exclusion, which is counting, and which is signalling?
Practice
1. S = 15. Then 12 P operations and 7 V operations. Final value?
Solution
15 − 12 + 7 = 10.
2. A blocking semaphore has value −4. How many threads are waiting? What will the value be after 4 signal operations, and how many threads are still waiting?
Solution
4 threads wait. After 4 signals the value is 0 and no thread is waiting (each signal woke one).
3. Make thread B print "B" only after thread A prints "A", using one semaphore.
Solution
sem_t done; // sem_init(&done, 0, 0)
void *A(void *x) { printf("A\n"); sem_post(&done); return NULL; }
void *B(void *x) { sem_wait(&done); printf("B\n"); return NULL; }
The semaphore starts at 0, so B sleeps until A signals. This is exactly the chai-ready program.
4. Why must pthread_cond_wait release the mutex and sleep in one atomic step?
Solution
If it released the mutex first and then went to sleep, the cook could take the mutex in between, add a cup and signal. Nobody was waiting yet, so the signal is lost; then the customer goes to sleep and never wakes. Doing both atomically means the signal can only come after the thread is on the wait queue.
5. With Hoare semantics, is if (cups == 0) wait(c); correct? With Mesa?
Solution
Hoare: yes, because the signaller hands the lock directly to the woken thread, so cups > 0 is still true when it runs. Mesa: no, because other threads may run between the signal and the waiter getting the lock; use while.
6. Can a binary semaphore replace a mutex? Can a mutex replace a binary semaphore?
Solution
A binary semaphore can provide mutual exclusion (start at 1, wait/post around the critical section), though it has no ownership checks. A mutex cannot replace a semaphore used for signalling, because only the thread that locked a mutex may unlock it.
7. Rewrite the chai stall in Java with synchronized, wait() and notifyAll().
Solution
See "The same monitor in Java" above.
Quick quiz
// counting semaphore, blocking version
S = 4;
// 9 threads call wait(S)
// 2 threads call signal(S)
What is the final value of S? A. −3 B. 0 C. −5 D. 3
Answer
A. −3. 4 − 9 + 2 = −3. In the blocking version a negative value means 3 threads are still asleep in the waiting queue.
Interview questions
- What is a semaphore? An integer shared by threads, changed only by the atomic operations wait (P) and signal (V).
- Counting vs binary semaphore? Counting: any value 0..N, guards N identical resources. Binary: 0 or 1, works as a lock.
- What do P and V stand for? Dijkstra's Dutch: V = verhogen (raise), P = prolaag (a made-up word, "try to lower").
- Mutex vs binary semaphore? A mutex has an owner and only the owner may unlock; a semaphore has no owner, so it can also signal between threads.
- What does a negative semaphore value mean? In the blocking implementation, the number of threads waiting.
- Why does a real semaphore block instead of busy-waiting? Spinning wastes CPU time the holder may need; blocking frees the CPU.
- What is a monitor? Shared data plus the procedures that use it, with automatic mutual exclusion: at most one thread active inside.
- What is a condition variable? How is it different from a semaphore? A queue of threads waiting for a condition inside a monitor; it has no value, so a signal with no waiter is lost, while a semaphore remembers V operations in its count.
- Hoare vs Mesa semantics? Hoare: signal hands the lock to the waiter, which runs immediately. Mesa: the waiter just becomes ready; re-check the condition in a
while. - Why
whileand notifaroundpthread_cond_wait? Mesa semantics (and spurious wake-ups): the condition may be false again when the thread runs. - How does Java implement monitors?
synchronizedmethods/blocks pluswait(),notify(),notifyAll()on the object.
Glossary
| Term | Meaning in plain words | Example |
|---|---|---|
| Shared resource | Something several threads need, possibly in several copies | 3 washing machines |
| Semaphore | An integer counter shared by threads, used only via atomic wait and signal | sem_t machines = 3 |
| wait (P) | Decrement the semaphore; if nothing was free, wait/sleep | sem_wait(&s): take a token |
| signal (V) | Increment the semaphore; wake a waiting thread if any | sem_post(&s): return the token |
| P / V (prolaag / verhogen) | Dijkstra's Dutch names: try to lower / raise | P = wait, V = signal |
| Atomic operation | Happens as one unbreakable step | the check-and-decrement in wait |
| Counting semaphore | A semaphore with any value 0..N, guarding N copies | parking lot with 50 spots |
| Binary semaphore | A semaphore that only holds 0 or 1 | sem_init(&s, 0, 1) as a lock |
| Semaphore value numericals | Exam questions computing S after P and V operations | 10 − 6 + 4 = 8 |
| Busy waiting / spinning | Waiting by looping and checking, using the CPU | while (S <= 0) ; |
| Blocking | A thread leaves the CPU and sleeps until woken | dozing on the clinic bench |
| Waiting queue (semaphore list) | The list of threads sleeping on a semaphore | names in the clinic register |
| block() | Put the calling thread to sleep, off the CPU | inside wait |
| wakeup(T) | Move a sleeping thread T to the ready queue | "Token 14, please!" |
| Ready queue | Threads that are ready to run, waiting for a CPU | episode 21 |
| Negative semaphore value | In the blocking version, minus the number of waiters | S = −3: 3 waiting |
sem_init(&s, 0, n) |
Create a semaphore with value n, shared among threads of this process | sem_init(&machines, 0, 3) |
<semaphore.h> |
C header declaring sem_t and the sem_ functions |
#include <semaphore.h> |
| Mutex | A lock with an owner; only the locker unlocks | room key card |
| Ownership | Only the thread that locked may unlock | Operation not permitted |
PTHREAD_MUTEX_ERRORCHECK |
A mutex type that reports misuse instead of misbehaving | the ownership demo |
strerror |
Turns an error number into text | EPERM → "Operation not permitted" |
| Signalling (ordering) | Making one thread wait until another says an event happened | chai ready → serve |
| Monitor | Shared data + procedures + automatic mutual exclusion | bank locker room with a guard |
| Procedure (of a monitor) | A function that is the only way to touch the monitor's data | take(), make() |
synchronized (Java) |
Makes a method or block take the object's lock automatically | synchronized void add() |
| Condition variable | A queue of threads waiting inside a monitor for a condition | the bench at the chai stall |
| wait on a condition variable | Atomically release the monitor lock and sleep; re-take the lock on waking | pthread_cond_wait(&ready, &m) |
| signal on a condition variable | Wake one waiting thread (lost if none waits) | pthread_cond_signal(&ready), Java notify() |
| broadcast | Wake all waiting threads | pthread_cond_broadcast(&ready), Java notifyAll() |
| Hoare semantics | Signal hands the lock to the woken thread, which runs at once | cup put into your hand |
| Mesa semantics | Signal only makes the waiter ready; it must re-check | "Chai ready!" shouted, re-check |
| Spurious wake-up | A wait returning without a signal (allowed by POSIX) | handled by the while loop |
IllegalMonitorStateException |
Java error: wait/notify without holding the monitor lock |
lock.wait() outside synchronized |
| Undefined behaviour | C gives no guarantee at all about what happens | unlocking a default mutex you don't own |
Summary
- A semaphore is a shared counter changed only by atomic wait (P) and signal (V); Dijkstra introduced it (idea 1962, P and V published 1968).
- A counting semaphore lets N threads in (3 machines: 6 s → 2 s); final S = initial − P + V.
- Real semaphores block in a waiting queue instead of busy-waiting; a negative value counts the waiters.
- A binary semaphore (0/1) works as a lock; a mutex has an owner, while a semaphore can signal between threads. The initial value matters: 1 for a lock, N for N resources, 0 for an event.
- Semaphores are easy to misuse, so the monitor bundles data, procedures and automatic mutual exclusion (Java
synchronized; Brinch Hansen, Hoare 1974). - Inside a monitor, condition variables let threads wait (release the lock and sleep atomically) and be signalled or broadcast. Under Mesa semantics (POSIX, Java) a signal is only a hint, so always wait in a
whileloop; under Hoare semantics anifwould do.
Next episode: Classic synchronization problems: bounded-buffer producer-consumer, readers-writers, dining philosophers, sleeping barber and cigarette smokers, solved with semaphores in code.