CABCABCAB....OR ABCABCABC....

Dark Mode

5,017 views

10 votes

Consider the following threads, $\text{T}_{1}, \text{T}_{2},$ and $\text{T}_{3}$ executing on a single processor, synchronized using three binary semaphore variables, $\text{S}_{1}, \text{S}_{2},$ and $\text{S}_{3},$ operated upon using standard $\textsf{wait}()$ and $\textsf{signal}().$ The threads can be context switched in any order and at any time.

$$\begin{array}{|c|c|c|} \hline \text{T}_{1} & \text{T}_{2} & \text{T}_{3} \\\hline \text{while(true)} \{ & \text{while(true)} \{& \text{while(true)} \{ \\ \text{wait(S}_{3}); & \text{wait(S}_{1}); & \text{wait(S}_{2}); \\ \text{print(“C”)}; & \text{print(“B”)}; & \text{print(“A”)}; \\ \text{signal(S}_{2}); \} & \text{signal(S}_{3}); \} & \text{signal(S}_{1}); \} \\\hline \end{array}$$

Which initialization of the semaphores would print the sequence $\text{BCABCABCA} \dots ?$

- $\text{S}_{1} = 1; \text{S}_{2} = 1; \text{S}_{3} = 1$
- $\text{S}_{1} = 1; \text{S}_{2} = 1; \text{S}_{3} = 0$
- $\text{S}_{1} = 1; \text{S}_{2} = 0; \text{S}_{3} = 0$
- $\text{S}_{1} = 0; \text{S}_{2} = 1; \text{S}_{3} = 1$

13 votes

Best answer

Thread $T_2$ prints $B.$ Thread $T_1$ prints $C.$ Thread $T_3$ prints $A.$

These three threads are executing on a single processor. We want these threads to be synchronized in such a way that we get the sequence $BCA \,\, BCA \,\, BCA \dots$ printed.

The threads can be context switched in any order and at any time. But in **whichever order** they run, pre-empt, run again; the sequence that should be printed is $BCA \,\, BCA \,\, BCA \dots$

Hence, **Logically,** we want the threads to execute in the following order : $T_2,T_1, T_3, \,\,\,\,\, T_2,T_1, T_3, \,\,\,\,\, T_2,T_1, T_3$

First $T_2$ should be able to print. Hence, binary semaphore $S_1 $ must be $1$ initially.

Clearly, first $T_1$ Or $T_3$ should not be able to print, So, $S_3 =0, S_2 =0$ initially.

Also, with $S_1 = 1,S_3 =0, S_2 =0$ initially, we can verify that the sequence $BCA \,\, BCA \,\, BCA \dots$ is printed, as following :

$T_2$ prints $B$, then wakes up $T_1.$

$T_1$ prints $C$, then wakes up $T_3.$

$T_3$ prints $A$, then wakes up $T_2.$

Same scenario repeats continuously.

$\color{red}{\text{Complete Analysis : }}$

**Question 1 :**

If we have the following initialization of the semaphores : $S_1 = 1,S_3 =1, S_2 =1;$ then what are the sequences possible ?

**Question 2 :**

If we have the following initialization of the semaphores : $S_1 = 1,S_3 =0, S_2 =1;$ then what are the sequences possible ?

**Question 3 :**

If we have the following initialization of the semaphores : $S_1 = 0,S_3 =1, S_2 =1;$ then what are the sequences possible ?

To answer these questions, **NOTE that**, for the given threads, **whatever initialization** we take, the sequence that will be printed, definitely must have the following three properties :

Between any two $B’s,$ there must be an $A.$ (Because only $T_3$ can wake $T_2.$)

Between any two $A’s,$ there must be a $C.$ (Because only $T_1$ can wake $T_3.$)

Between any two $C’s,$ there must be a $B.$ (Because only $T_2$ can wake $T_1.$)

Let’s call these three properties as $P.$

**Answer 1: **

If $S_1 = 1,S_3 =1, S_2 =1$ initially, then **any sequence, **that satisfies the above three properties, is possible. For example, the following sequences are possible :

$BCA \,\, BCA \,\, BCA \dots ;$ $ABC \,\, ABC \,\, ABC \dots ;$ $BA \,\, BCA \,\, BCA \dots ;$ $AC \,\, ABC \,\, ABC \dots ;$

Basically, once you know the first three letters that are printed, you can write remaining sequence using the above three properties.(NOTE that first three letters also must satisfy the above three properties)

**Answer 2 :**

If $S_1 = 1,S_3 =0, S_2 =1$ initially, then the following sequences are possible :

$ABC \,\,\,ABC\,\,\, ABC \dots ,OR$ If sequence starts with $B$ then the sequence must satisfy the properties of $P.$

Similarly, Question 3 can be answered. Comment your answer for question 3 below.