ピーターソンのアルゴリズムとメモリバリア

programming multithreading


とkumagiさんが言っていたので、ちょっとしたコードを張り付けてみます。

これは wikipedia:ピーターソンのアルゴリズム の実装例で、2つのスレッドが排他制御しながら1つのカウンタをカウントアップしていくというものです。正しく排他制御できているなら、最後に "difference = 0" と出力されるはずです。
しかし実際は、このプログラムにはメモリバリアの記述が不足しているため、マルチコアな環境では "difference = 0" とはなりません。
興味深いのは、変数flag0, flag1, turnのそれぞれを別々のキャッシュラインに置くために __attribute__*1 変数が同じキャッシュラインに置かれているかどうかで動作が変わる、一つの例として紹介してみました。

詰めメモリバリア

ところで、前述のコードはどこにメモリバリアが足りていないのでしょうか? マルチコアでも正しく動作させるために、どのような記述を加えればよいか考えてみてください。
名付けて「詰めメモリバリア」。5分で1級の問題です。:-)

*1:aligned(64))) と指定しているのですが、これを外すとdifferenceの値が激減するのです。((手元のCore 2 Duo機では 4528637 → 26 のような感じになりました。