The following reader$-$writer algorithm works for multiple readers and a

single writer. It allows reading of the shared variables x$1$ and x$2$ into local

variables d$1$ and d$2$ without locking, thus not blocking the writer.

Before writing to the shared variables x$1$ and x$2,$ the writer increments a

counter c$.$ It then proceeds to write to the variables, and finally increments

c again. The two increments of c ensure that it is odd when the process

is writing to the variables, and even otherwise. Hence, when a reader

wishes to read the shared variables, it waits in a loop until c is even before

reading them. Also, before returning it checks that the value of c has not

changed $($i$.$e$.,$ another write has not begun$).$ If it has changed, the process

starts over. This ensures the pair of values read corresponds to a single

occurrence of a write.

Non$-$blocking reader$-$writer

integer c$,$ x$1,$ x$20$

reader

writer

integer c$0,$ d$1,$ d$2$

integer d$1,$ d$2$

loop forever

loop forever

p$1$: repeat

q$1$: d$1$ get$()$

p$2$: repeat

q$2$: d$2$ get$()$

p$3$: c$0$ c

q$3$: c $$ c$+1$

p$4$: until $($c$0$ mod $2=0)$

q$4$: x$1$ d$1$

p$5$: d$1$ x$1$

q$5$: x$2$ d$2$

p$6$: d$2$ x$2$

q$6$: c $$ c$+1$

p$7$: until $($c$0=$ c$)$

q$7$:

p$8$: use$($d$1,$d$2)$

q$8$:

$($a$)$ Describe a scenario showing that the algorithm is not correct when

there is more than one writer. Explain how you could modify the

algorithm to allow multiple writers by placing standard, i$.$e$.,$ non

language specific, synchronisation mechanisms in the code. Justify

that your modification ensures that no writer process is ever

blocked unnecessarily.

$($b$)$ Extend the algorithm with a third type of process called an incre

menter. An incrementer increments the values of x$1$ and x$2,$ i$.$e$.,$ adds

$11$ to them. It is a low priority process and so should not block writers

while reading x$1$ and x$2,$ and synchronisation mechanisms should give

preference to writers over incrementers.

include $3$ parts:

$$ Counter$-$example for original algorithm

$$ Justification of synchronisation constructs

$$ Modification of algorithm