试图了解彼得森算法 [英] Trying to understand the Peterson's Algorithm

问题描述

我试图理解彼得森的算法，但遇到了这个问题.我跟踪了代码，并写下了自己的看法.请检查我的观察结果，我走对了吗?

I am trying to understand the Peterson's algorithm and I came across this question. I traced the code and I wrote my observations. Please check my observation, Am I on the right track?

问题:假设只有两个进程，一个进程的pid值为0，另一个进程的pid值为1. em>

Question from Textbook: Suppose the are only two processes, one with pid value 0 and one with pid value 1. What is wrong with this concurrency algorithm?

  while(True)
    {
     flag[pid] = 1
     turn = 1-pid
     while( flag[1-pid] && turn == 1-pid ); // busy wait

     // critical section
     ...
     // end of critical section

     flag[pid] = 0
    }

跟踪代码:

    ---------- Process 0: ---------- | ---------- Process 1: ----------
                                     |
    pid = 0                          |    pid = 1
    flag[0] = 1                      |    flag[1] = 1
    turn = 1 - 0 = 1                 |    turn = 1 - 1 = 0
                                     |
    while (flag[1 - 0]               |    while (flag[1 - 1]    
            && turn == (1 - 0))      |            && turn == (1 - 1))
                                     |
    // --> while (flag [1] && true)  |    // --> while (flag [0] && true)
    // --> while (flag [1])          |    // --> while (flag [0])

我的观察

My observations

1. 我认为在繁忙的等待部分中，两个while循环都可能运行 永远.
2. 我还认为，例如过程0的其中一个过程退出时 它是while循环，然后可以将其标志设置为false(flag[0] = 0)并导致 其他进程不运行.因此，进程0可以运行两次，而进程1则根本不运行.此外，它还会导致进程1饿死，反之亦然.

1. I think in the busy waiting sections, both while loops may run forever.
2. I also think when one of the processes for example process 0 get out of it's while loop then it can set it's flag to false (flag[0] = 0) and causes the other process Not to run. Thus, process 0 can run twice and process 1 doesn't run at all. Further, it can also cause the process 1 to starve or vice versa.

推荐答案

Peterson算法保证两个过程都可以访问关键部分，而不会出现任何饥饿.

Peterson's Algorithm guarantees access to critical sections for both processes without any starvation.

• flag表示希望输入critical section.
进程使用
• turn来等待其他完成并继续执行critical section.
• 当一个进程完成时，它在critical section处工作，它声明它的欲望已经消失了(flag[pid] = False).这允许另一个人进入该部分.但是，如果由于上下文切换而使一个进程在不通知另一进程的情况下打开和关闭它的flag，它仍然必须在它的turn标志之间切换.

• flag indicates the desire to enter the critical section.
• turn is used by a process to allow the other finish waiting and proceed to critical section.
• When a process finish it's job at the critical section it states it's desire is gone (flag[pid] = False). This allows the other one to enter the section. However, if one process, due to context switches, toggles it's flag on and off without the other one noticing it, it still has to toggle it's turn flag.

彼得森算法之所以起作用，是因为每个过程都具有以下观念:

Peterson's Algorithm works because, each process has the following mindset:

I would like to access the critical section. So, I'll wait my turn

因此，您看到的一切最终都很好.没有饥饿，每个进程进行而没有被卡住，并且两个进程都通过和访问关键部分再次.

So you see, everything works out just fine in the end. There is no starvation, each process progresses without being stuck, and critical section is accessed by both processes over and over again.

这篇关于试图了解彼得森算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！