Semaphore Notes

Introduction

  • Semaphores are a blocking synchronization mechanism that uses the scheduler.

  • They allow processes to communicate through signals, forcing them to wait.

  • A semaphore acts as a barrier.

Principles of Operation

  • Semaphores use a decrement/increment mechanism.

  • Initialization: Semaphore S is initialized with a positive integer.

  • Wait: If S <= 0, the process waits; if S > 0, the process proceeds and S is decremented.

  • Signal: S is incremented.

  • The initial value determines how many processes can enter the critical section.

Counting Semaphore

  • Controls access to a resource with finite capacity.

  • Counts available resource units.

  • Initialized to a positive number.

  • wait() decrements the counter; signal() increments it.

Binary Semaphore – Mutual Exclusion

  • Guarantees mutual exclusion.

  • Initialized to 1, allowing one process in the critical section at a time.

  • Can implement mutex locks.

Implementation Details

  • Initialization: Semaphore is set to a positive value; the waiting queue is empty.

  • System calls: block() blocks the current process; wakeup(process) wakes up a process.

  • Code for wait(Semaphore S):

    S.value --;
if (S.value < 0) {
  add this process to S.plist;
  block();
}

  • Code for signal(Semaphore S):

    S.value ++;
if (S.value <= 0) {
  remove a process P from S.plist;
  wakeup(P);
}

  • Semaphore structure definition:

    typedef struct {
  int value;
  Queue plist;
} Semaphore;

init(Semaphore S, int val) {
  S.value = val;
  S.plist = empty queue;
}
Semaphore Counter

  • S.value >= 0: Number of available resources.

  • S.value < 0: Number of waiting processes.

Wait() Procedure

  • Decrements semaphore before checking if the process should wait.

  • Negative value indicates waiting processes.

  • block operation places the process in a waiting queue.

  • Code for wait(semaphore S):

    S.value--;
if (S.value < 0) {
  add this process to S.plist;
  block();
}
Signal() Procedure

  • Increments semaphore value.

  • If value <= 0, processes are waiting.

  • wakeup() restarts a waiting process.

  • A FIFO queue ensures bounded waiting.

  • Code for signal(semaphore S):

    S.value++;
if (S.value <= 0) {
  remove a process P from S.plist;
  wakeup(P);
}
Example: Binary Semaphore - Mutual Exclusion

  • Achieved by initializing the semaphore with 1: init(S, 1)

  • Demonstration of processes interacting with semaphore and blocked queue.

Semaphore Operations Example

  • Example calculation: Initialized to 8, 12 wait operations, and 7 signal operations result in a value of 3.

Semaphore Synchronization Example

  • Two semaphores, S and Q, ensure P1 executes before P2.

Deadlock Scenario Example

  • Two processes waiting on each other's semaphores result in a deadlock.

Concurrent Processes Example

  • Three concurrent processes and semaphores demonstrate process synchronization.