c - 试图理解彼得森的算法

Question

我试图理解 Peterson 的算法，我遇到了这个问题。我追踪代码并写下我的观察结果。请检查我的观察，我走在正确的轨道上吗？

教科书中的

问题:假设只有两个进程，一个pid值为0，另一个pid value 1. 这个并发算法有什么问题？

  while(True)
    {
     flag[pid] = 1
     turn = 1-pid
     while( flag[1-pid] && turn == 1-pid ); // busy wait

     // critical section
     ...
     // end of critical section

     flag[pid] = 0
    }

跟踪代码:

    ---------- Process 0: ---------- | ---------- Process 1: ----------
                                     |
    pid = 0                          |    pid = 1
    flag[0] = 1                      |    flag[1] = 1
    turn = 1 - 0 = 1                 |    turn = 1 - 1 = 0
                                     |
    while (flag[1 - 0]               |    while (flag[1 - 1]    
            && turn == (1 - 0))      |            && turn == (1 - 1))
                                     |
    // --> while (flag [1] && true)  |    // --> while (flag [0] && true)
    // --> while (flag [1])          |    // --> while (flag [0])

我的观察

1. 我认为在繁忙的等待部分，两个 while 循环都可能运行永远。
2. 我还认为当其中一个进程例如进程 0 退出时它的 while 循环然后它可以将它的标志设置为 false (flag[0] = 0) 并导致其他进程不要运行。因此，进程 0 可以运行两次，而进程 1 根本不运行。此外，它还会导致进程 1 饿死，反之亦然。

Answer 1

Peterson 算法 保证在没有任何饥饿的情况下访问两个进程的关键部分。

• flag表示希望进入临界区。
• turn 被一个进程用来让另一个进程完成等待并继续到临界区。
• 当一个进程完成它在临界区 的工作时，它表明它的愿望已经消失 (flag[pid] = False)。这允许另一个人进入该部分。但是，如果一个进程由于上下文切换而打开和关闭它的 flag 而另一个进程没有注意到它，它仍然必须切换它的 turn 标志。

总结

Peterson 算法之所以有效，是因为每个过程都有以下思维方式:

我想访问临界区。那么，轮到我了

---

所以你看，最后一切都很好。没有饥饿，每个进程都在没有被卡住，并且临界区被两个进程反复访问再来一遍。