multithreading - 为什么使用单个 'turn' 变量的 Peterson 算法的简化不提供进程同步？

Question

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

在 Peterson 的解决方案中，有两个有助于同步的共享变量:“boolean flag[2]”和“int turn”。 “flag[i]”表示特定进程是否试图进入其“临界区”，即访问共享数据的区段。 “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);

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

#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进入。 进程 i 能够进入临界区的唯一方法是 进程 j 再次进入临界区并设置 turn = i。

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