@kumagi STM はわかりやすく obstruction-free ですよねっていうのはあって、それ以外なんですよ!
2010-10-11 08:27:03TM以外でObstruction-freeって有るのかな。Obstruction-freeって言葉そのものがTMのために作られたような事態で…。
2010-10-11 08:34:50lock-free も CAS な例しか全然ない現実をぶち殺すマンが必要だ。ぶち殺すマンがんばれ!がんばれがんばれ!がんばれがんばれフトシ!ガンバレガンバレフトシ!
2010-10-11 07:08:42@lyrical_logical おっと、Fetch and Addです。Atomicな足し算命令です。fifoやpriority-queueなんかはそれを使ってのCAS無しlockfreeがあったはずです。
2010-10-11 08:29:34yamasa さんが大分前に言っていた lock-free も wait-free もおんなじじゃね?発言の気持ちがちょっと分かってきた気がするけど絶対気のせいだ…いつものパターンだ
2010-10-11 05:24:21wait-free にできるのは、どういう操作が atomic に提供されてるか次第だけど、atomic な操作とか全然ないし、atomic な操作だけですむアルゴリズムなんて全然ないし、なら wait-free について考えたりせず lock-free だけでよくね?という考え
2010-10-11 06:28:55@lyrical_logical ガタンッ!wait-freeはn個のスレッドでn-コンセンサスが取れる手段があれば実現可能です。単純な話だと調停者を用意して各スレッドに整理券を配ってやればwait-freeには成り得ます。でもパフォーマンスはあまり期待出来ません!
2010-10-11 08:07:30@kumagi そういうのも wait-free って言えるのかー、なるほどですね。何かでもそれってロック取るの厭だからタスクキューに突っ込んでタスクは逐次的に処理しようっていうのと近くて、何かこう個人的にはうんにゃらですね。
2010-10-11 08:19:33結局ロックしたくないかアトミックな操作に置き換えしたくない(できない)ときに、一部分だけを何か他所になげて、そっちはそっちでやってもらうっていうのは、確かに wait-free だけど投げた子は結局…みたいなのがあるというか。多分その子は wait-free にはできなくて悲しい
2010-10-11 08:23:51@lyrical_logical 操作に必要なステップ数の上限を規定する事が目的ですので、部分的にwait-freeにしたのに操作完了に必要なステップ数が不定なままだと設計ミスだと思います
2010-10-11 08:28:27@kumagi ようは、wait-free にできない一部分を、逐次的もしくは n まで並列に処理する人に押し付けて、無限 wait 祭が回避できてヤッタゼっていうことだと理解しているんですが、ボクはそういうの書いたことないんで本当に嬉しいのかなあ?という気持ちになってる訳ですね
2010-10-11 08:37:59@lyrical_logical http://gist.github.com/489195 に一回まとめた文があります。押し付ける、というのがよく分かってないのでもう少し教えて貰えますか?
2010-10-11 08:43:22@lyrical_logical んー…「lock-freeからスタベーションが無くなったもの」がwait-freeなので、このgistに書かれている方法でスタベーションが回避できるのなら立派なwait-freeです。
2010-10-11 09:13:02@kumagi それが wait-free であるというところには納得できるんですが、しかし現実にはこのうさんくさい操作は何かしらの制限があるはずですよねえっていうところに引っかかりを感じているわけです。
2010-10-11 09:16:07@lyrical_logical aが終わったあとでもBBBの処理内容が無駄にならずbを実行出来る状況というのが想像しにくくて、それはひょっとして完全にデータ並列性がある場面だったりしませんか。
2010-10-11 09:21:55@kumagi うーんそういうレアな状況があるという話だと思っていたんですが、そうでないとすると結局ボクがよく分かってないということになりますね…
2010-10-11 09:26:16@lyrical_logical 僕はまだ初歩をかじっただけですので、そういうレアな状況がありうるかもしれませんが、僕の少ない脳みそではその状況をインスタンス化出来ないんです…orz
2010-10-11 09:30:35@kumagi 結局 A さんと B さんをロックもウェイトもなしに直列にするっていうのは結局アトミックに提供されてる操作で解決できる形に問題を置き換える以外にないし、そういうことかなーと勝手に思ったんですが、実際の例を全く知らないので、あってるのかよくわからんという感じです…
2010-10-11 09:34:25