试图了解Peterson的N进程算法

Question

我想了解Peterson的N进程算法，并且遇到了这个问题。

问：假设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那么所有的 转值将被设置为比什么是给 给我们不同的值的循环。

• 如果我们通过执行问题的假设意味着过程0是在它的 关键部分，则在接下来的过程中会设置 转值别的东西的循环。

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

如果我得到一些提示来帮助我开始跟踪代码，那将会很棒。

谢谢你，对于长期问题抱歉。

Answer 1

既然你没有问的问题的答案，你问了一个合情合理的问题，我觉得有信心，我可以为你指明正确的方向，而不直接做作业（或其他）为您服务。

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

在由<flags[0], flags[1], flags[2], turn[0], turn[1]>值和当前正在执行的进程的ID定义的任何给定的时间假设系统的状态。进一步假设系统的当前状态是<0,0,0,2,-1>，进程0 当前正在执行。

由此我们可以假定系统在其执行过程中正常启动并达到该状态。所以我们需要找到一个系统可以处于该状态并且进程0正在执行的点。下一部分给我们一些回旋余地：

显示从这个状态开始运行到完成的三个进程的一种特定方式。

因此，可能有多种方法可以通过进程0执行到达这些变量值，但可以找到任何一个变量值并从那里去完成系统。

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

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

当一个进程在CPU上执行时，它可能会执行其代码的任何部分。

我觉得你只是措辞这个不好，我怀疑你了解的现实情况是，每个进程开始之初并运行，直到它的结束，因此“当进程在CPU上执行它开始离开的地方并且可以运行任意数量的指令直到它失去了在CPU上运行的权利（指令的数量取决于控制系统的任何数量）“是更准确的陈述。

所以，最简单的方法就是要从头开始，并转动手柄。这个问题不说，但旗帜，把通常初始化为-1所以在一开始我们有：

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

由于事情正在同时运行，让我们姑且认为每个进程有效地执行，同时每一行。它没有什么区别，因为你希望以后能够看到自己。

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

OK，算对所有进程= 0，他们都转到下一行：

flags[i] = count; 

所以现在：

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

到目前为止，一切都很好 - 下一行：

turn[count] = i; 

好的，这是有问题的 - 每个p rocess试图设置相同的变量。其中一个将赢，但我们不知道哪一个：

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

除了我们这样做，因为它是在问题中。我们可以制作turn[0] = 2。因此，我们在使用变量合适的状态，我们可以假设进程0是在控制，我们知道这是在这一行：

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

为了让您一开始，过程0，计数= 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个进程，看看发生了什么。

祝你好运吧。