Semaphores

Definition

A semaphore is an integer variable used for process synchronization. It’s more flexible than simple locks (mutex) because it can track multiple resources or signal multiple events. Only two atomic operations allowed: wait() and signal() (also called P and V operations).

Semaphore Operations

Two Operations

1. wait() (also called P, from Dutch “Proberen” = test)

wait(S) {
    S--;                    // Decrement
    if (S < 0) {
        // Block process, put in queue
        block();
    }
}

2. signal() (also called V, from Dutch “Verhogen” = increment)

signal(S) {
    S++;                    // Increment
    if (S <= 0) {
        // Wake up one waiting process
        wakeup();
    }
}

Critical Property: wait() and signal() are atomic - can’t be interrupted

Types of Semaphores

1. Binary Semaphore

Integer value: 0 or 1 only (acts like lock/mutex)

Initialization: S = 1 (resource available)

Usage: Mutual Exclusion

Semaphore s = 1;

wait(s);
// Critical Section (only one here)
shared_variable++;
signal(s);

Behavior:

Initial: s = 1
First wait(): s becomes 0, process enters
Second wait(): s becomes -1, process blocked

When signal() called: s becomes 0, wakes one process

2. Counting Semaphore

Integer value: 0 to N (tracks N resources)

Initialization: S = N (N available resources)

Usage: Resource allocation (pool of resources)

Semaphore available_buffers = 10;  // 10 buffers available

// Producer
wait(available_buffers);  // Use one buffer
produce_data();
signal(full_buffers);     // Signal data ready

// Consumer
wait(full_buffers);       // Wait for data
consume_data();
signal(available_buffers); // Release buffer

Behavior:

Initial: s = 3 (3 resources)
Process 1 wait(): s = 2 (2 resources left)
Process 2 wait(): s = 1 (1 resource left)
Process 3 wait(): s = 0 (no resources left)
Process 4 wait(): s = -1, BLOCKED (must wait)

Process 1 signal(): s = 0, wakes Process 4

Semaphore for Mutual Exclusion

Semaphore mutex = 1;

Process 1:              Process 2:
wait(mutex)             wait(mutex) [blocked, waits]
count++
signal(mutex)           now wait succeeds
                        count++
                        signal(mutex)

Semaphore for Ordering/Synchronization

Ensure Process B runs after Process A

Semaphore synch = 0;  // Initially 0 (block Process B)

Process A:                  Process B:
critical_section()          wait(synch)      [blocks here]
signal(synch)              critical_section()

Execution Flow:

1. Process A starts, does work
2. Process B starts, tries wait(synch) → blocked (synch=0)
3. Process A finishes, calls signal(synch) → synch becomes 1
4. Process B wakes up, continues

Classic Synchronization Problems

1. Producer-Consumer Problem

Scenario:

• Producer generates data
• Consumer uses data
• Limited buffer (size N)

Synchronization Needs:

• Producer waits if buffer full
• Consumer waits if buffer empty
• Only one modifies buffer at time

Solution with Semaphores:

Semaphore full = 0;          // Count of full slots
Semaphore empty = N;         // Count of empty slots
Semaphore mutex = 1;         // Mutual exclusion

Producer:
wait(empty);                 // Wait for empty slot
wait(mutex);
add_to_buffer();
signal(mutex);
signal(full);                // Signal data available

Consumer:
wait(full);                  // Wait for data
wait(mutex);
remove_from_buffer();
signal(mutex);
signal(empty);               // Signal empty slot available

2. Readers-Writers Problem

Scenario:

• Multiple readers (can read simultaneously)
• Multiple writers (exclusive access)
• Readers and writers can’t access simultaneously

Solution with Semaphores:

Semaphore read_mutex = 1;    // Protect reader count
Semaphore write_mutex = 1;   // Protect writer
int reader_count = 0;

Reader:
wait(read_mutex);
reader_count++;
if (reader_count == 1)
    wait(write_mutex);       // Block writers if first reader
