Given the 2 assertions, prove the mutual exclusion is satisfied in Bakery Algori

ID: 3734530 • Letter: G

Question

Given the 2 assertions, prove the mutual exclusion is satisfied in Bakery Algorithm

Assertion A: if processes i and k are in the bakery, and i entered the bakery before k entered the doorway, then number[i] < number[k]

Assertion B: if process i executes its Critical Section, and process k is in the bakery (k !=i) then ( number[i], i ) < (number[k], k )

_________________________________________________________________________________________________________

while(true) {

choosing[i] = 1;

number[i] = 1 + max(number[1], …, number[n]);

number[n]);

choosing[i] = 0;

for (int j = 1; j <= n; j++) {

while (choosing[j] = 1) {}

while(number[j] != 0 and (number[j],j) < (number[i], i)) {}

}

critical section

number[i] = 0;

Lets consider process i and j (where i and j are not equal ) are in the critical section at the same time.

We have,

Since both the proxcess i and j are in critical section, both have to choose a non zero number before entering critical section

=> number[i] ! = 0

number[j] ! =0

As process i is in critical section and j inside bakery

=> ( number[i], i) < ( number[j], j)

As process j is in critical section and i inside bakery

=> ( number[j], j) < ( number[i], i)

This means ( number[i], i) = ( number[j], j )

This is a contradiction because i and j are two different process with different IDs

=> Satisfies mutual exclusion

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.