Lock-Free Algorithm, CriticalSection, IHostCrst - NyaRuRuが地球にいたころ

スレッド化で「普通は」気をつけるべきこと

「高木浩光＠自宅の日記」より．

ギャー、ここも杜撰だった。（モニタリング用のコードとはいえ。）

int connectionTriedCount = 0;
int handshakeSucceededCount = 0;
int extractionSucceededCount = 0;
connectionTriedCount++;
handshakeSucceededCount++;
extractionSucceededCount++;

java.util.concurrent.atomic.AtomicInteger を使ってみよう。

import java.util.concurrent.atomic.AtomicInteger;
...
AtomicInteger connectionTriedCount = new AtomicInteger(0);
AtomicInteger handshakeSucceededCount = new AtomicInteger(0);
AtomicInteger extractionSucceededCount = new AtomicInteger(0);
...
connectionTriedCount.getAndIncrement();
handshakeSucceededCount.getAndIncrement();
extractionSucceededCount.getAndIncrement();

まあいわゆる初心者にありがちだけど，かといっていわゆる上級者にあり得なくはないというか，まあそんなバグですな．でも一言で言えばやっぱり「杜撰」だと思います．
とはいえ私も 17日のエントリは拝見していて，最近の Java に疎いこともあってソースコードの方も流し読みだったのですが，それでもこのバグに気付かなかったのはちょっと反省です．

インテルスレッド・チェッカー

そういえば先日の VSUG イベントで，インテルスレッド・チェッカーを使ってこの手のバグを検出するというデモを拝見しました．
動作環境を見る限り，.NET や Java で使えるか微妙なところです．VTune は .NET 2.0 にも使えるので色々重宝してますけど．

java.util.concurrent

さて，引用文中で java.util.concurrent.atomic.AtomicInteger が紹介されていますが，「java.util.concurrent はイイ」って話がちらほら伝わってくるのと，多分 Microsoft のセンスというか芸風だと concurrent なんてネームスペース作らないような気がするのとで，java.util.concurrent というネームスペースには微妙に憧れがあります．はい．
一方で，Windows NT 3.1 時代から存在し，当然のごとく .NET 1.0 からサポートされたInterlocked API が，Java では JDK 5.0 までサポートされていなかったというのは，少し意外な気もします．

JDK 5.0までは、Java言語でwait-free、lock-freeなアルゴリズムを書くのはネイティブ・コードを使わない限り不可能でした。java.util.concurrentにアトミック変数クラスが追加されたことによって、それが変わるのです。この新しいクラスによって、いかに高度にスケーラブルな非ブロック・アルゴリズムがJavaで開発できるようになったかを、並行性のエキスパートであるBrian Goetzが解説して行きます。

compare-and-swap (CAS) と Lock-free アルゴリズム

Interlocked API，特に compare-and-swap (CAS) と呼ばれる操作が興味深いのは，それが数々の Lock-Free Algorithm の実装で重要な役割を果たすからです．
「Radium Software Development」より．

昨今の多くの CPU には "compare-and-swap" (CAS) と呼ばれる類の命令が用意されている [Wikipedia] 。これは，比較とスワップ（あるいは代入）をアトミック（不可分）に実行するというものであり，次のような擬似コードによって表される（[Michael] より引用）。
CAS(addr, expval, newval) atomically do
  if (*addr == expval) { 
    *addr = newval;
    return true;
  }
  else return false;
この挙動を一言で表せば，「知らぬ間に値が変えられている場合は代入を失敗させる」というようなものになるだろうか。この命令を利用することによって，様々な処理をアトミックに実行することが可能となる。

再度「IBM developerWorks」より．

Lock-freeアルゴリズムとwait-freeアルゴリズム

他のスレッドに任意の遅れが生じても（あるいは失敗が起きても）、どのスレッドも継続して進行する場合には、そのアルゴリズムはwait-free と言われます。対照的にlock-free アルゴリズムでは、一部のスレッドのみが継続して進行すればよいのです。（別の仕方で定義すると、wait-freeでは他のスレッドのアクションやタイミング、インターリーブ、またはスピードによらず、各スレッドはそのスレッドのステップとして指定された数の演算操作を正しく行うことが保証されている、ということです。この指定数は、システム中にあるスレッド数の関数になっている場合があります。例えば10のスレッドがそれぞれCasCounter.increment()操作を一度行うと、最悪の場合、各スレッドは増加操作を完了するまでに最大9回のリトライを行う必要があることになります。）

