Hatena::ブログ(Diary)

くまメモ このページをアンテナに追加 RSSフィード Twitter

2010-12-22

lock-free stackと並行アルゴリズムの区分

23:32 |

この記事は

カーネルVM Advent Calendar http://atnd.org/events/10701

のために書かれました。

これまで複数回に渡ってlock-freeデータ構造を紹介して来ましたが

そもそもの前提を話していなかったり目的も不明だったりと不備だった点があったので

根元から一度おさらいしてみたいと思います。


まずロックを用いる事の欠点から

f:id:kumagi:20101222205026j:image

上図のような構図でロックによる相互排他を行うと様々な問題が発生します。

具体的に言うと排他に成功したスレッドに様々な災難が降りかかります。

主な事例として

f:id:kumagi:20101222205550j:image

↑ロック確保できたのにOSによってプリエンプションされる。

f:id:kumagi:20101222210035j:image

↑物理メモリに乗ってない仮想メモリにアクセスしてしまった。

f:id:kumagi:20101222210633j:image

↑キャッシュミスヒットによるメモリ待ち。

そんなに気にするほどのパフォーマンス低下ではないと思うかも知れませんが

マルチコアの方向へ舵を切った新世代CPUを使いこなすに当たっては重大なスループット低下を招きます。



ロック内のスレッドが無駄にした1クロックは

ロック外のすべてのスレッドにとっての1クロックでもあるのです。



至高のパフォーマンスを目指す近代のアルゴリズマー達はこの問題を決して野放しにはしませんでした。

その対策の一部がこれから紹介するnon-blockingデータ構造の数々です。

brbr 2010/12/23 02:10 ABA問題 - Wikipedia
http://ja.wikipedia.org/wiki/ABA%E5%95%8F%E9%A1%8C

hiraku_wfshiraku_wfs 2010/12/24 00:58 __sync_bool_compare_and_swap(*top, oldtop, newnode)
の1つ目の引数は *top じゃなくて top じゃないかと思ったのですがどうでしょうか?
間違っていたらすいません。。。

kumagikumagi 2010/12/24 02:24 >hiraku_wfsさん
…本当だ!おっしゃるとおりです。
第一引数に書き換え対象のポインタを入れるので、ポインタのポインタそのものは永久に書き換わらないはずです!
修正します。ありがとうございます。

bsdhousebsdhouse 2010/12/24 14:36 とりあえずコードのところにだけコメントします。

pop()のループ内にて、*top に何度もアクセスしてますが、
これだと途中で *top の値が他スレッドによって書き換えられてしまう可能性がありますよね。
oldtop = *top;
if(oldtop == NULL){return false;}
nexttop = oldtop->next;
のようにすべきでしょう。

あと、pop()のほうの __sync_bool_compare_and_swap の前に ! が抜けているようです。
それと push() で malloc の戻り値をキャストする先は T* じゃなくて node* ですよね。

あとはメモリバリアとかABA問題とかへの対処も必要ですが、これは拙著のブログへのリンクを貼るだけにしておきます。;-)
http://d.hatena.ne.jp/bsdhouse/20100131/1264920091
http://d.hatena.ne.jp/bsdhouse/20090720/1248085754

kumagikumagi 2010/12/27 04:52 >bsdhouseさん
おお!仰る通りです!共有する変数へのアクセスはポイントを抑えなくてはいけませんね。
ケアレスミス申し訳ないです。修正させていただきます。
__sync_bool_compare_and_swapは手元のgcc環境(4.4)ではlock cmpxchgに置換され、lock-prefixのついた機械語はメモリフェンスを使用するためこの限りにおいては手動でメモリバリアを挟む必要はありませんが、より高いパフォーマンスや確実性を求めるには一層配慮を行う必要がありそうです。
ABA問題に対しては以前の記事でも触れましたがまだ何もブログ上では話していませんでした。何か検討して書いてみようと思います。
ありがとうございました。

bsdhousebsdhouse 2010/12/27 23:44 あ、私がメモリバリアで懸念していたところは
__sync_bool_compare_and_swapではなく
oldtop = *top;
nexttop = oldtop->next;
のところです。
いわゆる Data-Dependency Ordering の話になるので、貼り付けるURLも
http://d.hatena.ne.jp/bsdhouse/20090929/1254237835
のほうが適切でしたね。
とはいえ、これは非常に些細な問題ですのであまり気にする必要はないかもしれません。

図解がとても面白い記事でしたので、これからも期待しています!