c - 修改彼得森算法

Question

我知道 Peterson Algo 的默认实现。为我提供 - 相互排斥、进步和有限等待。

正常的 Peterson 算法如下。

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。任何人都可以向我提供更多信息吗？

感谢您的宝贵时间。

Answer 1

查看这篇论文

On Variations of Peterson's Mutual Exclusion Algorithm

Abstract

In 1981 the most concise version presented for two concurrent processes was Peterson's Algorithm. Peterson used the OR operator in the decision control. Tanenbaum uses a claimed version of Peterson's Algorithm that uses the AND operator in the decision control and there is no resetting of the flags. We show that this AND version leads to a trivialization of Peterson's original form. The first cycle, which looks interleafed, reverts to batch processing. Since batch processing is in serial order, this eliminates the need for a mutual exclusion algorithm designed for concurrent processes. Using Peterson's original OR operator and resetting the flags as he does, every run is interleafed. Furthermore, as should be expected, a DeMorgan on the Peterson control operator yields an AND version that sustains the interleafing identical to Peterson's original form. However, this form is clearly not simpler than the original OR form. It requires three additional NOT operators and the flags must still be reset.