Binary Semaphore

operating-systems concurrency

Definition

Binary Semaphore

A binary semaphore is a semaphore restricted to values $\{0,1\}$. It is used primarily to implement mutual exclusion for access to a single shared resource.

Operations

A binary semaphore supports two atomic operations:

Operation	Semantics	Effect
wait(S)	Acquire	If $S=1$, set $S=0$ and proceed; otherwise block until $S=1$
signal(S)	Release	Set $S=1$, potentially unblocking a waiting process

Mutual Exclusion Protocol

Semaphore S = 1                    // resource initially free

Void process()
    while (true) {
        wait(S);                   // acquire lock
        
        /* --- Critical Section --- */
        
        signal(S);                 // release lock
        
        /* --- Remainder Section --- */
    }

State Machine

The semaphore alternates between two states:

• $S=1$: resource available, next wait succeeds immediately
• $S=0$: resource held, processes block on wait

Comparison with Mutex

Ownership Distinction

A binary semaphore is functionally similar to a mutex, but differs in ownership semantics:

• Mutex: Only the process that locked the mutex may unlock it (ownership property)
• Binary semaphore: Any process may call signal(S), enabling different signalling patterns