Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.
Show Hint
In synchronization problems involving semaphores, the key is to initialize the semaphores in such a way that allows the threads to execute in the correct order while preventing race conditions. Here, the semaphores control which thread runs next by using wait and signal operations.
The given program consists of three threads \(T_1\), \(T_2\), and \(T_3\), synchronized using three binary semaphores \(S_1\), \(S_2\), and \(S_3\). Each thread waits on one semaphore, prints a character, and then signals another semaphore. The objective is to repeatedly generate the output sequence:
\[
BCABCABC\ldots
\]
Thread behavior:
- \(T_1:\) waits on \(S_3\), prints C, then signals \(S_2\).
- \(T_2:\) waits on \(S_1\), prints B, then signals \(S_3\).
- \(T_3:\) waits on \(S_2\), prints A, then signals \(S_1\).
These semaphore operations form a circular dependency:
\[
T_2 \rightarrow T_1 \rightarrow T_3 \rightarrow T_2
\]
which must be initialized correctly to start the cycle in the desired order.
Correct semaphore initialization:
To begin the sequence with the correct execution order, only the thread that should run first must be unblocked initially.
Setting:
\[
S_1 = 1,\quad S_2 = 0,\quad S_3 = 0
\]
ensures the following:
- Since \(S_1 = 1\), thread \(T_2\) executes first and prints B, then signals \(S_3\).
- With \(S_3\) signaled, thread \(T_1\) executes next and prints C, then signals \(S_2\).
- With \(S_2\) signaled, thread \(T_3\) executes next and prints A, then signals \(S_1\).
- The cycle repeats in the same order, producing:
\[
BCABCABC\ldots
\]
Thus, the semaphore initialization that guarantees the required printing order is:
\[
S_1 = 1,\ S_2 = 0,\ S_3 = 0
\]
