Explain whether the above solution satisfy the necessary conditions (mutual excl

Question

Explain whether the above solution satisfy the necessary conditions (mutual exclusion, progress & bounded waiting) of critical region problem.

A solution to critical region problem for n processes is suggested as follows Shared data among the processes enum pstate fidle, want in, in cS; state flag[n]; int turn All elements of flag are initially idle. The initial value of turn is something between 0 and n -1 (it is immaterial). The general structure of process Pi is do f = true; while (flag[j]) f if (turn-j) f flag [i] false; while (turn j); /* do nothing */ flag[1] -true ; ] true; /* critical section*/ turn = j; flag [i] = false; /* remainder section */ while (true);

Explanation / Answer

Mutual exclusion is not violated. Consider the case where one thread enters the critical section before the other. This thread sets its flag to true. The other thread will loop in the while loop until the other thread sets its own flag in its exit section. So the second thread can't enter until the first exits.

In the event of tie, turn will be set so that only one of them can enter. The other thread will get caught in the innermost while loop. We don't know which thread will get turn, but it can't be both. In the exit section, turn will be set to allow the other one to exit. Again, one thread can't enter until the other exits. Mutual exclusion is satisfied. Progress isn't violated, because the resource is never available, but guarded. If there is only one thread that wants the thread, the flag variable is a non-factor and the wanting thread can enter. In the other case, the turn variable and the inner while loop wille sure that one of the two thread gets into the critical section. The progress condition is satisfied. Bounded wait isn't violated. Assuming there is no competition for the resource, this case is trivial. The thread can immediately enter (see discussion in progress). The other case of interest is ensuring that the wait is bounded if both processes want the critical section. In this case we need to ensure that one process can't keep winning forever. This is satisfied, because as a thread exits, it gives the other process the turn. The other process can immediately enter. And and since the other process's flag is set, the first process can't re-enter first.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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