Semaphore — in parallel and concurrent programming, a semaphore is a counter-based synchronization primitive that provides synchronization and mutual exclusion between multiple processes or threads. A semaphore controls access to shared resources and allows a limited number of processes to access a resource at the same time. It has two main operations: wait (P, down) — decrements the counter and waits if necessary; signal (V, up) — increments the counter and wakes a waiting process. The semaphore was invented by Edsger Dijkstra in 1965.

What is a Semaphore?

A semaphore consists of a non-negative integer counter and two atomic operations that manage it. The counter indicates how many processes can access a resource simultaneously. A semaphore is a more general mechanism than a mutex — a mutex allows access to only one process (binary), while a semaphore can allow access to N processes (counting).

Types of Semaphores

1. Binary Semaphore

The counter can take values 0 or 1. It is equivalent to a mutex and ensures that only one process can enter a critical section at a time. It is used for mutual exclusion.

2. Counting Semaphore

The counter can take values from 0 to N. It manages parallel access to N identical resources (for example, 10 connections in a database connection pool, or 5 printers in a printer queue).

How a Semaphore Works

A semaphore provides two basic operations, both of which must be atomic (indivisible and uninterrupted):

wait() / P() / down() operation

wait(S):

S = S - 1

if S < 0:

block process (the process is added to the waiting queue)

When a process wants to access a resource, it calls wait(). The counter is decremented. If the counter becomes negative (no resource available), the process is blocked and waits.

signal() / V() / up() operation

signal(S):

S = S + 1

if S <= 0:

wake up one blocked process

When a process releases a resource, it calls signal(). The counter is incremented. If there are waiting processes (S ≤ 0), one of them is awakened and continues execution.

Example Scenario (Print Queue with 3 Printers)

• Semaphore initial value = 3 (3 printers available)
• Process A calls wait() → S = 2, gets a printer, prints
• Process B calls wait() → S = 1, gets a printer
• Process C calls wait() → S = 0, gets a printer
• Process D calls wait() → S = -1, no printer available, D is blocked and waits
• Process A calls signal() (printing finished) → S = 0, releases a printer, D wakes up and gets the printer

Code Examples

POSIX (C / Linux)

#include <semaphore.h>

#include <pthread.h>

sem_t semaphore;

// Initialize semaphore

sem_init(&semaphore, 0, 3); // 0 = thread-shared, 3 = initial value

void* worker(void* arg) {

sem_wait(&semaphore); // P operation, counter decreases

// Critical section - resource in use

printf("Thread %ld using resource\n", (long)arg);

sleep(2); // Simulate resource usage

sem_post(&semaphore); // V operation, counter increases, resource released

return NULL;

}

int main() {

pthread_t threads[5];

for (long i = 0; i < 5; i++) {

pthread_create(&threads[i], NULL, worker, (void*)i);

}

for (int i = 0; i < 5; i++) {

pthread_join(threads[i], NULL);

}

sem_destroy(&semaphore);

return 0;

}

Python (threading.Semaphore)

import threading

import time

# Semaphore allowing 3 resources

semaphore = threading.Semaphore(3)

def worker(worker_id):

print(f"Worker {worker_id} waiting for resource...")

semaphore.acquire() # wait()

print(f"Worker {worker_id} acquired resource")

time.sleep(2) # Resource usage

print(f"Worker {worker_id} releasing resource")

semaphore.release() # signal()

# Create 5 threads, but only 3 can run at the same time

threads = []

for i in range(5):

t = threading.Thread(target=worker, args=(i,))

threads.append(t)

t.start()

for t in threads:

t.join()

Java

import java.util.concurrent.Semaphore;

public class SemaphoreExample {

private static Semaphore semaphore = new Semaphore(3); // 3 permits

static class Worker extends Thread {

private int id;

Worker(int id) {

this.id = id;

}

public void run() {

try {

System.out.println("Worker " + id + " waiting...");

semaphore.acquire(); // wait()

System.out.println("Worker " + id + " acquired resource");

Thread.sleep(2000);

System.out.println("Worker " + id + " releasing resource");

semaphore.release(); // signal()

} catch (InterruptedException e) {

e.printStackTrace();

}

}

}

public static void main(String[] args) {

for (int i = 0; i < 5; i++) {

new Worker(i).start();

}

}

}

