Semaphores in OS

Semaphores: Detailed Notes with Examples

1. Introduction to Semaphores

A semaphore is a synchronization mechanism used to control access to shared resources in a concurrent system. Introduced by Edsger Dijkstra, semaphores solve critical section problems and avoid race conditions. They maintain an internal counter and manage two atomic operations:

• Wait (P): Decrements the counter. If the counter becomes negative, the process blocks.
• Signal (V): Increments the counter. If there are blocked processes, one is unblocked.

2. Semaphore Operations

Pseudocode for Wait and Signal

// Wait (P) Operation
procedure wait(S):
    S.count -= 1
    if S.count < 0:
        block the process and add it to S.queue

// Signal (V) Operation
procedure signal(S):
    S.count += 1
    if S.count <= 0:
        unblock a process from S.queue

3. Types of Semaphores

1. Binary Semaphore (Mutex)

• Values: 0 (locked) or 1 (unlocked).
• Used for mutual exclusion (e.g., protecting critical sections).
• Ex: Controlling access to a shared variable.

Pseudocode for Binary Semaphore

binary_semaphore mutex = 1

// Process 1
wait(mutex)
// Critical Section
signal(mutex)

// Process 2
wait(mutex)
// Critical Section
signal(mutex)

2. Counting Semaphore

• Values: Non-negative integers.
• Used when multiple instances of a resource are available (e.g., a buffer with N slots).
• Ex: Producer-Consumer problem with a buffer of size 5.

Pseudocode for Counting Semaphore

counting_semaphore empty = 5  // Initially, all slots are empty
counting_semaphore full = 0   // No slots are full
binary_semaphore mutex = 1    // For mutual exclusion

// Producer
while true:
    produce item
    wait(empty)
    wait(mutex)
    add item to buffer
    signal(mutex)
    signal(full)

// Consumer
while true:
    wait(full)
    wait(mutex)
    remove item from buffer
    signal(mutex)
    signal(empty)
    consume item

4. Classic Problems with Semaphores

1. Producer-Consumer Problem

• Problem: Producers add items to a buffer, and consumers remove them. Ensure no overflow/underflow and mutual exclusion.
• Solution:
  • Use empty (counting semaphore for empty slots).
  • Use full (counting semaphore for filled slots).
  • Use mutex (binary semaphore for buffer access).

C Code Example (POSIX Semaphores)

#include <semaphore.h>
#include <stdio.h>
#include <pthread.h>

#define BUFFER_SIZE 5

sem_t empty, full, mutex;
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

void *producer(void *arg) {
    for (int i = 0; i < 10; i++) {
        sem_wait(&empty);
        sem_wait(&mutex);
        buffer[in] = i;
        printf("Produced: %d\n", buffer[in]);
        in = (in + 1) % BUFFER_SIZE;
        sem_post(&mutex);
        sem_post(&full);
    }
    return NULL;
}

void *consumer(void *arg) {
    for (int i = 0; i < 10; i++) {
        sem_wait(&full);
        sem_wait(&mutex);
        int item = buffer[out];
        printf("Consumed: %d\n", item);
        out = (out + 1) % BUFFER_SIZE;
        sem_post(&mutex);
        sem_post(&empty);
    }
    return NULL;
}

int main() {
    pthread_t prod, cons;
    sem_init(&empty, 0, BUFFER_SIZE);
    sem_init(&full, 0, 0);
    sem_init(&mutex, 0, 1);

    pthread_create(&prod, NULL, producer, NULL);
    pthread_create(&cons, NULL, consumer, NULL);

    pthread_join(prod, NULL);
    pthread_join(cons, NULL);

    sem_destroy(&empty);
    sem_destroy(&full);
    sem_destroy(&mutex);
    return 0;
}

2. Readers-Writers Problem

• Problem: Multiple readers can read simultaneously, but writers need exclusive access.
• Solution:
  • Use rw_mutex (binary semaphore for writers).
  • Use mutex (binary semaphore to protect reader count).
  • Track read_count (number of active readers).

C Code Example

#include <semaphore.h>
#include <stdio.h>
#include <pthread.h>

sem_t rw_mutex, mutex;
int read_count = 0;

void *reader(void *arg) {
    sem_wait(&mutex);
    read_count++;
    if (read_count == 1) {
        sem_wait(&rw_mutex);
    }
    sem_post(&mutex);

    printf("Reading...\n");

    sem_wait(&mutex);
    read_count--;
    if (read_count == 0) {
        sem_post(&rw_mutex);
    }
    sem_post(&mutex);
    return NULL;
}

void *writer(void *arg) {
    sem_wait(&rw_mutex);
    printf("Writing...\n");
    sem_post(&rw_mutex);
    return NULL;
}

int main() {
    pthread_t r1, r2, w1;
    sem_init(&rw_mutex, 0, 1);
    sem_init(&mutex, 0, 1);

    pthread_create(&r1, NULL, reader, NULL);
    pthread_create(&w1, NULL, writer, NULL);
    pthread_create(&r2, NULL, reader, NULL);

    pthread_join(r1, NULL);
    pthread_join(w1, NULL);
    pthread_join(r2, NULL);

    sem_destroy(&rw_mutex);
    sem_destroy(&mutex);
    return 0;
}

5. Common Issues with Semaphores

• Deadlock: Occurs when processes wait indefinitely (e.g., incorrect order of wait calls).
• Starvation: Processes might never get access (e.g., writers in the readers-writers problem).
• Priority Inversion: Low-priority processes hold semaphores needed by high-priority ones.

6. Summary

• Binary Semaphores: Mutual exclusion (mutex locks).
• Counting Semaphores: Resource management (e.g., buffer slots).
• Use Cases: Producer-consumer, readers-writers, and thread synchronization.

By carefully coordinating wait and signal operations, semaphores ensure safe access to shared resources in concurrent systems.