Topic 5.2 · Process Synchronization & Concurrency Problems

Condition Variables & Semaphores (Binary vs. Counting)

3 min read1 question to test yourself

1Definition

A Condition Variable is a synchronization primitive that enables threads to suspend execution and yield locks until a specific application state condition becomes true. A Semaphore is an integer variable accessed exclusively through two atomic operations: wait() (or P()) and signal() (or V()). Semaphores are classified into Binary Semaphores (value 0 or 1) and Counting Semaphores (unrestricted non-negative integer domain).

2Simple Explanation

  • Condition Variables: Imagine sitting in a restaurant waiting for your food. Instead of running into the kitchen every 5 seconds to ask "Is my pizza ready?" (Busy Waiting), you take a table, go to sleep (Wait state), and let the waiter ring a bell (Signal / Notify) when the pizza is done. You wake up, grab the lock, and eat.
  • Binary Semaphore: Functions identically to a Mutex lock (value 0 or 1).
  • Counting Semaphore: Functions like a parking lot gate manager. If a parking lot has 5 open slots, the counting semaphore initialized to 5. Every arriving car calls wait(), decrementing the count (5→4→3→2→1→05\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 0). The 6th car calling wait() finds value 0 and is blocked outside. When a car leaves, it calls signal(), incrementing the count and letting the next waiting car enter.

3Real-Life Example / Analogy

  • Condition Variable: Waiting for a package delivery notification on your phone instead of standing at the front door all day.
  • Counting Semaphore: A bouncer at a nightclub licensed for 50 guests. The bouncer decrements the counter for each guest entering and increments it for each guest leaving. When count reaches 0, new guests must wait in line outside.

4Diagram / Visual Representation

Yes

No

Process calls wait(S)

Decrement S.value

Is S.value < 0?

Block process
Add to semaphore queue
Invoke scheduler

Enter critical section
Use resource

5Working / How It Works

  • Atomic Operations on Semaphore SS:
C
Code
// Atomic wait() operation (P)
void wait(Semaphore S) {
    S.value--;
    if (S.value < 0) {
        // add this process to S.queue;
        block(); // Transition to WAITING state
    }
}
// Atomic signal() operation (V)
void signal(Semaphore S) {
    S.value++;
    if (S.value <= 0) {
        // remove a process P from S.queue;
        wakeup(P); // Transition process P to READY state
    }
}

6Types / Components / Characteristics

  • Binary vs. Counting Semaphores:
    • Binary Semaphore: Integer value ranges only between 0 and 1. Used strictly for Mutual Exclusion.
    • Counting Semaphore: Integer value ranges over an unrestricted non-negative domain. Used to manage access to a finite resource pool containing NN identical resource instances.
  • Eliminating Busy Waiting: Non-busy-waiting semaphores place blocked processes into a waiting queue associated with the semaphore structure, transferring CPU control to the scheduler rather than wasting cycles spinning.

7Solved Examples / Problems

Problem: A counting semaphore SS is initialized to 8. Then 12 wait() operations and 5 signal() operations are executed in sequence on SS. What is the final value of SS? Solution:

  1. Initial Value: S=8S = 8
  2. Execute 12 wait() operations: S=8−12=−4S = 8 - 12 = -4
  3. Execute 5 signal() operations: S=−4+5=1S = -4 + 5 = \mathbf{1} (Note: A final value of +1+1 indicates 1 resource instance is currently available, and 0 processes are waiting).

8Advantages, Disadvantages & Applications

  • Semaphore Advantages: Eliminates CPU-wasting busy waiting via queue-based block() and wakeup() primitives; manages multi-instance resources cleanly.
  • Disadvantages: Misplacing a single wait() or signal() call in code causes system-wide deadlocks or race conditions.

9Important Points to Remember

  • A Binary Semaphore behaves functionally like a Mutex lock.
  • Non-busy waiting semaphores utilize internal process queues and kernel block() / wakeup() calls.

10Test Your Understanding

  1. MCQ: A counting semaphore is initialized to 5. After 7 wait() and 3 signal() operations, what is the value of the semaphore?
    • A) 2
    • B) 1
    • C) 0
    • D) -1
    Show answer
    B (Calculation: 5−7+3=15 - 7 + 3 = 1).
  2. Conceptual Question: Write the exact pseudocode definitions for non-busy-waiting wait() and signal() semaphore operations.
  3. Application Question: Explain why Condition Variables must always be paired with a Mutex lock during execution.

Finished this topic?

0 of 27 topics read in Operating Systems

Handwritten notes for the exam

Unit-wise SPPU notes and PYQs for this subject.

Helpful? Share it with your class

Free for everyone, no login needed.

Share topic