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.
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 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
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
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)
