Binary Semaphores and Mutual Exclusion: Controlling Concurrent Access to Shared Resources

Understand binary semaphores and their role in enforcing mutual exclusion in concurrent programming. This guide explains how binary semaphores work, comparing them to mutexes, and detailing the Down() and Up() operations for managing access to shared resources.

Binary Semaphores and Mutual Exclusion

Binary Semaphores: Ensuring Mutual Exclusion

While counting semaphores allow multiple processes to access a resource concurrently, a binary semaphore enforces mutual exclusion—only one process can access a shared resource at a time. This is achieved by limiting the semaphore's value to 0 or 1. A binary semaphore is functionally very similar to a mutex, but they are implemented differently.

Implementing a Binary Semaphore

Here's a possible structure for a binary semaphore:

struct Bsemaphore {
  enum Value { 0, 1 }; // Value is either 0 (locked) or 1 (unlocked)
  QueueType L; // Queue of blocked processes
};

L holds the process control blocks (PCBs) of processes waiting for the semaphore.

Semaphore Operations: Down and Up

Down Operation

The Down() operation attempts to acquire the resource (enter the critical section):

void Down(struct Bsemaphore &S) {
  if (S.value == 1) { //Resource available
    S.value = 0; 
  } else {
    //Add process to blocked queue.
    sleep(); //Process blocks until woken
  }
}

Up Operation

The Up() operation releases the resource:

void Up(struct Bsemaphore &S) {
  if (S.L.isEmpty()) { // No waiting processes
    S.value = 1;
  } else {
    //Remove a process from the blocked queue.
    wakeup(); //Wake a blocked process.
  }
}