试图理解彼得森的算法

Question

我试图理解彼得森的算法,我遇到了这个问题.我追踪了代码并写了我的观察结果.请检查我的观察,我是否在正确的轨道上？

教科书中的问题:假设只有两个进程,一个pid值为0,另一个pid值为1.这个并发算法有什么问题？

  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])

我的观察

1. 我认为在繁忙的等待部分,两个循环可能永远运行.
2. 我也认为当示例进程的其中一个进程0离开它的while循环时,它可以将它的标志设置为false(flag[0] = 0)并导致另一个进程不运行.因此,进程0可以运行两次,进程1根本不运行.此外,它还可能导致该过程1饿死,反之亦然.

Answer 1

Peterson的算法可以保证在没有任何饥饿的情况下访问两个过程的关键部分.

• flag表示进入的愿望critical section.
• turn由进程使用以允许其他完成等待并继续critical section.
• 当一个过程完成它的工作时,critical section它表明它的欲望已经消失(flag[pid] = False).这允许另一个进入该部分.但是,如果一个进程由于上下文切换flag而在没有另一个注意到它的情况下切换它,它仍然必须切换它的turn标志.

摘要

彼得森的算法之所以有效,是因为每个过程都有以下思维方式:

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

所以你看,到最后一切都很好.没有饥饿,每个进程都不会被卡住,并且两个进程一次又一次地访问关键部分.