COMP[39]161 Concepts of Programming Languages
Semester 2, 2018

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

2018-11-16 Fri 19:37

Announcements RSS