Semaphores for Ordering

So far, we have seen how semaphores can be used as locks (binary semaphores) to protect critical sections.

However, semaphores are more general than locks. Another very important use is ordering events in concurrent programs.

---

What Does “Ordering” Mean?

In concurrency, ordering means:

Ensuring that one thread performs an action only after another thread has completed some event.

This is different from mutual exclusion:

• Locks → prevent simultaneous access

• Ordering semaphores → enforce “this must happen before that”

This usage is similar in spirit to condition variables, but semaphores can do both jobs.

---

Parent–Child Example 

Consider a simple program:

• The parent thread creates a child thread

• The parent must wait until the child finishes

• Desired output order:

  parent: begin
  child
  parent: end
  

---

Code Using a Semaphore

sem_t s;

void *child(void *arg) {
    printf("child\n");
    sem_post(&s);   // signal that child is done
    return NULL;
}

int main() {
    sem_init(&s, 0, 0);  // initialize semaphore to 0
    printf("parent: begin\n");
    pthread_t c;
    pthread_create(&c, NULL, child, NULL);
    sem_wait(&s);       // wait for child
    printf("parent: end\n");
    return 0;
}

---

Key Question: Why Is the Initial Value 0?

The semaphore represents an event:

“The child has finished executing”

• Before the child finishes → event has not happened

• After the child finishes → event has happened

Thus:

• Initial value must be 0

• sem_post() signals the event

• sem_wait() waits for the event

---

Case 1: Parent Waits Before Child Runs (Figure 31.7)

Situation

• Parent creates child

• Parent reaches sem_wait() before child runs

What Happens?

Semaphore Value	Parent State	Child State	Explanation
0	Run	Ready	Semaphore initialized
0	call sem_wait()	Ready	Parent tries to wait
-1	Run → Sleep	Ready	Semaphore < 0 → parent blocks
-1	Sleep	Run	Child now runs
-1	Sleep	call sem_post()	Child signals completion
0	Sleep	Run	Semaphore incremented
0	Ready	Run	Parent is awakened
0	Run	Ready	Parent resumes
0	sem_wait() returns	Ready	Ordering achieved

Result

• Parent waits correctly

• Child prints first

• Parent resumes afterward

---

Case 2: Child Runs Before Parent Waits (Figure 31.8)

Situation

• Child runs immediately

• Parent hasn’t reached sem_wait() yet

What Happens?

Semaphore Value	Parent State	Child State	Explanation
0	Run	Ready	Semaphore initialized
0	Ready	Run	Child scheduled first
0	Ready	call sem_post()	Child signals completion
1	Ready	Run	Semaphore incremented
1	Run	Ready	Parent now runs
1	call sem_wait()	Ready	Parent waits
0	Run	Ready	No blocking; semaphore ≥ 0
0	sem_wait() returns	Ready	Parent continues

Result

• Parent does not block

• Semaphore “remembers” the signal

• Correct ordering still achieved

---

Why Semaphores Work for Ordering

Semaphores work for ordering because:

1. They remember signals

   • If sem_post() happens first, the value increases

2. They block when necessary

   • If sem_wait() happens first, the thread sleeps

3. No lost wakeups

   • Unlike naive signaling, semaphores store state

This is why semaphores are often described as:

“A counter + a queue of waiting threads”

---

Comparison: Locks vs Ordering Semaphores

Aspect	Lock	Ordering Semaphore
Purpose	Mutual exclusion	Event ordering
Initial value	1	0
Blocks when	Lock held	Event not occurred
Typical usage	Critical section	Parent–child, producer–consumer

---

 Summary

• Semaphores can be used not only as locks, but also to order events

• Initialize semaphore to 0 for ordering

• sem_wait() waits for an event

• sem_post() signals an event

• Works correctly regardless of thread scheduling order

• Figures 31.7 and 31.8 show that both execution orders are handled safely