Concurrency Conditions

There are certain conditions for concurrency. Here we have listed them for you in this article.

$R(S_i) = \{ a_1, a_2, a_3,$$, a_m \}$, the read set for $S_i$, is the set of all variables whose values are referenced in statement $S_i$ during its execution.

$W(S_i) = \{b_1, b_2, b_3,$$, b_n \}$, the write set for $S_i$, is the set of all variables whose values are changed or written by the execution of statement $S_i$.

Example:

Consider the statement.

$C:= A - B$

$R(C:= A - B) = \{A, B\}$

The write set:

$W(C:= A - B) = \{C\}$

The intersection of $R(S_i)$ and $W(S_i)$ need not be null.

Example:

Consider following statement:

X:= X + 2

$R(X:= X + 2) = \{ X \}$

The write set:

$W(X:= X + 2) = \{ X \}$

Bernstein’s Conditions

The following three conditions must be satisfied for two successsive statements $S_i$ and $S_j$ to be exeuted concurrently and still produce the same results known as Bernstein’s conditions.

• $R(S_1) \cap W(S_2)$ = $\{ \}$.
• $W(S_1) \cap R(S_2)$ = $\{ \}$.
• $W(S_1) \cap W(S_2)$ = $\{ \}$.

Example:

Consider the following statements.

$S_1: a:=x-y$.
$S_2: b:=z-1$.

$R(S_1) = \{ x, y \}$.
$R(S_2) = \{ z \}$.
$W(S_1) = \{ a \}$.
$W(S_2) = \{ b \}$.

In the example above, all three conditions are satisfied. Therefore, the statement $S_1$ and $S_2$ can be executed concurrently.

We could use the precedence graph, but the precedence graph cannot be used in programming as it is a two-dimensional object. Moreover, it only shows the dependency relationship between statements.