Question

Considering the following algorithm:

bool thread1 = false;

bool thread2 = false;

thread1 {

While (true) {   

    while(thread2 == true);      

    thread1 = true;  

               /* start of critical section */     

    …   ...

    /* end of critical section */  

    thread1 = false  

               …  

}   

}  

thread2 {

While (true) {   

    while(thread1 == true);      

    thread2 = true;  

               /* start of critical section */     

    …     

    /* end of critical section */  

    thread2 = false  

               …  

}   

}  

Does this solution have mutual exclusion?

Answer 1

Mutual exclusion allows only one process to enter the critical section at a time.

Initially the values of thread1 and thread2 both are false.

Let process 1 correspond to thread1 and process 2 correspond to thread2.

In the given segment, suppose Process1 executes till the line :

while(thread2==true);

and this will evaluate the false as thread2 = false, and then context switch takes place to Process 2.

Now the values of both thread1 and thread2 are still false.

Now let Process 2 executes till the line :

while(thread1==true);

and this will evaluate to false as thread1 = false. Then, let thread2 execute the remaining line and enter the critical section.

Now the value of thread2 = true and thread1 = false.

So, when Process 2 is in critical section, let Process 1 perform the remaining lines and enter the critical section.

Process 1 will update the value of thread1 from false to true and proceed towards critical section.

In this way, both Process 1 and Process 2 are present inside the critical section at the same time.

This violates the definition of mutual exclusion.

Hence, the solution does not have mutual exclusion.