1

我知道 Peterson Algo 的默认实现。给我 - 互斥、进步和有限的等待。

正常的彼得森算法如下。

bool flag[0]   = false;
bool flag[1]   = false;
int turn;

P0: flag[0] = true;
    turn = 1;
    while (flag[1] && turn == 1)
    {
        // busy wait
    }
    // critical section
    ...
    // end of critical section
    flag[0] = false;


P1: flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0)
    {
        // busy wait
    }
    // critical section
    ...
    // end of critical section
    flag[1] = false;

我希望对这个版本进行一些修改。

1) 进程 P0 中的语句 flag[0] = TRUE 和 flag[0] = FALSE 互换，在进程 P1 中进行类似的更改。这个算法会为我提供 - 互斥、进步和有限等待。- 我觉得这个算法不支持互斥。任何人都可以为我提供更多信息吗？

2) Peterson 解中的语句 while (flag[1] && turn = 1) 改为 while (flag[1] or turn = [1] ) 并在进程 P1 中进行类似的更改。结果系统违反了临界区的哪些属性，为什么？- 这仍然会有互斥，但我怀疑 Progress 和 Bounded waiting。任何人都可以为我提供更多信息吗？

谢谢你的时间。

4

1 回答 1

1

见这篇论文

关于彼得森互斥算法的变体

抽象的

1981 年，针对两个并发进程提出的最简洁的版本是彼得森算法。Peterson 在决策控制中使用了 OR 运算符。Tanenbaum 使用声称的彼得森算法版本，该算法在决策控制中使用 AND 运算符，并且没有重置标志。我们表明，这个 AND 版本导致彼得森原始形式的琐碎化。第一个循环看起来是交错的，然后恢复为批处理。由于批处理是按顺序进行的，因此无需为并发进程设计互斥算法。使用 Peterson 的原始 OR 运算符并像他一样重置标志，每次运行都是交错的。此外，正如预期的那样，Peterson 控制运算符上的 DeMorgan 产生一个 AND 版本，该版本维持与 Peterson 的原始形式相同的交错。但是，这种形式显然并不比原来的 OR 形式简单。它需要三个额外的 NOT 运算符，并且仍然必须重置标志。

于 2015-05-18T15:45:21.943 回答