CODEWITHSUNDEEP
mutex
Chris
Chris

Reputation: 9509

Mutual Exclusion Problem

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!

Upvotes: 4

Views: 5059

Answers (6)

johannes
johannes

Reputation: 7272

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);

Upvotes: 2

Ikke
Ikke

Reputation: 101231

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

Upvotes: 5

Roger Lipscombe
Roger Lipscombe

Reputation: 91845

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

Upvotes: 0

zvrba
zvrba

Reputation: 24546

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.

Upvotes: -1

derobert
derobert

Reputation: 51157

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.

Upvotes: -1

starblue
starblue

Reputation: 56772

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

Upvotes: -1

Related Questions