相互排斥问题

Question

请看下面的伪代码:

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
}

我认为可以使用上面的代码实现一个简单的Mutual-Exclution解决方案.但它不起作用.有谁知道为什么？

真的很感激任何帮助!

Answer 1

由于以下原因,相互排除在此示例中无法保证:

我们从以下情况开始:

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

P1现在执行,并跳过

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

现在的情况是:

blocked {false, true}
turn = 0;

现在P0执行.它通过第二个while循环,准备执行临界区.当P1执行时,它设置为1,并且还准备好执行临界区.

顺便说一下,这种方法最初是由海曼发明的.他于1966年将其发送给了Acm通讯公司