以下は、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 のスレッドもそのクリティカル セクションに入る!!
コードは実際に間違っているのでしょうか、それとも何か間違っていると解釈しましたか?