edited by
47,120 views
112 votes
112 votes

Consider the following proposed solution for the critical section problem. There are $n$ processes : $P_0....P_{n-1}$. In the code, function $\text{pmax}$ returns an integer not smaller than any of its arguments .For all $i,t[i]$ is initialized to zero.

Code for $P_i$;

do {
    c[i]=1; t[i]= pmax (t[0],....,t[n-1])+1; c[i]=0;
    for every j != i in {0,....,n-1} {
        while (c[j]); 
        while (t[j] != 0 && t[j] <=t[i]);
    }
    Critical Section;
    t[i]=0;
    
    Remainder Section;
    
}  while (true);

Which of the following is TRUE about the above solution?

  1. At most one process can be in the critical section at any time
  2. The bounded wait condition is satisfied
  3. The progress condition is satisfied
  4. It cannot cause a deadlock
edited by

7 Answers

Best answer
91 votes
91 votes

Answer is (A).
 

 while (t[j] != 0 && t[j] <=t[i]);

This ensures that when a process $i$ reaches Critical Section, all processes $j$ which started before it must have its $t[j] = 0$. This means no two process can be in critical section at same time as one of them must be started earlier.

returns an integer not smaller


is the issue here for deadlock. This means two processes can have same $t$ value and hence

while (t[j] != 0 && t[j] <=t[i]);

can go to infinite wait. ($t[j] == t[i]$). Starvation is also possible as there is nothing to ensure that a request is granted in a timed manner. But bounded waiting (as defined in Galvin) is guaranteed here as when a process $i$ starts and gets $t[i]$ value, no new process can enter critical section before $i$ (as their $t$ value will be higher) and this ensures that access to critical section is granted only to a finite number of processes (those which started before) before eventually process $i$ gets access.

But in some places bounded waiting is defined as finite waiting (see one here from CMU) and since deadlock is possible here, bounded waiting is not guaranteed as per that definition.

edited by
55 votes
55 votes

Given question is a wrongly modified version of actual bakery algorithm, used for N-process critical section problem.

Bakery algorithm code goes as follows : (as in William stalling book page 209, 7th edition)

Entering[i] = true;
Number[i] = 1 + max(Number[1], ..., Number[NUM_THREADS]);
Entering[i] = false;

for (integer j = 1; j <= NUM_THREADS; j++) {
    // Wait until thread j receives its number:
    while (Entering[j]) { 
      /* nothing */ 
    }

    // Wait until all threads with smaller numbers or with the same
    // number, but with higher priority, finish their work:
    while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { 
      /* nothing */ 
    }
}

    <Critical Section>

    Number[i] = 0;
    /*remainder section */

code explanation:

The important point here is that due to lack of atomicity of max function multiple processes may calculate the same Number.

In that situation to choose between two processes, we prioritize the lower process_id.

(Number[j], j) < (Number[i], i)) this is a tuple comparison and it allows us to correctly select only one process out of i and j.but not both (when Number[i] = Number[j] )


Progress and Deadlock:

The testing condition given in the question is while (t[j] != 0 && t[j] <=t[i]); which creates deadlock for both i and j ( and possibly more) processes which have calculated their Numbers as the same value. C and D are wrong.


Bounded waiting :

If the process is waiting and looping inside the for loop. Why is it waiting there ? Two reasons,

  1. Its number value is not yet the minimum positive value.
  2. Or, its Number value is equal to some other's Number value.

Reason1 does not dissatisfy bounded waiting , because if the process has the Number value = 5 then all processes having less positive Number will enter CS first and will exit. Then Process will definitely get a chance to enter into CS. 

Reason2 dissatisfy bounded waiting because assume process 3 and 4 are fighting with the equal Number value of 5. whenever one of them (say 4) is scheduled by the short term scheduler to the CPU, it goes on looping on  $Number[3] \Leftarrow Number[4]$ .Similarly with process 3 also. But when they are removed from the Running state by the scheduler , other processes may continue normal operation. So for process 3 and 4 although they have requested very early, because of their own reason, other processes are getting a chance of entering into CS. B is wrong.

note : in this all the processes go into deadlock anyway after a while.


How mutual exclusion is satisfied ?

Now we assume all processes calculate their Number value as distinct.

And categorize all concurrent N processes into three groups;

  1. Processes which are now testing the while condition inside the for loop.
  2. Processes which are now in the reminder section. 
  3. Processes which are now about to calculate its Number values.

 In Category 1, assume process wins the testing condition, that means no one else can win the test because has the lowest positive value among the 1st category of processes.

Category 3 processes will calculate Number value more than the Number of using max the function.

Same goes with Category 2 processes if they ever try to re-enter. 


detail of bakery algorithm Link1 and Link2 and Link3_page53

 


 

For curious minded people:

https://cacm.acm.org/magazines/2022/9/263810-deconstructing-the-bakery-to-build-a-distributed-state-machine/fulltext

 

 

edited by
34 votes
34 votes
1.do {
2.    c[i]=1; 
3.   t[i]= pmax (t[0],....,t[n-1])+1;
4.    c[i]=0;
5.    for every j != i in {0,....,n-1} {
6.        while (c[j]); 
7.        while (t[j] != 0 && t[j] <=t[i]);
8.   }
9.    Critical Section;
10.    t[i]=0;
    
11.    Remainder Section;
    
12.}  while (true);

