c - 试图理解 Peterson 的 N-Process 算法

Question

我试图理解 Peterson 的 N-Process 算法，但我遇到了这个问题。

问题:假设 3 个进程具有进程 ID 0, 1 and 2 .这些进程在单处理器上并发执行，并使用 Peterson 的 N 进程算法来控制临界区的执行。每个进程运行以下伪代码:

lock(pid);
<critical section>;
unlock(pid

哪里 lock()和 unlock()函数定义为

lock(for Process i):

/* repeat for all partners */
for (count = 0; count < (NUMPROCS-1); count++) {
    flags[i] = count;
    turn[count] = i;
    "wait until (for all k != i, flags[k]<count) or (turn[count] != i)"
}


Unlock (for Process i):

/* tell everyone we are finished */
flags[i] = -1;

假设系统在任何给定时间的状态由 <flags[0], flags[1], flags[2], turn[0], turn[1]> 定义。值和当前正在执行的进程的 id。进一步假设系统当前状态为 <0,0,0,2,-1>带进程 0 当前正在执行 .展示从这个状态开始运行到完成的三个进程的一种特殊方式。当您跟踪三个进程的并发执行时，请显示每个步骤的系统状态。

我的观察

在单处理器上并发运行的进程不能同时在 CPU 上执行。一次只能在 CPU 上执行其中之一。
当进程在 CPU 上执行时，它可以执行其代码的任何部分。

// NUMPROCS = 3

-- 对于 i = 0

lock(for Process 0):
for (count = 0; count < 2; count++) {
    flags[0] = count;
    turn[count] = 0;
    "wait until (for all k != 0, flags[k]<count) or (turn[count] != 0)"
}


Unlock (for Process 0):
flags[0] = -1;

-- 对于 i = 1

lock(for Process 1):
for (count = 0; count < 2; count++) {
    flags[1] = count;
    turn[count] = 1;
    "wait until (for all k != 1, flags[k]<count) or (turn[count] != 1)"
}


Unlock (for Process 1):
flags[1] = -1;

-- 对于 i = 2

lock(for Process 2):
for (count = 0; count < 2; count++) {
    flags[2] = count;
    turn[count] = 2;
    "wait until (for all k != 2, flags[k]<count) or (turn[count] != 2)"
}


Unlock (for Process 2):
flags[2] = -1;

我的问题是 从哪里开始跟踪代码？给出 flags[0]=0, flags[1]=0, flags[2]=0, turn[0]=2, turn[1]=-1但是它将如何帮助我们从哪里开始跟踪代码呢？

如果我们在进程 0 的 for 循环之前开始那么所有的
转弯值将设置为不同于给定值的其他值
给我们。

如果我们假设通过执行问题意味着处理 0在它的
临界区然后下一个进程的 for 循环将设置
将值(value)观转向其他事物。

为什么给我们状态值，以及它如何帮助我们找到从哪里开始跟踪代码。

如果我能得到一些提示来帮助我开始跟踪代码，那就太好了。

谢谢你，很抱歉问这么长的问题。

Answer 1

由于您没有询问问题的答案，而且您提出了一个合理而明智的问题，我相信我可以为您指明正确的方向，而无需为您做功课(或其他任何事情)。

首先，问题的关键部分在这里:

Suppose the state of the system at any given time is defined by <flags[0], flags[1], flags[2], turn[0], turn[1]> values and the id of the currently executing process. Further suppose that the current state of the system is <0,0,0,2,-1> with process 0 currently executing.

由此我们可以假设系统正常启动并在执行期间到达该状态。所以我们需要找到一个点，系统可以处于该状态并且进程 0 正在执行。下一部分给了我们一些回旋余地:

Show one particular way for three processes to run to completion starting from this state.

因此，可能有多种方法可以在进程 0 执行时获取这些变量值，但是可以找到任何一种并从那里开始完成系统。

此外，我们可以看到所有进程都运行一次并退出——有一个循环，但我们也可以看到它增加了 flags 的值。在每个回合中，我们可以很好地猜测我们只为变量值遇到了一次这种情况。但我们应该通过它来找出答案。

这些进程同时运行，但在单个处理器上运行。因此，实际上只有一个正在执行，但某些更高的功能(例如操作系统)正在以我们无法确定的方式在它们之间切换。你说:

While a process is executing on the CPU it may execute any part of its code.

我认为你的措辞很糟糕，我怀疑你理解现实情况是每个进程从头开始一直运行到结束，因此“当一个进程在 CPU 上执行时，它从它停止的地方开始，并可能运行任意数量的指令直到它失去在 CPU 上运行的权利(指令的数量取决于控制系统的任何东西)”是更准确的说法。

所以最简单的方法就是从头开始，转动 handle 。问题没有这么说，但标志和转弯通常被初始化为 -1所以一开始我们有:

flags = [ -1, -1, -1 ]; turn = [ -1, -1 ] 

由于事情是并发运行的，让我们假设每个进程同时有效地执行每一行。它没有任何区别，因为您希望以后能够亲眼看到。

for (count = 0; count < (NUMPROCS-1); count++) {

好的，所有进程的计数 = 0，它们都转到下一行:

flags[i] = count;

所以现在:

flags = [ 0, 0, 0 ]; turn = [ -1, -1 ]

到目前为止，一切都很好——下一行:

turn[count] = i;

好吧，这是有问题的——每个进程都试图设置相同的变量。其中一个会赢，但我们不知道是哪一个:

flags = [ 0, 0, 0 ]; turn = [ ?, -1 ]

除了我们这样做，因为它在问题中。我们可以制作 turn[0] = 2 .所以我们处于变量的合适状态，我们可以假设进程 0 处于控制之中，我们知道它在这条线上:

"wait until (for all k != i, flags[k]<count) or (turn[count] != i)"

为了让您开始，对于进程 0，count = 0 和 i = 0 所以

"wait until (for all k in {1,2}, flags[k]<0) or (turn[0] != i)"

您可以看到 or子句为假，因此进程 0 将再次循环。所以将处理 1。 for all k条款不适用于任何人。所以进程2会因为 turn[0]的值而等待-- 你也可以看到这永远不会改变，所以进程 2 现在被锁定等待 for all k子句成真——事实上，这是这个系统如何运作的关键。如果您按照逻辑来回答问题，您将看到进程如何相互锁定，以便一次只有一个人执行临界区。继续做我上面做的事情，因为你只需要找到一个可以同时执行行的路径，当有潜在冲突时，只需选择一个值并从那里开始。

您还可以看到，如果进程 2 在其他进程有机会之前立即执行了所有它的行，然后进程 1 和进程 0 最终会在同一个地方。如果您以各种方式处理整个系统，您会发现模式相似(请注意，不能保证进程执行其关键部分的顺序，这取决于谁在有争议的线路上“获胜”)。

所以回到最初的问题，只有少数几个地方进程 0 可以控制该系统状态。要么上 wait行，或在 for当计数增加到 1 时(在循环之后)或在它设置的行 flag[0] .之后系统状态就不一样了。最好假设最早的一个，因为进程 1 没有被阻塞(还)并且也可能改变状态。

为了完整性，最后的皱纹。还有一个地方可以控制该进程，系统状态也可以是这样。它就在 turn[count] = i; 之前线。在这个场景中，进程 2 刚刚设置了变量，进程 0 即将覆盖它。您可以从这里继续，但将是进程 1 和 2 循环。我包括这个预期的评论，我实际上并不是建议你使用它作为起点，尽管它是完全有效的。几乎可以肯定，这个问题希望您从进程 0 和 1 开始循环，其中 2 阻塞在忙等待中，以查看从那里发生的情况。

祝你好运。