Binary Semaphores

 

Binary Semaphores (Using Semaphores as Locks)

1. What Is a Binary Semaphore?

A binary semaphore is a semaphore whose value is restricted to two logical states:

• 1 → resource available

• 0 → resource unavailable (lock held)

Because it behaves exactly like a mutex lock, a binary semaphore is often used to protect a critical section and enforce mutual exclusion.

---

2. Why Use a Semaphore as a Lock?

Earlier, we used:

• Mutex locks for mutual exclusion

Now we ask:

Can a semaphore be used to do the same job?

✅ Yes.
By initializing a semaphore to the correct value and surrounding the critical section with sem_wait() and sem_post(), we can build a lock.

---

3. Code Structure of a Binary Semaphore

sem_t m;
sem_init(&m, 0, X);   // what should X be?

sem_wait(&m);
// critical section
sem_post(&m);

The key question is:

❓ What should X be?

---

4. Choosing the Correct Initial Value

To behave like a lock, the semaphore must allow only one thread to enter the critical section at a time.

👉 Therefore, the initial value must be:

X = 1

Why?

• A value of 1 means the resource is initially available

• The first thread can acquire it immediately

• Any additional thread must wait

---

5. How Binary Semaphores Work (Single Thread Case)

Initial value:

m = 1

Execution Trace:

1. Thread calls sem_wait(&m)

   • Value goes from 1 → 0

   • Thread enters the critical section

2. Thread calls sem_post(&m)

   • Value goes from 0 → 1

   • Lock is released

✔ No blocking occurs
✔ Semaphore behaves like an uncontended lock

---

6. Binary Semaphore with Two Threads (Key Scenario)

Now consider two threads, T0 and T1.

Step-by-Step Behavior

Thread T0:

1. Calls sem_wait()

   • Semaphore: 1 → 0

   • Enters critical section

Thread T1 (while T0 holds the lock):

2. Calls sem_wait()

   • Semaphore: 0 → −1

   • Value is negative → T1 is blocked

   • T1 goes to sleep

Thread T0:

3. Calls sem_post()

   • Semaphore: −1 → 0

   • One waiting thread (T1) is woken up

Thread T1:

4. Resumes execution

   • sem_wait() returns

   • T1 enters the critical section

Thread T1 finishes:

5. Calls sem_post()

• Semaphore: 0 → 1

• Lock becomes free again

---

7. Meaning of Semaphore Values in Binary Semaphores

Semaphore Value	Meaning
1	Lock is free
0	Lock is held, no waiting threads
−1	Lock held, 1 thread waiting
−2	Lock held, 2 threads waiting

👉 Negative values indicate the number of blocked threads

---

8. Why It Is Called a “Binary” Semaphore

Even though the internal value may temporarily become negative:

• The logical behavior has only two states:

  • Locked

  • Unlocked

Hence the name binary semaphore.

---

9. Binary Semaphore vs Mutex Lock

Feature	Binary Semaphore	Mutex Lock
Mutual exclusion	✔	✔
Blocking	✔	✔
Ownership enforced	✘	✔
Can signal from other threads	✔	✘

⚠️ Important distinction:

• A mutex must be unlocked by the thread that locked it

• A semaphore does not enforce ownership

---

10. Key Observations for Students

• Binary semaphores are conceptually simple

• They enforce mutual exclusion

• They block instead of spinning (efficient)

• Incorrect use can still cause:

  • Deadlock

  • Missed signals

  • Logical errors

---

11. Summary 

• A binary semaphore is a semaphore initialized to 1

• It can be used to implement a lock

• sem_wait() acquires the lock

• sem_post() releases the lock

• Negative semaphore values represent waiting threads

• Binary semaphores provide mutual exclusion