Introduction to Semaphores

1. Why Do We Need Semaphores?

In concurrent systems, multiple threads or processes often share data and resources. To ensure correctness, we must control how and when threads access these shared resources.

Earlier, we learned two fundamental synchronization tools:

• Locks (mutexes) → enforce mutual exclusion

• Condition variables → allow threads to wait for conditions

However, managing both together can be complex.

👉 Semaphores were introduced as a single, unified synchronization primitive capable of expressing both mutual exclusion and thread coordination.

---

2. Historical Background

The semaphore was introduced by Edsger W. Dijkstra in the late 1960s.

Dijkstra is well known for:

• Dijkstra’s shortest path algorithm

• “Goto Statements Considered Harmful”

• Foundational work in concurrency and synchronization

His key insight was that a single integer-based primitive, combined with two atomic operations, could solve a wide range of synchronization problems.

---

3. What Is a Semaphore?

A semaphore is a synchronization object that consists of:

• An integer value

• Two atomic operations:

  • wait() (also called P, down)

  • post() (also called V, up)

In POSIX systems, these operations are:

• sem_wait()

• sem_post()

Note: They stem from Dutch words Prolaag(P)  and Verhoog (V).

• V stands for 'Verhoog', which can be translated as "increment".

• P stands for 'Prolaag', a madeup Dutch word of 'probeer verlaag', which can be translated as "try to decrease".

---

4. Semaphore Initialization

Before using a semaphore, it must be initialized.

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);

Meaning of Parameters:

• &s → semaphore variable

• 0 → semaphore shared among threads in the same process

• 1 → initial value of the semaphore

👉 The initial value determines the behavior of the semaphore

---

5. Semaphore Operations

sem_wait(s)

Conceptually:

- Decrement the semaphore value
- If the value becomes negative:
    → block the calling thread

sem_post(s)

Conceptually:

- Increment the semaphore value
- If threads are waiting:
    → wake one waiting thread

These operations are atomic, meaning they execute without interruption.

---

6. Key Properties of Semaphores

1. Blocking Behavior

• sem_wait() may block if the resource is unavailable

• sem_post() never blocks

---

2. Queueing of Threads

• Multiple threads can wait on a semaphore

• Waiting threads are queued by the operating system

---

3. Negative Values Have Meaning

If the semaphore value becomes negative, then:

The absolute value equals the number of waiting threads

This is an important invariant:

• Value = 0 → resource unavailable, no waiters

• Value = −3 → three threads are blocked

---

7. Binary vs Counting Semaphores

Binary Semaphore

• Initial value: 0 or 1

• Behaves like a mutex lock

• Used for mutual exclusion

Example:

sem_init(&s, 0, 1);

---

Counting Semaphore

• Initial value: N > 1

• Represents N identical resources

• Allows up to N threads to access the resource simultaneously

Example:

sem_init(&s, 0, N);

---

8. Semaphores vs Locks and Condition Variables

Feature	Locks	Condition Variables	Semaphores
Mutual exclusion	✔	✘	✔
Waiting & signaling	✘	✔	✔
Single primitive	✘	✘	✔
Can replace others	✘	✘	✔

👉 Semaphores can be used to implement both locks and condition variables

---

9. Why Semaphores Are Powerful (and Dangerous)

Advantages

• Very expressive

• Can solve complex synchronization problems

• Widely supported (POSIX, UNIX, Linux)

Challenges

• Incorrect use can lead to:

  • Deadlock

  • Starvation

  • Hard-to-debug errors

👉 This is why modern code often prefers mutex + condition variables, even though semaphores are more general.

---

10. Summary 

• Semaphores were introduced by Dijkstra as a universal synchronization tool

• A semaphore is an integer with wait and post operations

• The initial value defines its behavior

• Semaphores can act as:

  • Locks (binary semaphores)

  • Resource counters (counting semaphores)

  • Condition synchronization tools

• They form the foundation of many modern synchronization mechanisms