SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 26
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 26 of 90

Semaphores and monitors

semaphorewait (P) and signal (V)counting semaphorebinary semaphoresemaphore value numericalsblocking semaphore implementation with waiting queuemutex vs binary semaphoremonitorcondition variablewait and signal on condition variablesHoare vs Mesa semantics

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).
  • wait decrements first, so the value can go negative. A negative value tells you how many threads are waiting: S.value = −3 means 3 threads are asleep in S.list.
  • In signal, value <= 0 after the increment means someone was waiting.
  • If S.list is FIFO (first in, first out), every waiter is eventually woken: bounded waiting (episode 24).
  • wait and signal themselves 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

  1. What is a semaphore? An integer shared by threads, changed only by the atomic operations wait (P) and signal (V).
  2. Counting vs binary semaphore? Counting: any value 0..N, guards N identical resources. Binary: 0 or 1, works as a lock.
  3. What do P and V stand for? Dijkstra's Dutch: V = verhogen (raise), P = prolaag (a made-up word, "try to lower").
  4. 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.
  5. What does a negative semaphore value mean? In the blocking implementation, the number of threads waiting.
  6. Why does a real semaphore block instead of busy-waiting? Spinning wastes CPU time the holder may need; blocking frees the CPU.
  7. What is a monitor? Shared data plus the procedures that use it, with automatic mutual exclusion: at most one thread active inside.
  8. 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.
  9. 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.
  10. Why while and not if around pthread_cond_wait? Mesa semantics (and spurious wake-ups): the condition may be false again when the thread runs.
  11. How does Java implement monitors? synchronized methods/blocks plus wait(), 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 while loop; under Hoare semantics an if would do.

Next episode: Classic synchronization problems: bounded-buffer producer-consumer, readers-writers, dining philosophers, sleeping barber and cigarette smokers, solved with semaphores in code.