Peterson のアルゴリズム

例 9–6 のコードは、2 つのスレッド間の相互排他を処理する Peterson のアルゴリズムの実装例です。このコードは、危険領域に同時に複数のスレッドが存在しないことを保証しようとしています。スレッドは、mut_excl() を呼び出すと、「すばやく」危険領域に入ります。

ここで、スレッドは危険領域に入るとすばやく抜け出るものとします。

例 9–6 2 つのスレッド間での相互排他

void mut_excl(int me /* 0 or 1 */) {
    static int loser;
    static int interested[2] = {0, 0};
    int other; /* local variable */
   
    other = 1 - me;
    interested[me] = 1;
    loser = me;
    while (loser == me && interested[other])
        ;

    /* critical section */
    interested[me] = 0;
}

このアルゴリズムは、マルチプロセッサのメモリーが強く順序付けられているときは成立します。

SPARC ベースのマルチプロセッサを含む一部のマルチプロセッサは、ストアバッファーを装備しています。スレッドがストア命令を実行すると、データがストアバッファーに入れられます。このバッファーの内容は最終的にキャッシュに送られますが、すぐに送られるとは限りません。各プロセッサのキャッシュはデータの整合性を維持していますが、変更されたデータはキャッシュにすぐには送られません。

複数のデータが格納されたとき、その変更はキャッシュ (およびメモリー) に正しい順序で伝わりますが、通常は遅延を伴います。SPARC ベースのマルチプロセッサでは、この性質のことを「トータルストア順序 (TSO) をもつ」と言います。

あるプロセッサが A 番地にデータを格納して次に B 番地からデータをロードして、別のプロセッサが B 番地にデータを格納して次に A 番地からデータをロードした場合、「最初のプロセッサが B 番地の新しい値を得る」と「2 番目のプロセッサが A 番地の新しい値を得る」の一方または両方が成立します。しかし、「両方のプロセッサが以前の値を得る」というケースは起こりえないはずです。

さらに、ロードバッファーとストアバッファーの遅延が原因で、上記の起こりえないケースが起こることがあります。

このとき Peterson のアルゴリズムでは、それぞれ別のプロセッサで実行されている 2 つのスレッドが両方とも危険領域に入ります。各スレッドは特定の配列の自分のスロットにデータを格納し、別のスロットからデータをロードします。両方のスレッドは以前の値 (0) を読み取り、相手がいないものと判定し、両方が危険領域に入ってしまいます。この種の問題は、プログラムのテスト段階では発生せず、あとになって発生する可能性があります。

この問題を回避するには、スレッドの同期プリミティブを使用します。それらのプリミティブには、ストアバッファーをキャッシュに強制的にフラッシュする特別な命令が含まれています。第 4 章同期オブジェクトを使ったプログラミングを参照してください。