Semaphores in Process Synchronization

In multiprogramming systems, multiple processes may need to access shared resources like files, printers, or memory. To handle this, operating systems use synchronization mechanisms. One of the most widely used mechanisms is the Semaphore.

A Semaphore is simply a variable (integer) used to control access to a shared resource by multiple processes in a concurrent system. It ensures that only the allowed number of processes can use a resource at a given time.

A semaphore works using two fundamental operations:

1. Wait (P operation / down)

• Decreases the semaphore value.
• If the value becomes negative, the process is blocked until the resource becomes available.

2. Signal (V operation / up)

• Increases the semaphore value.
• If there are waiting processes, one of them gets unblocked.

Features of Semaphores

• Mutual Exclusion: Semaphore ensures that only one process accesses a shared resource at a time.
• Process Synchronization: Semaphore coordinates the execution order of multiple processes.
• Resource Management: Limits access to a finite set of resources, like printers, devices, etc.
• Reader-Writer Problem: Allows multiple readers but restricts the writers until no reader is present.
• Avoiding Deadlocks: Prevents deadlocks by controlling the order of allocation of resources.

Types of Semaphores

Semaphores are mainly of two Types:

1. Counting Semaphore

• Used when multiple instances of a resource exist.
• The semaphore value can range over an unrestricted domain (0 to N).
• Example: Managing access to a pool of 5 printers.

2. Binary Semaphore

• Special case of counting semaphore with only two values: 0 and 1.
• Works like a lock: either the resource is free (1) or busy (0).
• Example: Managing access to a single critical section.

To learn more refer: Types of Semaphores

Working of Semaphore

A semaphore works by maintaining a counter that controls access to a specific resource, ensuring that no more than the allowed number of processes access the resource at the same time.

To achieve synchronization, every critical section of code is surrounded by two operations- Wait (P operation) and Signal (V operation) that are discussed above.

Example: Let’s consider two processes P1 and P2 sharing a semaphore S, initialized to 1:

• State 1: Both processes are in their non-critical sections, and S = 1.
• State 2: P1 enters the critical section. It performs wait(S), so S = 0. P2 continues in the non-critical section.
• State 3: If P2 now wants to enter, it cannot proceed since S = 0. It must wait until S > 0.
• State 4: When P1 finishes, it performs signal(S), making S = 1. Now P2 can enter its critical section and again sets S = 0.

This mechanism guarantees mutual exclusion, ensuring that only one process can access the shared resource at a time, see the image below for reference:

Counting semaphore

A counting semaphore is useful when there are multiple identical resources. The semaphore’s value represents the number of available resources.

Pseudocode:

Semaphore structure:

struct semaphore{

int count; // number of available resources
queue q; // waiting processes

};

wait() method:

void wait(semaphore s) {

s.count--
if( s.count <=0 ){
// remove one process from the waiting queue and wake it up
}

}

• If s.count > 0 → resource available, a process can access it.
• If s.count <= 0 → no resource available, processes is added to the queue.

signal() method:

void signal(semaphore s) {

s.count++
if( s.count >0 ){
// assign the resource process queue

}

Code Implementation for Counting Semaphores:

struct Semaphore {  int value;  Queue<process> q; }; P(Semaphore s) // wait() {  s.value = s.value - 1;  if (s.value < 0) {  q.push(p);  block();  }  else  return; } V(Semaphore s) // signal() {  s.value = s.value + 1;  if (s.value <= 0) {  Process p = q.pop();  wakeup(p);  }  else  return; } 

typedef struct {  int value;  struct process_queue q; } Semaphore; void P(Semaphore* s) {  s->value = s->value - 1;  if (s->value < 0) {  push(&s->q, p);  block();  } } void V(Semaphore* s) {  s->value = s->value + 1;  if (s->value <= 0) {  Process p = pop(&s->q);  wakeup(p);  } } 

import java.util.LinkedList; import java.util.Queue; class Semaphore {  int value;  Queue<Process> q = new LinkedList<>();  void P() {  value = value - 1;  if (value < 0) {  q.add(p);  block();  }  }  void V() {  value = value + 1;  if (value <= 0) {  Process p = q.poll();  wakeup(p);  }  } } 

from collections import deque class Semaphore: def __init__(self): self.value = 0 self.q = deque() def P(self): self.value -= 1 if self.value < 0: self.q.append(p) block() def V(self): self.value += 1 if self.value <= 0: p = self.q.popleft() wakeup(p) 

Explanation

• Whenever a process executes wait(), if resources are unavailable, it is blocked and added to the queue.
• When a process finishes and calls signal(), another waiting process is woken up to use the resource.

Binary Semaphores

A binary semaphore works like an ON/OFF switch. Only one process can enter the critical section at a time.

Pseudocode

Semaphore structure:

struct Semaphore{

int value; // can be 0 or 1
queue q;

};

wait() method:

void wait(semaphore s) {

if( s.value == 1){
// acquire lock
}
else {
// resource not available, block process
}

}

• Value = 1 → Resource is free, process can enter.
• Value = 0 → Resource is locked, other processes must wait.

signal() method:

void signal(semaphore s) {

if( q is empty){
// release lock
}
else {
// wake up one waiting process
}

}

Code Implementation for Binary Semaphore:

struct semaphore {  enum value(0, 1);  Queue<process> q; }; P(semaphore s) // wait() {  if (s.value == 1) {  s.value = 0;  }  else {  q.push(P) sleep();  } } V(semaphore s) // signal() {  if (s.q is empty) {  s.value = 1;  }  else {  Process p = q.front();  q.pop();  wakeup(p);  } } 

typedef enum { ZERO, ONE } value; typedef struct {  value s_value;  process q[MAX_PROCESSES];  int front, rear; } semaphore; void P(semaphore* s) {  if (s->s_value == ONE) {  s->s_value = ZERO;  }  else {  enqueue(s, P);  sleep();  } } void V(semaphore* s) {  if (is_empty(s)) {  s->s_value = ONE;  }  else {  process p = dequeue(s);  wakeup(p);  } } 

enum Value { ZERO, ONE } import java.util.LinkedList; import java.util.Queue; class Semaphore {  Value value = Value.ONE;  Queue<Process> q = new LinkedList<>(); } void P(Semaphore s) {  if (s.value == Value.ONE) {  s.value = Value.ZERO;  }  else {  s.q.add(P);  sleep();  } } void V(Semaphore s) {  if (s.q.isEmpty()) {  s.value = Value.ONE;  }  else {  Process p = s.q.poll();  wakeup(p);  } } 

from queue import Queue from enum import Enum class Value(Enum): ZERO = 0 ONE = 1 class Semaphore: def __init__(self): self.value = Value.ONE self.q = Queue() def P(s): if s.value == Value.ONE: s.value = Value.ZERO else: s.q.put(P) sleep() def V(s): if s.q.empty(): s.value = Value.ONE else: p = s.q.get() wakeup(p) 

Limitations of Semaphores

• Priority Inversion: A low-priority process holding a semaphore can block a high-priority one.
• Deadlock: Processes may wait on each other’s semaphores in a cycle, causing indefinite blocking.
• Complex to Manage: The OS must carefully track wait and signal calls; misuse can cause errors.
• Busy Waiting: In basic implementations, processes may keep checking the semaphore value, wasting CPU time.