为什么使用单个 'turn' 变量简化彼得森算法不提供进程同步？

Question

我正在阅读“Operating System Concepts”并试图理解 Peterson 的解决方案（第 208 页），这是一种确保共享内存的两个进程不会同时访问共享资源的算法（可能创建竞争条件）。

在 Peterson 的解决方案中，有两个有助于同步的共享变量："boolean flag[2]" 和 "int turn"。 "flag[i]" 指示特定进程是否正在尝试进入其 "critical section," 它访问共享数据的部分。 "turn" 包含两个进程的索引（0 或 1）之一，并指示轮到哪个进程访问共享数据。

Peterson算法（对于进程i，其他进程用j表示）如下：

do {
    #set flag to say I'm trying to run
    flag[i] = true
    #let the other process have a turn
    turn = j
    while(flag[j] == true && turn == j);

    #enter critical section

    flag[i] = false

    #do non-critial remaining stuff

} while (true);

为什么彼得森算法的以下简化也没有提供进程同步？如果我明白为什么不，我相信这将有助于我理解彼得森的算法。

#initialize turn to i or j
do {
    while(turn == j);

    #enter critical section

    turn = j;

    #do non-critial remaining stuff

} while (true);

在这个简化的算法中，在我看来，给定进程 i 将继续循环，直到另一个进程 j 完成其临界区，此时 j 将设置 "turn = i"，允许 i 开始。为什么这个算法没有实现进程同步？

Answer 1

因为简化版有几率饿死

如你所说：

j finishes its critical section, at which point j will set "turn = i", allowing i to begin.

好的，现在说 Process i 完成并将设置 turn = j 。现在如果Process i，又要进入临界区，它不能进入turn = j。 Process i能够进入临界区的唯一方法是Process j再次进入临界区并设置turn = i.

因此，如您所见，简化版要求进程必须严格交替进入临界区，否则会导致饥饿。

为什么使用单个 'turn' 变量简化彼得森算法不提供进程同步？

Why does a simplification of Peterson's Algorithm using a single 'turn' variable not provide process synchronization?

multithreading

operating-system

mutex

locking

process