C1. Prove that the conditions of the Critical Section problem are satisfied in B

Question

C1. Prove that the conditions of the Critical Section problem are satisfied in Bakery's Algorithm. . Mutual Exclusion (you can use the 2 given assertions) . No Starvation . Progress Condition (no delay and no deadlock) C2. What will be the outcome of eliminating the choosingll array from the Bakery's Algorithm code? Explain. What condition is violated? Give the sequence that violates the condition. D. Implement Mutual Exclusion for n processes using hardware support, and the following atomic instruction: CSW(a,b,c) t if(a== b) { b = c; Sign 1;) else (a = b; Sign = 0;} return sigr

Explanation / Answer

C1.

Firstly the process sets its “choosing” variable to be TRUE indicating its intent to enter critical section. Then it gets assigned the highest ticket number corresponding to other processes. Then the “choosing” variable is set to FALSE indicating that it now has a new ticket number. This is in-fact the most important part of the algorithm.

It is actually a small critical section in itself ! The very purpose of the first three lines is that if a process is modifying its TICKET value then at that time some other process should not be allowed to check its old ticket value which is now obsolete. This is why inside the for loop before checking ticket value we first make sure that all other processes have the “choosing” variable as FALSE.

After that we proceed to check the ticket values of processes where process with least ticket number/process id gets inside the critical section. The exit section just resets the ticket value to zero

C2. If we remove choosing array [] then mutual exclusion is violated.

Suppose we have two processes just beginning; call them p0 and p1. Both reach line 5 at the same time. Now, we'll assume both read number[0] and number[1] before either addition takes place. Let p1complete the line, assigning 1 to number[1], but p0 block before the assignment. Then p1 gets through the while loop at lines 9-11 and enters the critical section. While in the critical section, it blocks; p0unblocks, and assigns 1 to number[0] at line 5. It proceeds to the while loop at lines 9-11. When it goes through that loop for j = 1, the condition on line 9 is true. Further, the condition on line 10 is false, so p0 enters the critical section. Now p0 and p1 are both in the critical section, violating mutual exclusion.

The reason for choosing is to prevent the while loop in lines 9-11 from being entered when process j is setting its number[j]. Note that if the loop is entered and then process j reaches line 5, one of two situations arises. Either number[j] has the value 0 when the first test is executed, in which case process i moves on to the next process, or number[j] has a non-zero value, in which case at some point number[j] will be greater than number[i] (since process i finished executing statement 5 before process j began). Either way, process i will enter the critical section before process j, and when process jreaches the while loop, it will loop at least until process i leaves the critical section.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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