难道Peterson算法满足饥饿？ [英] Does Peterson's algorithm satisfy starvation?

问题描述

我一直在寻找在 Peterson的算法信息但所遇到的引用，说明它不符合饥饿，但只有僵局。这是真的？如果是这样有人可以详细说明它为什么没有？

I've been searching information on Peterson's algorithm but have come across references stating it does not satisfy starvation but only deadlock. Is this true? and if so can someone elaborate on why it does not?

Peterson算法：

Peterson's algorithm:

flag[0]   = 0;
flag[1]   = 0;
turn;

P0: flag[0] = 1;                                       
    turn = 1;                                               
    while (flag[1] == 1 && turn == 1)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[0] = 0;   

P1: flag[1] = 1;                                       
    turn = 0;                                               
    while (flag[0] == 1 && turn == 0)                        
    {                                                       
           // busy wait                                             
    }                                                                                      
    // critical section                                     
       ...                                                     
    // end of critical section                              
    flag[1] = 0;

该算法使用两个变量，标志和转弯。 1一个标志值表示进程想进入临界区。变量则持有过程中该轮到谁的ID。入口临界区被授予过程P0如果P1并不想进入临界区或P1通过设置变为0优先考虑以P0。

The algorithm uses two variables, flag and turn. A flag value of 1 indicates that the process wants to enter the critical section. The variable turn holds the ID of the process whose turn it is. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.

推荐答案

由于本杰克逊怀疑，这个问题是一个广义的算法。标准的2-过程Peterson算法满足无饥饿属性。

As Ben Jackson suspects, the problem is with a generalized algorithm. The standard 2-process Peterson's algorithm satisfies the no-starvation property.

显然，彼得森的原纸竟然出现了一个算法 N 的处理器。这里是一个草图，我只是写了，在C ++ - 如语言，也就是所谓算法：

Apparently, Peterson's original paper actually had an algorithm for N processors. Here is a sketch that I just wrote up, in a C++-like language, that is supposedly this algorithm:

// Shared resources
int pos[N], step[N];

// Individual process code
void process(int i) {
    int j;
    for( j = 0; j < N-1; j++ ) {
        pos[i] = j;
        step[j] = i;
        while( step[j] == i and some_pos_is_big(i, j) )
            ; // busy wait
    }
    // insert critical section here!
    pos[i] = 0;
}

bool some_pos_is_big(int i, int j) {
    int k;
    for( k = 0; k < N-1; k++ )
        if( k != i and pos[k] >= j )
            return true;
    }
    return false;
}

下面是一个死锁情况与 N = 3 ：

Here's a deadlock scenario with N = 3:

• 在进程0开始第一台 POS [0] = 0 和步[0] = 0 ，然后等待的时间。
• 在处理2开始下一个，集 POS [2] = 0 和步[0] = 2 ，然后等待的时间。
• 在处理1开始最后，台 POS [1] = 0 和步[0] = 1 ，然后等待的时间。
• 在处理2是第一个注意到的的更改步骤[0] 等集 J = 1 ， POS [2] = 1 和步骤[1] = 2 。
• 进程0和1被阻止，因为 POS [2] 就大了。
• 在处理2不堵塞，因此它设置 J = 2 。它这个逃脱的for循环，并进入临界区。项目建成后，集 POS [2] = 0 但马上又开始争夺临界区，从而设置步[0] = 2 和等待。
• 在处理1是第一个注意到的的更改步骤[0] 并继续像以前一样处理2。
• ...
• 处理1和2轮流进行竞争的过程中0。

• Process 0 starts first, sets pos[0] = 0 and step[0] = 0 and then waits.
• Process 2 starts next, sets pos[2] = 0 and step[0] = 2 and then waits.
• Process 1 starts last, sets pos[1] = 0 and step[0] = 1 and then waits.
• Process 2 is the first to notice the change in step[0] and so sets j = 1, pos[2] = 1, and step[1] = 2.
• Processes 0 and 1 are blocked because pos[2] is big.
• Process 2 is not blocked, so it sets j = 2. It this escapes the for loop and enters the critical section. After completion, it sets pos[2] = 0 but immediately starts competing for the critical section again, thus setting step[0] = 2 and waiting.
• Process 1 is the first to notice the change in step[0] and proceeds as process 2 before.
• ...
• Process 1 and 2 take turns out-competing process 0.

参考的。从纸张获得的所有细节关于著名互斥算法的一些神话的由Alagarsamy。显然，Block和宇提出了一种改进算法中的的彼得森的互斥算法更有效的推广，做满足无饥饿，这Alagarsamy在<以后的改进href="http://portal.acm.org/citation.cfm?id=1113142&dl=GUIDE&coll=GUIDE&CFID=110671243&CFTOKEN=49762291">A互斥算法优化界旁路（通过获取绑定的最佳饥饿 N-1 ）。

References. All details obtained from the paper "Some myths about famous mutual exclusion algorithms" by Alagarsamy. Apparently Block and Woo proposed a modified algorithm in "A more efficient generalization of Peterson's mutual exclusion algorithm" that does satisfy no-starvation, which Alagarsamy later improved in "A mutual exclusion algorithm with optimally bounded bypasses" (by obtaining the optimal starvation bound N-1).

这篇关于难道Peterson算法满足饥饿？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！