マルチスレッドプログラミング相談室 その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・言語・環境は問わないが、それゆえ明記すべし。 テンプレ 【ＯＳ】 【言語】 【実行環境】 【その他特記する事項】 34 名前：デフォルトの名無しさん mailto:sage [2009/09/22(火) 22:43:58 ] ｗｗｗ 俺以外全員馬鹿ｗｗｗｗｗ ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ 35 名前：デフォルトの名無しさん mailto:sage [2009/09/22(火) 23:35:51 ] >>32 lock-free queueとは、スレッド間で共有するキューがあっても、 そのアクセスに「lock操作そのものが不要(free)」なキューである。 これは分かる。 では、wait-free queueとは、スレッド間で共有するキューがあり、 たとえそのキューが空であっても「wait操作そのものが不要(free)」な キューである。 うーみゅ、どうやって実装しているんだ？それとも何か勘違いしてる？ 分かんねーーーヨ....orz 36 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:18:28 ] lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。 wait-freeはロックがかからないし、一定時間で完了する。 でいいのかな？ 37 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:30:03 ] >>36 いいんじゃないかな 38 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:31:06 ] >>36 > lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。 CASで失敗したときは操作を繰り返す、ってのは lock-free なの？ だとしたら、スピンロックは lock-free ってことになるよね？ 39 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:33:51 ] >>38 ロック変数をspinlockするのなら、それはlock-freeとは言えない 40 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:45:03 ] >>35 キューが空ならnullを返したり例外を投げたりすればいい。 たとえばJavaでは、要素が空のときにnullを返したりする Queue と、 要素が空のときに新たな要素が来るまで待機する操作がある BlockingQueue とが、 ちゃんと区別されている。 で、Queueにはwait-freeな実装クラス ConcurrentLinkedQueue があるけど、 BlockingQueueの実装クラスである LinkedBlockingQueue や ArrayBlockingQueue とかは wait-freeでもlock-freeでもない。 で、君が欲しいのは Queue なの? BlockingQueueなの? 41 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:47:32 ] >>39 ロック変数をCASで変更しようとして失敗したらリトライってのはlock-freeではない。 リンクリストのポインタ変数とかをCASで変更しようとして失敗したらリトライってのはlock-freeである。 ってこと？ 42 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 00:53:59 ] >>41 うん 43 名前：35 mailto:sage [2009/09/23(水) 06:49:21 ] >>40 レスありがトン。詳しい解説は、とても助かる。 欲しいのは、待機が可能なwait-free queueの実装クラスです。 この場合には、ConcurrentLinkedQueueでキューを生成し、 nullあるいは例外発生であればスレッドを(たとえばwait操作で)待機させるよう アプリケーション側で実装することになるのでしょうか？ スレッドを待機させる方法はwait操作以外にもいろいろあるから、 どの方法を選ぶかはアプリケーションにまかせる、という考え方になります。 wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、 「wait操作を実装していないキュー」の意味に思えてきました。 こんな感じで合っていますか？ 44 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 09:15:31 ] LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。 もし読み手をwaitでブロックさせるなら文字通りlock-freeでもwait-freeにもならない。 その場合、書き手はブロックした読み手を起こすためにカーネルの世話になるのでlockが発生するかもしれない。 45 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:23:13 ] >>43 > 欲しいのは、待機が可能なwait-free queueの実装クラスです。 「待機が可能な」ってことは BlockingQueue が欲しいってことだね。 BlockingQueueの実装方法は2つ。 ・待機しないQueueを用意し、要素が空だったらスピンしまくる。 ・「キューが空でない」という条件変数を用いたモニタ同期を組み込む。 前者は明らかにCPUの無駄遣い。 後者はlock-freeでもwait-freeでもない。 てことで、>40にも書いたようにJavaのBlockingQueueの実装クラスが wait-freeでもlock-freeでもないのは、手抜きしているわけではなく そのように実装するのが不可能だからだ。 > wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、 > 「wait操作を実装していないキュー」の意味に思えてきました。 だからそれは "wait-free" って言葉の意味を誤解してるって。 "wait-free" の wait とは、モニタ同期のwait()操作とかとは別物。 もちろん、sleep()とかyield()でもない。 46 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:27:50 ] >>44 > LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。 CASを使った wait-free なQueueの実装はあるよ。 java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html 47 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:41:43 ] 連結リスト使うくらいなら別にmutexでも、と思いかけたが、mutexは格段に重いから そうも言えないか 48 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:47:45 ] >>47 > mutexは格段に重いから Win32のmutexが無駄に重いだけ。 最近のOSが用意しているmutexなら、競合がない場合のコストは ロックとアンロックそれぞれで高々CAS一回分程度。 49 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:50:23 ] なら連結リストよりmutexの方がいい場面は多そうだな、Windows以外は 50 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:50:28 ] Win32のmutexはプロセスレベルじゃなくてシステムレベル？ で排他してるから重いのはしょうがないかと・・ 51 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:54:36 ] >>50 ですな。 というか、一般的に言う "mutex" に相当するものを、 Win32では "Critical Section" と呼んでいるから 混乱を招いているだけなんだけど。 52 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 11:58:17 ] W32はCSもMutexも両方Mutexで特性が違うと考えるのが自然 53 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 12:58:23 ] プロセスレベルで排他するからじゃなくて、 カーネルオブジェクトなのが原因なんじゃね？ 54 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 13:24:11 ] 目的がそうだからしょうがない 55 名前：35 mailto:sage [2009/09/23(水) 13:27:30 ] >>45 >てことで、>40にも書いたようにJavaのBlockingQueueの実装クラスが >wait-freeでもlock-freeでもないのは、手抜きしているわけではなく >そのように実装するのが不可能だからだ。 明解な説明です。理解できました。 >だからそれは "wait-free" って言葉の意味を誤解してるって。 >"wait-free" の wait とは、モニタ同期のwait()操作とかとは別物。 そのモニタ同期のwaiti()操作をイメージしていました。間違っていたんですね。 でわ、wait-freeの意味は、単純に「待ちが発生しない」へ改めます。 となると、lock-freeの意味も「待ちが発生する」に変わります。 ただし、どちらも「lock操作は不要」という特徴は共通している、と。 これでスッキリしました。 実は>>13,14,23のカキコ主だったのですが、lock-freeでは生産者-消費者モデルを 実現できない(畑違いである)ことが分かったので、次はwait-freeをと考えていましたが、 それも同様に誤解であることが理解できました。lock-free/wait-freeはスレッド間同期を 実現するプリミティブではない。それを実現するには、(lock操作を伴う)mutexや モニタ同期(signal/wait)などを導入する必要がある、と。 lock-free/wait-freeの使い方について、ここ数日で急速にイメージが掴めてきた感覚です。 たいへんありがとうございました。>>all(特に>>15,32,40,45) 後は、Javaだけでなく、C/C++でも利用できる一般的なlock-free/wait-freeの実装技法が 確立し、標準ライブラリとして仕様化されることを願っています。 56 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 13:37:41 ] え lock-free queueは同期にも使えるよね？ 57 名前：35 mailto:sage [2009/09/23(水) 14:30:47 ] >>56 lock-free queueは「待ちが発生する」キューなので、スレッド間同期に 利用できるように見えるのですが、実際にはスピンによる実装なので、 「一般的な」アプリケーションでは利用できないと考えました。 言い換えると、lock-free queueだけで(mutexやモニタを一切使わずに) 「一般的な」アプリケーションを開発することは、現実的ではないという判断です。 もちろん、スピンが許されるケースや、mutexなどのオーバヘッドさえも 問題視される環境下では、lock-free queueを使わざるをえないケースも 存在していることは承知しています。あるいは、パフォーマンスクリティカルな 部分だけをlock-free queueで同期させ、残る大半ではmutexを使う設計も あるでしょう。論理的にlock-free queueが同期に利用できないと 考えているわけではありません。 58 名前：35 mailto:sage [2009/09/23(水) 14:39:25 ] (>>57に追記) >>57の「一般的なアプリケーション」というのは、 生産者-消費者モデルで設計された、言い換えるとスレッド間同期が 前提となるマルチスレッドアプリケーションのことを指します。 たとえば>>13,14のアプリケーションではスレッド間同期が 必要ありませんから、lock-free queueを使用することができます。 （もちろんwait-free queueも使用できます。） 59 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 17:49:20 ] CASとスピンは違うよ。スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。 lock-freeの待ち時間は、よっぽどの酷い競合が起きたときに発生するにすぎない。一般的なアプリでは問題にならない。 そのような競合が起きるのは設計が悪いと思われる。 60 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 18:05:46 ] >>55 www.ddj.com/hpc-high-performance-computing/208801974 これは？ 俺はよく解んないからboost.threadのshared_mutexでmultiple-reader/single-writerやってるよ マルチスレッドは奥が深いなぁ 61 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 18:24:48 ] >>59 > スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。 スピンロックは観察対象がロックオブジェクトで、CAS は操作対象そのもの。 スピンロックは失敗時にはクリティカル領域に居る競合 相手の処理を促進する意味もあって普通ディスパッチす ると思う（悪くすると飢餓状態に陥る）けど、CAS は領 域がそもそも小さいのですぐにリトライして ok ってこと? 相当限定的な使い方しか出来ない気がするなぁ…。「ス レッドの状態を気にしなくて良い」んじゃなくて、気に できないんじゃないの? 62 名前：デフォルトの名無しさん mailto:sage [2009/09/23(水) 18:29:10 ] >>60 boostのshared_ptrもlock-freeで実装されていなかったっけ？ ヘッダ見ると幸せになれるかもね 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である必要は無いね。

---

---

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

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