# Tute (Week 12)

## Table of Contents

## 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\]