Semaphores for Synchronization in Operating Systems

Semaphores: Synchronization Tool

Semaphores are a synchronization tool designed to solve critical section and synchronization problems. A semaphore is an integer variable accessed only through two atomic operations: Wait and Signal. When a process modifies the semaphore's value, no other process can simultaneously modify that same semaphore value. The semaphore is initialized to a non-negative value.

Wait and Signal Operations

• Wait (P): Decrements the semaphore's value. If the value becomes negative, the process is blocked.
• Signal (V): Increments the semaphore's value. If the value is not positive, a blocked process waiting on this semaphore is unblocked.

The definitions are:

P(s):

while (s <= 0)
s--;

V(s):

s++;

Operating System Usage

Operating systems use semaphores to control access to critical sections or shared resources. The semaphore is initialized to a value corresponding to the number of available resources. Each process that wishes to use a resource performs a Wait operation on the semaphore. When the process releases the resource, it performs a Signal operation. When the semaphore's count reaches 0, it indicates that all resources are being used, and processes that want to use a resource will be blocked until the counter is greater than 0.

Implementation: Avoiding Busy Waiting

A common problem is that when a resource is unavailable, the process might engage in "busy waiting," repeatedly checking for availability and wasting CPU cycles. To avoid this, a locking mechanism is used. When a process finds a resource unavailable, it suspends itself and is placed in a queue associated with the semaphore, transitioning to a waiting state. Control then returns to the CPU scheduler, which selects another process for execution.

A blocked process waiting on a semaphore is restarted when another process executes a Signal operation. The process is restarted via a Wakeup operation, changing its state from waiting to ready. This process is then placed in the ready queue.

The Dining Philosophers Problem

Consider five philosophers who spend their lives thinking and eating. They share a circular table with five chairs, one for each philosopher. In the center of the table is a bowl of rice, and there are five single chopsticks for eating. When a philosopher thinks, they do not interact with their colleagues. When a philosopher gets hungry, they try to pick up the two chopsticks closest to them. They can only pick up one chopstick at a time and cannot take a chopstick already in the hand of another philosopher. The philosopher eats only when they have both chopsticks, and once finished, they put down the chopsticks and start thinking again.

A Classic Synchronization Problem

This is a classic synchronization problem, representing a large class of concurrency control problems. It illustrates the need to allocate multiple resources among multiple processes.

Proposed Solution

Each chopstick can be represented by a semaphore. A philosopher tries to grab a chopstick by executing a Wait operation on that semaphore. They release the chopsticks by executing the Signal operation.