Critical Section solution for N processes with bounded waiting/* the shared data
ID: 3582706 • Letter: C
Question
Critical Section solution for N processes with bounded waiting/* the shared data structures among the participants are boolean waiting[n]; where n is the wait queue, initialized to F boolean lock; which is returned by test and set initialized to F */do {waiting [i] = true; key = true; while (waiting[i] && key) key = test_and_set(&lock;); waiting[i] = false;/* critical section */j = (i + 1) % n; while ((j! = i) && !waiting[j]) j = (j + 1) % n; if (j == i) lock = false; else waiting[j] = false;/* remainder section */} while (true); The mutex is guarded by a test-and-set which we can assume is an atomic operation at a hardware level. Notice that there is no scan on the part of the waiting process at all. Also note this is the code for an arbitrary process "I" and that all n processes are doing the same thing. Is the waiting process waiting for one condition, or one of two conditions, before entering the critical sector? What is the condition, or what are the 2 conditions? Does the process exiting the critical section reset one or two conditions in any given case? What are the conditions, which are reset, and why? Note that the process exiting the CS in this algorithm does pretty much the same thing as the exiting process in Eisenberg and McGuire. Why is this algorithm so different from Eisenberg-McGuire in terms of what the waiting process has to do before it can enter the CS? I am not interested in WHAT they do differently, but WHY.Explanation / Answer
a.
Here waiting condition waiting for two conditions before entering critical sector.
That is while(waiting[i] && key), here this loop checks that whether waiting process has any waiting queue and key >0 than, it will set lock on hardware accordingly.
b.
here in the critical section, two conditions are being reset.
(1) lock = false;
(2) waiting[j] = false;
here, if we have example of 5 processes than n=5.
so in the critical section ,
let's take i=1
j = (1+1) % 5 = 2 %5 = 2
now checking the condition while((j!=i) && !waiting[j])
j = (j+1) % n;
if(j==i) //in this j!=i
so we go to else part waiting[j] = false.
which will set waiting of process j to reset.
if it found j=i than it will set lock to reset as both the processes are same.
c.
Here the difference between Eisenberg-Mcguire algorithm and our algorithm is in Eisenberg-McGuire algorithm they are using "mod" operator for the finding the process flow whereas in our algorithm we are using "modulo" operator for finding process flow of waiting processes.
So that here in before entering the CS it has to set lock accordingly while checking the both the conditions.Also with the help of modulo operator in CS we can precisely identify the consequent processes those are within waiting queue and we can avoid dead lock scenario with it.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.