Unit 2 · Concurrent Processes

Lecture 6: Semaphores

Learning outcomes

Define a semaphore and explain why its operations must be atomic.
Differentiate binary and counting semaphores with correct use cases.
Use wait() / signal() to implement mutual exclusion and resource synchronization.
Explain why modern semaphores avoid long busy-waiting using a waiting queue.

Prerequisites

Race condition and critical section concepts (Unit 2, Lecture 2–3). Mutual exclusion, progress, bounded waiting (critical-section requirements). Basic idea of blocking/wakeup by OS scheduler (Ready/Waiting states).

Lecture Notes

Main content

Semaphores (Binary & Counting) — Synchronization Primitive

1) What is a Semaphore?

A semaphore is a synchronization primitive provided by the operating system. It is an integer variable that is accessed only through two operations: wait() and signal(). These operations are atomic (cannot be interrupted in the middle), so they safely coordinate concurrent processes/threads.

Atomic means:

Either the entire wait()/signal() operation happens, or none of it happens. No other thread/process can “see” a half-completed update to the semaphore value.

2) The two operations: wait() and signal()

wait(S) (P / down)

Decrements S.
If resources are not available, the calling process blocks (sleeps).

signal(S) (V / up)

Increments S.
If some process is waiting, the OS wakes up one waiting process.

// Semaphore S structure (conceptual)
struct semaphore {
  int value;
  queue<process> wait_queue;
}

// Atomic operations (conceptual)
wait(S) {
  S.value--;
  if (S.value < 0) {
    add this process to S.wait_queue;
    block();   // move to Waiting state
  }
}

signal(S) {
  S.value++;
  if (S.value <= 0) {
    remove one process P from S.wait_queue;
    wakeup(P); // move P to Ready state
  }
}

3) Semaphore internals: value + waiting queue (no long busy-wait)

A key OS idea is: if a thread cannot proceed, it should sleep instead of wasting CPU cycles in a spin loop. Therefore, a semaphore is typically implemented as an integer plus a waiting queue.

wait(), a process may move to the queue and block; on signal(), one waiting process is woken up.

Semaphores block and wake processes using a queue, avoiding long busy-wait loops.

4) Types of Semaphores

Type	Value Range	Primary Meaning	Typical Use
Binary semaphore	0 or 1	Acts like a single permit (lock/unlock behavior)	Mutual exclusion for a critical section
Counting semaphore	0 to N	Counts available instances of a resource	Control access to a pool of identical resources (N printers, N buffer slots)

Binary semaphore vs Mutex (concept)

A mutex typically has ownership (the locker must unlock).
A binary semaphore does not strictly enforce ownership; one thread can signal() what another thread wait()ed on.
So: use mutex for pure mutual exclusion, use semaphore for signaling + counting resources.

5) Using semaphores for synchronization

5.1 Binary semaphore for mutual exclusion (critical section)

// Shared
semaphore mutex = 1;   // binary (1 = free, 0 = busy)
int count = 0;

Process Pi:
do {
  wait(mutex);         // enter CS
  count = count + 1;   // critical section (shared update)
  signal(mutex);       // exit CS

  // remainder section
} while(true);

5.2 Counting semaphore for a pool of resources (N identical units)

// Suppose there are N printers
semaphore printers = N;

Process Pi:
do {
  wait(printers);      // request one printer (may block)
  // use printer
  signal(printers);    // return printer
} while(true);

5.3 Semaphore for ordering (event synchronization)

A semaphore initialized to 0 can enforce ordering: one process signals “event done”, the other waits for it.

semaphore S = 0;

// P1
print("A");
signal(S);

// P2
wait(S);
print("B");

6) Common mistakes (must avoid)

Deadlock by wrong ordering

If a thread holds a mutex while waiting for another semaphore/resource, it can block others from making progress. Always acquire semaphores in a consistent safe order.

Missing signal()

If you forget a signal() on some path (especially error/return paths), another process may block forever.

Worked Example

Bounded Buffer (Producer–Consumer) — semaphores used together

This classic example shows both types of semaphores together: counting semaphores track available slots/items, and a binary semaphore provides mutual exclusion for buffer index updates.

Semaphores used

semaphore mutex = 1;  // binary, protects buffer access
semaphore empty = N;  // counting, free slots
semaphore full  = 0;  // counting, filled slots

empty prevents overflow (producer waits if buffer full).
full prevents underflow (consumer waits if buffer empty).
mutex prevents race conditions on buffer pointers/counters.

Producer & Consumer (standard order)

// Producer
do {
  // produce item x
  wait(empty);
  wait(mutex);
    // add x to buffer
  signal(mutex);
  signal(full);
} while(true);

// Consumer
do {
  wait(full);
  wait(mutex);
    // remove item y from buffer
  signal(mutex);
  signal(empty);
  // consume item y
} while(true);

Important:

Do not acquire mutex before empty/full. If a producer holds mutex and then waits for empty, it can block the consumer from entering and freeing space → deadlock risk.

One-Page Summary

Semaphore: integer synchronization variable accessed only via atomic wait() and signal().
wait(S): decrements; if unavailable, blocks the process and puts it into a waiting queue.
signal(S): increments; if processes are waiting, wakes one.
Binary semaphore (0/1): used like a lock for mutual exclusion (critical section protection).
Counting semaphore (0..N): controls access to N identical resources (N printers, N buffer slots).
No long busy-wait: semaphores typically block/wakeup via an OS-managed queue.
Illustrations:
- Binary semaphore protects shared counter update.
- Counting semaphore manages resource pool.
- Producer–consumer uses mutex (binary) + empty/full (counting).
Common errors: wrong wait order (deadlock risk), missing signal() (indefinite blocking).