Semaphores — binary and counting, P() and V() operations

WHY do we even need semaphores?

WHAT is a semaphore? A non-negative integer plus two atomic operations. HOW does it work? The value tells you how many threads may still proceed; the operations adjust it safely.

The definition, built from first principles

Deriving P() and V() from what we want

We want $S$ to mean: "number of permits currently available."

HOW P() must behave: to take a permit, we must (a) wait until one exists ( $S>0$ ), then (b) atomically decrement.

P(S):\quad \textbf{while } S = 0 \textbf{ do wait}; \qquad S \leftarrow S - 1

In this pure busy-wait form $S$ never goes negative — it stays in $\{0,1,2,\dots\}$ and simply counts permits. The test ( $S=0$ ) and the decrement must happen as one atomic test-and-decrement, otherwise two threads could both see $S>0$ and both decrement.

HOW V() must behave: to release a permit, just increment (and a waiting thread will see $S>0$ on its next loop).

V(S):\quad S \leftarrow S + 1

P(S):\ S \leftarrow S-1;\ \textbf{if } S<0 \textbf{ then block(self)}

V(S):\ S \leftarrow S+1;\ \textbf{if } S\le 0 \textbf{ then wakeup(one waiter)}

Binary vs Counting

Figure — Semaphores — binary and counting, P() and V() operations

Worked Example 1 — Mutual exclusion (binary)

Goal: only one thread updates balance at a time.

semaphore mutex = 1            // 1 permit available
 
Thread:
    P(mutex)                   // Why? grab the only permit; others now block
    balance = balance + 100    // critical section — exclusive
    V(mutex)                   // Why? return the permit so someone else can enter

Why start at 1? Because one thread is allowed inside. The first $P$ makes mutex = 0; any second thread's $P$ sees $0$ and blocks until $V$ restores it.

Worked Example 2 — Counting (resource pool)

Goal: a printer pool with 3 printers.

semaphore printers = 3
 
Use a printer:
    P(printers)     // Why? value 3→2→1→0; 4th requester finds 0 and waits
    print_document()
    V(printers)     // Why? frees one printer, value goes back up, wakes a waiter

Why start at 3? Exactly 3 threads may print simultaneously; the 4th blocks until one finishes.

Worked Example 3 — Ordering with a 0-semaphore

Goal: line B in Thread‑2 must run after line A in Thread‑1.

semaphore done = 0     // no permit yet → forces waiting
 
Thread-1:              Thread-2:
    A                      P(done)   // blocks until permit appears
    V(done)                B         // runs only after A's V(done)

Why this step? Starting at $0$ means $P$ must block first. The signal can only come from Thread‑1's $V$ , guaranteeing $A$ happens-before $B$ .

Common Mistakes (Steel-manned)

Flashcards

What is a semaphore?

An integer guarded by the OS, accessed only via the atomic operations P() (wait/down) and V() (signal/up).

What does P() do (blocking version)?

Decrement S; if S<0, block the calling process on the semaphore's queue.

What does V() do (blocking version)?

Increment S; if S≤0, wake up one waiting process.

Why must P() and V() be atomic?

Otherwise a context switch between testing and updating S reintroduces the race condition the semaphore exists to prevent.

Range of a binary semaphore?

{0, 1}.

What value range can a counting semaphore take?

Any non-negative integer (unbounded); the initial value is chosen to equal the number of available resources. (In the blocking design it may go transiently negative to count blocked waiters.)

Initialize a semaphore to enforce mutual exclusion.

1 (binary).

Initialize a semaphore for a pool of k identical resources.

k (counting).

Initialize a semaphore for pure ordering / signaling.

0 — P() blocks until another thread V()s.

If S = -3, what does that mean (blocking semaphore)?

3 processes are currently blocked waiting on it.

Difference between a binary semaphore and a mutex?

A mutex has ownership (only the locker can unlock); a binary semaphore has no owner, so any thread may signal it.

What do P and V stand for?

Dutch: P = proberen (to test), V = verhogen (to increment); coined by Dijkstra.

How can two semaphores cause deadlock?

Threads acquire them in opposite orders → circular wait; fix by enforcing a global lock-ordering.

Consequence of a missing V()?

A permit is leaked → waiting threads block forever (starvation / resource leak).

In a pure busy-wait semaphore, can S go negative?

No — it loops on "while S==0" and only decrements when S>0, so it stays ≥ 0.

Recall Feynman: explain it to a 12-year-old

Imagine a small library with 3 reading chairs. At the door is a bowl with 3 tokens. To sit, you must grab a token (that's P); when leaving, you drop your token back (that's V). If the bowl is empty, you wait at the door until someone returns one. The number of tokens left tells everyone how many chairs are free. A binary semaphore is just a library with one chair and one token — only one person inside at a time.

Connections

Critical Section Problem — the problem semaphores solve.
Mutex Locks — the owned, exclusive cousin of a binary semaphore.
Producer-Consumer Problem — classic use of one mutex + two counting semaphores (empty, full).
Deadlock — caused by bad ordering of P() calls.
Race Condition — what atomic P()/V() prevents.
Monitors — a higher-level synchronization construct built on similar ideas.
Atomic Operations — the hardware foundation that makes P()/V() indivisible.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, semaphore ek simple cheez hai: ek integer counter jo OS protect karta hai, aur use sirf do operations se chhoo sakte ho — P() (wait/down) aur V() (signal/up). Isko aise socho ki ek bowl me tokens rakhe hain. Andar jaane ke liye token uthao (P), bahar aate waqt token wapas daal do (V). Token khatam ho gaye to door par wait karo. Counter batata hai kitne permits bache hain.

Binary semaphore matlab sirf 1 token — yaani ek hi banda andar (mutual exclusion, lock jaisa). Counting semaphore matlab N tokens se start — N resources ka pool, jaise 3 printers. Yaad rakho counting semaphore ki value ki koi fixed upper limit nahi hoti — woh kisi bhi non-negative integer tak ja sakti hai; bas hum use initialize resources ki ginti ke barabar karte hain. Aur agar tum semaphore ko 0 se start karo, to woh pure ordering/signaling ke liye kaam karta hai: ek thread P() pe ruk jaata hai jab tak doosra V() na de.

Ek detail jo log galat samajhte hain: pure busy-wait (spinlock) version me semaphore ki value kabhi negative nahi hoti — wahan loop "while S==0" hota hai aur decrement tabhi hota hai jab S>0 ho. Negative value sirf us blocking design me aati hai jahan OS process ko sula deta hai, aur tab |S| batata hai kitne processes wait kar rahe hain. P() aur V() atomic hone chahiye — agar tum khud "value padho phir ghatao" karoge to beech me context switch aa ke wahi race condition wapas aa jaayegi.

Do common galtiyan yaad rakho: (1) binary semaphore aur mutex same nahi hain — mutex me ownership hota hai, semaphore me nahi. (2) Do alag locks ko ulte order me lene se deadlock ho jaata hai, isliye hamesha ek fixed order me P() karo. Aur har P() ke saath ek V() zaroor karo, warna permit leak ho ke baaki threads forever block ho jaayenge.

Test yourself — Operating Systems

Connections