Peterson のアルゴリズム

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

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

例 9-6 2 つのスレッド間での相互排他が成立するか

void mut_excl(int me /* 0 または 1 */) {
    static int loser;
    static int interested[2] = {0, 0};
    int other; /* 局所変数 */
   
    other = 1 - me;
    interested[me] = 1;
    loser = me;
    while (loser == me && interested[other]);

    /* 危険領域 */
    interested[me] = 0;
}

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

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

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

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

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

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

この問題は、スレッドの同期プリミティブを使用すると回避できます。それらのプリミティブには、ストアバッファをキャッシュに強制的にフラッシュする特別な命令が含まれているからです。