What's the standard technique to test if the algorithm satisfies mutual exclusion, progress and bounded waiting or not?

Question

Sorry if this is a stupid question. But it really intrigued  me. Same resources at different algorithms are telling different ways to test these stuffs.

Here's an algorithm and how I'd test for its 3 things.

    
    Process Larry:
    
    do{
            while(turn!="Larry");
                critical section
            turn="Jim";
                remainder section
            }while(TRUE);    
        }while(1);

**Mutual Exclusion:**

No two cooperating processes can enter into their critical section at the same time. For example, if a process P1 is executing in its critical section, no other cooperating process can enter in the critical section until P1 finishes with it.

    1) Initially turn="Larry".
    2) Larry and Jim both want to enter critical section.
    3) But only Larry succeeds because turn="Larry".
    So, mutual exclusion is achieved.

**Progress:**

    1) Larry Enters his critical section.
    2) Larry Finished his critical section.
    3) Larry sets the turn to Jim.
    4) Jim Enters the critical section/
    5) Jim Finished his critical section.
    6) Jim sets the turn to Larry.
    7) Jim quickly finishes his remainder section whereas Larry is stuck indefinitely in his remainder section.
    8) Jim can't access the critical section again till Larry doesn't access Critical Section and set turn to Jim.

Thus it fails to achieve Progress.

**Bounded Waiting:**

    1) Let turn="Larry".
    2) Larry executes his critical section.
    3) Larry wants to execute his critical section again.
    4) But it immediately sets turn="Jim".
    5) Larry executes his remainder section.
    6) Even if Jim doesn't want access to critical section, Larry won't be able to access the critical section.

Now,I want to test these 3 conditions for another algorithm, which is given below.

    Initially both the flags are false; flag[0]=flag[1]=F.
    P_0
    while(true)
    {
        flag[0]=T;
        while(flag[1]==T);//wait if P_1's turn
        critical section
        flag[0]=F
    }
    
    P_1
    while(true)
    {
        flag[1]=T;
        while(flag[0]==T);//wait if P_0's turn
        critical section
        flag[1]=F
    }

How do I follow a specific approach to test it? Or does it not exist? I want a  mental model to think about testing these 3 things in each algorithm.

Answer 1

I am going to check all three conditions in this algo.

 

    Initially both the flags are false; flag[0]=flag[1]=F.
    P_0
    while(true)
    {
        flag[0]=T;
        while(flag[1]==T);//wait if P_1's turn
        critical section
        flag[0]=F
    }
    
    P_1
    while(true)
    {
        flag[1]=T;
        while(flag[0]==T);//wait if P_0's turn
        critical section
        flag[1]=F
    }

 

 

 

I). checking Mutual Exclusion

if one process is executing its critical section then no other co-operative process should be allowed to execute its dependent critical section at same time.

to check mutual exclusion preempt processes in any order by intuitively thinking that is there any way they both can go  in critical section together.

 

Attempt 1 of checking mutual exclusion:

 

so initially suppose,

P_0 came in CPU and  it enters in while(true)

it makes flag[0]=T;

suppose then preemption happens and P_1 came and it enters in its while(true) and it makes flag[1]=T;

now suppose again preemption happens and P_0 came   and it runs  while(flag[1]==T);

and because flag[1]=T so P_0  stuck in while doing nothing.

now suppose again preemption happens and P_1 came and it runs  while(flag[0]==T);

and because flag[0]=T so P_1  stuck in while doing nothing.

so now you preempt in any order both process will be stuck here only and will not move ahead so it causes deadlock.

but we are not checking deadlock we are checking mutual exclusion which is still there. as no two cooperative process are executing critical section at a time.

now again try to execute P_0  and P_1  but this time do preemption in between in different order than previous one

 

Attempt 2 of checking mutual exclusion:

so initially suppose,

P_0 came in CPU and it enters in while(true)

it makes flag[0]=T;

now it runs next statement  while(flag[1]==T); and while loop will be ended as flag[1] =F till now. so P_0 enters in Critical section.

suppose then preemption happens and P_1 came and it enters in its while(true) and it makes flag[1]=T; and tries to run  next statement while(flag[0]==T); which is true because P_0 made flag[0]=T. so P_1 will stuck in while doing nothing.

now preemption happens and P_0 came and runs its critical section and made flag[0]=F and terminated.

now P_1 came and it was busy waiting for flag[0] to be false which is false now so it will come out of  while(flag[0]==T);

and will execute its critical section and will make flag[1] = F and terminates.

so here also we can see mutual exclusion holds as no two cooperative process execute their critical sections at a time.

so now after running like this in my brain i automatically think that if i will run in any manner mutual exclusion will hold good so i am not trying further but if you have little doubt try running both in other possible orders.

so i can say that mutual exclusion holds here.

 

 

II). Checking Progress:

