Skills101

AdvancedOperating Systems · Lesson 14 of 17 · Updated ·

Semaphores in Depth — Value Numericals, Bounded Buffer in Python, Readers-Writers and Dining Philosophers

Lesson 4 introduced race conditions, mutexes and semaphores. This lesson goes one level deeper: what a semaphore does inside, the numerical questions built on it, and complete solutions to the classic problems — with programs you can run.

1. A semaphore with a blocked queue

The simple definition "wait blocks while S is 0" would make a waiting process loop and burn CPU (a busy wait or spinlock). Operating systems instead keep a queue of blocked processes inside the semaphore:

  • wait(S): S = S − 1. If S is now negative, put the caller in the queue and block it.
  • signal(S): S = S + 1. If S is still ≤ 0, someone is waiting — remove one process from the queue and wake it.

In this (textbook) version, a negative value tells you how many processes are blocked: S = −2 means two are waiting.

Example: an office has 2 printers, so S starts at 2. Four jobs A, B, C, D arrive.

Table of semaphore S starting at 2: A and B wait and get printers (S 1, then 0); C and D wait and block (S −1, −2, queue C, D); A signals and C wakes (S −1); B signals and D wakes (S 0)

The same thing as a program:

from collections import deque

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

    def wait(self, who):                 # also called P() or down()
        self.value -= 1
        if self.value < 0:
            self.queue.append(who)       # no instance free: block
            return f"{who} blocks"
        return f"{who} gets a printer"

    def signal(self, who):               # also called V() or up()
        self.value += 1
        if self.value <= 0:
            woken = self.queue.popleft() # hand the instance to a waiter
            return f"{who} releases, {woken} wakes up"
        return f"{who} releases"

s = Semaphore(2)
steps = [("wait", "A"), ("wait", "B"), ("wait", "C"), ("wait", "D"), ("signal", "A"), ("signal", "B")]
for op, who in steps:
    msg = getattr(s, op)(who)
    print(f"{op}({who}) -> S = {s.value:2}  queue = {list(s.queue)}  ({msg})")
wait(A) -> S =  1  queue = []  (A gets a printer)
wait(B) -> S =  0  queue = []  (B gets a printer)
wait(C) -> S = -1  queue = ['C']  (C blocks)
wait(D) -> S = -2  queue = ['C', 'D']  (D blocks)
signal(A) -> S = -1  queue = ['D']  (A releases, C wakes up)
signal(B) -> S =  0  queue = []  (B releases, D wakes up)

In a real OS, wait and signal must themselves be atomic — the kernel disables interrupts or uses a hardware instruction such as test-and-set while it changes S and the queue.

2. Semaphore value numericals

Each wait subtracts 1 and each signal adds 1, so the final value does not depend on the order:

Final S = initial + (number of signals) − (number of waits)

QuestionWorkingAnswer
S = 10; 6 wait and 4 signal operations. Final S?10 − 6 + 48
S = 7; 20 waits and 15 signals. Final S?7 − 20 + 152
S = 0; 5 waits, then 2 signals. How many processes are still blocked?0 − 5 + 2 = −33

A related question: "a counting semaphore starts at x; after 8 waits and 3 signals it is 1. Find x." → x − 8 + 3 = 1 → x = 6.

3. What can an unprotected counter end up as?

Two threads both run x = x + 1 on a shared x = 0. The CPU does this in three steps — load x into a register, add 1, store it back — and the threads can be interleaved between any two steps. This program tries every interleaving and collects the possible final values:

from itertools import combinations

def run(order, steps):
    x = 0
    reg = {"A": 0, "B": 0}           # each thread's private register
    pos = {"A": 0, "B": 0}
    for t in order:
        op = steps[pos[t]]
        pos[t] += 1
        if op == "load":
            reg[t] = x
        elif op == "add":
            reg[t] += 1
        else:                         # store
            x = reg[t]
    return x

def all_results(increments):
    steps = ["load", "add", "store"] * increments
    n = len(steps)
    results = set()
    for a_slots in combinations(range(2 * n), n):   # every interleaving
        order = ["A" if i in a_slots else "B" for i in range(2 * n)]
        results.add(run(order, steps))
    return sorted(results)

print("each thread does x = x + 1 once:  ", all_results(1))
print("each thread does x = x + 1 twice: ", all_results(2))
each thread does x = x + 1 once:   [1, 2]
each thread does x = x + 1 twice:  [2, 3, 4]

