I came across following problem:

Consider following code:

πš πš‘πš’πš•πšŽ(𝟷) 
    πšπš•πšŠπš[πš’] = πšπš›πšžπšŽ;  
    πš πš‘πš’πš•πšŽ(πšπš•πšŠπš[πš“]);  
    /* π™²πš›πš’πšπš’πšŒπšŠπš• πšœπšŽπšŒπšπš’πš˜πš— */  
    πšπš•πšŠπš[πš’] = πšπšŠπš•πšœπšŽ;  
    /*πšπšŽπš–πšŠπš’πš—πšπšŽπš› πšœπšŽπšŒπšπš’πš˜πš— */  

Let flag is declared as Boolean flag[2] and Pi denote one process while Pj denotes other process and i=1-j. Both processes execute concurrently, then does the progress requirement of the solution to the critical section problem satisfied in the above case?


The solution says that both processes Pi and Pj can simultaneously execute flag[i]=true and then both may busy wait on while(flag[j]), thus leading to deadlock and hence progress requirement of the solution to the critical section problem is not satisfied.

I know the normal / day to day meaning of "progress" gives us feeling that if there can be deadlock, then there may not be the progress. But Galvin's book defines "Progress" as this:

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 can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

So I am guessing whether progress has anything to do with deadlock. And whether the code indeed satisfies progress requirement of critical section problem.


1 Answer 1


and this selection cannot be postponed indefinitely

In case of deadlock, deciding which process will enter next will be postponed indefinitely. So progress won't happen.


Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.