Mutual Exclusion Problem

Question

Hi!

Please take a look on the following pseudo-code:

boolean blocked[2];
int turn;
void P(int id) {
      while(true) {
             blocked[id] = true;
             while(turn != id) {
                    while(blocked[1-id])
                    /* do nothing */;
                    turn = id;
             }
             /* critical section */
             blocked[id] = false;
             /* remainder */
      }
}
void main() {
      blocked[0] = false;
      blocked[1] = false;
      turn = 0;
      parbegin(P(0), P(1)); //RUN P0 and P1 parallel
}

I thought that a could implement a simple Mutual - Exclution solution using the code above. But it's not working. Has anyone got an idea why?

Any help would really be appreciated!

Answer 1

Maybe you need to declare blocked and turn as volatile, but without specifying the programming language there is no way to know.

Answer 2

Concurrency can not be implemented like this, especially in a multi-processor (or multi-core) environment: different cores/processors have different caches. Those caches may not be coherent. The pseudo-code below could execute in the order shown, with the results shown:

get blocked[0] -> false   // cpu 0
set blocked[0] = true     // cpu 1 (stored in CPU 1's L1 cache)
get blocked[0] -> false   // cpu 0 (retrieved from CPU 0's L1 cache)
get glocked[0] -> false   // cpu 2 (retrieved from main memory)

You need hardware knowledge to implement concurrency.

Answer 3

Compiler might have optimized out the "empty" while loop. Declaring variables as volatile might help, but is not guaranteed to be sufficient on multiprocessor systems.

Answer 4

Is this homework, or some embedded platform? Is there any reason why you can't use pthreads or Win32 (as relevant) synchronisation primitives?

Answer 5

Mutual Exclusion is in this exemple not guaranteed because of the following:

We begin with the following situation:

blocked = {false, false};
turn = 0;

P1 is now executes, and skips

  blocked[id] = false; // Not yet executed.

The situation is now:

blocked {false, true}
turn = 0;

Now P0 executes. It passes the second while loop, ready to execute the critical section. And when P1 executes, it sets turn to 1, and is also ready to execute the critical section.

Btw, this method was originally invented by Hyman. He sent it to Communications of the Acm in 1966

Answer 6

Mutual Exclusion is in this exemple not guaranteed because of the following:

We begin with the following situation:

turn= 1;
blocked = {false, false};

The execution runs as follows:

P0: while (true) {
P0:   blocked[0] = true;
P0:   while (turn != 0) {
P0:     while (blocked[1]) {
P0:     }
P1: while (true) {
P1:   blocked[1] = true;
P1:   while (turn != 1) {
P1:   }
P1:   criticalSection(P1);
P0:     turn = 0;
P0:   while (turn != 0)
P0:   }
P0:   critcalSection(P0);