The above code is N process synchronization solution (Lamport's bakery algorithm)

For detailed information on it , I'd request you to please refer below link and then come to this question.It'd really help you to understand the algorithm in detail and then the below solution would become very trivial.

https://www.youtube.com/watch?v=3pUScfud9Sg

Lines 2-4 can be termed as doorway for getting the token number. Each process which wants to enter into Critical section, gets a token number similar to restaurant system and wait for his token to be announced.

2. c[i]=1; //announce that process Pi is now ready to take it's token number


3. t[i]= pmax (t[0],....,t[n-1])+1; //get token number

This line 3, can be further decomposed as

(a)LOAD R1  MAX[0..N-1] where max[0..n-1] is the same function which returns max of t[0..n-1]

(b) INCR R1

(c) STORE t[i]


4. c[i]=0; //announce that process Pi has taken it's token number.

Now consider a scenario when processes P1, P2 P3 and P4 want to enter critical section

now since in question, there is no way indicated that line 3 is atomic, two or more processes may get same token value.

So when P1, P2 , P3 and P4 want to enter say

below is an instance of array t[i] for the above processes.

P1 P2 P3 P4
0 1 1 1

As you can see, processes P2, P3 and P4 have got same t[i] value because line 3 was not atomic in nature.

Suppose their respective C[i] values are all zero as of now,

then 

Say P2 wanted to enter C.S. so it executed below line

while (t[j] != 0 && t[j] <=t[i]);

Now for J!=i, P2 scans for processes P1,P3 and P4 and checks if one any one of them would have it's timestamp less than or equal to it's own timestamp or token value.

P2 finds this to be true and loops at this condition.

Similarly processes P3, and P4 keep looping at while condition.

Suppose now P1 wants to enter C.S. and now t[i] array is as follows

P1 P2 P3 P4
2 1 1 1

P1 gets a timestamp value of 2.

Now when P1 gets to execute line number 7

while (t[j] != 0 && t[j] <=t[i]);

it finds that all other processes have their timestamp non-zero and have value less than that of token of P1, so P1 also waits.

As, we can see now a deadlock is created. No process will now be able to proceed.

Hence option (d) is ruled out.

When there is deadlock possibility, progress is definitely not satisfied, because progress states that in a finite amount of time decision must be taken which process will get to execute CS next.

When a deadlock is present, bounded waiting may or may not be satisfied.

Good Read on the above point is : https://cs.stackexchange.com/questions/63730/how-to-satisfy-bounded-waiting-in-case-of-deadlock

Let's examine case of bounded waiting here.

Consider we have  4 processes and they have been assigned timestamp as below

$P_0$ $P_1$ $P_2$ $P_3$
1 2 3 3

Now, process $P_0$ and $P_1$ will get chance to execute CS, and after they complete the $t[i]$ values are as under:

$P_0$ $P_1$ $P_2$ $P_3$
0 0 3 3

Now, process $P_2$ and $P_3$ would keep looping in while loop and never get to execute CS.

Now, consider a scenario where we have 7 processes which have been assigned t[i] values as under

$P_0$ $P_1$ $P_2$ $P_3$ $P_4$ $P_5$ $P_5$
1 2 3 4 5 6 6

 

Now, processes $P_0,P_1,P_2,P_3,P_4$ will get to execute CS but $P_5,P_6$ won't get a chance to execute CS.

Similarly another scenario can be there where some processes are allowed into CS, who have got distinct t[i] values and the processes with the same t[i] values(say t[i]=k) and the processes having t[i] values greater than the k, won't get a chance to execute CS.

Now I ask you this question. Since this code is a solution for "N" processes, is your "K" bounded?

And bounded waiting says that there exist a bound on the number of times that other processes are allowed entry into CS between the time the process placed its request for CS and the time the request for CS is finally granted.

Does, your code guarantee that under any circumstances, for a constant k , after k processes execute finally process $P_i$ would get a chance to get into CS?

The answer is NO. K is variable here and not constant.K depends on the moment when two or more processes take the same t[i] value.

So, Bounded waiting is NOT Satisfied.

 

Now let's prove option (a)

Consider that again we have four processes and below is their token value

P1 P2 P3 P4
0 1 0 0

Suppose only now P2 wants to enter C.S. so, it gets its token value as 1.

When P2, executes line number 7, it succeeds as no other process has t[i] non-zero.

P2 enters into C.S.

Now suppose P2 is executing in C.S. and it is preempted.

P3 now wants to enter C.S. and gets it token

P1 P2 P3 P4
0 1 2 0

When P3 will execute line number 7, it will find that process P2 has it's token value non-zero and it is less than it's own token value(1<2). So, P3 will now wait.

Hence, Mutual Exclusion is satisfied.

Answer- Option (a)

edited by
2 votes
2 votes

This Question is a little bit wrong modification of bakery algorithm. You can learn about bakery algorithm from this 15 min video of NPTEL. 

NPTEL - Bakery Algorithm

https://youtu.be/3pUScfud9Sg

Answer:

Related questions