4,515 views

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 ?$

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

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.$

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)

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.$

### 1 comment

CABCABCAB....OR ABCABCABC....
Required Sequence : BCA BCA BCA BCA …..

Then T1 and T3 should wait until T2 print B.

That means, even though Thread T1 start it’s execution prior then Thread T2, it must be blocked.

Therefore S1=1, S2=S3=0.

Option C is correct
The sequence we want is BCA in repeating manner and Thread T2 is printing “B” so, execution of threads must begin with T2 only and for that S1 = 1, S2 = 0 and S3 = 0.