Question $1$: Mutual Exclusion $[20$ marks$]$

Consider the following program intended to solve the mutual exclusion problem for the case of two processes.

$\backslash [$

$\backslash$begin$\{$array$\}\{$l$\}$

$\backslash$text $\{$ int $\}\backslash$mathrm$\{$cp$\}=0\backslash \backslash$

$\backslash$text $\{$ int $\}\backslash$mathrm$\{$cq$\}=0$

$\backslash$end$\{$array$\}$

$\backslash ]$

$```$

Process P

while$($ true $)\{$

P$1$: non$-$critical$-$section;

P$2$a: if$($ cq $==-1)\{$

P$2$b: $\}\backslash$quadcp$=-1\backslash$mathrm$\{$ ;

P$2$c: $\}$ else $\{$ cp $=1$; $\}$

P$3$: while$($cp $==$ cq$)\{\}$

P$4$: critical$-$section;

P$5$: cp $=0$;

$\}$

end P;

$```$

$```$

Process Q

while$($ true $)\{$

Q$1$: non$-$critical$-$section;

Q$2$a: if$($ cp $==-1)\{$

Q$2$b: $\backslash$q $=1$;

Q$2$c: $\}$ else $\{$ cq $=-1$; $\}$

Q$3$: while$($cq $==-$cp$)\{\}$

Q$4$: critical$-$section;

Q$5$: $\backslash$q $=0$;

$\}$

end Q;

$```$

Assuming that each line is atomic, answer the following questions $($and pay careful attention to the signs of quantities$)$:

$($i$)$ Find an execution of this algorithm that demonstrates that mutual exclusion is not upheld.

$($ii$)$ Now assume that the statements $($P$2$a$,$P$2$b$,$P$2$c$)$ are executed as a single atomic instruction and the same for $($Q$2$a$,$Q$2$b$,$Q$2$c$)($see next page$).$ Does the program now uphold mutual exclusion? Provide a proof. $```$

Process P

while$($ true $)\{$

P$1$: non$-$critical$-$section;

P$2$: if$($ cq $==-1)\{$cp $=-1$;$\}$ else $\{$cp $=1$; $\}$

P$3$: while$($cp $==$ cq$)\{\}$

P$4$: critical$-$section;

P$5$: cp $=0$;

$\}$

end P;

$```$

$```$

Process Q

while$($ true $)\{$

non$-$critical$-$section;

if$($ cp $==-1)\{$cq $=1$;$\}$ else $\{$ cq $=-1$; $\}$

while$($cq $==-$cp$)\{\}$

critical$-$section;

cq $=0$;

$\}$

end Q;

$```$