修改Peterson算法

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] orturn = [1] )，并且在进程 P1 中进行类似的更改。生成的系统违反了关键部分的哪些属性？为什么？ - 这仍然会有互斥，但我对进度和有界等待表示怀疑。谁能给我提供更多这方面的信息吗？

感谢您的宝贵时间。

Answer 1

请参阅本文

Peterson 互斥算法的变体

摘要

1981年最 为两个并发提供的简洁版本 过程是彼得森算法。彼得森使用 决策控制中的 OR 运算符。 塔南鲍姆使用了彼得森的声称版本 在中使用 AND 运算符的算法 决策控制并且没有重置 旗帜。我们证明这个 AND 版本会导致 彼得森原始形式的平凡化。首先 看起来交错的循环恢复为批处理 加工。由于批处理是串行的 顺序，这消除了相互的需要 专为并发设计的排除算法 流程。使用 Peterson 最初的 OR 运算符 并像他一样重置标志，每次运行都是 交错的。此外，正如预期的那样， 德摩根谈彼得森控制算子的收益率 维持交错的 AND 版本 与彼得森的原始形式相同。然而， 这个形式显然并不比原来简单 或形式。它需要三个额外的 NOT 运算符和标志仍必须重置。

Answer 2

1. 为了提供互斥，您还需要将标志的 while 循环条件更改为

   while(flag[1] == 0 && 转 == 1)

2.可能会造成死锁。如果两个进程同时将其标志设置为 true，然后忙于等待 while 循环，那么它们都将无法继续进行。