Counting Semaphores: Managing Concurrent Resource Access in Operating Systems

Understand how counting semaphores control concurrent access to shared resources. This tutorial explains their functionality, implementation using `Down()` and `Up()` operations, and how they differ from binary semaphores, providing a robust mechanism for managing multiple processes or threads accessing a critical section.

Counting Semaphores for Concurrent Access to Resources

Understanding Counting Semaphores

A counting semaphore is a synchronization primitive used in operating systems to control access to shared resources among multiple processes or threads. Unlike a binary semaphore (which only allows 0 or 1 process access), a counting semaphore can allow multiple processes to enter a critical section (a section of code accessing a shared resource) concurrently, up to a predefined limit. This is a very powerful tool for coordinating access to resources in situations where multiple processes need to use the same resource but should not access it simultaneously.

Implementing a Counting Semaphore

A counting semaphore can be implemented using a structure like this:

struct Semaphore {
  int value; // Number of processes that can be in critical section.
  queueType L; // Queue of blocked processes.
};

value represents the number of available slots in the critical section. L is a queue of processes blocked because the critical section is full.

Semaphore Operations: Down and Up

void Down(Semaphore &S) {
  S.value--;
  if (S.value < 0) {
    put_process(PCB) in L; // Block if no slots are available
    sleep();
  }
}

void Up(Semaphore &S) {
  S.value++;
  if (S.value <= 0) {
    select a process from L;
    wakeup(); //Wake a blocked process.
  }
}

Down() attempts to enter the critical section; Up() signals that a slot is free.

How Counting Semaphores Work

The semaphore's value indicates the number of processes allowed in the critical section. A process decrements the value before entering and increments it upon exiting.

• If the value is negative, the process is added to the blocked queue and sleeps. This ensures that the number of processes in the critical section does not exceed the semaphore's value.
• If the value is positive, the process enters the critical section.
• When a process exits, it increments the semaphore. If the value was negative, it wakes up a blocked process.
• Processes are woken up in FIFO order.

A negative semaphore value shows the number of blocked processes.