2006-07-21

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

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

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

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

これ読んでいて思い出しましたが，Windows の Hot-patching について．
以前社本さんに教えていただいたアレです．

あーーーっ。コレだーーーっ！！
＃TechEdで某部屋にいた人には分かるよね？(笑)

Windows Server 2003 SP1 から、プロセスに読み込まれた(メモリ内にある)DLLを置き換えることができるようです。すげ〜〜〜。

でも、きっと、ステートレスなDLLじゃないとダメだよね。

どういう風に実装されているかについては，社本さんが紹介されているリンク先にあるのですが，要するに DLL のエクスポート関数の先頭を jmp 命令で書き換えてしまうという，古典的な方法の模様．

Hotpatching

Hotpatching, also known as “in-memory patching,” is designed to reduce server downtime when you install updates onto computers that are running 32-bit versions of Windows Server 2003 with Service Pack 1 (SP1). The goal is to enable the installation of software updates without having to restart your servers.

If a file is in use when you install a software update, it usually cannot be replaced with the new version until the computer restarts. Hotpatching, however, allows for the automatic insertion of code from a simple software update into a running process. This means that system files can be updated while they are in use.

When a file is hotpatched, the new version of a function from the software update is loaded into memory, and a single line of code in the original function is changed to branch to the new version. After the jump to the new function is injected, each subsequent execution of the function points to the new version. (The next figure illustrates this process.) Applications that are in the middle of a call to the function before the software update was applied are allowed to terminate normally.

Hotpatching is complemented by the usual software update process in which the file on disk is replaced, allowing future spawns of the affected process to contain the software update. Hotpatching is possible only for software updates that provide isolated fixes for individual functions; it is not compatible with software updates that update several interdependent functions. The Knowledge Base article that describes a particular software update will clearly indicate that it is compatible with hotpatching if this is the case.

Figure 4 - Hotpatching overview

これを実現するには DLL のエクスポート関数の先頭が 2 byte 命令でないと厄介なため，コンパイラレベルで考慮してあげる必要があって，実際最近の Visual C++ にはこんなオプションが追加されています．
/hotpatch (Create Hotpatchable Image)
もうちょっと調べてみると，Windows x64 環境についておもしろい話が見つかりました．
「FreiK's WebLog」より．
発端はx64 ABI vs. x86 ABI (aka Calling Conventions for AMD64 & EM64T)という記事のコメント欄．
そこから派生して，この記事です．

What if I don't want hot-patchability

Honestly, I don't think there's anything that prevents you from breaking these particular rules, except the cost is so minimal, there's really just no good reason not to do it. X86 has something like a 30% hot-patchable kernel. And x64 has a 100% hot-patchable kernel. You tell me which one is better.

このように，x64 kernel は 100% hot-patchable とのこと．一方で x64 kernel はこのようなカーネルパッチ対策も盛り込まれており，hot-patchable kernel が第三者にとって有利に働くとは限らないようです．
Kernel Patch Protection
んで，Vista はどうなのというとこの辺に話が載っていて，hot-patch テクノロジは Vista SP1 からサポートと書かれていますね．
また，hot-patch が適用できないモジュールにどんなものがあるかについても触れられています．
http://www.msblog.org/?p=433

NyaRuRuが地球にいたころ

Lock-Free Algorithm, CriticalSection, IHostCrst

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

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

java.util.concurrent

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

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

Win32 CriticalSection

IHostCrst

Hot-patching

Hotpatching

What if I don't want hot-patchability

.NET＆Windows Vistaへ広がるDirectXの世界〜第2回 DirectXマスターを目指すあなたが持つべき視点

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

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

java.util.concurrent

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

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

Win32 CriticalSection

IHostCrst

Hotpatching

What if I don't want hot-patchability

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