OS Notes

Semaphores

Complete guide to semaphores — counting and binary semaphores, wait() and signal() operations, implementation, usage patterns, and solving synchronization problems with semaphores.

Introduction

In 1965, Edsger Dijkstra invented the semaphore — one of the most elegant synchronization tools in computer science. Named after the railroad signaling system (a semaphore is a flagged signal post that tells trains whether the track ahead is clear), a semaphore in OS is an integer variable that controls access to shared resources through two atomic operations: wait and signal.

Think of a semaphore like a bouncer at a nightclub counting people. The club has a maximum capacity (the semaphore value). Each person entering decrements the count (wait). Each person leaving increments it (signal). When the count reaches zero, new people must wait outside until someone leaves.

Types of Semaphores

Binary Semaphore (Mutex)

Value can only be 0 or 1. Used for mutual exclusion — like a lock. Either the resource is available (1) or taken (0).

Counting Semaphore

Value can range from 0 to N. Used to control access to a resource with multiple identical instances (e.g., a pool of database connections, limited printer slots).

Operations: wait() and signal()

Originally called P (proberen = to test, in Dutch) and V (verhogen = to increment):

Example

// wait() — also called P() or down() void wait(Semaphore *S) { S->value--; if (S->value < 0) { // Add this process to S->waiting_queue block(); // Process sleeps } } // signal() — also called V() or up() void signal(Semaphore *S) { S->value++; if (S->value <= 0) { // Remove a process P from S->waiting_queue wakeup(P); // Wake one sleeping process } }

Critical: Both operations must be atomic — they cannot be interrupted midway. The OS typically implements this using hardware disable-interrupts or spinlocks within the kernel.

Using Semaphores for Mutual Exclusion

c example

Semaphore mutex = 1;  // Binary semaphore, initially 1 (resource free)

// Process Pi
void process_i() {
    wait(&mutex);       // Entry section: decrement (becomes 0)
    
    // === CRITICAL SECTION ===
    // Only one process can be here at a time
    
    signal(&mutex);     // Exit section: increment (becomes 1 again)
}

When mutex = 1, the first process to call wait() enters (mutex becomes 0). Any other process calling wait() finds mutex = 0, decrements to -1, and blocks. When the first process calls signal(), mutex becomes 0 and one waiting process is woken.

Using Counting Semaphores for Resource Pools

Example

Semaphore pool = 5; // 5 database connections available void use_connection() { wait(&pool); // Acquire connection (pool--) // Use the database connection execute_query(); signal(&pool); // Release connection (pool++) } // Up to 5 processes can be inside simultaneously // The 6th process will block until one finishes

Using Semaphores for Ordering (Signaling)

Semaphores can enforce execution order between processes:

c example

Semaphore sync = 0;  // Initially 0

// Process A: Must execute Statement 1 BEFORE Process B executes Statement 2
// Process A:
execute_statement_1();
signal(&sync);          // Signal that statement 1 is done

// Process B:
wait(&sync);            // Wait until statement 1 is done
execute_statement_2();  // Only runs after statement 1

If B reaches wait() before A signals, B blocks. If A signals before B reaches wait(), the semaphore becomes 1 and B passes through without blocking.

Implementation Detail

c example

typedef struct {
    int value;
    struct ProcessList *waiting_queue;  // Queue of blocked processes
} Semaphore;

The waiting queue ensures fairness (FIFO wakeup) and prevents starvation. Processes that block on a semaphore are moved to the waiting queue and removed from the ready queue, freeing the CPU for productive work.

Semaphore vs Busy Waiting

Unlike spinlocks (which waste CPU cycles in a loop), semaphores put waiting processes to sleep. This is efficient when the wait is long. However, for very short critical sections (a few instructions), the overhead of sleeping/waking may exceed the cost of spinning.

Common Pitfalls

Deadlock: Two semaphores locked in opposite order by two processes

c example

// Process A:          // Process B:
wait(&S);             wait(&Q);
wait(&Q);  // BLOCKED wait(&S);  // BLOCKED — DEADLOCK!

Forgetting to signal: Process enters CS but crashes before signaling — semaphore remains locked forever

Wrong semaphore value: Initializing with wrong value (e.g., 0 instead of 1 for mutex)

Signal before wait: Can cause the semaphore count to exceed expected bounds

Real-World Analogy

A counting semaphore is like a parking lot with a limited number of spaces and an electronic sign showing available spots. When a car enters (wait), the count decreases. When a car leaves (signal), the count increases. When the sign shows 0, new cars must wait at the entrance. A binary semaphore is a single-car garage — either empty (available=1) or occupied (available=0).

Key Takeaways

