Concurrency

Semaphores

The atomic primitive variable managing resource scheduling and mutual exclusion.

What is Semaphores?

A Semaphore is a kernel synchronization variable that controls access to shared system resources. It consists of an integer value counter and a process thread queue. It provides two atomic operations: wait/acquire (P) and signal/release (V) to block/wake processes safely.

Key Characteristics:

  • Counting Semaphores manage multiple concurrent instances of a resource.
  • Binary Semaphores (Mutexes) restrict access to a single client.
  • Operations P() and V() execute atomically without interruption.
  • Implements queue sleeping to eliminate active polling CPU waste.

Complexity Analysis

Avg Time Complexity: O(1) constant scheduling time
Space Complexity: O(1) primitive integer memory allocation
Best Case: O(1) (resource available immediately without sleeping)
Worst Case: Thread sleep suspension inside wait block

How it Works Step-by-Step

  1. P (Wait) Operation: Decrement value: value = value - 1.
  2. Suspend: If value < 0, suspend thread, insert it into queue, and sleep.
  3. V (Signal) Operation: Increment value: value = value + 1.
  4. Wake: If value <= 0, remove a thread from queue, and wake it up.

Code Implementation

Worked Trace Example

Managing 1 printer with Semaphore S initialized to 1:
1. Thread A calls P(S): S decrements to 0. Thread A prints.
2. Thread B calls P(S): S decrements to -1. S < 0, Thread B is blocked and put to sleep.
3. Thread A finishes, calls V(S): S increments to 0. Since S <= 0, Thread B is woken up.
Result: Serialized printer access.

Ready to Understand Semaphores Visually?

Don't just read about it. Launch our interactive, premium OS visualizer to see the processes, memory blocks, Page replacement queues, or disk head movements update in real-time.

Launch Semaphores Visualizer →