互斥问题 [英] Mutual Exclusion Problem

问题描述

请查看以下伪代码:

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
}

我认为a可以使用上面的代码实现简单的互斥解决方案.但这不起作用.有人知道为什么吗?

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?

任何帮助将不胜感激！

推荐答案

由于以下原因，因此无法保证互斥:

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

我们从以下情况开始:

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

P1现在执行并跳过

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

现在的情况是

blocked {false, true}
turn = 0;

现在执行P0.它通过第二个while循环，准备执行关键部分.当执行P1时，它会将turn设置为1，并准备执行关键部分.

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.

顺便说一句，这种方法最初是由海曼发明的.他在1966年将其发送给Acm的通讯部门

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

这篇关于互斥问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！