Semaphores are integer variables with atomic wait() and signal() operations
Binary semaphores (0 or 1) provide mutual exclusion like locks
Counting semaphores (0 to N) control access to pools of N identical resources
Wait decrements and potentially blocks; signal increments and potentially wakes
Semaphores can enforce execution ordering between processes
Both operations MUST be atomic — implemented by the OS kernel
Incorrect semaphore use can cause deadlocks and permanent blocking
Semaphores are lower-level than monitors but more flexible

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Semaphores.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, semaphores

Continue learning this concept

Process SynchronizationCritical Section ProblemDeep dive into the critical section problem — requirements, software solutions (Peterson\Process SynchronizationDining Philosophers ProblemThe classic dining philosophers problem — problem statement, naive solution showing deadlock, correct solutions using semaphores, monitors, and resource hierarchy.Process SynchronizationMonitorsUnderstanding monitors as a high-level synchronization construct — encapsulation, condition variables, wait and signal operations, and comparison with semaphores.Process SynchronizationMutex LocksUnderstanding mutex locks for mutual exclusion — acquire and release operations, spinlocks vs blocking mutexes, recursive mutexes, and practical mutex usage patterns.Process SynchronizationProducer-Consumer ProblemThe classic producer-consumer (bounded buffer) synchronization problem — solutions using semaphores, mutex locks, and monitors with complete code examples.Process SynchronizationReaders-Writers ProblemThe readers-writers synchronization problem — first readers-writers problem (readers preference), second variant (writers preference), and starvation-free solutions.

PreviousReaders-Writers Problem NextIntroduction to Process Synchronization

OS Notes

Semaphores

Complete guide to semaphores — counting and binary semaphores, wait() and signal() operations, implementation, usage patterns, and solving synchronization problems with semaphores.

Introduction

Types of Semaphores

Binary Semaphore (Mutex)

Value can only be 0 or 1. Used for mutual exclusion — like a lock. Either the resource is available (1) or taken (0).

Counting Semaphore

Value can range from 0 to N. Used to control access to a resource with multiple identical instances (e.g., a pool of database connections, limited printer slots).

Operations: wait() and signal()

Originally called P (proberen = to test, in Dutch) and V (verhogen = to increment):

Example

Critical: Both operations must be atomic — they cannot be interrupted midway. The OS typically implements this using hardware disable-interrupts or spinlocks within the kernel.

Using Semaphores for Mutual Exclusion

c example

Semaphore mutex = 1;  // Binary semaphore, initially 1 (resource free)

// Process Pi
void process_i() {
    wait(&mutex);       // Entry section: decrement (becomes 0)
    
    // === CRITICAL SECTION ===
    // Only one process can be here at a time
    
    signal(&mutex);     // Exit section: increment (becomes 1 again)
}

Using Counting Semaphores for Resource Pools

Example

Using Semaphores for Ordering (Signaling)

Semaphores can enforce execution order between processes:

c example

Semaphore sync = 0;  // Initially 0

// Process A: Must execute Statement 1 BEFORE Process B executes Statement 2
// Process A:
execute_statement_1();
signal(&sync);          // Signal that statement 1 is done

// Process B:
wait(&sync);            // Wait until statement 1 is done
execute_statement_2();  // Only runs after statement 1

If B reaches wait() before A signals, B blocks. If A signals before B reaches wait(), the semaphore becomes 1 and B passes through without blocking.

Implementation Detail

c example

typedef struct {
    int value;
    struct ProcessList *waiting_queue;  // Queue of blocked processes
} Semaphore;

Semaphore vs Busy Waiting

Common Pitfalls

Deadlock: Two semaphores locked in opposite order by two processes

c example

// Process A:          // Process B:
wait(&S);             wait(&Q);
wait(&Q);  // BLOCKED wait(&S);  // BLOCKED — DEADLOCK!

Forgetting to signal: Process enters CS but crashes before signaling — semaphore remains locked forever

Wrong semaphore value: Initializing with wrong value (e.g., 0 instead of 1 for mutex)

Signal before wait: Can cause the semaphore count to exceed expected bounds

Real-World Analogy

Key Takeaways

Semaphores are integer variables with atomic wait() and signal() operations
Binary semaphores (0 or 1) provide mutual exclusion like locks
Counting semaphores (0 to N) control access to pools of N identical resources
Wait decrements and potentially blocks; signal increments and potentially wakes
Semaphores can enforce execution ordering between processes
Both operations MUST be atomic — implemented by the OS kernel
Incorrect semaphore use can cause deadlocks and permanent blocking
Semaphores are lower-level than monitors but more flexible

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Semaphores.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.

Search Terms

operating-systems, operating systems, operating, systems, process, synchronization, semaphores

Continue learning this concept

PreviousReaders-Writers Problem NextIntroduction to Process Synchronization