Lecture 3: Semaphores

Semaphore

A special non-negative integer variable used for process synchronization, offering built-in power for mutual exclusion and condition synchronization.

P Operation (wait / down / acquire)

An atomic operation that waits until the semaphore value s > 0, then decrements s by 1.

V Operation (signal / up / release)

An atomic operation that increments the semaphore value s by 1 and awakens a blocked process if one is waiting.

Binary Semaphore

A semaphore that only takes values 0 or 1, most commonly used as a mutual exclusion lock (mutex).

Counting Semaphore

A general semaphore that can take any non-negative integer value, typically used to track available units of a shared resource.

Semaphore Fairness

Ensures that processes delayed inside P-operations are awoken in the order they were blocked (FIFO queueing).

Split Binary Semaphores

A set of binary semaphores where at most one semaphore in the set equals 1 at any given time (sum <= 1).

Bounded Buffer (Producer/Consumer)

A synchronization pattern that uses two counting semaphores (empty slots, full slots) and binary semaphores to protect array indices for asynchronous communication.

Dining Philosophers Problem

A classic concurrency problem illustrating deadlocks and resource allocation when multiple processes share limited adjacent resources.

Dining Philosophers Deadlock Solution

Break symmetry by requiring at least one process to pick up its required tools in reverse order (e.g., right tool first).

Readers/Writers Invariant

Allows multiple readers concurrent access when no writer is active, but requires exclusive access whenever a writer is modifying the dataset.

Passing the Baton Technique

An advanced design pattern where an exiting process evaluates state conditions and directly signals the specific semaphore of the next eligible waiting process.

Java Semaphore acquire()

Java method equivalent to the P operation; decrements permits or blocks until one is available.

Java Semaphore release()

Java method equivalent to the V operation; increments permits and unblocks a waiting thread.

Java Condition await()

Atomically releases an associated lock and suspends the thread until explicitly signaled by another thread.

Java Condition signal()

Wakes up one thread that is waiting on the given condition.