$2.[30$ points$]$ Synchronization

$1)(15$ points$)$ Suppose that there are n processes wanting to execute a critical section. We would like to impose a strict ordering execution of the processes as P$1,$ P$2,...$ Pn$,$ P$1,$ p$2....$ Please sketch the code with the use of binary semaphores to enforce the ordering. $($Hint: the simple solution is that you need n binary semaphores with proper initialization$)$

Process P$1$:

while $($TRUE$)\{$

BLANK$1$;

Critical Section

BLANK$2$;

$\}$ Process P$2$:

while $($TRUE$)\{$

BLANK$3$;

Critical Section

BLANK$4$;

$\}$ Process Pi:

while $($TRUE$)\{$

BLANK$5$;

Critical Section

BLANK$6$;

$\}$ Process Pn:

while $($TRUE$)\{$

BLANK$7$;

Critical Section

BLANK$8$;

$\}$

$1)(15$ points$)$ In the following code, three processes synchronize with three semaphores L$,$ M$,$ R to produce output.

$/*$ Initialize the three binary semaphores $*/$

semaphore L $=1$;

semaphore M $=0$;

semaphore R $=0$;

$/*$ random$()$ function return a random float value that is greater than $0$ and less than $1$ with equal probability $*/$

$/*$ Process $1*/$

while $($true$)\{$

wait$($L$)$;

printf$($A$)$;

signal$($R$)$;

$\}$

$/*$ Process $2*/$

while $($true$)\{$

wait$($R$)$;

printf$($B$)$;

x $=$ random$()$;

if $($x $<mtext></mtext><mn>0</mn><mn>.</mn><mn>5</mn><mi>)</mi>$

signal$($L$)$;

else

signal$($M$)$;

$\}$

$/*$ Process $3*/$

while $($true$)\{$

wait$($M$)$;

printf$($C$)$;

printf$($D$)$;

x $=$ random$()$;

if $($x $<mtext></mtext><mn>0</mn><mn>.</mn><mn>4</mn><mi>)</mi>$

signal$($L$)$;

else if $($x $<mtext></mtext><mn>0</mn><mn>.</mn><mn>8</mn><mi>)</mi>$

signal$($R$)$;

$\}$

Please answer the following questions.

A$)(2$ points$)$ What is the minimum length $($minimum number of characters$)$ of output?

B$)(3$ points$)$ Is ABABCDBACD a possible output sequence when this set of processes runs? If it is possible, please calculate the probability, if not, explain why.

C$)(3$ points$)$ Is ABCDABABCD a possible output sequence when this set of processes runs? If it is possible, please calculate the probability, if not, explain why.

D$)(3$ points$)$ What is the probability that exactly two $$C$$s are printed on the screen?

E$)(4$ points$)$ What is the probability that exactly two $$B$$s are printed on the screen?