38,658 views

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

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

what does above line means?

I conclude it like this-

if (t[j] !=0 and t[j]<= t[i]) is true then process will be in the while loop (because of semicolon in while loop) and if any of the condition is false ( means if ( t[j] == 0 ) or ( t[j] > t[i] )) then it will enter into critical section?

consider 3 processes P0,P1,P2 with t[]= {0,0,0} //Will be ignoring c[i] for this example.

 P0 P1 P2 t[0]=1 t[1]=2 t[2]=3 // t[i] can be viewed as a timestamp for a process, relative to the other processes (hence the reason for max(ti)+1) while (t[j] != 0 && t[j] <=t[i]) //As no other t[j] (where i!=j) is zero, which implies no other processes has been to critical section yet. Also, t[j] <=t[i] implies the current process should busy wait, until the older process (smaller timestamp) still exists in the queue. Overall, the point of this whole condition is that older processes must enter CS first. As a result P0 enters CS and t[0] becomes 0. Now that t[0] = 0, no need for comparing its time stamp with t[1], as it has been already been to CS, being an older process. for other j ie t[2]=3, t[1]

Hence, we can conclude only one process is allowed to enter CS at a time // Not concrete proof though
Also, I believe bounded waiting is satisfied, but read the below answers for more details on that.

update the tags in go book also

 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.

by

@hitechga, yes

As it is not assumed that the statement t[i]=pmax()+1 is atomic more than one process can take up the same value. And if all the processes take up the same value then the system will be in deadlock right?

And if that statement is atomic then no deadlock right?

edited

@HitechGa @Sachin Mittal 1 Sir can we think in this way,

→ We can see initial values of c[i] are not given. So, we can initialize c[0] to c[n-1] with 1.

Acc to the definition of progress “ if no process is executing in it’s critical section and some processes wish to enter the CS , then those processes that are not executing in their remainder sections can participate in deciding which will enter its CS next and this section cannot be postponed indefinitely”.

Let’s say process P1 wants to enter CS and other processes don’t want to enter the CS. So value of j will be {0,2,3….,n-1} and while(c[j]) will be true for all values of j and P1 can’t enter the CS. P1 has to wait indefinitely for no reason. It has to wait for other processes. So, we can say progress is not guaranteed.

-> Let's say there are only 2 processes P0 and P1 and both want to enter the CS.

t[i]= pmax (t[0],....,t[n-1])+1 this is not an atomic expression.

R1 <-  pmax (t[0],t[1])

R1 <- R1 + 1

t[i] <- R1

P0                                                                                                 P1

c[0]=1

c[1] = 1

R1 <-  pmax (t[0],t[1]) // R1 <- 1

R2 <-  pmax (t[0],t[1]) // R2 <- 1

R1 <- R1 + 1 // R1<- 2

R2 <- R2 + 1 // R2<- 2

t[0] <- R1 // t[0] <- 2

t[1] <- R2 // t[1] <- 2

c[0]=0;

c[1]=0;

value of j is 1

while (c[1]); // false

while (t[1] != 0 && t[1] <=t[0]); // condition satisfied

value of j is 0

while (c[0]); // false

while (t[0] != 0 && t[0] <=t[1]); // condition satisfied

Both get stuck and can't proceed. So these processes are in deadlock bcz t[j] =t[i].

Bounded waiting is also guaranteed.

 t[0] t[1] t[2] t[3] t[4] 2 3 7 6 5

 c[0] c[1] c[2] c[3] c[4] 2 3 7 6 5

1. First P0 will enter the CS bcz (t[j= 1,2,3,4] > t[0]) and make t[0]=0.

 t[0] t[1] t[2] t[3] t[4] 0 3 7 6 5

2. P1 will enter the CS bcz ((t[j= 2,3,4] > t[1]) and t[j=0] == 0 ) and make t[1] =0.

 t[0] t[1] t[2] t[3] t[4] 0 0 7 6 5

3. P2 will enter the CS bcz ((t[j=3,4] > t[2]) and t[j=0] == 0, t[j=1] == 0 ) and make t[2] =0.

 t[0] t[1] t[2] t[3] t[4] 0 0 0 6 5

4. P3 will enter the CS bcz ((t[j=4] > t[3]) and t[j=0] == 0, t[j=1] == 0, t[j=2] =0) and make t[3] =0.

 t[0] t[1] t[2] t[3] t[4] 0 0 0 0 5

3. P4 will enter the CS bcz ( t[j=0] == 0, t[j=1] == 0, t[j=2] =0, t[j=3] =0 ) and make t[4] =0.

So, all processes can enter the CS(critical section), and bounded waiting is satisfied. Bounded waiting means providing a bound time of waiting for each process.

Mutual Exclusion is also satisfied.

P1, P2, P3, and P4 want to enter CS.

Let's say P0 is in CS it means (c[j = 1,2,3,4 ] =0) and (t[j=1,2,3,4] > t[i=0])

P1 can't enter into the CS bcz while (t[j=0] != 0 && t[j=0] <=t[1]) will be satisfied and will keep on checking this condition. Similarly for P2,P3,P4. In CS there will be atmost 1 process at a time. So, mutual exclusion is satisfied.

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++) {
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] )

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 i  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 i has the Number value = 5 then all processes having less positive Number will enter CS first and will exit. Then Process i 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 i wins the testing condition, that means no one else can win the test because i has the lowest positive value among the 1st category of processes.

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

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

by

amazing explanation. That little confusion has gone away now. Thanx a lot.
@Akriti

Bounded waiting means after a Process request to go in CS, how many other process it allows to enter CS before it going to CS.

Here as deadlock possible , so this bound is infinite. So, BW dissatisfied

@srestha So it  means that as per this problem Bounded Waiting is considered as no of processes that a given process has to wait in succession to enter the CS again.

Like if we have process  P0 to P9999 then for Process P0(after its first round of execution) to enter again,has to wait until all the processes from P1 to P9999 has completed.Then only it can enter?

Is this waiting for P1 considered to be unbounded? i.e.,BW here is considered based on no. of processes but not on wait time?

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.

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.

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.

@Ayush Upadhyaya I think Bounded Waiting is not satisfied since a process can apply to get the token any number of times after exiting its critical section. So bounded waiting is not satisfied.

@Shaik Masthan commented that:

problem is, more than one process waiting for entering into CS, then it lead to DEADLOCK.

let P0 only want to enter into CS ===> it can enter.

while P0 is in CS, P1 and P2 in the for loop for waiting into the for loop.

P0 out from CS, then P1 and P2 both are strucked in the loop ===> DEADLOCK

A processes (P1 & P2) get stucked in while loop whenever a process ,say P0, exist whose non-zero token number is less than the current process. P1 & P2 comes out of the while loop when P0 makes its token 0 i.e it comes out of CS and resumes while loop from where it get stucked.

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

We can guarantee that it will be n-bounded. Where n is the number of processes, can’t we?

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

by

Wrong modification or modification?
yes it is wrong modification, because in the correct modification of original bakery algorithm, it is free from deadlock, it insures progress as well as bounded waiting also. for further information you can refer to the answer provided by the arjun sir.