ロックフリーアルゴリズムについて理解する - 逐次一貫性

逐次一貫性(sequential consitency)とは何か

最初に逐次一貫性の概念についてまず理解しよう

逐次一貫性はコンピュータシステムに関するメモリ一貫性モデルの一つであり、定義をWikipediaから引用すると「どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること」とのことだ。

何のことだかよくわからんが、並列処理中の実行結果が常に逐次的に実行した場合と同等となる、ということのようだ。

例えば下記のようなコードがあるとして

std::atomic<int> X(0), Y(0);
int r1, r2;

void thread1()
{
    X.store(1);
    r1 = Y.load();
}

void thread2()
{
    Y.store(1);
    r2 = X.load();
}

どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく とはXとYの結果が{X,Y} = {0, 1} , {1, 0}, {1, 1} のどれかは起こり得るが{0,0}は論理的に起こり得ないので起こってはならない、ということ

個々のプロセッサの処理順序がプログラムで指定された通りである とは例えばthread1ならばX.store(1)とr1=Y.load()の実行順序が入れ変わらない、ということ

あまりにも当たり前のように感じるが、マルチコア環境では逐次一貫性が満たされないことが多い。

リオーダリング(reordering)

マルチコア環境では必ずしもメモリ操作が順番通りに行われるとは限らない。

例えば以下のような指揮があった場合、

x = A;
y = B;

プロセッサがAとBという値を取得しようとした場合、Aはプロセッサのキャッシュに存在せず、Bがプロセッサのキャッシュに存在した場合には実行結果の取得するタイミングが入れ替わってしまう

もちろんAの結果が返ってくるのを待ってからBの結果を取得しても良いが、待ち時間の分パフォーマンスが劣化するので必ずしも待つのが適切とは言えない

このように状況により命令の実行順序が入れ替わることを リオーダリング(reordering) と言う

x86メモリモデルにおけるリオーダリング

では実環境ではどのようなケースでリオーダリングが起こりがちなのかを見ていこう。

x86メモリモデルでは TSO(total-store order model) を守っている

TSOとは「ロード同士は順序を守る。ストア同士は順序を守り、ストアはロードを追い越さない。」という規則であり、同一プロセッサ内での順序一貫性(processor consistency)は維持されているが、一方でマルチプロセッサに置いては命令の順序が補償されない書き込み直後に読み込み命令を出しても最新のものが取得できるとは限い

下記は以前に示したコードだが、マルチプロセス環境ではX.storeやY.storeがメモリに反映される前にX.loadとY.loadの両方が実行され、r1 = 0, r2 = 0となることがあり得る、よってこのままでは逐次一貫性が無いということになる

std::atomic<int> X(0), Y(0);
int r1, r2;

void thread1()
{
    X.store(1);
    r1 = Y.load();
}

void thread2()
{
    Y.store(1);
    r2 = X.load();
}

メモリバリア

メモリのリオーダリングを避けるための手法としてメモリバリア(メモリフェンス)とわれるメモリ操作の順序性を制限するCPU命令がある。

高レベル言語ではメモリバリアを使って実装される同期プリミティブ(synchronization primitive)を使って同期処理を実装することになる。同期プリミティブはmutexやセマフォなどの並列実行のための仕組みのことである。

まとめ

逐次一貫性とは「どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること」である
マルチプロセス環境ではリオーダリングにより逐次一貫性が保たれないケースが存在する
リオーダリングを防ぐためにメモリバリアを利用する。メモリバリアはCPU命令であり、mutexやセマフォなどの実装に使われている