過去15年の間、wait-freeアルゴリズムとlock-freeアルゴリズムには広範な研究が行われ、数多くの一般的なデータ構造に対して非ブロック・アルゴリズム（nonblocking algorithms ）が発見されています。非ブロック・アルゴリズムは、OSやJVMのレベルで、スレッドやプロセスのスケジューリングなどのタスクに対して広く使われています。非ブロック・アルゴリズムは実装がより複雑ですが、ロック・ベースのアルゴリズムよりも有利な点が幾つかあります。つまりpriority inversionやデッドロックのような危険性が回避され、競合のコストは低くなり、協調はよりキメ細かなレベルで起こるので、より高度な並行処理が実現するのです。

私の興味の範囲内で出会った Lock-Free アルゴリズムというと，「Radium Software Development」で紹介されているようなメモリアロケータか，いわゆるコレクション・クラスが挙げられます．
例えば CLR は GC ヒープからのメモリ確保に Lock-Free アルゴリズムを活用していますし，従来から Windows カーネル内では Interlocked Singly Linked Listsと呼ばれる Lock-Free List が使用されていました．
というわけで，ブックマークやら IRC のログやらに残っている記事も，だいたいその方面に偏っているようです．

XTLog:「IBM developerWorks: Javaのノンブロッキング同期化手法についての解説」: 上の記事を知るきっかけになった記事
Concurrent Programming Without Locks: MS Research な人の論文
Lock Free Data Structures using STM in Haskell: MS Research な人の論文．Haskell．
Implementing a high-perf IAsyncResult: lock-free lazy allocation: 遅延評価による IAsyncResult パターンの高パフォーマンス化
Lock-free data structures: the queue: C# による Lock-Free Queue

Win32 CriticalSection

ちなみに，前述の C# による Lock-Free Queue に触発されて，自分でも C# による Lock-Free なコレクションを作ってみたことがあります．とりあえず動いて一通り満足したところで，普通のコレクションに lock キーワードを使ったものとパフォーマンスを比較してみると，実は全然パフォーマンスが出ていなかったという苦い思い出ですが．
そのときはあんまりまじめにプロファイリングをしたわけではないのですが，実際のところそれほど不思議な現象ではないかな，と思っています(負け惜しみ)．
C# の lock は以前紹介したように (id:NyaRuRu:20060605#p2) System.Threading.Monitor で実装されていて，さらに CLR は Monitor クラスの実装に OS のクリティカルセクションを使用しているため，元々かなり軽量な作りになっていると考えられます．たまに EnterCriticalSection を呼ぶと必ずカーネルモードへの遷移が起きると思っている人がいるみたいですが，スピンカウントを設定することで，高コストなカーネルモードへの遷移の前に，Interlocked API を使用したスピンループで軽量な待機動作を行わせることができます．スピンループのカウント数が設定値に達した場合は，スレッドを待機状態にするべくカーネルモードへ遷移が行われます．(この辺は Advanced Windows でも言及されていたはず)
カーネルモードへの遷移を必要としないのは Lock-Free なコレクションも同じですが，CriticalSectionについてもほとんどスピンループで待機動作が済んでしまうような状況では，できの悪い Lock-Free なコレクションが惨敗してもまあ不思議ではないかなと*1．時間が出来たら CLR のクリティカルセクションがスピンループを使っているか？使っているならどれぐらいのリミット値かを調べてみようかと思います．

IHostCrst

さて，このような調査をどうやって行うかですが，手っ取り早いのは「アンマネージデバッグを有効にする」を選んで，API 呼出しにトレースポイントを仕掛けてみることでしょう．しかし，CLR Hosting API を使用すれば，クリティカルセクションの作成と使用動作そのものを自前で提供することが可能なので，もっとエレガントに行うことができます．
具体的には，Host アプリケーションは，IHostCrst を実装することで，自前のクリティカルセクション実装に置き換えることができます．興味がある方は，この辺のコード(id:NyaRuRu:20060616#p2)を参考に挑戦してみてはいかがでしょうか？

*1:ただ，このとき作ったコードはロックのたびに一時オブジェクトを生成していて，それがパフォーマンスをかなり落としていたような気もしていたり