8

私はピーターソンのアルゴリズムに関する情報を検索してきましたが、それが飢餓を満足させるのではなく、デッドロックを満足させるだけであるという言及に出くわしました。これは本当ですか？もしそうなら、誰かがなぜそうしないのか詳しく説明できますか？

ピーターソンのアルゴリズム：

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;

アルゴリズムは、フラグとターンの2つの変数を使用します。フラグ値1は、プロセスがクリティカルセクションに入ろうとしていることを示します。変数turnは、そのターンのプロセスのIDを保持します。P1がクリティカルセクションに入ることを望まない場合、またはP1がターンを0に設定することによってP0を優先した場合、クリティカルセクションへの入り口はプロセスP0に許可されます。

4

3 に答える 3

9

ベンジャクソンが疑うように、問題は一般化されたアルゴリズムにあります。標準の2プロセスピーターソンのアルゴリズムは、飢餓なしの特性を満たしています。

どうやら、ピーターソンの元の論文は実際にNプロセッサのためのアルゴリズムを持っていました。これは、C ++のような言語で書いたばかりのスケッチで、おそらくこのアルゴリズムです。

// 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です：

  • プロセス0は最初に開始し、設定pos[0] = 0しstep[0] = 0てから待機します。
  • プロセス2は次に開始し、設定pos[2] = 0しstep[0] = 2てから待機します。
  • プロセス1は最後に開始し、設定pos[1] = 0しstep[0] = 1てから待機します。
  • プロセス2は、の変更に最初に気付くため、、、、およびstep[0]を設定j = 1します。pos[2] = 1step[1] = 2
  • pos[2]が大きいため、プロセス0と1はブロックされます。
  • プロセス2はブロックされていないため、を設定しますj = 2。これはforループを脱出し、クリティカルセクションに入ります。完了後、設定しますpos[2] = 0が、すぐにクリティカルセクションの競合を再開し、設定step[0] = 2して待機します。
  • プロセス1は、変更に最初に気づき、step[0]前のプロセス2として進行します。
  • ..。
  • プロセス1と2は、プロセス0と競合します。

参照。Alagarsamyによる論文「有名な相互排除アルゴリズムに関するいくつかの神話」から得られたすべての詳細。どうやらBlockandWooは、飢餓なしを満足する「ピーターソンの相互排除アルゴリズムのより効率的な一般化」で修正されたアルゴリズムを提案しました。 。N-1

于 2010-10-28T07:32:35.390 に答える
2

レックスはデッドロック状態で間違っています。
（補足として：正しい用語は飢餓シナリオです。デッドロックの場合、「スタック」する必要があるスレッドが少なくとも2つあるため、ウィキペディアを参照してください：デッドロックと飢餓）

プロセス2と1がレベル0に入ると、step [0]が1または2に設定され、プロセス0のアドバンス条件がfalseになるため、 falseになりstep[0] == 0ます。

2つのプロセスのピーターソンアルゴリズムは少し単純で、飢餓から保護します。

n個のプロセスのピーターソンアルゴリズムははるかに複雑です

プロセスが飢餓状態になる状況を作るには、その条件step[j] == i and some_pos_is_big(i, j)が永遠に真でなければなりません。これは、他のプロセスが同じレベルに入らないこと（step[j] == ifalseになる）、および少なくとも1つのプロセスが常にiと同じレベルまたはより高いレベルにあることを意味します（これがsome_pos_is_big(i, j)trueに保たれることを保証するため）

さらに、このレベルでデッドロックできるプロセスは1つだけですj。2つがデッドロックされた場合、そのうちの1つはstep[j] == i誤りであるため、デッドロックは発生しません。つまり、プロセスが同じレベルに入ることができず、常に上のレベルにプロセスが存在する必要があることを意味します。

他のプロセスは上記のプロセスに参加できないため（レベルjに入ることができないため、lelel jを超えないため）、少なくとも1つのプロセスがデッドロックしすぎている必要があります。そうしないと、クリティカルセクションのプロセスがクリティカルセクションを解放しません。

クリティカルセクションのプロセスが有限時間後に終了すると仮定すると、上記のプロセスの1つだけがデッドロックする必要があります。

ただし、その1つをデッドロックするには、上の別のプロセスをデッドロックする必要があります。ただし、上記のプロセスは有限であるため、クリティカルセクションが解放されると進行するため、最終的には最上位のプロセスをデッドロックできません。

そのため、n個のプロセスのピーターソンアルゴリズムが飢餓から保護します。

于 2012-03-28T19:56:40.177 に答える
0

飢餓についてのコメントは、一般化されたNプロセスのピーターソンのアルゴリズムに関するものだと思います。制限付き待機を使用してNプロセスバージョンを構築することは可能ですが、特に議論する必要がない場合、その特定の一般化が飢餓にさらされる可能性がある理由を言うことはできません。

簡単なグーグルは、擬似コードを含むこの論文を出しました。ご覧のとおり、一般化されたバージョンははるかに複雑です（そして高価です）。

于 2010-10-27T22:48:17.343 に答える