Types of Semaphores: Binary, Counting and Mutex with Worked Examples
Learn what semaphore values mean, when calls block, and how counting, binary and mutex primitives differ through resource, lost-update and buffer traces.
KnowledgeGate Team
Exam prep & CS education

Many learners memorise wait() and signal() but cannot explain what a semaphore value represents, why a process blocks, or why a binary semaphore is not always a mutex. Real permits and queues reveal the traps that change exam answers.
Process Synchronization and Semaphores: A Worked Trace connects semaphores to the wider critical-section problem, Peterson's solution, and readers-writers. Counting, binary, and mutex semantics need a separate decision rule plus exact permit-handoff traces.
What a semaphore records and what its operations do
A semaphore is a synchronization variable changed only through atomic operations. The visible non-negative value is the number of permits currently available:
wait(S)takes one permit and decreasesSwhenS > 0. IfS = 0, the caller blocks and joins the waiting queue.signal(S)hands a permit directly to one waiting process. If nobody is waiting, it increasesS.
Atomic means the test and change form one indivisible action. If two processes test S = 1 non-atomically, both might see 1 and enter. With atomic wait(S), only one takes the permit; the other sees 0 and blocks.
Some textbooks let a negative internal value record the number waiting. Do not mix that convention with these traces: here, S never goes below zero, and a separate queue records waiters.
Types of semaphores and the distinctions that matter
Type | Allowed value | Typical initial value | What it controls | Ownership |
|---|---|---|---|---|
Counting semaphore |
|
| A pool of identical resources | No necessary owner |
Binary semaphore |
|
| A one-bit event or one permit | No necessary owner |
Mutex | Locked or unlocked | Unlocked | An owner-held critical section | Locker must unlock |
Strong and weak describe scheduling, not another value-range type. A strong semaphore defines a wake-up order such as FIFO. A weak semaphore leaves it unspecified and can permit starvation.
Count interchangeable resources with a counting semaphore, pass a one-bit event with a binary semaphore, and protect an owner-held critical section with a mutex. CS Fundamentals for Exams & Placements places these choices in the broader operating-systems context.
Worked example: counting three resources
Assume resources R1, R2, and R3, with available = 3. Held is the number currently assigned. At every row, S + held = 3; a waiter holds nothing.
Event | Result | Visible | Held | Queue | Check |
|---|---|---|---|---|---|
Start | All resources free | 3 | 0 |
|
|
|
| 2 | 1 |
|
|
|
| 1 | 2 |
|
|
|
| 0 | 3 |
|
|
|
| 0 | 3 |
|
|
|
| 0 | 3 |
|
|
|
| 1 | 2 |
|
|
|
| 2 | 1 |
|
|
|
| 3 | 0 |
|
|
At P2 signal, the permit goes straight to P4, so the visible count does not briefly rise to 1. Only the holder changes.

Worked example: binary semaphore versus a lost update
Start with shared count = 41. Without exclusion, this interleaving loses one increment:
P1reads41.P2reads41.Each computes
42.P1writes42.P2writes42.
The result is 42, although two increments from 41 should give 43.
Now protect the read, addition, and write with mutex = 1: wait(mutex); temp = count; temp = temp + 1; count = temp; signal(mutex).
P1 changes mutex from 1 to 0, reads 41, and writes 42. P2 reaches wait(mutex) at 0 and blocks. P1 then signals, handing the permit directly to P2 while the visible value stays 0. P2 reads 42, writes 43, and signals with no waiter, restoring mutex = 1. The correct result is 43.
This binary semaphore acts like a lock, but it is not necessarily a mutex. Another process may signal it to announce an event; only the owner may release a mutex.

How semaphore types cooperate in a bounded buffer
For capacity 4, initialise empty = 4, full = 0, and mutex = 1. empty counts free slots, full counts filled slots, and mutex protects insertion or removal.
The producer order is wait(empty), wait(mutex), insert, signal(mutex), signal(full). The consumer order is wait(full), wait(mutex), remove, signal(mutex), signal(empty).
The state starts at (empty, full) = (4, 0). After two productions it is (2, 2); after one consumption it is (3, 1). After each completed operation, empty + full = 4, while mutex returns to 1 outside the critical section.
Traps that change the answer
Wrong initial values. With mutex = 0, the first entrant blocks although nobody owns the section. If an empty capacity-4 buffer starts with empty = 0 and full = 4, a producer sees no free slot and a consumer may remove a nonexistent item.
Wrong operation order. In a full buffer, a producer that runs wait(mutex) before wait(empty) takes the mutex and blocks because empty = 0. A consumer can take a full permit but cannot acquire the mutex to remove an item and signal empty. Neither proceeds, so this is deadlock. Taking empty first avoids holding the mutex while waiting for capacity.
Wrong accounting or terminology. Do not increment the visible count when signal wakes a waiter directly under this convention. Do not assume a binary semaphore has ownership. Do not infer FIFO wake-up unless the question specifies a strong semaphore or a FIFO queue.
How exams test semaphore reasoning
Questions may ask you to classify a primitive, compute a final value and queue, trace shared output, detect a bad operation order, or distinguish mutex ownership from binary event signalling.
Try this before reading the answer. Assume a strong semaphore with a FIFO queue and S = 1, then run P1 wait, P2 wait, P3 wait, P1 signal, P2 signal, P3 signal. What are the visible value and queue after every call?
P1 wait takes the only permit, leaving S = 0 and queue []. P2 wait finds 0 and blocks, giving queue [P2]; P3 wait blocks too, giving [P2, P3]. P1 signal hands the permit to the queue head P2, so S stays 0 and the queue becomes [P3]. P2 signal passes it to P3, so S stays 0 and the queue empties. P3 signal finds no waiter, so S returns to 1. Practise with Process Synchronization MCQs: 12 Solved GATE Questions with Explanations, predicting both the value and queue before checking.
The short version and next step
Counting semaphore means many interchangeable permits. Binary semaphore means a 0/1 permit or event. Mutex means owner-held exclusion.
For every problem, track the initial value, each atomic wait and signal, the blocked queue, and whether a signal increments the count or hands a permit directly to a waiter. Apply that routine to a fresh semaphore trace, checking the value and queue only after predicting both.
For a complete CS foundation, continue with Zero to Hero Complete CS Course. For technical interview preparation, use CS Fundamentals for Placements by Sanchit Sir.
Keep learning
Types of Semaphores MCQs: 11 Solved Questions on P, V and Mutex
Solve 11 semaphore MCQs on counting-value arithmetic, option-order traps and a broken mutex trace. Each explanation shows the deciding equation or interleaving.
Semaphores and Process Ordering in OS: P/V Traces, Worked Examples and GATE Traps
Learn one consistent semaphore convention, then trace ordering constraints, shared-variable updates, bounded-buffer permits, rendezvous, and deadlock step by step.
Process Synchronization in Operating Systems: Semaphores, Critical Sections and Worked Examples
Build process-synchronization reasoning from a lost update to critical-section rules, semaphore operations, a capacity-3 buffer trace and common failure patterns.
Process Synchronization and Semaphores: race conditions, Peterson's solution, wait and signal
Process synchronization explained: the race condition, critical-section problem, Peterson's solution, binary and counting semaphores, and a worked trace.





