Question

Please prove the correctness of the following extended compare_and_wait program in terms of mutual exclusion, progress, and bounded waiting.

please show it in the in terms of mutual exclusion, progress, and bounded waiting.aspects thankyou

while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)

key = compare_and_swap(&lock,0,1);

waiting[i] = false;

  

// critical section

j = (i + 1) % n;

while ((j != i) && !waiting[j])

j = (j + 1) % n;

if (j == i)

lock = 0;

else

waiting[j] = false;

  // remainder section

}

Answer 1

Mutual exclusion can be provided as follows --

A global variable (lock) is declared and initialized to 0. The first process that invoke compare_and_swap() will set lock to 1, it will then enter in critical section , because the original value of lock is equal to the expected value of 0.

subsequent calls to  compare_and_swap() will not succeed , because lock now is not equals to the expected value of 0. When a process exits critical section ,it sets lock back to 0, which allow other process to enter in critical section

hence it satisfies Mutual exclusion as well as progress is also satisfied as new process is entering in critical section

Bounded waiting is also satisfied as follows :-

• when process leaves the critical section it scans the array waiting in cyclic ordering (i+1,i+2------------n-1,0,--------i-1)
• It designates the first process in this ordering and this is the entry section (waiting[j]==true) as the next one to enter the critical section .
• Any process waiting to enter its critical section will thus do so within ( n-1 ) turns.

Hence it has a finite waiting time

THANK YOU!!