Deciding if mutual exclusion and progress is satisfied

Question

Consider the following

Process Pi while(1) {    while(turn != i);    //critical section    turn = j;    //remainder section }

Process Pj while(1) {    while(turn != j);    //critical section    turn = I;    //remainder section }

In above case,

• A. Mutual exclusion & progress are not satisfied
• B. Only mutual exclusion is satisfied
• C. Only progress is satisfied
• D. Both mutual exclusion and progress are satisfied

Comments

The very code in this problem is example of strict alteration while satisfying progress. Can you have a look at my comment on the below answer. In that answer, I have

• put screenshot of Galvin's book page explaining how book proves Peterson's solution satisfies Progress  
• put screenshot of Galvin's book page defining Progress requirement
• given proof of how code in this problem satisfies progress requirement on the exact same line as that of Galvin's proof for Peterson's solution
• Noted that how both Peterson's solution and code in this problem have possibility blocked process on other process's termination

Link to that comment: this comment

---

@Raj Singh 1 is there strict alternation in Peterson's algo? 

i don't think so. You are saying above problem satisfy progress.right?

 

---

Bro there is no strict alteration in Peterson's algorithm, but in the comment on the answer, I have used same method that is used in Galvin's book to prove that Peterson's solution satisfy progress, to prove that code with strict alteration also satisfy the progress:

Have you read that comment? 

Answer 1

Mutual exclusion is satisfied as Only one can enter into critical section

but progress is not satisfied

suppose its I's turn but got pre empted before entering into CS. Now j wants to enter into cs, but it cannot enter into CS as its I's turn

Comments

So you mean that

neither process is "not non-blocking" for other process, when it (the first process) terminates. In other words, if a process terminates before setting turn to other process, then it blocks the other process and hence the given solution for critical section problem does not ensure progress.

Right?

However, can you please refer Peterson's solution from Galvin's book? The same applies to Peterson's solution also:

do {
    flag [i] = TRUE;
    turn= j;
    while (flag[j] && turn==j);
    //critical section
    flag [i] = FALSE; 
    //remainder section
} while (TRUE);

Above, if any process terminates before setting flag[i] to FALSE, then the other process is blocked indefinitely. By your logic, even Peterson's algorithm does no satisfy progress requirement of the solution to the critical section problem. But Galvin's book says different and it goes on to prove how Peterson's solution satisfies progress requirement.

Also have a look at the definition of the progress requirement for the solution to the critical section problem from Galvin's book. It is defined in the book as follows:

If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections (that is processes executing in their entry and exit section) can participate in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.

This definition does not say anything about process termination and also about deadlock. (There are other problems and posts like this: https://gateoverflow.in/161404/me-bw-progress and this: https://gateoverflow.in/189234/deadlock-progress which relate deadlock with progress requirement.)

I feel process termination and deadlock is not considered while evaluating whether given code satisfies progress requirement of the solution of the critical section problem. Am I right?

I asked the detailed doubt here: https://gateoverflow.in/287646/relating-termination-deadlock-progress-requirement-solution

---

see above question is same as strict alternation

In the above question even though its I turn it got pre empted, even J willing to enter critical section it cannot enter due to mutual exclusion constraint... nothing but I stopping J to enter critical section dis obeying progress

Coming to peterson's algo -

A process has to say before  whether it is interested or not

If it is interested (true) then turn = that process

suppose there are two processes p1 and p2

at first both are initialized to false (by default)... If p1 wants to enter CS then it will initialize it to true

 

---

I didnt get your point. What you mean to say? See this is how Galvin's book proves Peterson's algorithm satisfies progress: 

Also have a look at definition of Progress given in Galvin:

Now let me prove how given code satisfies progress on the similar lines of how Galvin proves Peterson's solution satisfies progress:

Also note that 

Termination is the possibility with Peterson's solution (if either process terminates before setting flag[i]=FALSE, other process is blocked forever) as well as with the codes given in various problems and of course in this / current problem (as explained in your answer). The proof of progress satisied by Peterson's solution given in Galvin's book does not consider termination. However the solutions to various problems on gateoverflow and many other sources does indeed consider termination to decide upon whether progress requirement is satisfied or not.