Binary 2.0カンファレンス2006

発表資料が公開されている。http://0xcc.net/blog/archives/000151.html

はげしくもえる。実は登録していたのだが、プロジェクト会議で10時まで拘束されていて、にっちもさっちもいかづ、参加できなかった。(ごめんなさい)

自分的には、マルチコア時代の並列プログラミング：ロックとメモリオーダリング - 中村実(id:nminoru)に強烈にインスパイアされていて、早速いくつかのブックマークをして、関連論文を印刷＆読書した。

やっぱlock-freeだよな。wait-freeだよなあと強く思うのだけど、実は、どのような時に使えばいいのかよく判っていない。

たしかにCAS(compare-and-swap)でlock-freeで同期をとったとして、同期がとれない場合、ループで同期がとれるまで繰りかえすのなら、spin-loopとあんまりかわらないのじゃないかなあとか素人考えで思うのだけど、どーなんだろう。

某オープンソースRDBMSは激しくスケーラビリティがなくて、pthread_mutex_trylockなんかを多発していて、そこにロックの競合(コンテンション)があるので、そいつを削減したかったりするのだが、一つの戦略としてlock-freeアルゴリズムへのコンバートというのはあるかもしれないと思い、週末いろいろ考えを巡らしたのだが、知恵熱が出てしまい、昼寝をしてしまった。(難しい事を考える時は昼寝をするに限る)

でもって、われわれはロック競合の確率とロック競合コストの積を最小化したい。

ロック競合の確率は、ロックする物を小さくして、競合を減らすというのが、王道中の王道である。例えば、ファイルよりもページ、ページよりもレコード、レコードよりも属性みたいな感じで対象を小さくできないか考える。通常、ロック対象が小さい方が、ロック競合する確率は下るがロック管理のオーバヘッド(記憶域の増加などなど)が増加する。

ロックの競合のコストは、1)ロック取得のコスト、2)ロック取得してからロックを解放するまでの時間がある。

ロック取得のコストはおそらくspin-loopが一番安いと思うが、spin-loopしている間、同一CPU上の他のスレッドが全く動けないので影響が最も大きい。pthreadライブラリなどを利用すると、ロックを取得できない時はOSの制御にうつるので、他のスレッドが何か別の仕事をできるのであれば、効率は良くなる。pthreadライブラリを呼ぶオーバヘッドと、ロックを取得できなかった時OSに制御がうつるのでコンテキストスイッチのオーバーヘッドがどうしてもかかる。

さてlook-freeの同期アルゴリズムはどうだろうか？

というところで昼寝をした。