マルチスレッドとメモリ同期

今回はマルチスレッドプログラミングでの厄介な問題、メモリ同期について。
要するにきちんと排他制御しろという当たり前の話なんだけど、何故きちんと排他制御しないといけないのかまで深く説明してるのはあまり見ない気がします。

例

例えばこんなコードで

bool g_complete = false;
int g_message[100];

void foo(int i)
{
    g_message[i/10] = 42;
    g_complete = true;
}

void bar()
{
   while(!g_complete) {
        // foo() が終わるまで busy loop して待つつもり
    }
    printf("%d\n", g_message[0]);
}

マルチスレッドでワーカースレッドが foo() を呼び、メインスレッドが bar() で仕事が終わるのを待って結果を表示する、ということをやるとします。
ところが、このプログラムは意図した動作をしない可能性があります。

out-of-order 実行

上記のソースを gcc-4.3.2 でコンパイルし、アセンブラコードを見てみます。以下は foo() に相当する部分です。

    movl    8(%ebp), %ecx
    movb    $1, _g_complete            ; g_complete を 1 で更新
    popl    %ebp
    movl    %ecx, %eax
    imull    %edx
    sarl    $31, %ecx
    sarl    $2, %edx
    subl    %ecx, %edx
    movl    $42, _g_message(,%edx,4)    ; g_message を更新
    ret

なんと g_complete　を 1 で更新した後に g_message を更新しています！これではメインスレッドは更新前の g_message を受け取りかねません。
この現象はコンパイラのメモリアクセスの最適化の結果引き起こされるものです。マルチスレッドで動かすという事情を知らないコンパイラは、遠慮無くシングルスレッドで動かす前提の最適化を行ないます。実際、この最適化はシングルスレッドでは有効に働くでしょう。
(＊コンパイラにより結果が大きく変わります。VisualC++ や　gcc-3.4.4, ｇcc-4.5.0 ではソースの順になりました)

さらに、CPU 側でも最適化のために命令の re-order が行われることがあります。この現象はシングル CPU 環境ではうまく遮蔽されていて意識する必要はなくなっていますが、マルチ CPU 環境でマルチスレッドのプログラムを動かしたとき表面化します。この問題に対策できるようにするため、大抵の CPU はメモリバリアと呼ばれるメモリ同期命令を備えています。

対策

コンパイラや CPU が勝手に re-order しないように、適切にメモリバリアを挟む必要があります。
とはいえ、マルチスレッドで一般的に使われる排他制御 (mutex, semaphore, critical section など) はメモリバリアを伴うので、適切に排他制御していればこの問題を気にする必要はありません。
また、WinAPI の Interlock 系関数もメモリバリアを伴います (＊PC の場合は。組み込み系 Windows ではただのアトミック操作になっている場合もあります)。Linux 環境などでは WinAPI の Interlock 系関数相当品が見当たりませんが、gcc に __sync_fetch_and_add() などのメモリバリアを伴なうアトミック操作系 built-in 関数があるので、これで代用可能です (詳細は「参考」のリンク先)。今回の例みたいな場合や、参照カウンタの上げ下げなどには interlock 系関数が適していると思われます。

メモリバリアの効果を確認するため、今回の例をメモリバリアで修正してみます。直接メモリバリアを挟むには WinAPI では MemoryBarrier()、gcc では built-in 関数の __sync_synchronize() を使います。

// 修正版 foo()
void foo(int i)
{
    g_message[i/10] = 42;
    __sync_synchronize(); // メモリバリア
    g_complete = true;
}

問題の gcc でのコンパイル結果

    movl    8(%ebp), %ecx
    movl    %ecx, %eax
    imull    %edx
    sarl    $31, %ecx
    sarl    $2, %edx
    subl    %ecx, %edx
    movl    $42, _g_message(,%edx,4)   ; g_message を更新
    lock orl    $0, (%esp)             ; メモリ同期
    movb    $1, _g_complete            ; g_complete を 1 で更新
    popl    %ebp
    ret

意図した通りになりました。

volatile の神話

「複数スレッドからアクセスされる変数は volatile にしとけば大丈夫」という話を聞くことがあります。
しかし今回の例では、問題を起こす gcc では volatile をつけても変化はありませんでした。MSDN の記事によると、VisualC++ 2003 では、コンパイラによる re-order は抑止できるようですが、CPU の re-order 抑止まではやってくれないようです。VisualC++ 2005 では両方とも解決できるようです。
このように volatile のコンパイラの解釈がばらばらな上、volatile は必要以上にパフォーマンスに悪影響を及ぼすので、この問題の対策に volatile は適切ではありません。

まとめ

複数スレッドからアクセスされる変数は横着せずに排他制御しましょう。シビアに速度を求められる場面とかでは interlock 系関数でなんとかしましょう。がんばって手動でメモリバリア挟む、というのはたぶんすぐに人間の注意力の限界を超えると思うので、interlock 系関数を自分で実装する場合とか以外ではやらない方がいい気がします。

参考

http://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-for-multi-threaded-programming/ Intel の人による「volatile はあてにしちゃダメよ」という話
http://msdn.microsoft.com/en-us/library/ms686355%28v=VS.85%29.aspx マルチプロセッサ環境下でのメモリ同期問題の解説、および WinAPI / VisualC++ での解決策
http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Atomic-Builtins.html gcc の atomic なメモリ操作系ビルトイン関数。
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%90%E3%83%AA%E3%82%A2 wikipedia「メモリバリア」。今回の記事とほとんど同じ内容。書いてる途中で気づいた…。