Semester 2, 2018

# Tute (Week 12)

## 1 LCR Conditions

Consider the following two processes, each manipulating a shared variable $$x$$, which starts out at $$0$$.

Thread 1: $$x := x + 1; x:= x - 1;$$

Thread 2: $$x := x \times 2$$

a) What are the possible final values of $$x$$ assuming each statement is executed atomically?

$$x$$ is either zero or one.

b) Rewrite the above program into one where each statement obeys the limited critical reference restriction. What are the possible final values now?

Thread 1: $$\textbf{var}\ t; t := x; x := t + 1; t := x; x := t - 1;$$

Thread 2: $$\textbf{var}\ u; u := x; x := u \times 2$$

This allows the final write of thread 2 to happen well after the read of thread 2. Thus, a final result of $$x = 2$$ or $$x = -1$$ is now also possible.

c) How could locks be used in your answer to (b) to ensure that only the final results from part (a) are possible?

Each formerly-atomic statement must now be protected by a shared lock $$\ell$$:

Thread 1: $$\begin{array}{l}\textbf{var}\ t; \mathbf{take}(\ell); t := x; x := t + 1; \mathbf{release}(\ell);\\ \mathbf{take}(\ell); t := x; x := t - 1; \mathbf{release}(\ell);\end{array}$$

Thread 2: $$\textbf{var}\ u; \mathbf{take}(\ell); u := x; x := u \times 2; \mathbf{release}(\ell);$$

## 2 Critical Section Solutions

This is the Manna-Pnueli algorithm for critical sections:

$\begin{array}{| c |} \hline \textbf{var}\ \mathit{wantp, wantq} := 0, 0\\ \begin{array}{l | l}\hline \mathbf{while}\ \mathit{True}\ \mathbf{do} & \mathbf{while}\ \mathit{True}\ \mathbf{do} \\ p_1: \quad \textit{non-critical section} & q_1: \quad \textit{non-critical section}\\ p_2: \quad \textbf{if}\ \mathit{wantq} = -1 & q_2: \quad \textbf{if}\ \mathit{wantp} = -1 \\ \quad\qquad\mathbf{then}\ \mathit{wantp} := -1 & \quad\qquad\mathbf{then}\ \mathit{wantq} := 1\\ \quad\qquad\mathbf{else}\ \mathit{wantp} := 1 & \quad\qquad\mathbf{else}\ \mathit{wantq} := -1\\ p_3: \quad \textbf{await}\ \mathit{wantp} \neq \mathit{wantq} & q_3: \quad \textbf{await}\ \mathit{wantp} \neq -\mathit{wantq} \\ p_4: \quad \textit{critical section} & q_4: \quad \textit{critical section}\\ p_5: \quad \mathit{wantp} := 0 & q_5: \quad \mathit{wantq} := 0\\ \textbf{od}&\textbf{od}\\\end{array}\\\hline \end{array}$

a) Explain how this algorithm meets the mutual exclusion property for critical section solutions. Note that the $$\textbf{if}$$ statement is atomic - executed in one step.

At statement $$p_3$$, observe that we know already that $$|\mathit{wantp}| = 1$$ from the previous if statement. Similarly at statement $$q_3$$ we also know that $$|\mathit{wantq}| = 1$$.

For $$p$$ to enter its critical section, it must pass the $$\textbf{await}$$ guard, thus for $$p$$ to be in it's critical section it must be the case that $$\mathit{wantp} \neq \mathit{wantq}$$. Similarly, for $$q$$ to be in it's critical section it must be the case that $$\mathit{wantp} \neq -\mathit{wantq}$$.

If both processes were in their critical section at the same time, that would mean that $$\mathit{wantp} \neq -\mathit{wantq}$$ and $$\mathit{wantp} \neq \mathit{wantq}$$, but also that $$|\mathit{wantp}| = 1 = |\mathit{wantq}|$$. This is a contradiction. Therefore, these two processes cannot be in their critical section at the same time and mutual exclusion is satisfied.

b) Now assume that the $$\textbf{if}$$ statement is split into two steps, one that checks the condition, and one that runs the $$\textbf{then}$$ or $$\textbf{else}$$ branch. Show that mutual exclusion is violated if that is the case.

Let the statement $$p_2$$ be split into $$p_C$$ before the condition is checked, and $$p_T$$ and $$p_E$$ before the then and else branches respectively. Similarly for the statement $$q_2$$.

Then the following interleaving violates mutual exclusion.

$p_1q_1p_Cq_Cp_Eq_Eq_3q_4p_3p_4$

2018-11-16 Fri 19:37