Critical section problem

Question

proces P0:                             proces P1:
while (true)                           while (true)
{                                      {
  flag[0] = true;                          flag[1] = true;
  while (flag[1])                          while (flag[0])
  {                                        {
     flag[0] = false;                        flag[1] = false;
     flag[0] = true;                         flag[1] = true;
  }                                        }
 crit0();                                  crit1();
 flag[0] = false;                          flag[1] = false;
 rem0();                                   rem1();
}                                       }

Could someone give me a scenario with context switches to prove if the above stated code meets the requirements of progress and bounded waiting.

And can anyone give me some tips about how to detect if a code meets the requirements of progress or bounded waiting(and maybe including starvation,deadlock and after-you after you)

Answer 1

The two processes are happening at the same time.

The trick here is that since there is nothing truly synchronizing the two programs, something could happen between lines. On the same note, it's possible things happen at the same time.

To see how this can be an issue, think about this situation...

What would happen if the first flag[0] = true and the first flag[1] = true happened on P0/P1 at exactly the same time?

Both process 1 and process 2 would be stuck in a while loop. How would they exit the while loop? One process would have to check while(flag[other]) at exactly the same moment the other process set their flag[me] to true. This is a very narrow time span. It's the equivalent of rolling dice over and over and not continuing until you hit a certain number.

This is why we need something of a higher level to handle the synchronization for us - real locks and the like.

edit: Oh, one other thing. You may want to check to see if the read/write operations are thread safe. What happens if the system tries to write to the bit the same time it tries to read it?

edit2: FYI - http://msdn.microsoft.com/en-us/library/aa645755(v=VS.71).aspx