The "expected" answers are 2 and 4, but lost updates make smaller values possible: both threads load the same old value, and one store overwrites the other. Wrapping the increment in wait(mutex) … signal(mutex) leaves only the correct answer.

4. Producer–consumer that really runs

Python's threading.Semaphore has acquire() (= wait) and release() (= signal). Here a producer makes items 1 to 10, the buffer holds at most 3, and a consumer takes them out:

import threading

N = 3                                   # buffer slots
buffer = []
mutex = threading.Semaphore(1)          # protects the buffer
empty = threading.Semaphore(N)          # free slots
full = threading.Semaphore(0)           # filled slots
largest = 0
eaten = []

def producer():
    global largest
    for item in range(1, 11):
        empty.acquire()                 # wait(empty)
        with mutex:
            buffer.append(item)
            largest = max(largest, len(buffer))
        full.release()                  # signal(full)

def consumer():
    for _ in range(10):
        full.acquire()                  # wait(full)
        with mutex:
            eaten.append(buffer.pop(0))
        empty.release()                 # signal(empty)

threads = [threading.Thread(target=producer), threading.Thread(target=consumer)]
for t in threads:
    t.start()
for t in threads:
    t.join()
print("consumed in order:", eaten)
print("buffer never held more than", N, "items:", largest <= N)
consumed in order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
buffer never held more than 3 items: True

The two threads interleave differently on every run, yet the output is always the same — that is what correct synchronisation means. Each semaphore has one job: empty stops the producer when the buffer is full, full stops the consumer when it is empty, and mutex stops them from changing the list at the same moment.

5. Peterson's solution (two processes, no special hardware)

flag[i] = true          // I want to enter
turn = j                // but you may go first
while (flag[j] and turn == j) { }   // wait
    ... critical section ...
flag[i] = false

Both processes set turn to the other one; whoever wrote last waits. It satisfies all three rules — mutual exclusion, progress and bounded waiting. It is taught because it is a neat proof, but on modern CPUs that reorder memory operations it needs memory barriers to be correct, so real code uses hardware atomic instructions instead.

6. Readers–writers (readers first)

Many readers may read together; a writer needs the data alone. Two semaphores, rw = 1 and m = 1, and a counter readers = 0:

Writer:                 Reader:
  wait(rw)                wait(m)
  ... write ...           readers = readers + 1
  signal(rw)              if readers == 1: wait(rw)    // first reader locks writers out
                          signal(m)
                          ... read ...
                          wait(m)
                          readers = readers - 1
                          if readers == 0: signal(rw)  // last reader lets writers in
                          signal(m)

Only the first reader waits on rw and only the last releases it. The weakness: a steady stream of readers can starve writers. "Writers-first" versions fix that at the cost of more semaphores.

7. Dining philosophers

Five philosophers P0 to P4 around a table with five forks F0 to F4 between them; each needs both neighbouring forks, and if everyone takes the left fork first they deadlock

If every philosopher does wait(left fork) then wait(right fork), all five can take their left fork at the same instant and wait for ever — all four deadlock conditions hold. Correct fixes, each breaking one condition:

FixCondition broken
Allow at most 4 philosophers at the table (a counting semaphore set to 4)circular wait — at least one can get both forks
Asymmetric: odd philosophers take left first, even ones right firstcircular wait
Pick up both forks or neither (check inside a critical section)hold and wait

Common mistakes

  • Thinking the final semaphore value depends on the order of waits and signals — it does not.
  • Swapping wait(empty) and wait(mutex) in the producer: a producer holding the mutex while the buffer is full blocks the consumer for ever.
  • Forgetting the readers counter needs its own mutex.
  • Believing the deadlock-free dining philosophers solutions also prevent starvation — they do not automatically.

Quick recap

  • wait: S −= 1, block if S < 0. signal: S += 1, wake one if S ≤ 0. Negative S = number blocked.
  • Final value = initial + signals − waits.
  • Unprotected x = x + 1 in two threads can lose updates.
  • Bounded buffer: empty = N, full = 0, mutex = 1, and the order of waits matters.
  • Readers-writers: first reader locks, last reader unlocks. Dining philosophers: break circular wait or hold-and-wait.

Practice what you learned

📝 Quiz: Semaphores and Classic Problems5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →