Explain why this algorithm does not guarantee mutual exclusion

Question

Consider the following ‘busy waiting’ attempt for a mutual exclusion algorithm. Explain why this does not guarantee mutual exclusion. I can't figure out why it doesn't, to me it looks like it should can anyone explain why it doesn't?

/*Process0 */
while (flag[1]) do {/* nothing */}
flag[0] = true;
/*critical section */
flag[0] = false;

/*Process1 */
while (flag[0]) do {/* nothing */}
flag[1] = true;
/*critical section */
flag[1] = false;

Answer 1

It doesn't work because things you're apparently thinking of as atomic (i.e., inseperable) aren't anything of the sort.

Right now, you seem to assume that as soon as the while loop in one process exits, execution will continue through at least the entirety of the assignment to flag[N] without any context switches.

This simply isn't true. For the sake of argument, let's break each process into part A (the while loop) and B (the critical section). It's entirely possible to have a sequence like:

1A
2A
1B [for a while, then interrupted by context switch]
2B [for a while, then interrupted by context switch]
1B [resumes after context switch]
2B [resumes after context switch]

This is exactly the sort of code that works 99.9% of the time. You can probably test it like crazy for months on end, and it'll seem like it works perfectly--then you demo it in front of a customer, it crashes, burns, and destroys its surroundings. Then you send it back to the lab, and try though they will, they can't duplicate the problem.

Answer 2

Two things can happen here.

1. You can have two (or more) processes running concurrently. Either one may grab

   while (flag[1]) do {/* nothing */} // Both processes may see the flag cleared at the same time

    flag[0] = true;  // Two process set the flag
   

2. You could have a context switch

   while (flag[1]) do {/* nothing */} // Process gets blocked here

       // Some other process sets flag [0]
   
    flag[0] = true;  // Gets set for a second time