Semaphores

Step 1: Understand the Code Behavior

The code implements a FIFO semaphore using a queue to manage waiting processes. Each process creates a private semaphore (X) when resources are unavailable (Counter == 0). Processes are added to the queue in arrival order. On FIFO_SIGNAL, the head of the queue is signaled to wake up the first waiting process. Key steps:

• FIFO_WAIT: Locks Mutex, checks Counter, enqueues private semaphore X, releases Mutex, waits on X.

• FIFO_SIGNAL: Locks Mutex, signals the head of the queue if not empty, increments Counter otherwise.

Step 2: Verifying FIFO Order

The design attempts FIFO order by:

• Adding processes to the end of the queue.

• Signaling the head of the queue on FIFO_SIGNAL.
  Apparent correctness: If the queue is properly synchronized, the first process to wait should be the first to proceed.

Identify the Potential Flaw

Critical flaw: The code releases the Mutex before waiting on X in FIFO_WAIT:

add X to the end of Q;
Signal(Mutex); // Release mutex BEFORE waiting!
Wait(X);       // Gap: Signal might arrive here.

This creates a race condition:

• A FIFO_SIGNAL can signal X before the process starts waiting on X.

• The signal is lost, causing the process to block indefinitely.

• Later processes may be signaled first, violating FIFO.

Why this breaks FIFO:

• The earliest process (e.g., P1) might miss its signal, allowing later processes (e.g., P2/P3) to proceed first.

Step 4: Example Execution Sequence

1. Processes P1, P2, P3 call FIFO_WAIT when Counter = 0:

   • Each creates X1, X2, X3 and adds them to the queue: [X1, X2, X3].

   • All release Mutex and prepare to wait on their X.

2. FIFO_SIGNAL sequence:

   • First signal: Signals X1 (head of queue).

     • If P1 hasn’t started Wait(X1) yet (paused by the OS), the signal is lost.

   • Second signal: Signals X2 (new head).

     • P2 proceeds.

   • Third signal: Signals X3.

     • P3 proceeds.

3. Result:

   • P1 remains blocked forever, despite being first in the queue.

   • FIFO violation: P2 and P3 acquire resources out of order.

Conclusion

The implementation is incorrect due to the race condition between releasing Mutex and waiting on X. To fix it, use atomic "unlock + wait" operations (e.g., condition variables) to eliminate the gap. Without this, FIFO fairness cannot be guaranteed.