Lock-freeデータ構造で使用されるABA避けカウンタについて - Togetter

トップ > IT・Web > プログラミング > Lock-freeデータ構造で使用されるABA..

2011/11/05 21:58:56
IT・Web プログラミング concurrent lockfree +

Lock-freeデータ構造で使用されるABA避けカウンタについて

Lock-freeなデータ構造などにおいて「ABA問題」を避けるためによく用いられるカウンタの安全性についてまとめました。
by yamasa

8 fav 1112 view

Fav

まとめ

メニューを開く

boost.atomicは64bit幅の時に上位16bitにカウンタを埋め込むっていうのが賛否あるみたいだけれど、反対意見の人はそのbit数まで必要なメモリを使うんでしょうか。48ビットあれば262テラバイトまで行けるはず…。

返信する RTするふぁぼる

kumagi 2011/11/04 22:48:06
@kumagi 私はカウンタが16bitである点が気になりますね。たとえば3000クロックに1の割合でカウントアップされると仮定すると、16bitカウンタが一周するのに196Mサイクル、2GHzのCPUだと100ms弱です。

返信する RTするふぁぼる

yamasa 2011/11/05 00:13:25
@kumagi 高ロードアベレージ状況なら、コンテキストスイッチしてる間にカウンタが一周してしまっていてもおかしくないわけで、どうも私は気に入りませんね。

返信する RTするふぁぼる

yamasa 2011/11/05 00:15:07
@yamasa 100msに一巡するにしてもカウンタごとABAる確率ってやっぱり天文学的でしょうしそれが嫌ならハザードポインタなどなどで回避したほうが…

返信する RTするふぁぼる

kumagi 2011/11/05 00:15:29
@kumagi カウンタが一巡してしまう時間が十分ありえるほど短ければ、ABAになる確率はずっと高くなりますよ。

返信する RTするふぁぼる

yamasa 2011/11/05 00:18:55
@kumagi まあ、私はカウンタ付ポインタが嫌いでハザードポインタ萌えなので、そっちを使ったほうが良いというのには大賛成ですｗ

返信する RTするふぁぼる

yamasa 2011/11/05 00:20:54
@yamasa 時間は相対的なもので、カウンタの一巡に4億カウント必要だろうとすごく速いCPUなら100msで済んでしまうこともあり得るわけで、bit幅と実時間を指標にするとあまりあてにならないかもと思うのです。で、数学的に算出するなら充分天文学的だろうな、と…。

返信する RTするふぁぼる

kumagi 2011/11/05 00:32:10
@yamasa はい、ハザードポインタ未だ一度もまともな実装作ったことないですがいずれ呼吸のように実装したいです。

返信する RTするふぁぼる

kumagi 2011/11/05 00:32:36
@kumagi いやいや、「実際のマシン上で一巡してしまう可能性があるか」は重要ですよ。4億カウントが100msで一巡してしまうようなCPUなら32bitですら不足してるわけだから64bit必要だ、みたいな感じです。

返信する RTするふぁぼる

yamasa 2011/11/05 00:39:57
@kumagi 実際にカウンタが一巡して同じ値になってしまう確率はいろいろ仮定が必要なので簡単には求まりませんが、単純に65536分の1としても十分大きな値だと思いますが。

返信する RTするふぁぼる

yamasa 2011/11/05 00:43:50
@yamasa うーん、65536分の1よりは遥かに低そうに思うのです。起こりうるスケジュールを全て列挙した場合、事故るパターンの少なさは凄まじくピンポイントな気がします。

返信する RTするふぁぼる

kumagi 2011/11/05 00:50:16
@yamasa これは納得しました。OSのプリエンプションは割と実時間的ですしねぃ…。

返信する RTするふぁぼる

kumagi 2011/11/05 00:50:53
@kumagi CASの直前でコンテキストスイッチが発生したとしましょう。コンテキストスイッチから戻ってきたときにカウンタの値がどれだけ進んでいるかは、コンテキストスイッチからの復帰時間の確率分布とカウンタの増加ペースから概算できます。

返信する RTするふぁぼる

yamasa 2011/11/05 00:57:47
@kumagi 復帰時間の確率分布はとりあえず今回は0ms～300msの一様分布としてみましょう。で、カウンタは100msで一周するペースだと仮定します。そうすると、一回のコンテキストスイッチの間に最大３周してしまう可能性があるわけですね。

返信する RTするふぁぼる

yamasa 2011/11/05 01:01:50
@kumagi で、このような仮定をした場合は復帰時のカウンタ値はどの値でも一様の確率になりますから、65536分の1ってことになります。まあ、最初の一様分布って仮定はちょっと無理がありますが、それでも天文学的っていうほど低い確率にはならないと思いますよ。

返信する RTするふぁぼる

yamasa 2011/11/05 01:04:59
@kumagi 数時間から数日間ぶん回して1回起きるか起きないかってくらいの確率でも、用途によっては十分危険と言えるでしょう。

返信する RTするふぁぼる

yamasa 2011/11/05 01:07:27
@yamasa うーん、300msでカウンタが一周するという感触がちょっと無いです。そんなに早く周りますかねぃ…？だとすると確かに危なそうな気がします。

返信する RTするふぁぼる

kumagi 2011/11/05 01:38:47
@yamasa 一週間ぶん回して落ちるのなら充分欠陥と呼べると思います。

返信する RTするふぁぼる

kumagi 2011/11/05 01:39:10
@kumagi 単純な掛け算の問題ですよ。 http://t.co/kiI2X4ZA 3000クロックに1回ってのはちょっと高頻度すぎる見積もりですが、3万クロックに1回でも1秒弱です。2GHzのCPUってのはそのくらい速いんですよ。

返信する RTするふぁぼる

yamasa 2011/11/05 11:52:49
@yamasa OSがフェアなスケジューリングをしてる前提で考えると、200msよりはずっと細かい頻度でコンテキストスイッチが為されるはずですが、それで200msに1回しか自分に廻ってこないとなると結構な数のスレッドですね。スイッチの粒度によっては少なくてもいいのか…。

返信する RTするふぁぼる

kumagi 2011/11/05 12:04:24
@kumagi スケジューリングの単位はちょっと前まで10ms単位ってのが多かったですね。そのときロードアベレージ20なら、200ms戻ってきません。

返信する RTするふぁぼる

yamasa 2011/11/05 12:10:40
@kumagi まあ、ここら辺の議論はよく紛糾するもんですよ。16bitのカウンタってのは相当悲観的な見積もりをしたときに１周するかもしれないぎりぎりのラインですから。16bitでも大丈夫だという人も結構居ます。

返信する RTするふぁぼる

yamasa 2011/11/05 12:12:59
Content from Twitter

Fav

あわせて読みたい

powered by Preferred Infrastructure

コメント

みんなのおすすめ商品

商品を編集

おすすめ商品を登録する

設定を変更する

ページのトップに戻る

まとめを作成する

プロフィール

フォローする

yamasa

まだ自己紹介が設定されていません。

yamasa twitter rss

新着のまとめ

もっと見る

最近追加された商品

	巨人の星コンプリートBOX Vol.2 [DVD]
	新巨人の星全6巻完結(文庫版) [マーケットプレイスコミックセット]
	現代に生きる大山振り飛車
	日本の著作権はなぜこんなに厳しいのか
	『断腸亭日乗』を読む (岩波現代文庫)

もっと見る

もっと見る

もっと見る