20

Javaでの相互排除のためのPetersonアルゴリズムの実装例はありますか?

4

5 に答える 5

27

ここでは、Javaでこのアルゴリズムの正しい/安全な実装を提供している人は誰もいません。John Wのソリューションは、断片が欠落しているため、どのように機能するのかわかりません（つまり、ThreadLocalsの宣言と、彼の配列にあるはずの説明-プリミティブにはありbooleansません）。get()set()

Java言語仕様の第17章では、Javaメモリモデルについて説明しています。特に興味深いのはセクション17.4.5で、これは発生前の注文について説明しています。単一のスレッド内で考えるのは非常に簡単です。スニペットについて考えてみましょう。

int x, y, z, w;
x = 0;
y = 5;

z = x;
w = y;

xこのスニペットの最後で、とは両方ともzに等しく、0両方はに等しいことに誰もが同意します。宣言を無視すると、ここでは6つのアクションがあります。yw5

  1. への書き込みx
  2. への書き込みy
  3. からの読み取りx
  4. への書き込みz
  5. からの読み取りy
  6. への書き込みw

それらはすべて同じスレッドに表示されるため、JLSは、これらの読み取りと書き込みがこの順序を示すことが保証されていると述べています。上記の各アクションn（アクションは単一のスレッドにあるため）には、すべてのアクションm、mとの発生前の関係があります。 > n。

しかし、異なるスレッドはどうですか？通常のフィールドアクセスの場合、スレッド間に確立された関係の前に発生することはありません。これは、スレッドAが共有変数をインクリメントし、スレッドBがその変数を読み取っても、新しい値が表示されない可能性があることを意味します。JVMでのプログラムの実行では、スレッドAの書き込みの伝播が、スレッドBの読み取り後に発生するように並べ替えられた可能性があります。

実際、スレッドAは変数xに書き込み、次に変数に書き込み、スレッドAy内のこれら2つのアクション間に発生前の関係を確立できます。ただし、スレッドBは読み取りxを行う可能性があり、Bがbeforeyの新しい値を取得することは合法です。の新しい値が表示されます。仕様によると：y x

より具体的には、2つのアクションが発生前の関係を共有する場合、それらが発生前の関係を共有しないコードに対して、必ずしもその順序で発生したように見える必要はありません。

これをどのように修正しますか？通常のフィールドアクセスの場合、volatileキーワードで十分です。

揮発性変数への書き込み（§8.3.1.4）vは同期します-任意のスレッドによるvの後続のすべての読み取り（後続は同期順序に従って定義されます）。

synchronizes-withは、happens-beforeよりも強力な条件であり、occurs-beforeは推移的であるため、スレッドAがスレッドBにとへの書き込みを確認させたい場合は、xとを書き込んだ後yに揮発性変数に書き込む必要があります。スレッドBは、読み取る前にから読み取る必要があり、との新しい値が表示されることが保証されます。zxyzxyxy

Gabrielのソリューションでは、次のパターンが見られます。書き込みが発生しin、他のスレッドには表示されませんが、書き込みが発生するため、他のスレッドは、最初turnに読み取る限り、両方の書き込みを確認することが保証されます。turn

残念ながら、whileループの条件は逆方向です。スレッドがの古いデータを認識しないことを保証するために、whileループは最初inから読み取る必要があります。turn

    // ...
    while (turn == other() && in[other()]) {
        // ...

この修正を念頭に置いて、残りのソリューションのほとんどは問題ありません。クリティカルセクションでは、データの古さは気にしません。クリティカルセクションにいるからです。他の唯一の欠陥は最後にあります：Runnableはin[id]新しい値に設定されて終了します。他のスレッドはの新しい値を確認することが保証されますin[id]か？仕様はノーと言っています：

スレッドT1の最後のアクションは、T1が終了したことを検出する別のスレッドT2のアクションと同期します。T2は、T1.isAlive（）またはT1.join（）を呼び出すことでこれを実現できます。

では、どうすれば修正できますか？turnメソッドの最後に別の書き込みを追加するだけです。

    // ...
    in[id] = false;
    turn = other();
}
// ...

whileループを並べ替えたので、他のスレッドはの新しいfalse値を確認することが保証されます。in[id]これは、書き込みがin[id]発生する前、書き込みがturn発生する前、読み取り元がturn発生する前、読み取り元が発生するためin[id]です。