Classic Semaphore Problems

1. Producer–Consumer Problem

In a bounded buffer, the producer writes data and the consumer reads data.

Three semaphores are used:

• empty: number of empty slots (initial = BUFFER_SIZE)
• full: number of full slots (initial = 0)
• mutex: exclusive access to the buffer (initial = 1)

sem_t empty, full, mutex;

int buffer[BUFFER_SIZE];

int in = 0, out = 0;

void init() {

sem_init(&empty, 0, BUFFER_SIZE);

sem_init(&full, 0, 0);

sem_init(&mutex, 0, 1);

}

void* producer(void* arg) {

while (1) {

int item = produce_item();

sem_wait(&empty); // Wait for empty slot

sem_wait(&mutex); // Lock buffer

buffer[in] = item;

in = (in + 1) % BUFFER_SIZE;

sem_post(&mutex); // Unlock buffer

sem_post(&full); // Signal full slot

}

}

void* consumer(void* arg) {

while (1) {

sem_wait(&full); // Wait for full slot

sem_wait(&mutex); // Lock buffer

int item = buffer[out];

out = (out + 1) % BUFFER_SIZE;

sem_post(&mutex); // Unlock buffer

sem_post(&empty); // Signal empty slot

consume_item(item);

}

}

2. Readers–Writers Problem

Multiple readers can read simultaneously, but writers require exclusive access.

Solution (reader priority):

sem_t mutex, write_lock;

int read_count = 0;

void init() {

sem_init(&mutex, 0, 1); // Protects read_count

sem_init(&write_lock, 0, 1); // Write lock

}

void* reader(void* arg) {

while (1) {

sem_wait(&mutex);

read_count++;

if (read_count == 1) {

sem_wait(&write_lock); // First reader blocks writers

}

sem_post(&mutex);

// Reading operation

read_data();

sem_wait(&mutex);

read_count--;

if (read_count == 0) {

sem_post(&write_lock); // Last reader allows writers

}

sem_post(&mutex);

}

}

void* writer(void* arg) {

while (1) {

sem_wait(&write_lock);

// Writing operation (exclusive)

write_data();

sem_post(&write_lock);

}

}

3. Dining Philosophers Problem

Five philosophers sit around a circular table. There is one fork between each pair. To eat, a philosopher needs two forks. This problem involves deadlock and starvation.

Solution strategies:

• Allow at most 4 philosophers to sit at the table at the same time (semaphore = 4)
• Asymmetric solution: odd-numbered philosophers pick up the left fork first, even-numbered pick up the right fork first
• Waiter (arbiter) solution: a central authority grants permission

Advantages

• Manages parallel access to multiple resources
• Solves synchronization problems like producer–consumer
• Can be used to prevent deadlock when applied correctly
• Supported at the OS level (POSIX sem_t)
• Can be shared between processes and threads

Disadvantages

• Incorrect usage can cause deadlock (e.g., wrong wait/signal order)
• Priority inversion problem (a low-priority process holds a semaphore)
• Difficult to test and debug (race conditions can be intermittent)
• Busy-waiting may occur (in spinlock semaphores)
• Counter overflow risk (if signal() is called excessively)

Security and Best Practices

• Always pair operations: for every wait() there must be a corresponding signal(). Handle exceptions carefully — signal() must always be called.
• Avoid deadlock: always acquire semaphores in the same order. Be cautious with nested semaphores.
• Use timeouts: use sem_timedwait() (POSIX) to avoid infinite waiting.
• Prevent counter overflow: check maximum counter values and set limits.
• Test thoroughly: use tools like Helgrind (Valgrind) and ThreadSanitizer for thread-safety analysis.
• Document clearly: specify which semaphore protects which resource.

Conclusion

A semaphore is a powerful and flexible synchronization mechanism in concurrent programming. Counting semaphores are ideal for managing access to limited resources (connection pools, thread pools, limited hardware). Binary semaphores can be used like mutexes. Classic problems such as producer–consumer, readers–writers, and dining philosophers can be solved using semaphores. When used correctly, they enable thread-safe, efficient, and deadlock-free programs; when used incorrectly, they can lead to deadlocks, race conditions, and priority inversion. Understanding semaphores and applying them properly is a fundamental skill in parallel programming.