为什么使用单个“转向"变量简化 Peterson 算法不提供进程同步?

问题描述

我正在阅读"

I'm reading "Operating System Concepts" and trying to make sense of Peterson's Solution (on page 208), an algorithm for ensuring two processes sharing memory do not access the shared resource at the same time (potentially creating a race condition).

在Peterson的解决方案中，有两个共享变量有助于同步:布尔标志[2]"和"int turn".flag[i]"表示特定进程是否试图进入其临界区"，即访问共享数据的部分."turn"包含两个进程的索引之一(0或1)，并指示它将访问共享数据的进程.

In Peterson's Solution, there are two shared variables that help with synchronization: "boolean flag[2]" and "int turn". "flag[i]" indicates whether a particular process is trying to enter its "critical section," the section where it accesses shared data. "turn" contains one of the two processes' indexes (0 or 1) and indicates which process' turn it is to access the shared data.

Peterson的算法(对于流程i，其他流程用j表示)如下:

Peterson's algorithm (for process i, where the other process is denoted by j) is below:

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算法的简化也不能提供过程同步?如果我理解为什么不这样，我相信它将帮助我理解Peterson的算法.

Why does the following simplification of Peterson's algorithm not also provide process synchronization? If I understand why not, I believe it will help me understand Peterson's algorithm.

#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开始.为什么该算法无法实现流程同步?

In this simplified algorithm, it seems to me that a given process i will continue while looping until the other process j finishes its critical section, at which point j will set "turn = i", allowing i to begin. Why does this algorithm not achieve process synchronization?

推荐答案

因为简化版有可能会饿死.

正如您提到的:

好吧，现在说 Process i 完成，并将设置 turn = j .现在，如果 Process i ，再次想要输入关键部分，则不能输入 turn = j .进程i 能够进入关键部分的唯一方法是进程j 再次进入关键部分并设置 turn = i .

Ok, now say Process i finishes and will set turn = j . Now if Process i, again wants to enter critical section, it cannot enter as turn = j. The only way for Process i to be able to enter Critical Section is Process j again enters Critical Section and sets turn = i.

因此，如您所见，简化版本要求流程必须严格交替进入关键部分，否则将导致饥饿.

So, as you see the simplified version requires that the processes must enter critical section in strict alternation, otherwise it will lead to starvation.

这篇关于为什么使用单个“转向"变量简化 Peterson 算法不提供进程同步?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！