マルチスレッドプログラミング相談室 その8

1 名前：デフォルトの名無しさん mailto:sage [2009/09/21(月) 17:19:27 ] マルチスレッドプログラミングについて語るスレ ■前スレ マルチスレッドプログラミング相談室 その７ pc12.2ch.net/test/read.cgi/tech/1215253576/ ■過去スレ その１ ttp://pc3.2ch.net/tech/kako/997/997345868.html その２ ttp://pc5.2ch.net/test/read.cgi/tech/1037636153/ その３ ttp://pc8.2ch.net/test/read.cgi/tech/1098268137/ その４ ttp://pc8.2ch.net/test/read.cgi/tech/1130984585/ その５ ttp://pc11.2ch.net/test/read.cgi/tech/1157814833/ その６ ttp://pc11.2ch.net/test/read.cgi/tech/1187008532/ OS・言語・環境は問わないが、それゆえ明記すべし。 テンプレ 【ＯＳ】 【言語】 【実行環境】 【その他特記する事項】 63 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 19:23:00 ] スピン(に限らず)ロックは、ロックされていたら解放されるまでただ待つしかない ロック保持者が何か処理に手間取って (ページングとか、割り込みとかで) 時間を取られたら、 それに引きずられて後続が全部渋滞してしまう lock freeは、相手がすでに処理に入ってても我関せずで自分も処理に入ってしまい、 相手が何か手間取ってたら自分の方が先にCASを勝ち取り、次の処理に進めるというのが強み 負けた方は残念ながら最初からやり直し、今までやったことが無駄になるが、 今戦ってた相手はもう去ったし、次はたぶん成功するんじゃね？ 次々に相手が現れていつまでも負け続けるようなひどい競合状態なら、普通のロックの方が良いらしい 負けたら同じ処理をもう一度やり直さないといけないという無駄がどうしてもあるし 64 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 19:40:40 ] >>63 そういうlock-freeもあるけど、単純にアトミックアクセスだけで済ます場合もlockが 無いならlock-freeって呼ぶし（boost::shared_ptrとかがまさにそれ）、その場合は lock-freeと言ってもバスロックを使ったりしてるからややこしいんだが、要するに、 何があってもデッドロックしないアルゴリズムならlock-free、ということだと思って いるんだが 65 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 19:45:19 ] デッドロックはまたややこしい話になると思うから置いとくとして そういうのはやっぱりwait freeに分類すべきじゃないかな wait freeもlock freeの一種といえばそうなんだけど 66 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 20:01:02 ] lock-free : ロックせずにアクセスできる wait-free : lock-freeの条件を満たしており定数時間で処理が完了する事が保証される だけでそれ以外の要素は各実装による・・・じゃねーの 67 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 21:09:37 ] まぁ>>63と全然違う仕組みのlock-freeも色々あるよってことで 68 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 21:20:14 ] > 何があってもデッドロックしないアルゴリズムならlock-free 俺はこれが一番合点がいった。(dead)lock-free なわけ ね。 …しかし「たまたま動いてたプログラムがより堅実に動 くようになります」っていうのはかなり微妙なメリット な気もする（w 69 名前：35 mailto:sage [2009/09/23(水) 23:21:08 ] >>59 CASとスピンとで内部の実装方法が異なるのは分かります。 # その意味では、>>57は以下のように訂正したほうがよいかもしれませんね。 # # Ｘ：利用できるように見えるのですが、実際にはスピンによる実装なので、 # Ｏ：利用できるように見えるのですが、実際にはCASやスピンによる実装なので、 # # Ｘ：もちろん、スピンが許されるケースや、 # Ｏ：もちろん、CASやスピンが許されるケースや、 ただ、>>3が指摘した生産者-消費者モデルで生産時間<<消費時間な場合を除き、 言い換えると生産時間>消費時間な場合、大半の状態でキューは空(から)のままです。 その場合、(キューを読み出す側の)消費者スレッドは、どのようにして待てば よいのでしょうか？CPUを無駄にせず、いかにリトライをループさせるのでしょうか？ たとえば一般的なアプリケーションのキー入力「待ち」はCASやスピンで実装できますか？ 実は、生産者-消費者モデルに関する同じような疑問は>>3だけでなく、前スレでも たびたびカキコされていたのですが、レスがないか、あっても消費者スレッドを 待たせる方法に関する説明が無く、ずっと考え込んでいました。それが、>>45のレスで クリアになったので、生産者-消費者モデル実現の前提となるスレッド間の「同期」に ついては、lock-free/wait-freeは使えないと判断できました。 もちろん生産者-消費者モデルであっても、スレッド間の共有キューへの「排他(競合対策)」 については、lock-free/wait-freeを使用できます。一時的な待ちへの対応ですから。 スレッド間の「同期」と「排他」を意識的に区別して使い分けていることに注意してください。 70 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 01:24:47 ] 適当にスリープに落とせばいいんじゃ？ カーネルにスケジューリングを任せるより効率は若干落ちるが、高負荷時を見れば lock-freeの恩恵が受けられるから悪くないかと。 スレッド間通信がボトルネックの外にあるなら、好きな方法でいいと思われ。 71 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 01:47:24 ] すみません初歩的な質問で申し訳ないのですが，ｍｕｔｅｘで排他制御された場合、例えば ｍｕｔｅｘｌｏｃｋ()； Ａ［0］ = 0; mutexunlock(); の様な場合、スレッドＡはA[0]をアクセスして、スレッドBはA[100]をアクセスするとします。 その場合、スレッドBはスレッドAの処理が終わるまで配列Aにアクセスできないのでしょうか？ 72 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 01:50:07 ] >>71 そうなるね 73 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 02:22:05 ] 「の様な場合」なんていう他人に通じない省略しないで、 スレッドBの処理も書けばいいのに 74 名前： ◆0uxK91AxII mailto:sage [2009/09/24(木) 04:50:22 ] >>71 //ｍｕｔｅｘｌｏｃｋ()； Ａ［100］ = ~0; //mutexunlock(); :b 75 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 06:02:29 ] >>71です。 しょうもない質問をしてすみません。mutexでロックをかけた場合、配列にアクセスする場合はその間配列全体がアクセス禁止になるのか、 それともその一部のみ（例えばキャッシュライン分）がアクセス禁止になるのかを知りたかったのです。 アクセスできないとなると、 int D[10000]位確保されていたとして、 int *A,*B,*C; A = &D[0]; B = &D[1000]; C = &D[2400]; のようにポインタでAの場所を指して、 スレッドA： D[0]〜D[1199]の内容を書き換え、スレッドB：D[1200]〜D[2399]の内容を書き換え、スレッドC：D[2400]〜D[3599]の内容を書き換え、 オーバーラップする領域はまずAの処理を優先するため、その領域を保護するためにmutexでロックをかけている間、 BはAの処理が終わるのを待たなければならないのは分かるのですが、CもAの処理が終わるまで待たなければならないのでしょうか？ Thread A: for(i=0;i<1200;i++){ mutexlock(mu); 　　　　A[i]=100; mutec_unlock(mu); } Thread B: for(i=0;i<1200;i++){ B[i]=200; } Thread C:: for(i=0;i<1200;i++){ C[i]=300; } 76 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 07:34:43 ] >>61 > 相当限定的な使い方しか出来ない気がするなぁ…。 > 「スレッドの状態を気にしなくて良い」んじゃなくて、 > 気にできないんじゃないの? これ書いたの俺だけど、malloc() の内部処理辺りには 使えそうだと思った。それと類似して C++ の new() を オーバーライドしといて予め準備しといたメモリプール から取ってくるとかいうよくある奴。 例としてはそんなのでいいだろか? > 例を要求してた人 77 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 08:25:29 ] >>75 その例の場合は素通り 配列が自動的にアクセス禁止になるわけではない ThreadBもThreadCもmutexをロックしてどこからどこまで保護するのか明確にしなければならない 78 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 09:17:59 ] >>77 ロックする範囲が限定されていれば、 他のスレッドは進行を妨げられずに処理できるのですね。 ありがとうございました。 79 名前：35 mailto:sage [2009/09/24(木) 11:56:35 ] >>60 記事の紹介、ありがとうございます。読んでみました。 記事では、C++でlock-freeを使って生産者-消費者モデルを実現していますね。 以下はすべてC++のWaitFreeQueueクラスとして実装されています。 ・まずlock-freeで「排他」を実現するキューを実装。 　この時点では「排他」だけですから、スレッド間の「同期」は実現できていません。 ・次に、キューが空である間、消費者スレッドをループさせ続けることで「同期」を実現。 　この方式では、キューが空であればCPUを100%消費します。 　==> NATIVE_POOLING方式 ・続いて、キューが空である間、消費者スレッドをスリープさせ続けるループを 　組むことで「同期」を実現。 ==> SLEEP方式 ・最後に、BOOSTのcondition(timed_wait/notify操作)を使う事で、 　「同期」を実現。==> TIME_WAIT方式 (続く) 80 名前：35 mailto:sage [2009/09/24(木) 11:59:49 ] (>>79の続き) このC++ by DDJ実装と、>>40が紹介してくれたJavaの実装とを比較すると、 lock-free/wait-freeの意味に違いがあるように感じられました。 C++ by DDJ実装のTIME_WAIT方式は、JavaであればBlockingQueueクラスに相当しますが、 >>40では、BlockingQueueクラスは(同期の実現はモニタ使用が前提だから) lock-free/wait-freeではない、と定義しています。 これらの一見矛盾しているように見える事柄を、自分なりに以下のように解釈してみました。 ・lock-free/wait-free単独では「同期を実現できない」 ・ただし、lock-free/wait-freeとスリープ(あるいはモニタ/conditionなど)とを組み合わせた制御を 　アプリケーション側で(たとえばクラスとして)実装することで「同期を実現できる」 誰も皆「排他」に関しては「実現できる」と見解は一致していますが、 この「同期」が「実現できる/できない」という解釈に関しては、人によって見解が 分かれているように思えます。違いは、「スリープ/モニタ/conditionなど」の使用を含めて 「できる」とする考え方と、それらは純粋なlock-free/wait-freeではない、とする考え方です。 難しい論争で、技術的な課題でもありませんから、私もこれ以上の考察は止めにします。 81 名前：35 mailto:sage [2009/09/24(木) 12:10:08 ] >>70 レスありがとうございます。 >>80の最後で書いたように、lock-free/wait-freeとスリープとを組み合わせた制御を アプリケーション側で実装することによって「同期」は実現できますね。 # せっかく>>60がDDJの記事を紹介してくれていたのに、それを読まずに>>69を # カキコしてたのが、まずかったと反省しています。余計な手間をとらせてごめんなさい。 82 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 12:24:59 ] リング遷移よりはスピンした方がいいとか、ある程度待っても何も来なかったら スリープとか、待機時の特性をアプリケーションがチューニングするやり方に なるのは、ハイパフォーマンス向けだと利点と言えるのでは。 まぁ、リング遷移が気にならない状況ならカーネルに任せていいと思うけど。 とりあえず、スピン待機は立派な同期だよ。CPU使用率をやけに気にしてるけど、 MP向けだとスピンじゃないと話にならないことも多い。 83 名前：35 mailto:sage [2009/09/24(木) 14:21:36 ] >>82 (CASやスピンを用いた)lock-free単独による同期については、メニーコア、 あるいはその先(未来)にある超並列な世界であれば、並列システム全体から 見ると個々のコア(CPU)の無駄は無視できます。だから、その時代になれば 「lock-free単独による同期が常識」となっている可能性は十分に予測できます。 もしかすると、現在でも>>82が主張されているMP(?)向け用途、それに HPC(High Preformance Computing)やCELLのプログラマにとっては、 既に「lock-free単独による同期は常識」なのかもしれませんね。 ただし、現在のPC向け汎用CPUはシングルコアかせいぜい4コアが主流です。 その世界では、いかに個々のコアを無駄無く使いつぶすかが、 性能設計上の大きな課題になります。ですから、現時点では、 「lock-free単独による同期は一般的ではない」、言い換えると、 一般アプリケーションにおいては「スリープなどと組み合わせない限り (単独の)lock-freeでは同期は実現できない」と解釈しています。 論理的にはCASやスピンでも同期は実現可能である(立派な同期である)。ただし、 一般的な多くのケースにおいては、その方式は現実的ではないということです。 これもまた「できる/できない論争」の一種ですよね。 84 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 14:28:13 ] デュアルコアでさえスピンは使うって。 lock-free queueのcalleeが同期の機能を持ってるか、にこだわってるの？ callerが同期処理をしなきゃならない、だとしても、lock-freeで同期してることに なると思うけど。そうじゃないなら、シーケンスロックはロックの機能を持たない とかいう変な話になるぞ？ つーか、ノンブロッキング同期の一種だぞ、lock-freeもwait-freeも。 85 名前：35 mailto:sage [2009/09/24(木) 14:51:24 ] >>84 同じ「待ち」でも、「排他(ロック)」と「同期」は別のものです。 「排他」による待ちは一時的です。もしもそれが長時間継続するようであれば、 それは「設計が悪い」のです(一般にはバグとして扱う)。 それに対して「同期」の継続時間は不定です。 最も長いケースでは、システム全体が終了するまで「待ち」状態が継続します。 また、共有キューを用いた「同期」を実現するには「排他」も必要です。 ただし、だからといって「排他」だけでは「同期」は実現できません。 「排他(ロック)」と「同期」を区別して、考え直してみてください。 lock-freeには「排他」機能があります。ですから「デュアルコアでさえ スピンを使う」ことはあります。でも、lock-freeを単独で「同期」に 用いるのは現実的ではないと言っています。 というか「できる/できない論争」は止めにしませんか？私はこれで降ります。 86 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 15:05:18 ] > 一般的な多くのケースにおいては、その方式は現実的ではないということです。 ここの認識が勘違いしてると思うけどなぁ。 まぁ降りるならどうぞ。 87 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 16:28:41 ] lock-free queueの話で同期の話が出てくる時点で何かおかしい気がしている lock-free queueってのはこういうものだと認識しているのだけど…↓ マルチスレッドにおけるQueueのpushとpopの処理では、内部の変数の更新が衝突すること によって破壊されてしまう場合があるため、何かしらの機構を備えておく必要がある。 mutex等による排他制御ではコンテキストスイッチが発生し、それは時間的にシビアな場面 においては非常に遅くなる場合がある。 そのためコンテキストスイッチさせないようにあの手この手を尽くして (mutex等排他制御のためのプリミティブが使われていない)lock-freeなものを作る場合がある。 lock-free queueでは複数のスレッドからQueueに対してpush/popされても、内部でmutex等 による排他制御は行われず、コンテキストスイッチが起こらないため、複数スレッドから の高速なデータのpush/popが期待できる。 ↑何か間違ってる？ Queue(待ち行列)という特性を見るかぎり、Queueを使った同期ってのがどういうものか イマイチ解らない。 88 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 16:51:14 ] if(v.empty()){/*待機コード*/} int i=v.pop(); 例えばこれも同期 89 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 16:52:09 ] ifじゃなくてwhileだった 90 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 17:23:43 ] >>88 それって、Queueを使うためにmutexやスピンロック等を使った同期であって、 Queueを使った同期ではないような… もし仮にそのことをQueueを使った同期と言っているのであれば、それとlock-free queueとは 関連性薄くない？(べつにbool値のflagだとしても議論できるし) もしかしてQueueとかもう話題的にあんまり関係なくて、 単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？ って議論だったりする？ 91 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 17:47:00 ] >>88 empty()とpop()が別だから、複数スレッドだとrace conditionになるね。 92 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 18:03:19 ] どう見てもmutexもスピンロックも使ってないし、empty()じゃなくなった後に empty()がtrueにならないことが保証されてるqueueなら競合もしないよ 93 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 18:08:41 ] お互いに勝手なコンテキストを想定して話すから、会話が成り立ってない。 94 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 18:13:27 ] ・読み手／書き手は単数なのか複数なのか ・一般例なのか状況限定の例なのか ・empty()はロックしないことを保証しているか（lock-freeならしているだろうけど） こういう重要な条件をお互いに伝える気も読み取る気も感じられない。 95 名前：87 mailto:sage [2009/09/24(木) 18:25:37 ] while (v.empty()){} ↑こういうコード(ある状態が真になるまでループする)がスピンロックなのかと思ってた。 >>92みると違うみたい？ 96 名前：としあき mailto:sage [2009/09/24(木) 18:34:00 ] > こういう重要な条件をお互いに伝える気も読み取る気も感じられない。 念 97 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 18:50:40 ] >>95 それロックじゃないでしょ 98 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 23:38:03 ] 空気読まずに lock-free C++ vector の論文貼るね。既出ならメンゴ。 ttp://www.research.att.com/~bs/lock-free-vector.pdf 2006 年、Bjarne Stroustrup も噛んでる。なかなか性能いいみたい。 99 名前：35 mailto:sage [2009/09/25(金) 02:21:30 ] >>87 lock-free queueを実装する視点であれば、その認識は間違っていないと思うよ。 >>90 >単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？ >って議論だったりする？ 自分はlock-free queueを使う立場だから、そういう視点で>>81まで議論を続けてきました。 で、その後から議論が拗れてしまったわけですね。 何が原因かを考えました。自分は、(共有キューの競合による破壊を防ぐ為の)「排他」制御の為に スピンを「使う」ことは「一般的である」けれど、キューが空の場合に「待つ」、いわゆる 「同期」の為にスピンを「使う」のは(汎用PC/CPUの世界では)「一般的ではない」という立場。 それに対して、いや、キューが空で「待つ」場合にも、スピンを「使う」のは(汎用PC/CPUの 世界であっても)「一般的である」というのが、相手の立場。 ある事柄に対して、それが「一般的である/ではない」という解釈は、一般常識論ですから、 それぞれの立場によって異なるのが当たり前です。そんな両者が納得できる結論を導くのは難しい。 だから、>>85では、これ以上議論を続けても不毛なので止めることを提案しました。 100 名前：デフォルトの名無しさん mailto:sage [2009/09/25(金) 13:02:48 ] できません ↓ できます ↓ 一般的じゃないからできないようなもんです ↓ ハァ？ って流れに見えた 101 名前：デフォルトの名無しさん mailto:sage [2009/09/25(金) 15:30:44 ] 私はこれで降ります ↓ 何が原因かを考えました ↓ 提案しました ワロタ 102 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 14:00:48 ] >>87 多分間違っていると思うよ コンテキストスイッチは関係ない。 lock-free なキューのメリットは、lock-free でないキューより （ロックしないから）アクセスの並列性が高まること。 もちろん競合するときには性能が落ちるけど、平均的には 性能向上が期待できる。 103 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 20:19:00 ] アクセスの並列性ってどういうこと？ それが高いと何がうれしいの？ 104 名前： ◆0uxK91AxII mailto:sage [2009/09/26(土) 20:34:29 ] こんなケースで、こういうlock-freeなのを実装したら、 これだけパフォーマンスが向上しました・ ．．．みたいなのを挙げてみてほしい。 どうでも良いけど、jemallocでも、spinlockしているね。 105 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 21:38:58 ] >>103 ロックは重い処理だから、それなしにCAS等の手法で数十ステップで収まるloc-freeは 軽い(逐次実行時間が短い)ってことを言いたいんだろ。 ただ、コンテクストスイッチは関係ないと言い切っちゃうのは、もう......だなw 106 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 22:37:25 ] lock-freeの定義が各人の頭の中にしかないから1000までこの話題でも結論は出ない(ｷﾘｯ 107 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 23:05:40 ] まず、スピンロックとlock-freeにおけるCASの違いは スピンロックは、単純に同じ動作(CAS)を再試行する lock-freeの実装では、単純に値を読み直す場合や全ての動作を最初からやり直す場合等いろいろあるが とにかく、「同じ値で再度CASを実行する」ということはしない。 wait-freeは、上記の「CASの再実行」が起こらない、ということだから 言い直せば、retry-freeとでも言えるのかも知れない。 108 名前：デフォルトの名無しさん mailto:sage [2009/09/26(土) 23:10:11 ] あと、上のほうで「CASを使わなくてもメモリバリアがあれば云々」という話があったようだが CASが重いのは、CASに含まれるメモリバリア(バスロック)動作が重いのが理由なのだから CASを無くしたからってメモリバリアが必要なら、たいしてメリットは無くなる。 もし、「メモリバリアも無くしてかつwait-freeな実装が可能」というなら話は別だが。 109 名前：デフォルトの名無しさん mailto:sage [2009/09/27(日) 09:14:18 ] >>103 ちょっと古いけど、 www.ibm.com/developerworks/jp/java/library/j-jtp07233/index.html のスケーラビリティの問題あたりから下の部分はどう？ 110 名前：デフォルトの名無しさん mailto:sage [2009/09/27(日) 15:28:18 ] >>108 > CASが重いのは、CASに含まれるメモリバリア(バスロック)動作が重いのが理由なのだから メモリバリアとバスロックは別の概念だぞ。 たとえばIA-64には、メモリバリア無しのCAS命令(ニーモニック:cmpxchg)と、 メモリバリア有りのCAS命令(cmpxchg.acq や cmpxchg.rel)がある。 そもそも、メモリバリア自体はそこまで重い操作じゃない。 特に、C++0xでの memory_order_acquire, memory_order_release に相当する メモリバリアは、自身のスレッド内での順序づけを保証するだけなので、 他CPUとの通信を必要としないためコストもかなり小さい。 で、これまで話題になっているwait-freeなlinked queueなど、 多くのlock-free, wait-freeアルゴリズムの実装では、 この acquire, release 相当のメモリバリアで十分だ。 111 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 09:08:46 ] 見よう見まねでスピンロック実装して動作テストしたら標準のCriticalSectionより劇おそだったのは苦い思い出：プライスレス(´・ω・｀) 112 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 10:15:16 ] Win32のCriticalSectionの激速の理由は プロセッサを判定して、可能ならばunlockにmovを使ってバスロックを避けているから と俺は勝手に想像している。 113 名前： ◆0uxK91AxII mailto:sage [2009/10/01(木) 18:03:15 ] push/popを必要最低限にして、 適宜pause(rep; nop)を入れれば良いだけ。 114 名前：234 mailto:sage [2009/10/01(木) 20:17:23 ] >>112 コンテキストスイッチが無いときはカーネルに入らずに、単にロックカウントをアップしてるだけだからだよ。 115 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 21:48:37 ] >>114 いやそんなの当たり前だし。 「単純なスピンロックより速い(>>111)」理由が何故か？だよ。論点は。 116 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 22:46:40 ] >>115 非コンテキストスイッチング時はアセンブラで10数命令しか実行して無いんだから速いよ。 それに>>111のコードを見なければなんともいえない。 117 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 23:01:29 ] だから、その命令の中に、lock xadd とかの重い命令があるんだよ。 118 名前：デフォルトの名無しさん mailto:sage [2009/10/01(木) 23:10:26 ] コンテキストスイッチが無いから速い、とか アセンブラで10数命令だから、とか 偉そうな態度の割に、底が浅すぎる。 119 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:06:49 ] お前も相当えらそうだが。 120 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:26:57 ] 無知が知ったかぶって偉そうにしながら恥を晒してるのとは違うみたいだけど。 121 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:44:09 ] 間違っているというだけで何が間違っているか書かないやつは大抵ハッタリだわな。 122 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:44:47 ] >>121 それ正解。 123 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:49:28 ] void __stdcall trylock(volatile int *spin) { __asm { mov ecx, spin; mov edx, 1; xor eax, eax; lock cmpxchg [ecx], edx; } } void __stdcall unlock(volatile int *spin) { __asm { mov ecx, spin; xor edx, edx; mov eax, 1; lock cmpxchg [ecx], edx; } } void __stdcall trylock_nlk(volatile int *spin) { __asm { mov ecx, spin; mov edx, 1; xor eax, eax; cmpxchg [ecx], edx; } } void __stdcall unlock_nlk(volatile int *spin) { __asm { mov ecx, spin; xor edx, edx; mov eax, 1; cmpxchg [ecx], edx; } } void __stdcall unlock_nbl(volatile int *spin) { *spin = 0; } 124 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:50:21 ] DWORD readtsc() { DWORD v; __asm { rdtsc; mov v, eax; } return v; } int main() { const COUNT = 1000; CRITICAL_SECTION cs; InitializeCriticalSection(&cs); volatile int spin = 0; int st = readtsc(); for (int i = 0; i < COUNT; ++i) { EnterCriticalSection(&cs); LeaveCriticalSection(&cs); } printf("%u clocks at %s\n", readtsc() - st, "CriticalSection"); st = readtsc(); for (int i = 0; i < COUNT; ++i) { trylock(&spin); unlock(&spin); } printf("%u clocks at %s\n", readtsc() - st, "CAS"); st = readtsc(); for (int i = 0; i < COUNT; ++i) { trylock_nlk(&spin); unlock_nlk(&spin); } printf("%u clocks at %s\n", readtsc() - st, "CAS(lockプリフィックス無し)"); st = readtsc(); for (int i = 0; i < COUNT; ++i) { trylock(&spin); unlock_nbl(&spin); } printf("%u clocks at %s\n", readtsc() - st, "CAS(movでunlock)"); } 125 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:51:21 ] ほれ、ベンチ用意したぞ。 シングルスレッドで、ロック獲得が必ず成功する場合の数字のみ。 実際はカウンタ持ってるから単純なcmpxchgじゃなくxaddで正負と0を駆使して判定してるだろうし ロックを獲得できなかった場合にブロックに移行する処理もあるだろうけどな。 まあ見難いが、面倒くさかったから TABのインデントは見たい人が自分でやってくれ。 126 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:54:44 ] これでもまだ「コンテキストスイッチが」「命令数が」と言いたいなら ご自由にどうぞ。 127 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 00:58:52 ] 乙 しかしお前がどのレス書いたやつで何を主張したいのかがわからん。 128 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 01:03:20 ] 実行してみなきゃ結果の意味するところもわからんからね。 まあ俺は>>112>>115>>117とかだが。 関係ないが、stdcallとか、全然意味なかったな。 全部展開されてるし。 しかも、Enter/Leaveもレジスタにコピーされてレジスタ間接コールになってる。 129 名前：128 mailto:sage [2009/10/02(金) 01:04:01 ] >>123-124が俺な。 130 名前：128 mailto:sage [2009/10/02(金) 01:27:59 ] まあ一応、俺の手元での数字を出しとく。 rdtscで計ってるので、別プロセスに割り込まれない限り 何回やっても似たような数字になる。 18065 clocks at CriticalSection 39098 clocks at CAS 13700 clocks at CAS(lockプリフィックス無し) 19025 clocks at CAS(movでunlock) １番上が、単純にCriticalSectionをEnter/Leaveしたもの。 次が、「教科書通り」のCAS(lock+cmpxchg)を使ったスピンの取得と解放。 おそらく、>>111もこれに似たコード(取れない時のループは無し)を書いたと思われる。 ３番目は、上のコードから、バスロックを除いたもの。バスロックのコストを示すため。 ４番目が、>>112に述べた、unlock時のバスロックを避けるようにしたもの。 結論としては、>>112の推測が確信に変わっただけ。 131 名前： ◆0uxK91AxII mailto:sage [2009/10/02(金) 11:18:35 ] spinlockの話題>>111 が、CASにすり変わっている件について。 132 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 12:33:54 ] 「教科書通りのスピンロック」って、普通は xchg (test-and-set)でロックを取って、movでアンロックじゃねーの？ それとも最近の教科書は test-and-set より先に compare-and-swap を教えるのかな？ 133 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 13:15:17 ] 一般のプロセッサでxchgが1バスサイクルで実行される保証なんて無い。 というより、普通は読みと書きになる。(x86が特殊なだけ) だから、ロックを取得するにはCASが必要。 134 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 13:17:13 ] あ、ごめん TASならば確かにCASである必要は無いね。 135 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 13:22:36 ] だけど、「アンロックがmovが普通」は違う。 理由は ja.wikipedia.org/wiki/%E3%82%B9%E3%83%94%E3%83%B3%E3%83%AD%E3%83%83%E3%82%AF#.E6.9C.80.E9.81.A9.E5.8C.96 のように、 movだと、直前のクリティカルな部分への書き込みが他のプロセッサに伝わる前に アンロック処理のmovの書き込みが他のプロセッサに伝わる可能性があるため。 136 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 13:52:10 ] >>135 それはメモリバリアの問題であって、movかCASかは関係ない。 mov命令がreleaseメモリバリア効果を持っていればそれで十分だし、 逆に>110で挙げたようなメモリバリア無しCAS命令では不十分。 137 名前： ◆0uxK91AxII mailto:sage [2009/10/02(金) 13:54:13 ] >>135 それはspinlockを使う側が考慮する問題であって、 作る側は無視して良い。 138 名前： ◆0uxK91AxII mailto:sage [2009/10/02(金) 13:59:49 ] W2kSP4, Athlon 64 X2 3800+, VC6SP6+PP5, 最適化無し 50239 clocks at CriticalSection 49180 clocks at CAS 21132 clocks at CAS(lockプリフィックス無し) 32103 clocks at CAS(movでunlock) 139 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 14:24:08 ] >>136 それがメモリバリアの問題だっていう、そんなことわかってるよ。 そして、「一般的なmov」はメモリバリアの機能など持っていない事 さらに、「(次に書く)このスレで"一般に"用いられるCASという用語」はメモリバリアを持っているもね。 もちろん、CASというのがメモリバリアとは直接は関係ないってことだって充分知ってるよ。 (そうでなければ、lockなしのcmpxchgなんてもの出すわけ無いだろ) だけどこのスレで一般的にCASと言ったら 「アトミック操作で用いる事が可能なCAS」のことが普通だろうに。 140 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 14:28:11 ] 「一般的なmov」つまり、普通のロード/ストア操作はメモリバリアを持っていないのだから 普通のスピンロックの実装では、アンロック処理に movではなくメモリバリアを持ったTASやCASを使う。 (それらはロック獲得処理の段階で存在が示されている) だから「普通はmovでアンロック」などということは有りえない。 141 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 14:37:59 ] >>140は「教科書では」ね。 142 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 14:53:16 ] Windows Vista 64bit SP1, Core2DuoE6750, Microsoft Visual Studio 2008(VC Version 9.0.21022.8 RTM) /O2 /Ob2 /Oi /Ot (実行速度で最適化、インライン関数は展開可能な関数すべて展開) 101192 clocks at CriticalSection 67904 clocks at CAS 20424 clocks at CAS(lockプリフィックス無し) 88688 clocks at CAS(movでunlock) /Od /Ob1(最適化なし、インライン関数は展開しない) 108568 clocks at CriticalSection 99976 clocks at CAS 24184 clocks at CAS(lockプリフィックス無し) 65280 clocks at CAS(movでunlock) >>130の結果が謎すぎる 143 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 15:17:56 ] >>139 アトミック性とメモリバリアは別の概念だぞ。 CASがアトミックなのは当たり前であり、俺もそんなことに 文句をつけているわけじゃない。 x86におけるlockプレフィックスのないcmpxchgは SMP環境ではアトミック性が保証されないから (正しい意味での)CASとは言えない。 でも、>110で挙げたのは「アトミック性は保証されているが メモリバリア効果を持たないCAS」だ。 CASとは「あるメモリ位置に対する内容の取得・比較から代入までが アトミックに行える操作」であり、メモリバリア効果、つまり 「前後の命令との間でリオーダーを行わないという保証」は必須ではないと 俺は言っている。 # 実際に、C++0xのatomicライブラリではそのように定義されているし。 「普通のロード/ストア命令はメモリバリアを持たない」と言うのなら、 メモリバリアを持つロード/ストア命令を定義して、それを使えばいい。 何故わざわざCASやTASのような複雑な操作を持ち出す必要がある? ちなみに、x86のmov命令は(初期のバグ持ちプロセッサを除いて) デフォルトでreleaseメモリバリア効果を持っているぞ。 144 名前：デフォルトの名無しさん mailto:sage [2009/10/02(金) 15:36:13 ] はいはいごめんよ。 全部俺が悪かったよ。 145 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 09:36:48 ] ttp://d.hatena.ne.jp/bsdhouse/20090720/1248085754 ここが勉強になった。 146 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 10:16:52 ] ちらっと見ただけなんだけど、「volatile つけた変数に排他性は無いよ」 ってことをグダグダ言ってるみたいだけど、そんなの当たり前では？ 都市伝説もくそもねーよ 147 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 11:06:13 ] acquire/releaseバリヤって、 「そのスレッドでのメモリアクセスについて」限定？ ↑のスライドだと前後の命令を・・・となってるけど 148 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 11:36:54 ] 当たり前よ っつかどういう意味で聞いてる？ 149 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 11:37:10 ] 菊池バリヤー！ 150 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 16:40:11 ] 「バリア」って概念には 「メモリアクセスがコーダーが記述した”順”に実行されることが 保証される」っていう以上のものは含まれていない（例えばインク リメント操作がアトミックになることまでは保証されない）と認識し ているのですが。当たってます？ ネットに散らばっている情報にはブレがあると思えるし、正直、 勉強不足ではっきりと分からないところがあるので質問します。 151 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 18:09:38 ] >>150 それで正しい。 ちなみに、マルチスレッドの世界には「バリア同期」っていう全然別のものもあるので、 メモリバリアのことは「メモリフェンス」と呼ぶようにした方がいい。 152 名前：デフォルトの名無しさん [2009/10/03(土) 19:15:56 ] >>151 ありがとうございます。頭の中がすっきりしました。 153 名前： ◆0uxK91AxII mailto:sage [2009/10/03(土) 21:22:33 ] どうでも良い事だけど。 spinlockを奪い合った場合、 先に取ろうとした方が取れず、 後から取ろうとした方が取れたとしても、 動作としては正しいんだよね。 154 名前：デフォルトの名無しさん [2009/10/03(土) 21:37:43 ] spinlockはアンフェアだからそれで正しいね。 155 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 22:29:57 ] ＞spinlockはアンフェアだからそれで正しいね。 それは答えになってるのか？？ 156 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 23:21:32 ] 間違いではない＝正しい という論理がわからないのか？ どうしょうーもねーな 157 名前：デフォルトの名無しさん mailto:sage [2009/10/03(土) 23:32:43 ] 正しいのか？って言ってんじゃなくて 答えになってるのか？ って言ってんだけど。 158 名前：デフォルトの名無しさん mailto:sage [2009/10/04(日) 00:51:01 ] 答えにはなっているように見える。「正しいのか？」という問いに「正しい」と答えている。 その答えが正しいのかどうかは別の話。 159 名前：デフォルトの名無しさん mailto:sage [2009/10/04(日) 03:29:21 ] ja.wikipedia.org/wiki/%E3%83%99%E3%83%B3%E5%9B%B3 160 名前：デフォルトの名無しさん mailto:sage [2009/10/05(月) 13:09:01 ] >>155 説明になっているかどうかはともかく 答えにはなっていると思うんだが。 161 名前：デフォルトの名無しさん mailto:sage [2009/10/13(火) 02:20:13 ] 火元の人 　やり方が理解できない質問者 　俺に分からないならこのスレにも理解できる奴いないんじゃね、とか思っていて、 　それが態度にも滲み出ている 煽る人 　分かってるつもりだけど分かってないで煽り続ける 　こいつを見た火元は「やっぱり分かってる奴いないんじゃないか」と思いこむ 住人タイプA 　一目で分かるがお前の態度が気に入らないしコード示すのマンドクセ 　つーかこの説明で分かれボユゲ 住人タイプB 　みんな何言ってんだかわかんね ちょっと違うけどこのパターンに似てる 162 名前：デフォルトの名無しさん mailto:sage [2009/10/14(水) 09:48:32 ] posix準拠のオーソドックスなやり方しかしない俺にはこのスレは不要なようだ おまえら何言ってるかわかんねぇーしｗ 163 名前：デフォルトの名無しさん mailto:sage [2009/10/14(水) 10:36:30 ] >>162 自分からPOSIXスレッドとかに関連したネタをふればいいんじゃないかな？ まあ正直なところ、ここは相談室スレなんだから、あまりにもハードウェア寄りな専門知識が 必要な話題については、できれば「並列化について語る」スレで熱く語ってくれって感じはしてる。 あっちはハード(マルチプロセッサ/マルチコア)全然オケーなスレなんだから。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef