ハザードポインタ版Lock-Free List

programming multithreading

前回の記事で時間切れのために書ききれなかった Lock-Free List について、サンプルコードをgithubに上げました。
GitHub - yamasa/lockfree: Experimental implementations of lock-free algorithms, using hazard pointers and tagged pointers.
sortedlistmap.h がそれです。わかりやすくするため、Allocator対応などの細かい機能については省いています。決して手抜きではありません。;-)
Lock-Free List のアルゴリズムについてはkumagiさんの解説記事が非常にわかりやすいので、そちらをご覧ください。

lock-freeアルゴリズムにおけるメモリ回収

programming multithreading

これは C++ advent calendar の参加記事です。
もともとは「マルチコア時代のLock-free入門」の補遺として書くつもりだったのが、何だかんだで一年近くほったらかしになってしまっていたので、今回 advent calendar という締切りを課すことでようやく書くことができました。(笑)
前の発表で、lock-freeアルゴリズムを C++ で実装するには「タグ付きポインタ」や「Hazard pointer」を使いましょうと言いましたが、具体的な実装コードについてはあまり触れませんでした。そこで、実際に「タグ付きポインタ」と「Hazard pointer」を使い、代表的なlock-freeアルゴリズムである Lock-Free Queue を実装してみました。
GitHub - yamasa/lockfree: Experimental implementations of lock-free algorithms, using hazard pointers and tagged pointers.
タグ付きポインタ版(queue_tagged.h)のほうはC++03とgcc拡張の範囲で実装していますが、Hazard pointer版(queue_hazard.h)のほうはC++0xの機能をバリバリに使っているので、おそらくgcc4.6でしかコンパイルできないと思います。ちょっと調子にのってしまいました。(笑)

「タグ付きポインタ」と「Hazard pointer」の違い

さて、今回実装したタグ付きポインタ版とHazard pointer版のそれぞれの Lock-Free Queue には、単にC++0x対応の有無だけではない大きな違いがあります。それはキューの要素として扱える型の制限です。
タグ付きポインタ版では、キューの要素は trivially copyable な型でなければなりません。 trivially copyable を簡単に説明すると、memcpy相当の操作だけでコピーできてデストラクタでは何も行なわないような型のことです。詳しくはC++0x仕様書やこちらの記事などを参照してください。
何故 trivially copyable でなければならないかというと、タグ付きポインタ版のほうの dequeue 操作では、valueを読み出そうとしてるNodeが他スレッドによって回収・再利用されたのを「検知」することはできても、回収そのものを「保留させる」ことはできないからです。よって、「data race覚悟でvalueをコピーし、直後のCASで失敗したらやり直す」という手段を取らざるを得ません。そのため、非 trivially copyable なクラスだと、他スレッドが書き換え途中の状態を見てしまい、不正なアドレスにアクセスしてしまったりする事故が起きてしまう可能性があるのです。
一方のHazard pointer版では、 dequeue 操作でのNodeの回収・再利用を「保留させる」ことができます。そのため、同時に複数のスレッドがキューの要素へアクセスすることは無いことが保証できるので、ムーブ代入なども自由に利用することが可能になるのです。
このように、同じようなlock-freeアルゴリズムであっても、メモリ回収に用いる手法の違いによって性質が大きく変わってしまうことがあるのです。

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

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 のような感じになりました。

今ココなう！ iPhone用Webアプリのソースコードを公開

programming webapps

私の作成した今ココなう！のiPhone用Webアプリについて、そのソースコードをgithubにて公開しました。
このWebアプリは、iPhoneだけでなくAndroid2.1以降やFireFox3.5以降、Chrome5やSafari5など、最近のHTML5対応ブラウザでも利用することができます。アプリが利用している技術要素を以下に列挙してみたので、興味のある方の参考になれば幸いです。

マルチコア時代のLock-free入門

programming multithreading

本日、並カンにてLock-freeアルゴリズムについて発表しました。発表資料は以下になります。
なお、今回の発表で割愛したメモリバリアの詳細については、以下の発表資料を参照ください。

また、Hazard pointerやタグ付きポインタを使用したサンプルコードを以下に置いています。こちらも参考にどうぞ。

C++0x時代の Double-Checked Locking

programming multithreading

今回は "Double-Checked Locking" (以下DCL)というマルチスレッドプログラム向けのイディオムを例にして、C++0xの(低レイヤ向け)マルチスレッド機能の利用方法を紹介してみます。
DCLとは、「ロック→条件判定」というロジックを「条件判定→ロック→(再度)条件判定」と書き換えるイディオムで、主に遅延初期化などの処理においてロックのオーバーヘッドを減らすために用いられます。DCLはシンプルかつ効果の高いイディオムだったので、一時期もてはやされました。ところが、DCLはコンパイラやCPUによるリオーダーの影響により正しく動作しない場合があることがわかったため(参考1、参考2)、今ではアンチパターンと呼ばれることすらある始末です。
しかし、DCLの問題点は、メモリモデルに関する知識があまり知られていなかったことと、プログラミング言語の仕様でメモリモデルが正しく定義されていなかったことにあり、DCLというイディオムそのものは正当なものです。そして、atomic変数とメモリバリアがきちんと定義されている C++0x では、DCLを正しく実装することが可能になったのです。
ではさっそく、「正しい」DCLの実装例を挙げてみましょう。

std::atomic p(nullptr);
std::mutex m;

Hoge& getInstance() {
  Hoge* tmp = p;
  if (tmp == nullptr) {
    std::lock_guard lk(m);
    tmp = p;
    if (tmp == nullptr) {
      tmp = new Hoge();
      p = tmp;
    }
  }
  return *tmp;
}

std::mutex や std::lock_guard は C++0x で追加されたロックを行うためのAPIです。上のコードだと「"std::lock_guard lk(m);" の行で排他ロックを行い、変数lkのスコープの終わり(つまりreturn文の前の行)でアンロックする」という意味になります。DCLの特徴である「条件判定→ロック→(再度)条件判定」という実装になっていることがわかるでしょうか。
このDCL実装の肝は、変数 p がatomic型として宣言されている点です。 C++0x のatomic型は、これまで繰り返し説明してきたように、操作がアトミック(不可分)に行われるだけでなく、メモリアクセスの順序付けを保証する効果(メモリバリア)も持っています。変数 p への読み書きの際にメモリバリア効果が発揮されるため、最初に挙げた「DCLの問題点」を解消できているのです。

続きを読む

C++0xのメモリバリアをより深く解説してみる

programming multithreading

もはや誰得レベルになりつつありますが、今回もメモリバリアについての話です。以前の話の続きになるので、まだの方は初回と前回のエントリを先にどうぞ。
さて、まず最初に、C++0xのatomicクラスを使った「正しく同期化されているコード」の例を挙げてみます。

struct Hoge {
   int  foo;
};

// 初期値
std::atomic p(nullptr);

// Thread 1
Hoge* r1 = new Hoge();
r1->foo = 42;
p.store(r1, std::memory_order_release);

// Thread 2
Hoge* r2;
do {
  r2 = p.load(std::memory_order_acquire);
} while (r2 == nullptr);
std::cout << r2->foo;   // 42が出力されることが保証される

Hogeインスタンスのメンバ変数 foo への読み書きに注目すると、アトミック変数 p を介して以下のような順序付けが成立しています。releaseやacquireメモリバリアの意味については初回の記事を参照してください。

r1->foo = 42
  ↓  releaseメモリバリアによる順序付け
p.store(r1, std::memory_order_release)
  ↓
r2 = p.load(std::memory_order_acquire)
  ↓  acquireメモリバリアによる順序付け
r2->foo

このような順序付けが成立している状態を「メンバ変数 foo へのアクセスが正しく同期化されている」と呼び、その結果、 r2->foo の値が42になることが保証されるのです。
では、次のコードはどうでしょうか?

// 初期値
std::atomic p(nullptr);

// Thread 1
Hoge* r1 = new Hoge();
r1->foo = 42;
p.store(r1, std::memory_order_release);

// Thread 2
Hoge* r2;
do {
  r2 = p.load(std::memory_order_relaxed);
} while (r2 == nullptr);
std::cout << r2->foo;   // Data race?

最初のコードとの違いは、Thread 2 側のメモリバリア指定が memory_order_relaxed (メモリバリア無し) に変わっている点です。つまり、先ほどの図で示した「acquireメモリバリアによる順序付け」が無くなっています。その結果、このコードはメンバ変数 foo への読み書きが正しく順序付けられていない、すなわち「正しく同期化されていない」不正なコードということになります。
でも、本当にこのコードは正しく動作しないのでしょうか? Thread 2において、式 r2->foo を評価するには、当然ながら r2 の値がわかっている必要があります。よって、明示的にacquireバリアを指定しなくても、 r2->foo の実行は p.load(...) より前にリオーダーされることはないと考えてよさそうです。従って、「r2->foo の結果は必ず 42 になる」と言い切ってもよさそうな気がします。
しかし、残念ながら一部のプロセッサではそうならないことが知られています(参考文献)。メモリバリアはキャッシュコヒーレンシの動作にも影響を与えているので、メモリバリアが無いとキャッシュメモリ内の古い値を読み込んでしまう可能性があるのです。そのため、acquireメモリバリアを省略した2つめのコードは、やはり正しく同期化されておらず不正だということになります。

続きを読む