If both process can run individually one after other in any order (firstly P_0 then P_1 or firstly P_1 then P_0) without any preemption in between then we can say progress is there.

 

i).Running P_0 Individually

P_0 came in CPU and  it enters in while(true) it makes flag[0]=T;

it runs  while(flag[1]==T); and comes out of while loop as flag[1] is still F. so now it runs its critical section and made flag[0]=F and terminated.

so P_0 can run individually.

 

i).Running P_1 Individually

P_1 came in CPU and  it enters in while(true) it makes flag[1]=T;

it runs  while(flag[0]==T); and comes out of while loop as flag[0] is still F.  so now it runs its critical section and made flag[0]=F and terminated.

so P_0 can run individually.

similarly try running P_1 first then P_0 then also no problem will come.

so both P_1 and P_0 can run individually without any problem so progress is there in this algorithm.

 

III). Checking Bounded waiting:

if one process(X) is executing its critical section and other cooperative process(Y) is waiting to go in critical section then when X is completed and if again X wants to go in critical section it should be not allowed as Y is waiting for Critical section for a long time so Y must get chance before X.

if this happens then we can say bounded waiting is holding.

but if if one process(X) is executing its critical section and other cooperative process(Y) is waiting to go in critical section then when X is completed and if again X wants to go in critical section and it is  allowed even though Y is waiting for Critical section for a long time then Bounded Waiting is violated.

 

so to test this firstly make one process(X) to go in critical section and make another process(Y) to wait for critical section and when X completed then again try to execute X even though Y is waiting if X is able to enter again in Critical Section then Bounded waiting is violated and if X is not able to enter again then bounded waiting is there.

similarly check by running Y first and then X and then also if bounded waiting there then we can say our algo holds bounded waiting.

 

i)checking bounded waiting by running P_0 in critical section and making P_1 wait for critical section.

P_0 came in CPU and  it enters in while(true) it makes flag[0]=T;

it runs  while(flag[1]==T); and comes out of while loop as flag[1] is still F. so now it is executing its critical section now preemption happens and

P_1 came in CPU and  it enters in while(true) it makes flag[1]=T;

it runs  while(flag[0]==T); and stuck there only as flag[0]=T as of now. now preemption happens

and P_0 came and it runs its critical section.

so we can see currently P_0 is executing its critical section and P_1 is waiting for executing its critical section.

now if P_0 executed its critical section and made flag[0]=F and terminated.

now even though P_1 is waiting for critical section execution then also you try to again run P_0 in critical section.

so

P_0 came in CPU and  it enters in while(true) it makes flag[0]=T;

it runs  while(flag[1]==T); but flag[1]=T so it will stuck in while loop and will not go to its critical section untill P_1 runs and make flag[1]=F again.

so bounded waiting is holding here.

 

similarly

ii)checking bounded waiting by running P_1 in critical section and making P_0 wait for critical section.

and do same as above step and this will also follow bounded waiting.

so this in this algo Bounded Waiting holds.

 

so we can see Mutual exclusion, Bounded waiting, Progress all holds here .

 

i hope i explained whatever you asked for.

Thank you.

 

P.S.  : ignore some spelling mistakes as i did not check for it.

 

Comments

I suspect you're wrong here. Anyone correct me I’m wrong. This is FLAG based solution to critical problem, and it only support mutual exclusion according to Prateek Jain Academy sir.

---

As per my understanding it supports all three.

but i may be wrong also , so kindly explain answer whenever you get it so that i can also check where i did wrong.

Thank You.

---

Progress here is not satisfied here 

Lets start with the definition=> If no process is currently executing in their critical section, and one or more processes want to execute their critical section, then only the processes not in their remainder sections can participate in the decision, and the decision cannot be postponed indefinitely. (No process in the critical section p1 arrives p1 enters  and other condition 2 or more process in the entry code waiting to enter the cs and are in entry code show that at least one will enter cs) 

Source-https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html

Also progress implies no deadlock.

P0 enters making flag[0] = true P0 stop working and CPU schedule P1 on CPU and after making flag[1] = true , P0 start working then both the processes are stuck in while loop so deadlock happens so , progress is violated.

Answer 2

1]Mutual exclusion is happening

Put P0 in critical section at that time flag[0] will be true, so if P1 want to enter in critical section

at that time P1 will stuck in while loop while(flag[0]==true); until P0 complete it's execution in critical section and make flag[0]=false , hence mutual exclusion is happening.

 

2] progress is violated.

Suppose P0 is star working after making flag[0] = true P0 stop working and CPU schedule P1 on CP and after making flag[1] = true , P0 start working then both the processes are stuck in while loop so deadlock happens so , progress is violated.

3] Bounded waiting is happening,

After completion of of P0 it will make flag[0] = false , and P1 is waiting at while loop for completion of process P0 so P1 get scheduled. So after completion of P0 it is not again get scheduled so bounded waiting is satisfied.