Skip to content

Semaphores

1. Introduction to Semaphores

A semaphore is a synchronization tool used to prevent race conditions among concurrent cooperative processes. It is essentially an integer variable used in a mutually exclusive manner to achieve synchronization.

  • Key Purpose: To manage access to a shared resource (Critical Section) and avoid data loss or deadlocks.

  • Types:

    • Counting Semaphore: The integer value can range from negative infinity to positive infinity.

    • Binary Semaphore: The value is restricted to 0 and 1.

2. Core Operations

Semaphores are managed through two atomic operations, often referred to by different synonyms:

Operation Synonyms Section Action
P() Wait, Down Entry Section Decrements the semaphore value (\(S = S - 1\)).
V() Signal, Up, Post, Release Exit Section Increments the semaphore value (\(S = S + 1\)).

3. Counting Semaphore Logic

A. The Down/Wait Operation (\(P\))

When a process wants to enter the critical section, it executes the Down(S) operation:

  1. Decrement: \(S.value = S.value - 1\).

  2. Check: If \(S.value < 0\), the process is blocked and its Process Control Block (PCB) is placed in a suspended list (Sleep state).

  3. Enter: If \(S.value \geq 0\), the process successfully enters the critical section.

B. The Up/Signal Operation (\(V\))

When a process leaves the critical section, it executes the Up(S) operation:

  1. Increment: \(S.value = S.value + 1\).

  2. Check: If \(S.value \leq 0\), it indicates there are processes waiting in the suspended list.

  3. Wake Up: The system selects a process from the suspended list (typically using FIFO) and wakes it up (moves it to the Ready Queue).

4. Interpreting Semaphore Values

The value of a counting semaphore at any given time provides specific information:

  • Positive Value (\(n\)): Indicates that \(n\) more processes can enter the critical section successfully without being blocked.

  • Zero (0): Indicates that the critical section is currently in use (or the limit is reached), and the next process to try will be blocked.

  • Negative Value (\(-n\)): The magnitude \(n\) represents the number of processes currently blocked and waiting in the suspended list.

5. Practical Example & Calculation

Consider a semaphore initialized with a value \(S = 10\).

  • If 6 P operations (Down) are performed: \(10 - 6 = 4\).

  • If 4 V operations (Up) are then performed: \(4 + 4 = 8\).

  • The final value of the semaphore is 8.

Key Rule for Competitive Exams:

  • Successful Operation: A process enters the critical section (\(S.value \geq 0\) after decrement).

  • Unsuccessful Operation: A process is blocked (\(S.value < 0\) after decrement).

1. Introduction to Binary Semaphores

A Binary Semaphore is a special type of semaphore that can only take two values: 0 and 1.

  • Shared Variable: It is an integer variable shared by multiple processes in a mutually exclusive manner.

  • Purpose: Primarily used to implement Mutual Exclusion (ensuring only one process enters the critical section at a time).

  • Comparison: While Counting Semaphores vary from \(-\infty\) to \(+\infty\), Binary Semaphores are simpler and more commonly used for basic locking mechanisms.

2. Core Operations

Binary semaphores rely on two main operations: Down and Up.

A. Down Operation (P / Wait)

This operation is used in the Entry Section of a process.

  1. Check Value: If the semaphore value (\(S\)) is currently 1, it is changed to 0. This is considered a successful operation, and the process enters the critical section.

  2. Blocking: If \(S\) is already 0, the operation is unsuccessful. The process is blocked and placed in a suspended list (Sleep state).

    • Note: In a binary semaphore, the value does not drop to -1; it remains at 0 while processes are blocked.

B. Up Operation (V / Signal)

This operation is used in the Exit Section of a process.

  1. Check Suspended List: The system first checks if there are any processes currently blocked in the suspended list.

  2. Wake Up: If the list is not empty, the semaphore value remains 0, but one process is selected from the suspended list and "woken up" (moved to the Ready Queue).

  3. Reset: If the suspended list is empty, the semaphore value is set to 1 (or remains 1 if it was already 1).

3. Mutual Exclusion Example

Consider two processes, \(P_1\) and \(P_2\), with a binary semaphore \(S\) initialized to 1.

  1. \(P_1\) arrives: Executes Down(S). Since \(S=1\), it becomes \(0\). \(P_1\) enters the Critical Section.

  2. \(P_2\) arrives: Executes Down(S). Since \(S=0\), \(P_2\) is blocked and added to the suspended list.

  3. \(P_1\) exits: Executes Up(S). It sees \(P_2\) in the suspended list, wakes \(P_2\) up, and \(S\) remains \(0\).

  4. \(P_2\) resumes: Now in the ready queue, \(P_2\) can eventually enter the Critical Section.

4. Key Takeaways for Problem Solving

  • Initial Value: If \(S=0\) initially, no process can enter the critical section until an Up operation is performed. This can lead to a deadlock if not handled correctly.

  • Success vs. Failure:

    • Successful Down: \(1 \rightarrow 0\) (Process enters CS).

    • Unsuccessful Down: \(0 \rightarrow 0\) (Process is blocked).

  • Synonyms:

    • Down = P = Wait

    • Up = V = Signal = Post