Chapter 28: Semaphores

28.1 What is a Semaphore?

A semaphore is a synchronization primitive with a counter that controls access to a pool of resources. Threads decrement the counter (P or wait) to acquire a resource and increment it (V or signal) to release it. If the counter reaches zero, threads block until another thread signals.

Semaphores come in two types:

• Binary semaphore: counter is 0 or 1 (like a mutex, but without ownership)
• Counting semaphore: counter can be any non-negative value (N resources)

28.2 Semaphore Data Structure

struct semaphore {
    int count;
    struct spinlock lock;
    struct wait_queue waiters;
};

28.3 Semaphore Operations

/* Initialize a semaphore with N resources */
void sem_init(struct semaphore *s, int initial_count) {
    s->count = initial_count;
    spinlock_init(&s->lock);
    s->waiters = NULL;
}

/* P (wait / down / acquire): decrement counter, block if zero */
void sem_wait(struct semaphore *s) {
    uint64_t flags = local_irq_save();

    while (1) {
        spinlock_lock(&s->lock);

        if (s->count > 0) {
            s->count--;
            spinlock_unlock(&s->lock);
            local_irq_restore(flags);
            return;
        }

        /* Count is zero: add to wait queue and block */
        struct tcb *current = get_current_thread();
        current->state = PROCESS_BLOCKED;
        wait_queue_add(&s->waiters, current);

        spinlock_unlock(&s->lock);
        local_irq_restore(flags);

        thread_schedule();  /* Will return here when woken */
        flags = local_irq_save();
    }
}

/* V (signal / up / release): increment counter, wake one waiter if any */
void sem_signal(struct semaphore *s) {
    uint64_t flags = local_irq_save();
    spinlock_lock(&s->lock);

    s->count++;

    struct tcb *waiter = wait_queue_remove(&s->waiters);
    if (waiter) {
        waiter->state = PROCESS_READY;
        thread_enqueue(waiter);
    }

    spinlock_unlock(&s->lock);
    local_irq_restore(flags);
}

28.4 Producer-Consumer Problem

The classic use of semaphores is the bounded buffer (producer-consumer) problem. A fixed-size buffer is shared between producers (add items) and consumers (remove items).

/* Bounded buffer with semaphores */
#define BUFFER_SIZE 256
struct ring_buffer {
    int data[BUFFER_SIZE];
    int head, tail;
    struct semaphore empty;  /* Counts empty slots */
    struct semaphore full;   /* Counts full slots */
    struct semaphore mutex;  /* Protects buffer access (binary) */
};

void producer(struct ring_buffer *buf, int item) {
    sem_wait(&buf->empty);   /* Wait for an empty slot */
    sem_wait(&buf->mutex);   /* Exclusive access to buffer */

    buf->data[buf->head] = item;
    buf->head = (buf->head + 1) % BUFFER_SIZE;

    sem_signal(&buf->mutex); /* Release buffer */
    sem_signal(&buf->full);  /* Signal that a slot is full */
}

int consumer(struct ring_buffer *buf) {
    sem_wait(&buf->full);    /* Wait for a full slot */
    sem_wait(&buf->mutex);   /* Exclusive access to buffer */

    int item = buf->data[buf->tail];
    buf->tail = (buf->tail + 1) % BUFFER_SIZE;

    sem_signal(&buf->mutex); /* Release buffer */
    sem_signal(&buf->empty); /* Signal that a slot is empty */
    return item;
}

28.5 Differences Between Semaphore and Mutex

Property	Semaphore	Mutex
Counter	Any number (counting)	0 or 1 (binary)
Ownership	No owner	Has owner (can detect double-unlock)
Signal from any thread	Yes	Must be unlocked by owner
Recursive locking	Not applicable	Optional (recursive mutex)
Use case	Resource counting, signaling	Mutual exclusion

28.6 Our Implementation

Our kernel provides counting semaphores with a FIFO wait queue. Binary semaphores are just counting semaphores initialized to 1. Key uses:

• Ring buffer synchronization: for UART output (Chapter 33) and IPC channels
• Thread pool: semaphore counts available worker threads
• Event completion: binary semaphore signals that an asynchronous operation finished
• I/O request queue: semaphore limits outstanding I/O operations

28.7 Exercises

28.8 Summary

Semaphores are counting synchronization primitives that control access to a pool of resources. The P operation decrements and blocks at zero; the V operation increments and wakes a waiter. Semaphores solve classic problems like producer-consumer and can be used for signaling between threads. Unlike mutexes, semaphores have no ownership concept and can be signaled by any thread. Our kernel implements counting semaphores with FIFO wait queues and interrupt-safe operations.