Semaphores & Monitors

By the end of this lesson you will be able to use a semaphore to limit access to a resource or to force an order between processes, trace semaphore values in exam questions, and explain what a monitor adds.

A mutex lets exactly one thread in. Many real problems need more: "let at most 3 users print at once" or "do not start step B until step A is done". The semaphore, invented by Edsger Dijkstra in the 1960s, handles both.

What is a semaphore?

A semaphore is a shared integer S that can be changed only by two atomic operations:

• wait(S), also written P(S) or down: decrease S by 1. If the result is negative, the caller blocks until it is woken.
• signal(S), also written V(S) or up: increase S by 1. If any process is blocked on S, wake one of them.

P and V come from Dutch words, because Dijkstra was Dutch. You only need to remember that P takes a unit and V gives one back.

A parking lot with a display board at the gate is a good picture. The board shows free spaces. Each car entering lowers the number. When the board shows zero, the next car waits at the gate. When a car leaves, the number goes up and a waiting car is let in.

There are two kinds:

• A counting semaphore can take any value. It guards a resource with several identical units, such as 3 printers or 50 database connections.
• A binary semaphore only takes 0 or 1 and behaves much like a mutex.

In this implementation a blocked process does not spin. The kernel puts it in a queue attached to the semaphore and runs something else. When the value is negative, its size tells you how many processes are waiting.

Simulating a semaphore

Real threads cannot run in the browser, so here is a tiny kernel. Each process is a generator that asks the kernel to do P, V or to print a message. The kernel runs them round robin and blocks or wakes them exactly as described above.

Step 1: run it with four cars and two parking spaces.

from collections import deque

class Semaphore:
    def __init__(self, value):
        self.value, self.waiting = value, deque()

def run(procs):
    """Tiny round-robin kernel. Processes are generators that yield
    ("P", sem), ("V", sem) or ("say", text)."""
    ready = deque(procs.items())
    while ready:
        name, proc = ready.popleft()
        try:
            op, arg = next(proc)
        except StopIteration:
            continue
        if op == "say":
            print(f"{name}: {arg}")
        elif op == "P":
            arg.value -= 1
            if arg.value < 0:                       # no unit left: block
                print(f"{name}: blocked (value={arg.value})")
                arg.waiting.append((name, proc))
                continue
        elif op == "V":
            arg.value += 1
            if arg.value <= 0:                      # someone was waiting: wake one
                woken = arg.waiting.popleft()
                print(f"{name}: wakes {woken[0]}")
                ready.append(woken)
        ready.append((name, proc))

spots = Semaphore(2)              # a parking lot with 2 spaces

def car(n):
    yield ("P", spots)
    yield ("say", "parked")
    yield ("say", "shopping")
    yield ("V", spots)
    yield ("say", "left")

run({f"Car{i}": car(i) for i in range(1, 5)})

Car3: blocked (value=-1)
Car4: blocked (value=-2)
Car1: parked
Car2: parked
Car1: shopping
Car2: shopping
Car1: wakes Car3
Car2: wakes Car4
Car3: parked
Car1: left
Car4: parked
Car2: left
Car3: shopping
Car4: shopping
Car3: left
Car4: left

Step 2: read the output. Car1 and Car2 take the two spaces. Car3 and Car4 block, and the value goes to -2, meaning two cars wait. Each time a car leaves, its V wakes one waiting car. Never more than two cars are parked at once.

Using a semaphore to force an order

Semaphores can also make one thing happen before another. Suppose Farhan's process must finish loading the marks file (statement A) before Ananya's process prints the report (statement B). Use a semaphore done that starts at 0:

Farhan:  A (load marks);  signal(done)
Ananya:  wait(done);      B (print report)

If Ananya runs first, wait(done) makes the value -1 and she blocks. Farhan's signal wakes her only after A is done. If Farhan runs first, the value becomes 1 and Ananya passes straight through. Either way, A happens before B.

Semaphore arithmetic in exam questions

A common question: "A counting semaphore starts at 7. Then 20 P operations and 15 V operations are performed. What is the final value?" Each P subtracts 1 and each V adds 1, whatever the order.

start, p_ops, v_ops = 7, 20, 15
final = start - p_ops + v_ops
print("final value:", final)
print("processes still blocked:", max(0, -final))

final value: 2
processes still blocked: 0

A negative final value would mean that many processes are still blocked.

Mistakes semaphores make easy

Semaphores are powerful but easy to misuse:

• Writing signal where you meant wait lets several processes into a critical section.
• Forgetting a signal leaves processes blocked for ever.
• Taking two semaphores in opposite orders in two processes can cause a deadlock, the subject of the Deadlocks lesson.

Another subtle problem is priority inversion: a high-priority task waits for a lock held by a low-priority task, which in turn cannot run because medium-priority tasks keep the CPU. NASA's Mars Pathfinder lander suffered repeated resets from this in 1997. The usual fix is priority inheritance: while a low-priority task holds a lock that a high-priority task needs, it temporarily runs at the high priority.

Monitors and condition variables

Because raw semaphores are error-prone, languages offer a higher-level tool: the monitor. A monitor is an object whose methods can be run by only one thread at a time. The compiler or library adds the locking for you, so you cannot forget it.

Inside a monitor, a thread that must wait for something uses a condition variable:

• wait(): release the monitor and sleep until signalled.
• signal() (often called notify): wake one thread waiting on that condition.
• broadcast() (notify_all): wake all of them.

In Python, threading.Condition gives you this pattern. This code cannot run in the browser, which has no real threads, but it shows how a ticket counter monitor looks:

import threading

class TicketCounter:
    def __init__(self, seats):
        self.seats = seats
        self.cond = threading.Condition()     # monitor lock + condition variable

    def book(self, name):
        with self.cond:                       # only one thread inside at a time
            while self.seats == 0:            # always re-check in a loop
                self.cond.wait()              # release the lock and sleep
            self.seats -= 1
            print(name, "booked; seats left:", self.seats)

    def cancel(self):
        with self.cond:
            self.seats += 1
            self.cond.notify()                # wake one waiting booker

Notice the while loop around wait(). In most real systems (Python, Java, POSIX threads), a woken thread does not run immediately; the signaller keeps going and the woken thread competes for the lock later. By then the condition may be false again, so it must check once more. This style is called signal-and-continue (or Mesa style). In the older signal-and-wait (Hoare style), the woken thread runs at once. Java's synchronized methods with wait() and notify() are another monitor you may meet.

Common mistakes

• Starting an ordering semaphore at 1. For "A before B", it must start at 0, or B can run first.
• Using if instead of while around a condition wait. Always re-check the condition after waking.
• Thinking the semaphore value is the number of waiters. Only a negative value counts waiters; a positive value counts free units.

Key points

• A semaphore is an integer changed only by atomic wait (P) and signal (V).
• Counting semaphores guard several identical units; binary semaphores act like locks.
• wait blocks when the value goes negative; signal wakes one blocked process.
• A semaphore initialised to 0 forces one statement to run before another.
• Final value = initial - number of P + number of V.
• Monitors add automatic mutual exclusion; condition variables let threads wait inside them.

done = Semaphore(0)

def ananya():
    yield ("P", done)
    yield ("say", "printing report")

def farhan():
    yield ("say", "loading marks")
    yield ("V", done)

run({"Ananya": ananya(), "Farhan": farhan()})

Ananya: blocked (value=-1)
Farhan: loading marks
Farhan: wakes Ananya
Ananya: printing report