signal(read_mutex);

// Read data

wait(read_mutex);
reader_count--;
if (reader_count == 0)
    signal(write_mutex);     // Allow writers if last reader
signal(read_mutex);

Writer:
wait(write_mutex);
// Write data
signal(write_mutex);

Semaphore Implementation

User-Level (Busy Waiting)

Using atomic test_and_set instruction:

struct Semaphore {
    int value;
    Queue waiting_queue;
};

wait(Semaphore *s) {
    while (test_and_set(&s->lock)) {
        // Spin
    }
    s->value--;
    if (s->value < 0) {
        add_to_queue(s->waiting_queue);
        release_lock(&s->lock);
        pause();            // Busy wait
    } else {
        release_lock(&s->lock);
    }
}

signal(Semaphore *s) {
    while (test_and_set(&s->lock)) {
        // Spin
    }
    s->value++;
    if (s->value <= 0) {
        remove_from_queue(s->waiting_queue);
        wakeup(process);
    }
    release_lock(&s->lock);
}

Kernel-Level (Sleep/Wakeup)

OS kernel manages waiting queue, processes sleep:

wait(Semaphore *s) {
    disable_interrupts();
    s->value--;
    if (s->value < 0) {
        add_to_waiting_queue(current_process);
        sleep();            // Actually sleep, don't spin
    }
    enable_interrupts();
}

signal(Semaphore *s) {
    disable_interrupts();
    s->value++;
    if (s->value <= 0) {
        wakeup(remove_from_queue());
    }
    enable_interrupts();
}

Much better than busy waiting!

Semaphore in Practice

POSIX Semaphores (C/Unix)

#include <semaphore.h>

sem_t semaphore;
sem_init(&semaphore, 0, 1);  // Binary semaphore, initial value 1

sem_wait(&semaphore);        // wait()
// Critical section
sem_post(&semaphore);        // signal()

sem_destroy(&semaphore);

Java Semaphore

import java.util.concurrent.Semaphore;

Semaphore mutex = new Semaphore(1);

try {
    mutex.acquire();
    // Critical section
    count++;
} finally {
    mutex.release();
}

Python

import threading

semaphore = threading.Semaphore(1)

with semaphore:
    # Critical section
    count += 1

Advantages of Semaphores

1. Simple: Easy to understand and use
2. Flexible: Can synchronize any number of resources
3. Mutual Exclusion: Prevents race conditions
4. Ordering: Can enforce execution order
5. Proven: Well-tested approach

Disadvantages of Semaphores

1. Correctness: Easy to make mistakes (forget wait/signal)
2. Deadlock: Wrong order of wait() calls causes deadlock
3. Starvation: Possible if not carefully designed
4. Not Composable: Can’t combine semaphores easily
5. Low-Level: Requires programmer to manage synchronization

Common Semaphore Mistakes

1. Forgetting wait()

// WRONG - no synchronization!
shared_variable++;
signal(s);

2. Forgetting signal()

wait(s);
shared_variable++;
// FORGOT signal(s) - DEADLOCK!

3. Wrong Order (Deadlock)

Thread 1:                    Thread 2:
wait(s1);                    wait(s2);
wait(s2);                    wait(s1);
// Circular wait → Deadlock!

4. Using for General Programming

Semaphores are synchronization primitive, not for logic control:

// WRONG - confusing
semaphore = 5;
wait(semaphore);
wait(semaphore);
// What does this mean? Hard to understand

Summary

Semaphores provide flexible synchronization mechanism for concurrent programs. Binary semaphores work like locks. Counting semaphores track multiple resources. Atomic wait() and signal() operations prevent race conditions. Semaphores are fundamental to solving producer-consumer and readers-writers problems. Modern approaches (monitors, condition variables) provide higher-level abstractions, but semaphores remain important for understanding synchronization concepts and are still widely used in systems programming.