Semaphores: Binary and Counting

A Semaphore: A Counter With Two Atomic Operations

A semaphore is a shared integer variable, accessed only through two special operations - traditionally called wait() (or P) and signal() (or V) - that are guaranteed to execute atomically, meaning no race condition can occur on the semaphore's own value itself.

wait(S):
  while S <= 0:
      (thread waits here)
  S = S - 1

signal(S):
  S = S + 1

Binary Semaphores: Just 0 or 1

A binary semaphore only ever holds the value 0 or 1, functioning essentially as a lock - a thread calls wait() to acquire it (blocking if it's already taken) and signal() to release it, guaranteeing at most one thread holds it at any time.

Counting Semaphores: Managing a Limited Pool of Resources

Semaphore initialized to 3 (representing 3 available identical resources)

Thread A: wait(S)  -> S becomes 2, Thread A proceeds
Thread B: wait(S)  -> S becomes 1, Thread B proceeds
Thread C: wait(S)  -> S becomes 0, Thread C proceeds
Thread D: wait(S)  -> S is 0, Thread D must wait until someone calls signal()

A counting semaphore can hold any non-negative integer value, commonly used to manage a pool of several identical resources (like a fixed number of database connections) - its value represents how many units are currently available.

Using a Binary Semaphore to Solve the Critical Section Problem

Semaphore mutex = 1

wait(mutex)
    // critical section - only one thread can be here at a time
signal(mutex)

This directly solves the mutual exclusion requirement covered in the previous note: the first thread to call wait() succeeds and enters, while any other thread calling wait() afterward blocks until the first thread calls signal() to release it.

Why the Atomicity of wait()/signal() Is the Whole Point

Unlike the naive flag-checking approach that failed earlier in this section, a semaphore's wait() and signal() operations are guaranteed by the OS or hardware to execute as a single, uninterruptible step - eliminating exactly the race condition that made a plain flag variable unsafe.