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

Updated 19 Nov 20266 min read
Types of Semaphores: Binary, Counting and Mutex with Worked Examples

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 decreases S when S > 0. If S = 0, the caller blocks and joins the waiting queue.

  • signal(S) hands a permit directly to one waiting process. If nobody is waiting, it increases S.

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

0 to N

N

A pool of identical resources

No necessary owner

Binary semaphore

0 or 1

0 for an event, 1 for exclusion

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 S

Held

Queue

Check

Start

All resources free

3

0

[]

3 + 0 = 3

P1 wait

P1 gets R1

2

1

[]

2 + 1 = 3

P2 wait

P2 gets R2

1

2

[]

1 + 2 = 3

P3 wait

P3 gets R3

0

3

[]

0 + 3 = 3

P4 wait

P4 blocks

0

3

[P4]

0 + 3 = 3

P2 signal

R2 passes directly to P4

0

3

[]

0 + 3 = 3

P1 signal

R1 becomes free

1

2

[]

1 + 2 = 3

P3 signal

R3 becomes free

2

1

[]

2 + 1 = 3

P4 signal

R2 becomes free

3

0

[]

3 + 0 = 3

At P2 signal, the permit goes straight to P4, so the visible count does not briefly rise to 1. Only the holder changes.

Counting semaphore timeline preserves S plus held equals 3, including direct handoff of R2 to blocked P4.

Worked example: binary semaphore versus a lost update

Start with shared count = 41. Without exclusion, this interleaving loses one increment:

  1. P1 reads 41.

  2. P2 reads 41.

  3. Each computes 42.

  4. P1 writes 42.

  5. P2 writes 42.

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.

Two panels comparing an unprotected increment ending at 42 with a mutex-protected one ending at the correct 43.

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.