Official PYQ · 2010Q23Concurrency and SynchronizationMCQ1 mark

GATE CS 2010 Q23 — Concurrency and Synchronization

Consider the methods used by processes $P1$ and $P2$ for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables $S1$ and $S2$ are randomly assigned.
$\begin{array}{|l|l|}\hline \textbf{Method used by P1} & \textbf{Method used by P2} \\ \hline \text{while (S1 == S2);} & \text{while (S1 != S2);} \\ \text{Critical Section} & \text{Critical Section} \\ \text{S1 = S2;} & \text{S2 = not(S1);} \\ \hline \end{array}$
Which one of the following statements describes the properties achieved?

View worked solution

Answer: A

To determine which properties are satisfied, let us analyze Mutual Exclusion and Progress individually.

1. Mutual Exclusion

For a process to enter its Critical Section (CS), it must bypass its respective while loop condition:

For $P1$ to enter CS, the condition S1 == S2 must be false, which means $S1 \neq S2$ .
For $P2$ to enter CS, the condition S1 != S2 must be false, which means $S1 == S2$ .

Since $S1 \neq S2$ and $S1 == S2$ cannot be true simultaneously, both processes can never be in their critical sections at the same time. Thus, Mutual Exclusion is satisfied.

2. Progress

The progress requirement states that if no process is in its critical section and some processes want to enter, then only those processes not in their remainder section can participate in deciding which process enters next, and this decision cannot be postponed indefinitely.

Let us test this with an scenario:

Suppose the initial values are $S1 = \text{true}$ and $S2 = \text{true}$ .
Process $P1$ wants to enter its critical section. It tests the condition S1 == S2, which evaluates to true == true (true). Thus, $P1$ gets blocked in the while loop.
If process $P2$ is currently in its remainder section and has no interest in entering its critical section, it will not execute its code.
Since $P2$ is inactive, the values of $S1$ and $S2$ remain unchanged. Consequently, $P1$ is blocked indefinitely by a process ( $P2$ ) that is not even competing for the critical section.