试图了解彼得森的N过程算法

Question

我试图理解Peterson的N-Process算法,我遇到了这个问题.

问题:假设3个进程具有进程ID0, 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了它,但它将如何帮助我们从哪里开始跟踪代码？

• 如果我们只是前开始在for循环过程0,那么所有的转值将被设置为比是给我们不同的值.

• 如果我们假设通过执行问题意味着进程0处于其关键部分,那么下一个进程的for循环将把转弯值设置为其他值.

为什么给他们我们的状态值以及它如何帮助我们找到开始跟踪代码的位置.

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

谢谢你,对不起,对不起.

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++) {

好的,所有进程的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子句为false,因此进程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,看看从那里发生了什么.

祝它好运.