Semaphore in Programming

Overview

• Semaphore: A variable or abstract data type used in computer science to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system.
• Synchronization primitive: Semaphores are a type of synchronization primitive.
• Trivial Semaphore: A plain variable that can be incremented or decremented based on conditions.

Real-World Analogy

• Library Study Rooms:
  • Represents a semaphore where the number of free rooms corresponds to the semaphore count.
  • Access to rooms is controlled by decrementing the semaphore value.
  • When a room is freed, the semaphore value is incremented.

Types of Semaphores

• Counting Semaphores: Allow arbitrary resource counts.
• Binary Semaphores: Restricted to 0 and 1, used to implement locks.

History

• Invented by Edsger Dijkstra in 1962/1963 while developing an operating system for Electrologica X8.

Important Observations

• Semaphores track the number of available resources, not which resources are free.
• Protocol success requires all applications to follow it correctly to avoid issues like:
  • Forgetting to release resources.
  • Releasing unrequested resources.
  • Holding resources unnecessarily.
  • Using resources without acquiring them first.
• Deadlocks: Can occur when different resources are managed by different semaphores.

Semantics and Implementation

• P and V Operations:
  • V (Increment): Increases semaphore count, making a resource available.
  • P (Decrement): Decreases semaphore count, blocking if resources are unavailable.
  • Atomicity is crucial to prevent errors.

Producer-Consumer Problem

• Semaphores Used:
  • emptyCount: Tracks empty slots.
  • fullCount: Tracks filled slots.
  • useQueue: Ensures queue integrity.
• Procedure:
  • Producer decreases emptyCount, uses useQueue, and increases fullCount.
  • Consumer decreases fullCount, uses useQueue, and increases emptyCount.

Passing the Baton Pattern

• Usage: Solves concurrency issues by using private semaphores for processes and a mutual exclusion semaphore.
• Principle: One process "passes the baton" to another, ensuring only one process is active at a time.

Semaphores vs. Mutexes

• Mutex: A locking mechanism with specific rules, ensuring:
  • Only the task that locked it can unlock it.
  • Priority inversion can be managed.
  • Task termination handled safely.
  • Prevention of accidental release.

Key Problems in Synchronization

• Priority Inversion
• Premature Task Termination
• Deadlocks
• Starvation

Related Concepts

• Async/await
• Flags, Mutexes, and Synchronization
• Various concurrency problems like Dining Philosophers, Readers-Writers, etc.