言うまでもなく、大量のコメントがなければ、この方法は脆弱であり、誰かがやって来て何かを変更し、微妙に正確さを損なう可能性があります。配列を宣言するだけvolatileでは十分ではありません。このスレッドでBillPugh（Javaメモリモデルの主任研究者の1人）が説明しているように、配列を宣言すると、配列参照volatileの更新が他のスレッドに表示されます。配列要素への更新は必ずしも表示されません（したがって、配列要素へのアクセスを保護するために別の変数を使用してジャンプする必要があったすべてのループ）。volatile

コードを明確かつ簡潔にしたい場合は、そのままにしてAtomicIntegerArrayinに変更します（falseの場合は0、trueの場合は1を使用します。AtomicBooleanArrayはありません）。このクラスは、要素がすべてである配列のように機能するため、すべての問題をうまく解決します。または、ブール配列を使用する代わりに、2つの揮発性変数とを宣言して更新することもできます。volatileboolean in0boolean in1

于 2010-05-26T20:21:41.900 に答える
5

Peterson のアゴリズム (Java のような高水準言語で作業する場合は奇妙なことです) が特に必要でない限り、言語に組み込まれている同期機能を調べてみることをお勧めします。

たとえば、Java での「Race Conditions and Mutual Exclusion」に関するこの本の章が役に立つかもしれません: http://java.sun.com/developer/Books/performance2/chap3.pdf

特に：

Java は、条件の概念を介して、この「状態の変更」を待機する組み込みサポートを提供します。ただし、条件が実際に発生したかどうかは完全にユーザー次第であるため、条件は少し誤った名称です。さらに、条件は具体的に true または false である必要はありません。条件を使用するには、Object クラスの 3 つの主要なメソッドに慣れる必要があります。

• wait(): このメソッドは、条件を待機するために使用されます。特定の (共有) オブジェクトのロックが現在保持されているときに呼び出されます。

• notify(): このメソッドは、条件が (おそらく) 変更されたことを単一のスレッドに通知するために使用されます。繰り返しますが、このメソッドは、特定のオブジェクトに対して現在ロックが保持されているときに呼び出されます。この呼び出しの結果として、単一のスレッドのみを起こすことができます。

• notifyAll(): このメソッドは、条件が (おそらく) 変更されたことを複数のスレッドに通知するために使用されます。このメソッドが呼び出された時点で実行中のすべてのスレッドに通知されます。

于 2010-05-26T10:23:31.273 に答える
4

自分でウェブ上で見つけることができなかったので、書いてみることにしました：


public class Peterson implements Runnable {

    private static boolean[] in = { false, false };
    private static volatile int turn = -1;

    public static void main(String[] args) {
        new Thread(new Peterson(0), "Thread - 0").start();
        new Thread(new Peterson(1), "Thread - 1").start();
    }

    private final int id;

    public Peterson(int i) {
        id = i;
    }

    private int other() {
        return id == 0 ? 1 : 0;
    }

    @Override
    public void run() {
        in[id] = true;
        turn = other();
        while (in[other()] && turn == other()) {
            System.out.println("[" + id + "] - Waiting...");
        }
        System.out.println("[" + id + "] - Working ("
                + ((!in[other()]) ? "other done" : "my turn") + ")");
        in[id] = false;
    }
}

お気軽にコメントしてください。

于 2010-05-26T10:10:45.183 に答える
3

本 The Art of Multiprocessor Programming を実際にチェックする必要があります。彼は、さまざまなロックの実装 (スピンとブロッキングの両方) について詳しく説明しています。彼はまた、他のさまざまなタイプの並行アルゴリズム (スキップ リストなど) についても説明しています。ピーターソン ロック アルゴリズムに関する彼の本からの抜粋を次に示します。

Class Peterson implements Lock{
   private final boolean []flag = new boolean[2];
   private volatile int victim;

   public void lock(){
        int i = ThreadID.get(); // ThreadID is a ThreadLocal field
        int j= 1 - i;
        flag[i] = true;    // I'm Interested
        victim = i;        // You go first
        while(flag[j] && victim == i){}; //wait
   }
   public void unlock(){
       int i = ThreadID.get();
       flag[i] = false;      //Not interested anymore
   }
 }
于 2010-05-26T13:39:17.417 に答える
0

Paterson アルゴではありませんが、AtomicBoolean クラスと Atomic* クラスは、ロックレスのビジー ループのアプローチを使用して共有データを更新します。それらはあなたの要件に合うかもしれません。

于 2010-05-26T21:07:59.553 に答える