0

以下は、Peterson の 2 スレッド ロック アルゴリズムの一般化されたバージョンであり、「n」個のスレッド/プロセスがクリティカル セクションをめぐって競合できるようになっています。

基本的に、「n」レベルと「n」スレッドがあります。非アクティブまたは非クリティカル セクション領域で実行中のスレッドはレベル 0 です。レベル n-1 はクリティカル セクションです。すべてのスレッド/プロセスは、クリティカル セクションに入る前に n-1 レベルを通過する必要があります。

レベル [n] と犠牲者 [n] の 2 つの配列があります。最初の配列は、スレッドの threadId によってインデックス付けされ、エントリ level[i] には、threadId 'i' を持つスレッドの現在のレベルが格納されます。2 番目の配列はレベル番号によってインデックス付けされ、エントリの犠牲者 [i] には、レベル「i」に入る最新のスレッドのスレッド ID が格納されます。

level[] のすべての要素は 0 に初期化されます。victim[] の特定の初期化はありません。

1    void lock()
2    {  int me = ThreadID.get();
3       for (int i = 1; i < n; i++)
4       { level[me] = i;
5         victim[i] = me;
6         while ((∃k != me) (level[k] >= i && victim[i] == me)) ;
7       }
8    }
9   
10   void unlock()
11   {  int me = ThreadID.get();
12      level[me] = 0;
13   }

このコードは、Maurice Herlihy と Nir ​​Shavit による本「The Art of Multiprocessor Programming」からの直接のコピーです。

問題は、コードが相互排他性を満たしていないように見えることです!!

理由:- 6 行目は、同じレベルまたはそれ以上のレベルのスレッドが存在し、スレッド自体が現在のレベルに入る最新のスレッドになるまで、スレッドがそのレベルでループし続けることを意味します。レベルにとどまります。2 番目のスレッドが同じレベルになると、最初のスレッドの 'victim[i] == me' 式が false になり、次のレベルにプッシュ ダウンされます。

ここで、各レベルに 1 つのスレッドがあり、レベル 0 のスレッドがレベル 1 に進もうとすると、レベル 1 のスレッドはレベル 1 の犠牲者ではなくなるため、レベル 1 のスレッドがレベル 2 にプッシュされます。波及効果と各スレッドが 1 レベルずつ押し下げられ、レベル n-2 のスレッドもそのクリティカル セクションに入る!!

コードは実際に間違っているのでしょうか、それとも何か間違っていると解釈しましたか?

4

1 に答える 1

0

n はスレッドの数、n はレベルの数です。レベルは 0 で始まり、n-1 レベルはクリティカル セクションです。

すべてのレベルがスレッドで満たされている場合、最初のレベルであるレベル 0 に入る他のスレッドはありません。だから決して起こらない。

たとえば、スレッド数とレベル数が 3 の場合、最初はすべてのスレッドがレベル 0 で、2 つのスレッドが次のレベルに進むことができ、1 つが条件に従って待機する必要があります while ((∃k != me) (level[ k] >= 私 && 被害者[私] == 私)) ; そしてその 2 つのスレッドのうちの 1 つが、クリティカル セクションであるレベル 2 に進みます。

現在、各レベルは 1 つのスレッドで満たされています。考えられる唯一のシナリオは、クリティカル セクション内のスレッドがレベル =0 にすることによって unlock() を呼び出すことであり、他のスレッドのみが続行できます。

ポイントは、レベルの数に等しいスレッドの数です

于 2014-01-03T05:49:37.237 に答える