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

4.2.16 · Coding › Operating Systems

Semaphores ki ZAROORAT kyun hai?

KYA hota hai ek semaphore? Ek non-negative integer plus do atomic operations. KAISE kaam karta hai? Value batati hai ki kitne threads aage proceed kar sakte hain; operations ise safely adjust karte hain.

Definition, pehle principles se banai gayi

P() aur V() ko hum jo chahte hain usse derive karna

Hum chahte hain ki $S$ ka matlab ho: "abhi kitne permits available hain."

P() ka kya behavior hona chahiye: permit lene ke liye, hume (a) wait karna hoga jab tak ek exist na kare ( $S > 0$ ), phir (b) atomically decrement karna hoga.

P (S) : while S = 0 do wait; S \leftarrow S - 1

Is pure busy-wait form mein $S$ kabhi negative nahi jaata — yeh ${0, 1, 2, \dots}$ mein rehta hai aur simply permits count karta hai. Test ( $S = 0$ ) aur decrement ek atomic test-and-decrement ke roop mein hone chahiye, warna do threads dono $S > 0$ dekh sakti hain aur dono decrement kar sakti hain.

V() ka kya behavior hona chahiye: permit release karne ke liye, bas increment karo (aur ek waiting thread apne next loop par $S > 0$ dekhegi).

V (S) : S \leftarrow S + 1

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

V (S) : S \leftarrow S + 1; if S \leq 0 then wakeup(one waiter)

Binary vs Counting

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

Worked Example 1 — Mutual exclusion (binary)

Goal: sirf ek thread ek waqt mein balance update kare.

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

1 se kyun shuru karein? Kyunki ek thread andar allowed hai. Pehla $P$ mutex = 0 kar deta hai; kisi bhi doosri thread ka $P$ $0$ dekhega aur block ho jaayega jab tak $V$ usse restore na kare.

Worked Example 2 — Counting (resource pool)

Goal: 3 printers ke saath ek printer pool.

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

3 se kyun shuru karein? Exactly 3 threads simultaneously print kar sakti hain; 4th block ho jaati hai jab tak koi ek finish na kare.

Worked Example 3 — Ordering with a 0-semaphore

Goal: Thread‑2 mein line B, Thread‑1 mein line A ke baad run ho.

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)

Yeh step kyun? $0$ se start karna matlab hai $P$ zaroor pehle block karega. Signal sirf Thread‑1 ke $V$ se aa sakta hai, guarantee karta hai ki $A$ happens-before $B$ .

Common Mistakes (Steel-manned)

Flashcards

Semaphore kya hota hai?

OS ke through guard kiya gaya ek integer, sirf atomic operations P() (wait/down) aur V() (signal/up) ke through access hota hai.

P() kya karta hai (blocking version)?

S

ko decrement karo; agar

S < 0

hai, toh calling process ko semaphore ki queue par block karo.

V() kya karta hai (blocking version)?

S

ko increment karo; agar

S \leq 0

hai, toh ek waiting process ko wake up karo.

P() aur V() atomic kyun hone chahiye?

Warna

S

ko test karne aur update karne ke beech ek context switch usi race condition ko wapas le aata hai jise rokne ke liye semaphore exist karta hai.

Binary semaphore ka range?

{0, 1}

Counting semaphore kya value range le sakta hai?

Koi bhi non-negative integer (unbounded); initial value available resources ki sankhya ke barabar choose ki jaati hai. (Blocking design mein yeh transiently negative ho sakta hai blocked waiters count karne ke liye.)

Mutual exclusion enforce karne ke liye semaphore initialize karo.

1 (binary).

k

identical resources ke pool ke liye semaphore initialize karo.

k

(counting).

Pure ordering / signaling ke liye semaphore initialize karo.

0 —

P ()

block karta hai jab tak koi doosri thread

V ()

na kare.

Agar

S = - 3

hai, toh iska kya matlab hai (blocking semaphore)?

3 processes currently us par blocked hokar wait kar rahi hain.

Binary semaphore aur mutex mein kya fark hai?

Mutex mein ownership hoti hai (sirf locker unlock kar sakta hai); binary semaphore ka koi owner nahi, toh koi bhi thread usse signal kar sakti hai.

P aur V kiska short form hai?

Dutch: P = proberen (test karna), V = verhogen (increment karna); Dijkstra ne yeh naam diye.

Do semaphores deadlock ka cause kaise ban sakte hain?

Threads unhe opposite orders mein acquire karti hain → circular wait; global lock-ordering enforce karke fix karo.

Missing

V ()

ka kya consequence hai?

Ek permit leak ho jaata hai → waiting threads forever block ho jaati hain (starvation / resource leak).

Pure busy-wait semaphore mein, kya

S

negative ho sakta hai?

Nahi — yeh "while

S = 0

" par loop karta hai aur sirf tabhi decrement karta hai jab

S > 0

ho, isliye yeh

\geq 0

rehta hai.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek chhoti library hai jisme 3 reading chairs hain. Darwaze par ek bowl hai jisme 3 tokens hain. Baithne ke liye, tumhe ek token lena hoga (woh hai P); jaate waqt, apna token wapas daalo (woh hai V). Agar bowl khali hai, toh darwaze par wait karo jab tak koi wapas na aaye. Baaki bache tokens ki sankhya sabko batati hai ki kitni chairs free hain. Ek binary semaphore sirf ek library hai jisme ek chair aur ek token hai — ek waqt mein sirf ek person andar.

Connections

Critical Section Problem — woh problem jise semaphores solve karte hain.
Mutex Locks — binary semaphore ka owned, exclusive cousin.
Producer-Consumer Problem — ek mutex + do counting semaphores (empty, full) ka classic use.
Deadlock — P() calls ki buri ordering se hota hai.
Race Condition — jo atomic P()/V() prevent karta hai.
Monitors — similar ideas par bani ek higher-level synchronization construct.
Atomic Operations — woh hardware foundation jo P()/V() ko indivisible banati hai.