09/09/22 00:08:35
lock-free queueって、計算処理は非常に重いけど、スレッドモデルとしては
比較的単純なケース(マスタ-スレーブモデル)に利用されるものなのかな？
たとえば動画エンコ/3Dレンダ/科学計算といった応用のように、
親スレッドが複数の子スレッドを生成し、各子スレッドが計算処理を実行し、
結果をlock-free queueに追加していく。親スレッドはjoinですべての計算の
終了を待ち、joinから抜けたらqueueから順に計算結果を取り出す...みたいな。
このモデルだと、スレッド間の同期なんて考える必要はまったく無い。
>>3の生産者-消費者モデルというのは、スレッド間同期の代表的な題材だから、
lock-free queueの話題とするのは、そもそも畑違いであると。
lock-free queueについては分かっていないので、有識者の指摘たのむ。
14:13
09/09/22 01:44:44
(>>13の続き)
あるいは、>>13の応用ならリアルタイム性は要求されず、しかも
計算処理が(親スレッドの処理よりも相対的に)重いという前提があるから、
親スレッドは全子スレッド群の終了を(joinで)待ってから再開しなくても、
pollingで定期的にqueueから計算結果を取り出し、ゆっくりと
計算処理の進捗状況に合わせて出力(画面表示)していく方法だってある。
これもスレッド間の同期は考えなくてもいい。
なにかlock-free queueの利用イメージが見えたような気がするのは漏れだけ？
lock-free queue専門家からすれば「何を今更、そんなの常識」な話なのかな？
15:デフォルトの名無しさん
09/09/22 02:22:42
そういう使い方はたぶん一般的だろうと思う
一対一の一方通行queueを双方向に張って適当にポーリングして同期っぽいことも
やれるし
ただ、汎用性をちょっと変えただけで実装が変わるから、結局バスロックするような
queueもあるだろうし、その辺ひっくるめてまとめて語るほどの経験は無いし
16:デフォルトの名無しさん
09/09/22 08:54:48
>>6
> 普通にlock-free queueを全く分かってなくね？
> アトミック操作も要らないタイプすら作れる
lock-free と wait-free を混同してね?
17:デフォルトの名無しさん
09/09/22 09:13:03
wait-freeが作れるならlock-freeでもあるからいいんじゃね？
18:デフォルトの名無しさん
09/09/22 09:43:04
>>6
是非作り方を教えてくれ。
アトミック操作もいらないなんて、君にとっては些細なことでも俺にとっては非常に大きな一歩なんだ。
19:デフォルトの名無しさん
09/09/22 17:21:21
どう見ても「本当は知らないんだろ？」と煽ってるようにしか見えないが…
ちょっと真面目に考えてみろよ。書き手が単数の場合、アトミック操作は要るか？
メモリバリアだけで書けるだろ。wait-freeじゃなくてlock-freeなんだから、準備
できてない間は待ってて貰っていいんだぞ。
複数の書き手を作るには、ハブのようなスレッドを作ってスター型トポロジーに
すればいい。
つーか、コードを全部示さないと信用できないってんなら、信用されなくていい。
勝手に妄想家とでも思っててくれ。いちいち何から何まで言うつもりは無い。
20:デフォルトの名無しさん
09/09/22 17:37:30
顔真っ赤にすんなよ＾＾；
21:デフォルトの名無しさん
09/09/22 17:48:31
妄想乙
22:デフォルトの名無しさん
09/09/22 20:44:22
>>19
> ちょっと真面目に考えてみろよ。書き手が単数の場合、アトミック操作は要るか？
ん、「書き手が単数」ってのはどこからわいてきた話だ?
こういうのは設計・実装に大きく影響する話なんだから、
勝手に仮定されると議論が成り立たないと思うぞ。
というか、読み手と書き手がそれぞれ一つずつって前提が置けるのであれば、
CASなしでwait-freeなキューを作るのは難しくないし。
23:13
09/09/22 20:46:03
>>14
レスありがとうございます。まずは、マスタ-スレーブモデルは一般的だろうと
いうことで、lock-free queue勉強の一歩を進めることができます。
あと、>>14のポーリング方式はスレッドプールモデルにも適用できますね。
スレッドプールとポーリングの組み合わせたキーワードで考えると、
更にlock-free queueの応用範囲が広がる気がします。
24:デフォルトの名無しさん
09/09/22 21:02:24
>>22
書き手が複数の場合どうするかも書いてあるだろ…
25:デフォルトの名無しさん
09/09/22 21:11:17
>>24
「ハブのようなスレッドを作ってスター型トポロジー」みたいな構造は
もはや「書き手複数で使えるキュー」とは言えないと俺は思うがねえ…
「ハブのようなスレッド」がそれぞれの書き手と繋がったキューを
順次ぐるぐるとチェックして回るんだろ?
それだけでCPUの1コアの使用率が100%になっちまうじゃねえか。
で、読み手が複数の場合はどのように対処するんで?
26:デフォルトの名無しさん
09/09/22 21:24:00
>>25
横だけど「ハブのようなスレッド」が渡して回るんじゃないの？
ほとんど(まったく？)lock-freeの利点が活きていないけど。
27:デフォルトの名無しさん
09/09/22 21:25:03
前スレからの元々の流れ忘れてる奴多くね？
俺も忘れたけど
28:デフォルトの名無しさん
09/09/22 21:36:59
まとめると、
書き手がひとつならアトミック不要、複数ならアトミック必要ですね。
読み手も同様
29:デフォルトの名無しさん
09/09/22 21:43:39
>>27
そんな君たちに僕の質問を再度コピペしておこう
| メモリとかキャッシュとかレジスターとかバスとかマルチコア/プロセッサーが絡むと
| どうなっているのかよくわからないからいつもmutex頼みです
| これらのHW関連とマルチスレッドについて詳しく知りたい場合のよい方法を教えてください
30:デフォルトの名無しさん
09/09/22 21:52:54
アセンブラでアトミック命令使ってみることをお勧めするであります。
31:デフォルトの名無しさん
09/09/22 21:55:29
>>26
> 横だけど「ハブのようなスレッド」が渡して回るんじゃないの？
キューだよ? FIFOだよ?
2つの読み手R1とR2がいて、R1はガリガリ計算中、
R2がキューから次の要素が来るのを待っているって状態なら、
次の要素はR2に渡さないといけないんだよ?
32:デフォルトの名無しさん
09/09/22 21:59:00
もしかして、lock-free, wait-freeの "wait" を
sleep()とかyield()とかのことだと勘違いしている奴がいるんじゃないか?
33:デフォルトの名無しさん
09/09/22 22:24:00
と、このような有様ですので、lock-freeのライブラリなんかそうそう出回らないって訳です
34:デフォルトの名無しさん
09/09/22 22:43:58
ｗｗｗ
俺以外全員馬鹿ｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
35:デフォルトの名無しさん
09/09/22 23:35:51
>>32
lock-free queueとは、スレッド間で共有するキューがあっても、
そのアクセスに「lock操作そのものが不要(free)」なキューである。
これは分かる。
では、wait-free queueとは、スレッド間で共有するキューがあり、
たとえそのキューが空であっても「wait操作そのものが不要(free)」な
キューである。
うーみゅ、どうやって実装しているんだ？それとも何か勘違いしてる？
分かんねーーーヨ....orz
36:デフォルトの名無しさん
09/09/23 00:18:28
lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。
wait-freeはロックがかからないし、一定時間で完了する。
でいいのかな？
37:デフォルトの名無しさん
09/09/23 00:30:03
>>36
いいんじゃないかな
38:デフォルトの名無しさん
09/09/23 00:31:06
>>36
> lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。
CASで失敗したときは操作を繰り返す、ってのは lock-free なの？
だとしたら、スピンロックは lock-free ってことになるよね？
39:デフォルトの名無しさん
09/09/23 00:33:51
>>38
ロック変数をspinlockするのなら、それはlock-freeとは言えない
40:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/09/23 00:47:32
>>39
ロック変数をCASで変更しようとして失敗したらリトライってのはlock-freeではない。
リンクリストのポインタ変数とかをCASで変更しようとして失敗したらリトライってのはlock-freeである。
ってこと？
42:デフォルトの名無しさん
09/09/23 00:53:59
>>41
うん
43:35
09/09/23 06:49:21
>>40
レスありがトン。詳しい解説は、とても助かる。
欲しいのは、待機が可能なwait-free queueの実装クラスです。
この場合には、ConcurrentLinkedQueueでキューを生成し、
nullあるいは例外発生であればスレッドを(たとえばwait操作で)待機させるよう
アプリケーション側で実装することになるのでしょうか？
スレッドを待機させる方法はwait操作以外にもいろいろあるから、
どの方法を選ぶかはアプリケーションにまかせる、という考え方になります。
wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、
「wait操作を実装していないキュー」の意味に思えてきました。
こんな感じで合っていますか？
44:デフォルトの名無しさん
09/09/23 09:15:31
LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。
もし読み手をwaitでブロックさせるなら文字通りlock-freeでもwait-freeにもならない。
その場合、書き手はブロックした読み手を起こすためにカーネルの世話になるのでlockが発生するかもしれない。
45:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/09/23 11:27:50
>>44
> LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。
CASを使った wait-free なQueueの実装はあるよ。
URLﾘﾝｸ(java.sun.com)
47:デフォルトの名無しさん
09/09/23 11:41:43
連結リスト使うくらいなら別にmutexでも、と思いかけたが、mutexは格段に重いから
そうも言えないか
48:デフォルトの名無しさん
09/09/23 11:47:45
>>47
> mutexは格段に重いから
Win32のmutexが無駄に重いだけ。
最近のOSが用意しているmutexなら、競合がない場合のコストは
ロックとアンロックそれぞれで高々CAS一回分程度。
49:デフォルトの名無しさん
09/09/23 11:50:23
なら連結リストよりmutexの方がいい場面は多そうだな、Windows以外は
50:デフォルトの名無しさん
09/09/23 11:50:28
Win32のmutexはプロセスレベルじゃなくてシステムレベル？
で排他してるから重いのはしょうがないかと・・
51:デフォルトの名無しさん
09/09/23 11:54:36
>>50
ですな。
というか、一般的に言う "mutex" に相当するものを、
Win32では "Critical Section" と呼んでいるから
混乱を招いているだけなんだけど。
52:デフォルトの名無しさん
09/09/23 11:58:17
W32はCSもMutexも両方Mutexで特性が違うと考えるのが自然
53:デフォルトの名無しさん
09/09/23 12:58:23
プロセスレベルで排他するからじゃなくて、
カーネルオブジェクトなのが原因なんじゃね？
54:デフォルトの名無しさん
09/09/23 13:24:11
目的がそうだからしょうがない
55:35
09/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:デフォルトの名無しさん
09/09/23 13:37:41
え
lock-free queueは同期にも使えるよね？
57:35
09/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
09/09/23 14:39:25
(>>57に追記)
>>57の「一般的なアプリケーション」というのは、
生産者-消費者モデルで設計された、言い換えるとスレッド間同期が
前提となるマルチスレッドアプリケーションのことを指します。
たとえば>>13,14のアプリケーションではスレッド間同期が
必要ありませんから、lock-free queueを使用することができます。
（もちろんwait-free queueも使用できます。）
59:デフォルトの名無しさん
09/09/23 17:49:20
CASとスピンは違うよ。スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。
lock-freeの待ち時間は、よっぽどの酷い競合が起きたときに発生するにすぎない。一般的なアプリでは問題にならない。
そのような競合が起きるのは設計が悪いと思われる。
60:デフォルトの名無しさん
09/09/23 18:05:46
>>55
URLﾘﾝｸ(www.ddj.com) これは？
俺はよく解んないからboost.threadのshared_mutexでmultiple-reader/single-writerやってるよ
マルチスレッドは奥が深いなぁ
61:デフォルトの名無しさん
09/09/23 18:24:48
>>59
> スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。
スピンロックは観察対象がロックオブジェクトで、CAS
は操作対象そのもの。
スピンロックは失敗時にはクリティカル領域に居る競合
相手の処理を促進する意味もあって普通ディスパッチす
ると思う（悪くすると飢餓状態に陥る）けど、CAS は領
域がそもそも小さいのですぐにリトライして ok ってこと?
相当限定的な使い方しか出来ない気がするなぁ…。「ス
レッドの状態を気にしなくて良い」んじゃなくて、気に
できないんじゃないの?
62:デフォルトの名無しさん
09/09/23 18:29:10
>>60
boostのshared_ptrもlock-freeで実装されていなかったっけ？
ヘッダ見ると幸せになれるかもね
63:デフォルトの名無しさん
09/09/23 19:23:00
スピン(に限らず)ロックは、ロックされていたら解放されるまでただ待つしかない
ロック保持者が何か処理に手間取って (ページングとか、割り込みとかで) 時間を取られたら、
それに引きずられて後続が全部渋滞してしまう
lock freeは、相手がすでに処理に入ってても我関せずで自分も処理に入ってしまい、
相手が何か手間取ってたら自分の方が先にCASを勝ち取り、次の処理に進めるというのが強み
負けた方は残念ながら最初からやり直し、今までやったことが無駄になるが、
今戦ってた相手はもう去ったし、次はたぶん成功するんじゃね？
次々に相手が現れていつまでも負け続けるようなひどい競合状態なら、普通のロックの方が良いらしい
負けたら同じ処理をもう一度やり直さないといけないという無駄がどうしてもあるし
64:デフォルトの名無しさん
09/09/23 19:40:40
>>63
そういうlock-freeもあるけど、単純にアトミックアクセスだけで済ます場合もlockが
無いならlock-freeって呼ぶし（boost::shared_ptrとかがまさにそれ）、その場合は
lock-freeと言ってもバスロックを使ったりしてるからややこしいんだが、要するに、
何があってもデッドロックしないアルゴリズムならlock-free、ということだと思って
いるんだが
65:デフォルトの名無しさん
09/09/23 19:45:19
デッドロックはまたややこしい話になると思うから置いとくとして
そういうのはやっぱりwait freeに分類すべきじゃないかな
wait freeもlock freeの一種といえばそうなんだけど
66:デフォルトの名無しさん
09/09/23 20:01:02
lock-free : ロックせずにアクセスできる
wait-free : lock-freeの条件を満たしており定数時間で処理が完了する事が保証される
だけでそれ以外の要素は各実装による・・・じゃねーの
67:デフォルトの名無しさん
09/09/23 21:09:37
まぁ>>63と全然違う仕組みのlock-freeも色々あるよってことで
68:デフォルトの名無しさん
09/09/23 21:20:14
> 何があってもデッドロックしないアルゴリズムならlock-free
俺はこれが一番合点がいった。(dead)lock-free なわけ
ね。
…しかし「たまたま動いてたプログラムがより堅実に動
くようになります」っていうのはかなり微妙なメリット
な気もする（w
69:35
09/09/23 23:21:08
>>59
CASとスピンとで内部の実装方法が異なるのは分かります。
# その意味では、>>57は以下のように訂正したほうがよいかもしれませんね。
#
# Ｘ：利用できるように見えるのですが、実際にはスピンによる実装なので、
# Ｏ：利用できるように見えるのですが、実際にはCASやスピンによる実装なので、
#
# Ｘ：もちろん、スピンが許されるケースや、
# Ｏ：もちろん、CASやスピンが許されるケースや、
ただ、>>3が指摘した生産者-消費者モデルで生産時間<<消費時間な場合を除き、
言い換えると生産時間>消費時間な場合、大半の状態でキューは空(から)のままです。
その場合、(キューを読み出す側の)消費者スレッドは、どのようにして待てば
よいのでしょうか？CPUを無駄にせず、いかにリトライをループさせるのでしょうか？
たとえば一般的なアプリケーションのキー入力「待ち」はCASやスピンで実装できますか？
実は、生産者-消費者モデルに関する同じような疑問は>>3だけでなく、前スレでも
たびたびカキコされていたのですが、レスがないか、あっても消費者スレッドを
待たせる方法に関する説明が無く、ずっと考え込んでいました。それが、>>45のレスで
クリアになったので、生産者-消費者モデル実現の前提となるスレッド間の「同期」に
ついては、lock-free/wait-freeは使えないと判断できました。
もちろん生産者-消費者モデルであっても、スレッド間の共有キューへの「排他(競合対策)」
については、lock-free/wait-freeを使用できます。一時的な待ちへの対応ですから。
スレッド間の「同期」と「排他」を意識的に区別して使い分けていることに注意してください。
70:デフォルトの名無しさん
09/09/24 01:24:47
適当にスリープに落とせばいいんじゃ？
カーネルにスケジューリングを任せるより効率は若干落ちるが、高負荷時を見れば
lock-freeの恩恵が受けられるから悪くないかと。
スレッド間通信がボトルネックの外にあるなら、好きな方法でいいと思われ。
71:デフォルトの名無しさん
09/09/24 01:47:24
すみません初歩的な質問で申し訳ないのですが，ｍｕｔｅｘで排他制御された場合、例えば
ｍｕｔｅｘｌｏｃｋ()；
Ａ［0］ = 0;
mutexunlock();
の様な場合、スレッドＡはA[0]をアクセスして、スレッドBはA[100]をアクセスするとします。
その場合、スレッドBはスレッドAの処理が終わるまで配列Aにアクセスできないのでしょうか？
72:デフォルトの名無しさん
09/09/24 01:50:07
>>71
そうなるね
73:デフォルトの名無しさん
09/09/24 02:22:05
「の様な場合」なんていう他人に通じない省略しないで、
スレッドBの処理も書けばいいのに
74: ◆0uxK91AxII
09/09/24 04:50:22
>>71
//ｍｕｔｅｘｌｏｃｋ()；
Ａ［100］ = ~0;
//mutexunlock();
:b
75:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/09/24 07:34:43
>>61
> 相当限定的な使い方しか出来ない気がするなぁ…。
> 「スレッドの状態を気にしなくて良い」んじゃなくて、
> 気にできないんじゃないの?
これ書いたの俺だけど、malloc() の内部処理辺りには
使えそうだと思った。それと類似して C++ の new() を
オーバーライドしといて予め準備しといたメモリプール
から取ってくるとかいうよくある奴。
例としてはそんなのでいいだろか? > 例を要求してた人
77:デフォルトの名無しさん
09/09/24 08:25:29
>>75
その例の場合は素通り
配列が自動的にアクセス禁止になるわけではない
ThreadBもThreadCもmutexをロックしてどこからどこまで保護するのか明確にしなければならない
78:デフォルトの名無しさん
09/09/24 09:17:59
>>77
ロックする範囲が限定されていれば、
他のスレッドは進行を妨げられずに処理できるのですね。
ありがとうございました。
79:35
09/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
09/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
09/09/24 12:10:08
>>70
レスありがとうございます。
>>80の最後で書いたように、lock-free/wait-freeとスリープとを組み合わせた制御を
アプリケーション側で実装することによって「同期」は実現できますね。
# せっかく>>60がDDJの記事を紹介してくれていたのに、それを読まずに>>69を
# カキコしてたのが、まずかったと反省しています。余計な手間をとらせてごめんなさい。
82:デフォルトの名無しさん
09/09/24 12:24:59
リング遷移よりはスピンした方がいいとか、ある程度待っても何も来なかったら
スリープとか、待機時の特性をアプリケーションがチューニングするやり方に
なるのは、ハイパフォーマンス向けだと利点と言えるのでは。
まぁ、リング遷移が気にならない状況ならカーネルに任せていいと思うけど。
とりあえず、スピン待機は立派な同期だよ。CPU使用率をやけに気にしてるけど、
MP向けだとスピンじゃないと話にならないことも多い。
83:35
09/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:デフォルトの名無しさん
09/09/24 14:28:13
デュアルコアでさえスピンは使うって。
lock-free queueのcalleeが同期の機能を持ってるか、にこだわってるの？
callerが同期処理をしなきゃならない、だとしても、lock-freeで同期してることに
なると思うけど。そうじゃないなら、シーケンスロックはロックの機能を持たない
とかいう変な話になるぞ？
つーか、ノンブロッキング同期の一種だぞ、lock-freeもwait-freeも。
85:35
09/09/24 14:51:24
>>84
同じ「待ち」でも、「排他(ロック)」と「同期」は別のものです。
「排他」による待ちは一時的です。もしもそれが長時間継続するようであれば、
それは「設計が悪い」のです(一般にはバグとして扱う)。
それに対して「同期」の継続時間は不定です。
最も長いケースでは、システム全体が終了するまで「待ち」状態が継続します。
また、共有キューを用いた「同期」を実現するには「排他」も必要です。
ただし、だからといって「排他」だけでは「同期」は実現できません。
「排他(ロック)」と「同期」を区別して、考え直してみてください。
lock-freeには「排他」機能があります。ですから「デュアルコアでさえ
スピンを使う」ことはあります。でも、lock-freeを単独で「同期」に
用いるのは現実的ではないと言っています。
というか「できる/できない論争」は止めにしませんか？私はこれで降ります。
86:デフォルトの名無しさん
09/09/24 15:05:18
> 一般的な多くのケースにおいては、その方式は現実的ではないということです。
ここの認識が勘違いしてると思うけどなぁ。
まぁ降りるならどうぞ。
87:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/09/24 16:51:14
if(v.empty()){/*待機コード*/}
int i=v.pop();
例えばこれも同期
89:デフォルトの名無しさん
09/09/24 16:52:09
ifじゃなくてwhileだった
90:デフォルトの名無しさん
09/09/24 17:23:43
>>88
それって、Queueを使うためにmutexやスピンロック等を使った同期であって、
Queueを使った同期ではないような…
もし仮にそのことをQueueを使った同期と言っているのであれば、それとlock-free queueとは
関連性薄くない？(べつにbool値のflagだとしても議論できるし)
もしかしてQueueとかもう話題的にあんまり関係なくて、
単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？
って議論だったりする？
91:デフォルトの名無しさん
09/09/24 17:47:00
>>88
empty()とpop()が別だから、複数スレッドだとrace conditionになるね。
92:デフォルトの名無しさん
09/09/24 18:03:19
どう見てもmutexもスピンロックも使ってないし、empty()じゃなくなった後に
empty()がtrueにならないことが保証されてるqueueなら競合もしないよ
93:デフォルトの名無しさん
09/09/24 18:08:41
お互いに勝手なコンテキストを想定して話すから、会話が成り立ってない。
94:デフォルトの名無しさん
09/09/24 18:13:27
・読み手／書き手は単数なのか複数なのか
・一般例なのか状況限定の例なのか
・empty()はロックしないことを保証しているか（lock-freeならしているだろうけど）
こういう重要な条件をお互いに伝える気も読み取る気も感じられない。
95:87
09/09/24 18:25:37
while (v.empty()){}
↑こういうコード(ある状態が真になるまでループする)がスピンロックなのかと思ってた。
>>92みると違うみたい？
96:としあき
09/09/24 18:34:00
> こういう重要な条件をお互いに伝える気も読み取る気も感じられない。
念
97:デフォルトの名無しさん
09/09/24 18:50:40
>>95
それロックじゃないでしょ
98:デフォルトの名無しさん
09/09/24 23:38:03
空気読まずに lock-free C++ vector の論文貼るね。既出ならメンゴ。
URLﾘﾝｸ(www.research.att.com)
2006 年、Bjarne Stroustrup も噛んでる。なかなか性能いいみたい。
99:35
09/09/25 02:21:30
>>87
lock-free queueを実装する視点であれば、その認識は間違っていないと思うよ。
>>90
>単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？
>って議論だったりする？
自分はlock-free queueを使う立場だから、そういう視点で>>81まで議論を続けてきました。
で、その後から議論が拗れてしまったわけですね。
何が原因かを考えました。自分は、(共有キューの競合による破壊を防ぐ為の)「排他」制御の為に
スピンを「使う」ことは「一般的である」けれど、キューが空の場合に「待つ」、いわゆる
「同期」の為にスピンを「使う」のは(汎用PC/CPUの世界では)「一般的ではない」という立場。
それに対して、いや、キューが空で「待つ」場合にも、スピンを「使う」のは(汎用PC/CPUの
世界であっても)「一般的である」というのが、相手の立場。
ある事柄に対して、それが「一般的である/ではない」という解釈は、一般常識論ですから、
それぞれの立場によって異なるのが当たり前です。そんな両者が納得できる結論を導くのは難しい。
だから、>>85では、これ以上議論を続けても不毛なので止めることを提案しました。
100:デフォルトの名無しさん
09/09/25 13:02:48
できません
↓
できます
↓
一般的じゃないからできないようなもんです
↓
ハァ？
って流れに見えた
101:デフォルトの名無しさん
09/09/25 15:30:44
私はこれで降ります
↓
何が原因かを考えました
↓
提案しました
ワロタ
102:デフォルトの名無しさん
09/09/26 14:00:48
>>87
多分間違っていると思うよ
コンテキストスイッチは関係ない。
lock-free なキューのメリットは、lock-free でないキューより
（ロックしないから）アクセスの並列性が高まること。
もちろん競合するときには性能が落ちるけど、平均的には
性能向上が期待できる。
103:デフォルトの名無しさん
09/09/26 20:19:00
アクセスの並列性ってどういうこと？
それが高いと何がうれしいの？
104: ◆0uxK91AxII
09/09/26 20:34:29
こんなケースで、こういうlock-freeなのを実装したら、
これだけパフォーマンスが向上しました・
．．．みたいなのを挙げてみてほしい。
どうでも良いけど、jemallocでも、spinlockしているね。
105:デフォルトの名無しさん
09/09/26 21:38:58
>>103
ロックは重い処理だから、それなしにCAS等の手法で数十ステップで収まるloc-freeは
軽い(逐次実行時間が短い)ってことを言いたいんだろ。
ただ、コンテクストスイッチは関係ないと言い切っちゃうのは、もう......だなw
106:デフォルトの名無しさん
09/09/26 22:37:25
lock-freeの定義が各人の頭の中にしかないから1000までこの話題でも結論は出ない(ｷﾘｯ
107:デフォルトの名無しさん
09/09/26 23:05:40
まず、スピンロックとlock-freeにおけるCASの違いは
スピンロックは、単純に同じ動作(CAS)を再試行する
lock-freeの実装では、単純に値を読み直す場合や全ての動作を最初からやり直す場合等いろいろあるが
とにかく、「同じ値で再度CASを実行する」ということはしない。
wait-freeは、上記の「CASの再実行」が起こらない、ということだから
言い直せば、retry-freeとでも言えるのかも知れない。
108:デフォルトの名無しさん
09/09/26 23:10:11
あと、上のほうで「CASを使わなくてもメモリバリアがあれば云々」という話があったようだが
CASが重いのは、CASに含まれるメモリバリア(バスロック)動作が重いのが理由なのだから
CASを無くしたからってメモリバリアが必要なら、たいしてメリットは無くなる。
もし、「メモリバリアも無くしてかつwait-freeな実装が可能」というなら話は別だが。
109:デフォルトの名無しさん
09/09/27 09:14:18
>>103
ちょっと古いけど、
URLﾘﾝｸ(www.ibm.com)
のスケーラビリティの問題あたりから下の部分はどう？
110:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/10/01 09:08:46
見よう見まねでスピンロック実装して動作テストしたら標準のCriticalSectionより劇おそだったのは苦い思い出：プライスレス(´・ω・｀)
112:デフォルトの名無しさん
09/10/01 10:15:16
Win32のCriticalSectionの激速の理由は
プロセッサを判定して、可能ならばunlockにmovを使ってバスロックを避けているから
と俺は勝手に想像している。
113: ◆0uxK91AxII
09/10/01 18:03:15
push/popを必要最低限にして、
適宜pause(rep; nop)を入れれば良いだけ。
114:234
09/10/01 20:17:23
>>112
コンテキストスイッチが無いときはカーネルに入らずに、単にロックカウントをアップしてるだけだからだよ。
115:デフォルトの名無しさん
09/10/01 21:48:37
>>114
いやそんなの当たり前だし。
「単純なスピンロックより速い(>>111)」理由が何故か？だよ。論点は。
116:デフォルトの名無しさん
09/10/01 22:46:40
>>115
非コンテキストスイッチング時はアセンブラで10数命令しか実行して無いんだから速いよ。
それに>>111のコードを見なければなんともいえない。
117:デフォルトの名無しさん
09/10/01 23:01:29
だから、その命令の中に、lock xadd とかの重い命令があるんだよ。
118:デフォルトの名無しさん
09/10/01 23:10:26
コンテキストスイッチが無いから速い、とか
アセンブラで10数命令だから、とか
偉そうな態度の割に、底が浅すぎる。
119:デフォルトの名無しさん
09/10/02 00:06:49
お前も相当えらそうだが。
120:デフォルトの名無しさん
09/10/02 00:26:57
無知が知ったかぶって偉そうにしながら恥を晒してるのとは違うみたいだけど。
121:デフォルトの名無しさん
09/10/02 00:44:09
間違っているというだけで何が間違っているか書かないやつは大抵ハッタリだわな。
122:デフォルトの名無しさん
09/10/02 00:44:47
>>121
それ正解。
123:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/10/02 00:51:21
ほれ、ベンチ用意したぞ。
シングルスレッドで、ロック獲得が必ず成功する場合の数字のみ。
実際はカウンタ持ってるから単純なcmpxchgじゃなくxaddで正負と0を駆使して判定してるだろうし
ロックを獲得できなかった場合にブロックに移行する処理もあるだろうけどな。
まあ見難いが、面倒くさかったから
TABのインデントは見たい人が自分でやってくれ。
126:デフォルトの名無しさん
09/10/02 00:54:44
これでもまだ「コンテキストスイッチが」「命令数が」と言いたいなら
ご自由にどうぞ。
127:デフォルトの名無しさん
09/10/02 00:58:52
乙
しかしお前がどのレス書いたやつで何を主張したいのかがわからん。
128:デフォルトの名無しさん
09/10/02 01:03:20
実行してみなきゃ結果の意味するところもわからんからね。
まあ俺は>>112>>115>>117とかだが。
関係ないが、stdcallとか、全然意味なかったな。
全部展開されてるし。
しかも、Enter/Leaveもレジスタにコピーされてレジスタ間接コールになってる。
129:128
09/10/02 01:04:01
>>123-124が俺な。
130:128
09/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
09/10/02 11:18:35
spinlockの話題>>111
が、CASにすり変わっている件について。
132:デフォルトの名無しさん
09/10/02 12:33:54
「教科書通りのスピンロック」って、普通は
xchg (test-and-set)でロックを取って、movでアンロックじゃねーの？
それとも最近の教科書は test-and-set より先に
compare-and-swap を教えるのかな？
133:デフォルトの名無しさん
09/10/02 13:15:17
一般のプロセッサでxchgが1バスサイクルで実行される保証なんて無い。
というより、普通は読みと書きになる。(x86が特殊なだけ)
だから、ロックを取得するにはCASが必要。
134:デフォルトの名無しさん
09/10/02 13:17:13
あ、ごめん
TASならば確かにCASである必要は無いね。
135:デフォルトの名無しさん
09/10/02 13:22:36
だけど、「アンロックがmovが普通」は違う。
理由は
URLﾘﾝｸ(ja.wikipedia.org)
のように、
movだと、直前のクリティカルな部分への書き込みが他のプロセッサに伝わる前に
アンロック処理のmovの書き込みが他のプロセッサに伝わる可能性があるため。
136:デフォルトの名無しさん
09/10/02 13:52:10
>>135
それはメモリバリアの問題であって、movかCASかは関係ない。
mov命令がreleaseメモリバリア効果を持っていればそれで十分だし、
逆に>110で挙げたようなメモリバリア無しCAS命令では不十分。
137: ◆0uxK91AxII
09/10/02 13:54:13
>>135
それはspinlockを使う側が考慮する問題であって、
作る側は無視して良い。
138: ◆0uxK91AxII
09/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:デフォルトの名無しさん
09/10/02 14:24:08
>>136
それがメモリバリアの問題だっていう、そんなことわかってるよ。
そして、「一般的なmov」はメモリバリアの機能など持っていない事
さらに、「(次に書く)このスレで"一般に"用いられるCASという用語」はメモリバリアを持っているもね。
もちろん、CASというのがメモリバリアとは直接は関係ないってことだって充分知ってるよ。
(そうでなければ、lockなしのcmpxchgなんてもの出すわけ無いだろ)
だけどこのスレで一般的にCASと言ったら
「アトミック操作で用いる事が可能なCAS」のことが普通だろうに。
140:デフォルトの名無しさん
09/10/02 14:28:11
「一般的なmov」つまり、普通のロード/ストア操作はメモリバリアを持っていないのだから
普通のスピンロックの実装では、アンロック処理に
movではなくメモリバリアを持ったTASやCASを使う。
(それらはロック獲得処理の段階で存在が示されている)
だから「普通はmovでアンロック」などということは有りえない。
141:デフォルトの名無しさん
09/10/02 14:37:59
>>140は「教科書では」ね。
142:デフォルトの名無しさん
09/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:デフォルトの名無しさん
09/10/02 15:17:56
>>139
アトミック性とメモリバリアは別の概念だぞ。
CASがアトミックなのは当たり前であり、俺もそんなことに
文句をつけているわけじゃない。
x86におけるlockプレフィックスのないcmpxchgは
SMP環境ではアトミック性が保証されないから
(正しい意味での)CASとは言えない。
でも、>110で挙げたのは「アトミック性は保証されているが
メモリバリア効果を持たないCAS」だ。
CASとは「あるメモリ位置に対する内容の取得・比較から代入までが
アトミックに行える操作」であり、メモリバリア効果、つまり
「前後の命令との間でリオーダーを行わないという保証」は必須ではないと
俺は言っている。
# 実際に、C++0xのatomicライブラリではそのように定義されているし。
「普通のロード/ストア命令はメモリバリアを持たない」と言うのなら、
メモリバリアを持つロード/ストア命令を定義して、それを使えばいい。
何故わざわざCASやTASのような複雑な操作を持ち出す必要がある?
ちなみに、x86のmov命令は(初期のバグ持ちプロセッサを除いて)
デフォルトでreleaseメモリバリア効果を持っているぞ。
144:デフォルトの名無しさん
09/10/02 15:36:13
はいはいごめんよ。
全部俺が悪かったよ。
145:デフォルトの名無しさん
09/10/03 09:36:48
URLﾘﾝｸ(d.hatena.ne.jp)
ここが勉強になった。
146:デフォルトの名無しさん
09/10/03 10:16:52
ちらっと見ただけなんだけど、「volatile つけた変数に排他性は無いよ」
ってことをグダグダ言ってるみたいだけど、そんなの当たり前では？
都市伝説もくそもねーよ
147:デフォルトの名無しさん
09/10/03 11:06:13
acquire/releaseバリヤって、
「そのスレッドでのメモリアクセスについて」限定？
↑のスライドだと前後の命令を・・・となってるけど
148:デフォルトの名無しさん
09/10/03 11:36:54
当たり前よ
っつかどういう意味で聞いてる？
149:デフォルトの名無しさん
09/10/03 11:37:10
菊池バリヤー！
150:デフォルトの名無しさん
09/10/03 16:40:11
「バリア」って概念には
「メモリアクセスがコーダーが記述した”順”に実行されることが
保証される」っていう以上のものは含まれていない（例えばインク
リメント操作がアトミックになることまでは保証されない）と認識し
ているのですが。当たってます？
ネットに散らばっている情報にはブレがあると思えるし、正直、
勉強不足ではっきりと分からないところがあるので質問します。
151:デフォルトの名無しさん
09/10/03 18:09:38
>>150
それで正しい。
ちなみに、マルチスレッドの世界には「バリア同期」っていう全然別のものもあるので、
メモリバリアのことは「メモリフェンス」と呼ぶようにした方がいい。
152:デフォルトの名無しさん
09/10/03 19:15:56
>>151
ありがとうございます。頭の中がすっきりしました。
153: ◆0uxK91AxII
09/10/03 21:22:33
どうでも良い事だけど。
spinlockを奪い合った場合、
先に取ろうとした方が取れず、
後から取ろうとした方が取れたとしても、
動作としては正しいんだよね。
154:デフォルトの名無しさん
09/10/03 21:37:43
spinlockはアンフェアだからそれで正しいね。
155:デフォルトの名無しさん
09/10/03 22:29:57
＞spinlockはアンフェアだからそれで正しいね。
それは答えになってるのか？？
156:デフォルトの名無しさん
09/10/03 23:21:32
間違いではない＝正しい
という論理がわからないのか？
どうしょうーもねーな
157:デフォルトの名無しさん
09/10/03 23:32:43
正しいのか？って言ってんじゃなくて
答えになってるのか？
って言ってんだけど。
158:デフォルトの名無しさん
09/10/04 00:51:01
答えにはなっているように見える。「正しいのか？」という問いに「正しい」と答えている。
その答えが正しいのかどうかは別の話。
159:デフォルトの名無しさん
09/10/04 03:29:21
URLﾘﾝｸ(ja.wikipedia.org)
160:デフォルトの名無しさん
09/10/05 13:09:01
>>155
説明になっているかどうかはともかく
答えにはなっていると思うんだが。
161:デフォルトの名無しさん
09/10/13 02:20:13
火元の人
やり方が理解できない質問者
俺に分からないならこのスレにも理解できる奴いないんじゃね、とか思っていて、
それが態度にも滲み出ている
煽る人
分かってるつもりだけど分かってないで煽り続ける
こいつを見た火元は「やっぱり分かってる奴いないんじゃないか」と思いこむ
住人タイプA
一目で分かるがお前の態度が気に入らないしコード示すのマンドクセ
つーかこの説明で分かれボユゲ
住人タイプB
みんな何言ってんだかわかんね
ちょっと違うけどこのパターンに似てる
162:デフォルトの名無しさん
09/10/14 09:48:32
posix準拠のオーソドックスなやり方しかしない俺にはこのスレは不要なようだ
おまえら何言ってるかわかんねぇーしｗ
163:デフォルトの名無しさん
09/10/14 10:36:30
>>162
自分からPOSIXスレッドとかに関連したネタをふればいいんじゃないかな？
まあ正直なところ、ここは相談室スレなんだから、あまりにもハードウェア寄りな専門知識が
必要な話題については、できれば「並列化について語る」スレで熱く語ってくれって感じはしてる。
あっちはハード(マルチプロセッサ/マルチコア)全然オケーなスレなんだから。
164:デフォルトの名無しさん
09/10/14 13:09:43
単に自分の付いていけないレベルの話題を締め出したいだけに見える
165:デフォルトの名無しさん
09/10/14 13:35:03
ということにしたいだけにも見える
166:デフォルトの名無しさん
09/10/14 21:17:55
つーか俺はposix準拠な世界で生きてきたので。
おまえらよくposix非準拠な話題で盛り上がれるなーｗ
167:デフォルトの名無しさん
09/10/14 22:48:54
>>166
CASやメモリバリアなどはpthreadライブラリの実装者にとっても
必須の知識だよ。
168:デフォルトの名無しさん
09/10/14 23:10:22
>>167
利用者にとっては？
169:デフォルトの名無しさん
09/10/15 03:21:14
POSIX厨としか言いようがない
170:デフォルトの名無しさん
09/10/15 08:47:16
>>169
POSIX使うのが普通じゃないの？
171:デフォルトの名無しさん
09/10/15 13:13:35
pthreadにはアトミック操作が定義されてないから、
単なるカウンタのインクリメントでも
いちいちロックしなきゃならんのが嫌だ。
172:デフォルトの名無しさん
09/10/16 00:37:47
なんでPOSIXで厨なんだよ(´・ω・｀)
173:デフォルトの名無しさん
09/10/16 02:28:34
POSIXスレッド以外の話題ってだけで叩くなら完全に厨だろ
174:デフォルトの名無しさん
09/10/16 06:51:32
他人を厨と決めつける人が厨に見える
175:デフォルトの名無しさん
09/10/16 08:03:36
何でも鸚鵡返しすれば反論になると思ってるだろ
176:デフォルトの名無しさん
09/10/16 08:04:58
baka
177:デフォルトの名無しさん
09/10/16 08:09:28
pthread地獄 part 2
ｽﾚﾘﾝｸ(unix板)
ここへ行けばいいのに
178:デフォルトの名無しさん
09/10/17 03:19:26
／＼ ┌┐ ┌┐ ___ ___
／ __ ＼ ／＼ ..｜｜.. ／＼ ｜｜ ___ ＼＼ ＼
／ ／ .＼ ＼ ＼ ＼ .｜｜. ／ ／ ┌─┘└─、＼＼ ￣ ￣
／ ／ .＼ ＼ ＼／ .｜｜. ＼／ └─┐┌─ 、｜ |__|
／ ／ ┌─┐.＼ ＼ ┌──┘└──┐ .｜｜ ｜｜
..＼／ └┐┌┘ .＼／ └──┐┌──┘ / / ｜｜
┌┘└┐ ／＼ .｜｜. ／＼ / / / /
└┐┌┘ ／ ／ .｜｜. ＼ ＼ ／ / / /
┌─┘└─┐ ＼／ ..｜｜.. ＼／ ＼／ / /
└──┘ └┘ ＼/
....､
....................--------､, i~ﾞ7 r‐ｯ !ﾞﾞ.! ! !
: !――;;;;;;''''''''ゝ ,,ﾉ゛ ._ / ./ .,! .,! ! ! .,..............! ヽ..........-、
| |.／ ／ .l､,｀''-./ ./ ! ! | | ―ｰｯ .iｰ''''''''i |
| l'-‐゛ ｀ﾞｯ .ゝ､ .| | | ,! ./ ./ ! !
../ .,! ／.,ｒ'"＼,/ .!ｰ′ ./ .,! . / ./ | │
.,./ ./ ,..‐" ／ . / / .／../ ./ .lﾞ
.ｒ'".／ ゝ／゛ : ,,-'゛.／ .〈 / .'|,ﾞ,ﾞ,,,, "
.｀゛ ﾞ'''"
179:デフォルトの名無しさん
09/10/20 15:39:31
その “全米” はグアム島を含むのでしょうか。
180:デフォルトの名無しさん
09/10/20 19:08:01
グアム、どうなんだろ。州に昇格すればいいのに。まあ、しないだろうけど。
181:デフォルトの名無しさん
09/11/03 00:02:53
スレッドを終了させるときは_endthreadexじゃなく
そのままreturnでもいいのか？スタックの開放されない？
182: ◆0uxK91AxII
09/11/03 00:28:01
良い。
mallocで取ってきた領域をfreeしなくて良いのと同じくらいに。
スタックとやらは、_endthreadexとは無関係。
183:デフォルトの名無しさん
09/11/03 00:59:57
freeしろよ
184:デフォルトの名無しさん
09/11/03 01:16:04
スレッドに強くないのに書き込んでみる。
URLﾘﾝｸ(msdn.microsoft.com)(VS.80).aspx
>ただし _endthread または _endthreadex は、_beginthread や _beginthreadex の
>パラメータとして渡されたルーチンからスレッドが戻ると自動的に呼び出されます。
ってことで、returnすれば問題ないかと。
どちらかというと
>_endthread と _endthreadex によって、C++ デストラクタはスレッドで保留状態になり、呼び出されません
なので、呼ばないほうが好ましいような。
185: ◆0uxK91AxII
09/11/03 01:52:01
182は無かった事にしてください。
んゆ。
186:184
09/11/03 14:42:55
スレッドに強い人に補強して欲しいのだけど、それとも184の認識で問題なし？
187: ◆0uxK91AxII
09/11/03 17:34:11
Microsoft Visual Studio\VC98\CRT\SRC\THREADEX.C
んゆ。
188:デフォルトの名無しさん
09/11/03 17:55:09
問題なし
189:デフォルトの名無しさん
09/11/03 22:08:15
スレッド識別子って何なんだ？
何に使うの？
190:デフォルトの名無しさん
09/11/03 22:25:48
殺したり、止めたり。
191:デフォルトの名無しさん
09/11/04 21:43:06
他スレッドの変数の中身知ることってできないかな？
192:デフォルトの名無しさん
09/11/04 21:55:11
メモリ空間は共有しているので、アドレスがわかれば普通に参照できる。
193:デフォルトの名無しさん
09/11/05 12:32:06
win32のインターロックをクリティカルセクションと
同じように使ったら早くて驚いた。
両者の内部的な違い・利点・欠点てなんですかね？
194:デフォルトの名無しさん
09/11/05 14:06:45
そもそも用途が違うんじゃない？
インターロックは変数1個ぶんの更新しかできないでしょ？
インターロックを使ってクリティカルセクションと同様のものを作ることはできるだろうし、
クリティカルセクションを使ってインターロックと同様のものを作ることもできるだろうけど、
そういう話？
195:デフォルトの名無しさん
09/11/05 14:31:15
インターロック一発で出来ることならインターロックで。
196:デフォルトの名無しさん
09/11/05 14:54:32
win32のクリティカルセクションは衝突しなければインターロックと同じくらい早いんだなこれが
197:デフォルトの名無しさん
09/11/05 16:01:33
いや倍くらいは遅いだろう。
198:デフォルトの名無しさん
09/11/05 16:15:02
んだ。インターロックで済むならそれが数倍早い。
199:193
09/11/05 19:29:23
今以下のクラスでクリティカルセクションと同じように扱ってテストしてるんだ。
class InterLock
{
private:
LONG m_Flag;
public:
void Enter()
{
while(InterlockedCompareExchange(&m_Flag,1,0)) Sleep(0);
}
void Leave()
{
InterlockedCompareExchange(&m_Flag,0,1);
}
public:
InterLock()
{
m_Flag = 0;
}
virtual ~InterLock()
{
}
};
200:193
09/11/05 19:30:08
こっちはクリティカルセクション晩
class CriticalSection
{
private:
CRITICAL_SECTION cs;
public:
void Enter()
{
EnterCriticalSection(&cs);
}
void Leave()
{
LeaveCriticalSection(&cs);
}
public:
CriticalSection()
{
InitializeCriticalSection(&cs);
}
virtual ~CriticalSection()
{
DeleteCriticalSection(&cs);
}
};
201:193
09/11/05 19:43:57
//グローバル変数
ロッククラス g_Lock;
int g_i = 0;
// 三つのスレッドで以下を走らせる
void Run()
{
for(int i=0; i<10000000; i++)
{
g_Lock.Enter();
g_i++;
g_Lock.Leave();
}
}
int main()
{
//３つのスレッドでRun()を走らせ、スレッド終了まで待機
(...省略)
cout << g_i << endl;
cout << time.result() << endl;
return 0;
}
結果
クリティカルセクション 35秒 g_i = 30000000
インターロック 5.5秒 g_i = 30000000
ロッククラス無し 0.16秒 g_i = 21203536(整合性無し)
環境 OS:win xp CPU:core2duo1.8G メモリ:3G
202:デフォルトの名無しさん
09/11/05 20:42:07
ソースまともに見てないけど、CSがもしインライン化されないなら性能的には勝てない
だろうしなぁ
まぁ、asm読めば全て分かるだろうけど
203: ◆0uxK91AxII
09/11/05 23:23:50
TryEnterCriticalSection ~ Sleepだとどうなるの、っと。
threadをCPUと1:1にbindしたらどうなるの、っと。
timesliceを変えたらどうなるの、っと。
結果は書かない方が良い。
204:193
09/11/06 07:01:38
＞TryEnterCriticalSection ~ Sleepだとどうなるの、っと。
これだけやってみた。
上記のテストだとインターロックとの差は0.5秒内、
つまりほとんど差がなくなった
205:デフォルトの名無しさん
09/11/06 13:00:12
プロセッサ数が2以上ならSpinWaitにしたらどうなる？
あとインターロックのIncrementでダイレクトアップデートにしたらどうなる？
206: ◆0uxK91AxII
09/11/06 20:26:47
違うネタだけど。
#include <windows.h>
#include <tchar.h>
#include <stdio.h>
#include <stdlib.h>
#define THREADS 64
#define LOOPS 123456789
struct SData { LARGE_INTEGER m_cntBegin; LARGE_INTEGER m_cntEnd;};
DWORD WINAPI thread(LPVOID pArg);
int __cdecl cmpForSort(const void *pArg0, const void *pArg1);
int _tmain()
{
int i; HANDLE ahThread[THREADS]; SData aData[THREADS];
LARGE_INTEGER diff;
for (i=0; i<THREADS; i++)
ahThread[i] = CreateThread(NULL, 0, thread, &aData[i], 0, NULL);
WaitForMultipleObjects(THREADS, ahThread, TRUE, INFINITE);
qsort(aData, THREADS, sizeof SData, cmpForSort);
for (i=0; i<THREADS; i++)
{
CloseHandle(ahThread[i]);
diff.QuadPart = 0<i? aData[i].m_cntBegin.QuadPart - aData[i-1].m_cntBegin.QuadPart: 0;
_tprintf(_T("thread: %d, diffBegin: %I64d, clock: %I64d\n"), i, diff.QuadPart, aData[i].m_cntEnd.QuadPart-aData[i].m_cntBegin.QuadPart);
}
return 0;
}
207: ◆0uxK91AxII
09/11/06 20:28:49
DWORD WINAPI thread(LPVOID pArg)
{
SData *pData; DWORD value; float sum;
pData = (SData *)pArg;
QueryPerformanceCounter(&pData->m_cntBegin);
__asm
{
mov ecx, LOOPS
fldz
LOOP_:
fadd QWORD PTR value
dec ecx
jnz LOOP_
fstp DWORD PTR sum
}
QueryPerformanceCounter(&pData->m_cntEnd);
return 0;
}
int __cdecl cmpForSort(const void *pArg0, const void *pArg1)
{
LARGE_INTEGER diff;
diff.QuadPart = ((SData *)pArg0)->m_cntBegin.QuadPart - ((SData *)pArg1)->m_cntBegin.QuadPart;
if (0 > diff.QuadPart) return -1;
if (0 < diff.QuadPart) return 1;
return 0;
}
208: ◆0uxK91AxII
09/11/06 20:37:44
同じ処理なのに所要時間がブレるとか、
先に開始したthreadよりも、後から開始した方が早く処理を終えるとか。
そういうのが起こりうる。
computer gameでmulti threadの利用に消極的な理由の一つだと思う。
209:193
09/11/06 23:12:33
>>205
＞インターロックのIncrementでダイレクトアップデートにしたらどうなる？
1.3秒だった
>SpinWait
これC#じゃん
210:デフォルトの名無しさん
09/11/07 01:40:37
スピン待機はC#限定じゃなく一般的な概念だ
211:デフォルトの名無しさん
09/11/07 09:40:03
スピンすると余計遅くなりそうだな。
一般的な使用状況に比べて処理と競合がタイトすぎるせいかな多分。
212:デフォルトの名無しさん
09/11/07 09:45:49
ああつまり3スレッド同時じゃなくて1スレッドで3回繰り返した方が速いとかっていう状態ね。
213:デフォルトの名無しさん
09/11/07 17:33:40
あーいやいや、これだとちょっと書き方がおかしいな…まあいいや
214:193
09/11/07 19:49:07
スピンロックは信頼性がないという話を聞いたような。
さて上記のベンチですが、1スレッドで3回繰り返したほうがずっと早いです。
衝突したときに別の処理をせずに待つ場合はシングルスレッドにした方がいいかも。
215:デフォルトの名無しさん
09/11/07 20:02:47
スピンロックに信頼性が無かったらどうすんだよｗ
全然仕組みとか分かってなくて使ってる匂いがぷんぷんするな
216:デフォルトの名無しさん
09/11/07 20:03:53
スピンロックとスピンウェイトは基本的に別物です。
217:デフォルトの名無しさん
09/11/08 00:12:02
それと信頼性に何の関係が？
218:デフォルトの名無しさん
09/11/08 02:55:49
スピン待ちの話をされてスピンロックどうこうと返すのがおかしい
219:デフォルトの名無しさん
09/11/08 10:06:21
上の人じゃないけど、スピンロックはスピンウエイトを使ってやってるかとおもてたよ(´・ω・｀)
220: ◆0uxK91AxII
09/11/08 12:45:22
spinlockでlockできる保証は無いね。
偶然上手く動いているだけ。
221:デフォルトの名無しさん
09/11/09 01:48:53
◆0uxK91AxIIで検索したら、NGしてもいいくらいトンチンカンな奴だな
222:デフォルトの名無しさん
09/11/10 14:27:27
トリップ付けるような奴だもの。
223:デフォルトの名無しさん
09/11/10 20:06:21
トンチンカンなんて久々に見た
おやつあげないわよ
224:デフォルトの名無しさん
09/11/11 09:14:41
抜作先生の方がまだ新しいな。
225:デフォルトの名無しさん
09/12/15 00:01:41
マルチスレッド対応の基数木のアルゴリズムって
どうやって記述すればいいのでしょうか？
CかC++で探しています。
226:デフォルトの名無しさん
09/12/22 22:31:16
読み込みと書き込みが１スレッドずつの場合でもメモリ破壊って起きるのでしょうか？
たとえば、ある変数をメインスレッドで読み込み続け、
複数のサブスレッドで、クリティカルセクションを用い、書き込むといった場合です
227:デフォルトの名無しさん
09/12/22 22:39:31
>>226
とりあえず破壊読み出しメモリだと死ぬよね。
228:デフォルトの名無しさん
09/12/22 23:29:29
>>226
まずメモリ破壊を定義してもらおうか
229:デフォルトの名無しさん
09/12/23 01:41:11
パソコンのネジ外して開けると見えてくるメモリの部分をハンマーで叩く
230:デフォルトの名無しさん
09/12/23 01:42:27
ハードウェア的な話題もするんか
231:デフォルトの名無しさん
09/12/23 02:21:03
宇宙線による確率的なビット反転は防ぎようがない
232:226
09/12/23 10:10:00
データが飛ぶという意味でのメモリ破壊です
ハード的にどのように動作しているのか分からないのですが
同アドレスに同時にアクセスされることによってメモリ破壊が起きるのでしょうか？
233:デフォルトの名無しさん
09/12/23 10:20:05
書き込みをクリティカルセクションで同期して、クリティカルセクションを抜けたところで可視性が保証されたとしても、
読む方が書き込み中にその変数を見る可能性があるなら、少なくとも意図しない値を読む可能性はあるんじゃない？
(+不変な変数見てると思われるかもね)
要求次第だけど、
この手のポーリングするやつは、次に読めればいいからその瞬間のスナップショットで十分だと思うので、
Atomicな操作用のAPI使うとか、書き込みがAtomicであることが保証されるならvolatileだけでもいいかも。
その変数の読み書きだけ同期とっても、読んでる間の書き込みは防げても、
読み込みが終わってクリティカルセクション抜けたあと、それで処理しようと思ったら
もう書き換わってることもあるし。
読んだ値の処理が終わるまで書き込ませないなら、話は別だけど。
234:デフォルトの名無しさん
09/12/23 11:15:37
昔使ったタイマ LSI でラッチ→lo-read→hi-readって
いう約束ごとのあるやつがあったな。hi-readでラッチ
が外れる奴。word-read 命令が使えるかどうかは CPU
次第。
235:デフォルトの名無しさん
09/12/23 12:47:17
>>226
ハードや操作による。
つーか、まずは「アトミックな操作」という概念をどっかで調べとけ。
例えば、x86のCPUなんかだと、どういう操作がアトミックかはIntelが規定している。
アトミックな書き込みなら、別のコアからの読み込みが割り込む可能性は無い。逆に
アトミックでない書き込みなら、例えば半分くらい書き込んだところで別のコアが
読み込む可能性があるということ。
x86なら、厳密な規定はIntelの英語版サイトに落ちてる。32bitアラインドなreadや
writeは確実にアトミックだ。相当古いx86以外はキャッシュアラインドなら大丈夫。
read-modify-writeはLOCKプリフィクスが無い限りアトミックではないが、xchg
命令はLOCK#が自動的にアサートされるのでアトミックだ。
まぁ、アセンブラを直接叩くんじゃなければ、イントリンシック命令を調べておけば
十分だが、その裏でどういうCPUの動きをしているかは理解しといた方がいい。
つーか、低水準の話と高水準の話で全然違いすぎるんだよな。俺はどっちの話でも
構わんけど、分けた方がいいのか？
236:226
09/12/23 12:53:08
ありがとうございます
もっと勉強します
237:デフォルトの名無しさん
09/12/23 13:31:19
>>232
そんな事は起きないようにハードウェアが作られてる
物理的なメモリへのアクセス経路は1個しかないから、同じアドレスに同時にアクセス
なんて事は出来ない
命令が書いた順に実行されるかとか、他のコアやスレッド云々は >>235 の通り
238:デフォルトの名無しさん
09/12/23 13:31:47
クリティカルセクションを用いって書いてあるから、なんとなくWindowsかと思ってた。
239:デフォルトの名無しさん
09/12/23 13:32:15
>>235
ここはム板だから低水準の話はついていけないと思う
240:デフォルトの名無しさん
09/12/23 13:49:38
>>237
> 物理的なメモリへのアクセス経路は1個しかないから、同じアドレスに同時にアクセス
> なんて事は出来ない
いつの時代の人?
241:デフォルトの名無しさん
09/12/23 14:00:02
>>239
いやそれは無い
242:デフォルトの名無しさん
09/12/23 14:00:28
ん？今はどこが違うの？
243:デフォルトの名無しさん
09/12/23 14:04:04
>>235
x86は巨視的には古典的設計だからまだ理解しやすいけど、PPCなんかだとリオーダー
とかが剥き出しになってくるからさらにごちゃごちゃするんだよな
244:デフォルトの名無しさん
09/12/23 14:06:45
そこでeioioですよ！
245:デフォルトの名無しさん
09/12/23 14:07:20
間違えた、eieioだった
イーアイイーアイオー！
246:デフォルトの名無しさん
09/12/23 14:28:55
ｴｲｯｴｲｯｵｯｰ
247:デフォルトの名無しさん
09/12/26 12:32:01
この辺の話題が体系的に書かれてる教科書が欲しい
248:デフォルトの名無しさん
09/12/26 14:41:39
開拓が進行中のジャンルだから、書いたそばから陳腐化しそうでなかなか難しいかも
しれないな
249:デフォルトの名無しさん
09/12/31 15:09:39
何をもって高性能とするかをはっきりさせたいな
シングルコア100%アイドル3コアでできることを4コア25%ずつで処理することに意味はあるの？
250:デフォルトの名無しさん
09/12/31 15:12:36
>>249
に追記
並列処理の有利はわかるけど、これからは直列処理も並列化しようとしてるんでしょ
そんなの意味ないよねという話
251:デフォルトの名無しさん
09/12/31 15:50:00
1コア100%3コア0%ってCPUがボトルネックになってんじゃねーの
252:デフォルトの名無しさん
09/12/31 15:50:26
何を言ってるの？
253:デフォルトの名無しさん
09/12/31 21:19:08
>>249は軽くエスパーが日本語に翻訳しないと分かりづらい
4スレッドにしたら全部25%になっちゃうような処理までマルチスレッドにする
意味あんの、って言いたいんだろうし、だからCPU屋は2コアや4コアで現状維持
しながら別の進化の方向性を探ってるのも事実
だがそもそも、そういう微妙なケースにまで頑張って適用しようぜMTマンセー、
というようなスレではないので、そんな的外れなこと言われても一瞬何の話だか
分からんし、今更何をとしか言いようがない
254:デフォルトの名無しさん
09/12/31 21:28:43
>>253
日本語でおk
255:デフォルトの名無しさん
09/12/31 21:35:30
>>253
余ってるCPUに仕事振る余地のない処理なら
それでいいんじゃね？
256:デフォルトの名無しさん
09/12/31 21:39:14
>>249の問題提起自体が微妙
アムダールの法則くらいで十分じゃねーの？
257:デフォルトの名無しさん
10/01/03 18:49:32
そもそも並列化できない処理まで並列化しようとしてるなんて話は聞いたこともない。
誰が言ったんだそんなこと。
258:デフォルトの名無しさん
10/01/03 21:49:55
>>249が言ってるな
259:デフォルトの名無しさん
10/01/16 03:00:47
質問させてください。
【ＯＳ】 UNIX/LINUX
【言語】 C言語
【実行環境】 gcc
【その他特記する事項】
メインスレッドからn個のスレッドを作成->全ての終了を待つという場合、
int i;
pthread_t id[n];
void* res[n];
for (i=0; i<n; i++) pthread_create(&id[i], NULL, funcptr, arg);
for (i=0; i<n; i++) pthread_join(id[i], &res[i]);
こんな感じで大丈夫でしょうか？
それとWindowsにあるWaitFor～みたいに複数待つというのは無いのでしょうか？
260:デフォルトの名無しさん
10/01/16 03:18:30
>>259
>WindowsにあるWaitFor～みたいに複数待つ
つ URLﾘﾝｸ(developers.sun.com)
261:デフォルトの名無しさん
10/01/26 00:12:16
スレッドを終了させないままアプリを閉じた場合
やっぱメモリリークとか起きるの？
262:デフォルトの名無しさん
10/01/26 00:20:29
環境を想定しないとなんともいえない。
263:デフォルトの名無しさん
10/01/26 00:33:22
>>261
OS破壊されるぞ？いいのかそんなことしても
264:デフォルトの名無しさん
10/01/26 00:49:27
>>261
ja.wikipedia.org/wiki/メモリリーク
265:デフォルトの名無しさん
10/01/26 10:22:10
破壊されるようなOSなんか使うなw
266:デフォルトの名無しさん
10/01/26 16:03:33
MTでそんな脆いOSはちょっと想像付かないなｗ
携帯の奴とかはどうなんだろう
267:デフォルトの名無しさん
10/01/26 16:15:09
問題(1) 名前を入れる入力ダイアログ１つとボタンを1つ表示し，ボタンを押したときは時間に応じて，
05時～11時 「おはようございます，○○さん」
11時～17時 「こんにちは，○○さん」
17時～05時 「こんばんは，○○さん」
と表示するJavaScriptプログラムを作成しなさい。
268:デフォルトの名無しさん
10/01/26 16:20:40
断る。
269:デフォルトの名無しさん
10/01/26 16:24:21
キミの実力を見せてみろ
270:デフォルトの名無しさん
10/01/26 16:28:23
マルチスレッドと何の関係が
271:デフォルトの名無しさん
10/01/26 16:32:31
スレ違いでした。
すいません・・
272:デフォルトの名無しさん
10/01/26 17:10:35
VCでマルチスレッドアプリをトレース実行してるとかなりの頻度でOSごと固まるんですが、
マルチスレッドの場合のデバッグはデバッガ使わないのが普通なんですか？
273:デフォルトの名無しさん
10/01/26 17:48:30
PCが貧弱
274:デフォルトの名無しさん
10/01/26 18:05:06
嫁が貧乳
275:デフォルトの名無しさん
10/01/26 18:13:39
ユーザが頻尿
276:デフォルトの名無しさん
10/01/26 18:19:25
>>272
詳細なテキストサービスをオフにすると少し幸せになれるかも。
ATOK使いの俺には無縁な話。
277:デフォルトの名無しさん
10/02/02 23:21:31
最近スレッド使い始めました。
クリティカルセクションとかインターロックで変数を共有するのは
なんとなく分かりました。
例えばCRITICAL_SECTIONを使う場合、アプリケーションで一つ用意すれば
よいのでしょうか?
極端に言えばCRITICAL_SECTIONをグローバル変数として定義して、
EnterCriticalSection等を使えばよろしいのでしょうか?
278:デフォルトの名無しさん
10/02/02 23:33:23
トイレに例えるなら何個個室があっても鍵がすべて連動してトイレにはひとりしか入れないってことだぞ
それでいいのか？
279:デフォルトの名無しさん
10/02/02 23:44:28
それでも良いが性能は良くない
性能向上のためにスレッドを使っているわけではないのなら、別に構わない
無理にシングルスレッドで処理するよりマルチスレッドの方が可読性が高くなることもあるからな
性能を上げたいのなら一人がどこかでロックを握ってる間全員が待たされるような構造は良くない
280:277
10/02/03 00:18:41
なるほど。問題点の指摘ありがとうございます。
では、3つスレッドがあるとして、1つは無関係で2つのスレッドで
変数を共有する場合は、クリティカルセクションをどう使えば
よろしいのでしょうか?
各スレッドループ中にCRITICAL_SECTIONを定義してりようすればよろしいのでしょうか?
何か根本的に勘違いしている気がしている気がします。
281:デフォルトの名無しさん
10/02/03 00:32:42
共有する変数がグローバルで1個しかないのならクリティカルセクションもグローバルで1個でいいよ
282:277
10/02/03 00:50:34
現在は全体からアクセスできる変数が一つです。
一気にやろうとはしないで少しずつ複雑なパターンを試してみます。
あと環境はWindowsです。失礼しました。
283:デフォルトの名無しさん
10/02/03 01:35:14
まあロックが1つで済むならデッドロックとか考えなくて済むし
可能ならその方が悩まない。
パフォーマンスの問題は、占有期間次第とも言えるから。
284:デフォルトの名無しさん
10/02/03 02:19:04
クリティカルな部分一個をトイレの個室一つと考える
285:デフォルトの名無しさん
10/02/03 04:12:03
たまに鍵かけないやつがいてトラブるんだ
286:デフォルトの名無しさん
10/02/03 07:23:37
そうするとトイレの中に
トイレがあって、その中にまたトイレがないと
説明不可能だろ。
トイレはネストできねーだろ
287:デフォルトの名無しさん
10/02/03 09:11:21
そうかクリティカルセクションはネスト出来たか
288:デフォルトの名無しさん
10/02/03 11:33:20
じゃあトイレがバスルームにあるということで
289:デフォルトの名無しさん
10/02/03 11:42:57
階層数に制限があるからダメ。
290:デフォルトの名無しさん
10/02/03 11:52:56
トイレ中に地震がくるのと
小便中に大便を催すのと
どっちが我慢できる？
291:デフォルトの名無しさん
10/02/03 13:45:14
メモリバリアとmutexの関係が解りません。
メモリバリアとmutexがどういうものか。とかじゃなくて、
関係性とか、必要とされる場面について解説してあるサイトないですか？
292:デフォルトの名無しさん
10/02/03 13:59:08
メモリバリア
URLﾘﾝｸ(ja.wikipedia.org)
メモリバリアは単に自CPUのメモリアクセスの順序を制御するだけのもので、
mutexのようなスレッド間の排他制御 (後続のスレッドを進入させずに待たせるような) 機能は無い
メモリバリアはCPUの1命令に過ぎず、mutexはOSのスレッド管理と絡むもっと複雑なものだ
mutexを実装するOSの中の人は、複数のCPU間の連携のためにメモリバリアを使うかもしれない
293:デフォルトの名無しさん
10/02/03 16:33:38
メモリバリアかアトミック命令が無いとMutexは実装出来ない
294:デフォルトの名無しさん
10/02/03 20:55:32
>>291 は同期処理のバリアのことじゃないの？
URLﾘﾝｸ(ja.wikipedia.org)
ロードストアのオーダリングの話と mutex はちょっと離れてる気がする
295:デフォルトの名無しさん
10/02/04 17:45:59
>>286
クリティカルセクションのネストって必要かな？
296:デフォルトの名無しさん
10/02/04 17:49:29
クラスのスレッドセーフなメソッドから同クラスのスレッドセーフなメソッドを呼び出す場合とかにあると便利かも
そういう動作を意図しなかった場合にバグらないっていう利点もあるね
297:デフォルトの名無しさん
10/02/04 17:55:39
同クラスなら同期処理しないプライベートメソッドを呼び出すのではないか
298:デフォルトの名無しさん
10/02/04 19:04:48
たとえば口座aから口座bに振替をおこなうには、
口座aと口座b両方のロックを取る必要がある、
という典型的な例は？
299:デフォルトの名無しさん
10/02/05 08:24:35
それは二つのCSをロックするだけでネストじゃないんでね？
300:デフォルトの名無しさん
10/02/05 09:08:04
こんな話題とメモリバリアの話題が同時進行するってかなりカオスな気がする
301:デフォルトの名無しさん
10/02/05 13:10:17
>>298
同時に入ってる必要は無くね？
302:デフォルトの名無しさん
10/02/05 21:40:05
両方とも、a→bの流れならトランザクションだけでよくないか？
303:デフォルトの名無しさん
10/02/06 00:40:47
スレッドがA、B、C、Dの4つあって
かならずA、B、C、Dの順番で仕事が
終わるようにするには
どんなアルゴリズム使えばいいのですか？
304:デフォルトの名無しさん
10/02/06 00:46:46
スレッド化する意味あるのか？
B,C,Dは寝かせておいて、Aが自分の仕事を終えたときにBを起こせばいいんじゃないか
305:デフォルトの名無しさん
10/02/06 13:44:25
スレッドの終了処理を順番にやる必要があるってことかな。
終わるタイミングを調整したいだけなら、
BがAの終了を待つ
CがBの終了を待つ
DがCの終了を待つ
って感じにやれば順番に終われるんじゃね?
306:デフォルトの名無しさん
10/02/06 18:28:33
そしてAがDの終了を待てば完璧
307:デフォルトの名無しさん
10/02/06 19:34:45
>>306
どうやって全部待てばいいの？
308:デフォルトの名無しさん
10/02/06 20:36:58
Eに管理してもらう
309:デフォルトの名無しさん
10/02/06 20:51:33
どうやるのか全然わからない
たすけて
310:デフォルトの名無しさん
10/02/06 22:14:37
Aの処理終了の際に2個のスレッドで破れるBarrier1を待つ
Bの処理開始の際に2個のスレッドに破れるBarrier1を待つ
Bの処理終了の際に2個のスレッドに破れるBarrier2を待つ
Cの処理開始の際に2個のスレッドに破れるBarrier2を待つ
Cの処理終了の際に2個のスレッドに破れるBarrier3を待つ
Dの処理開始の際に2個のスレッドに破れるBarrier3を待つ
311:デフォルトの名無しさん
10/02/06 22:16:11
>>310
>スレッドで破れるBarrier
こんなことすると破綻すると思うのですが
それは何か新しい概念なのでしょうか？
312:デフォルトの名無しさん
10/02/06 22:46:53
>>311
>>294のバリアのことだよ。
2個のスレッドがバリアに到達した瞬間にバリアが破れて同時に進行を再開する。
Wikipediaより…
並列コンピューティングにおけるバリア（英: Barrier）とは、同期方法の一つであり、
ソースコード中でスレッドやプロセスがある箇所で停止し、
他の全てのスレッドプロセスがバリアに到達するまで進行しないようなものを示す。
313:デフォルトの名無しさん
10/02/07 00:29:35
>>310
わかりにくい表現だな。
314:デフォルトの名無しさん
10/02/07 21:28:39
同期なり待機って言った方がわかりやすいな
315:デフォルトの名無しさん
10/02/11 00:13:07
追加削除順序を保持しつつ
効率的にアクセス可能なデータ構造って何があるの？
316:デフォルトの名無しさん
10/02/11 00:25:04
二分木
317:デフォルトの名無しさん
10/02/11 00:32:33
>>316
マルチスレッドの2分木のサンプル
教えて
318:デフォルトの名無しさん
10/02/11 00:50:06
>>315
Skip list.
実装例は java.util.concurrent.ConcurrentSkipListSet とかかな。
319:デフォルトの名無しさん
10/02/20 11:14:34
C++のマルチスレッドの本って
どんなのがありますか？
Intelの本は使い方しか書いてないで
困ってる
320:デフォルトの名無しさん
10/02/20 12:39:32
正直、使い方だけしか提示しようがない気がする
どこもかしこも開拓中で、定番というものが無い
321:デフォルトの名無しさん
10/02/21 18:06:11
>>319
Java並行処理プログラミングマジオススメ。
直接同じことは出来なくても、考え方は大いに参考になる。
volatileだけはC++と全くの別物なので注意だけど。
boost.threadのfutureでJavaのExecutorフレームワークに近いことが出来そうだなぁ。
322:デフォルトの名無しさん
10/02/21 18:16:04
>>321
その程度の書籍薦められても困るんだよ
もっとまともな本持って来い
323:デフォルトの名無しさん
10/02/21 18:29:39
>>322
Java並行処理プログラミングでも満足できない貴方には
↓がお勧め。
URLﾘﾝｸ(scholar.google.com)
最先端の研究成果が大量に手に入るぞ。
324:デフォルトの名無しさん
10/02/21 19:01:28
>>322
もっとまともな本があるなら俺も知りたいけどね。
325:デフォルトの名無しさん
10/02/21 23:35:25
並行コンピューティング技法―実践マルチコア/マルチスレッドプログラミング
URLﾘﾝｸ(www.oreilly.co.jp)
326:デフォルトの名無しさん
10/02/22 16:37:56
begintreadexを使ったときはclosehandleを使わないといけないらしいけど
CloseHandle((HANDLE)_beginthreadex());
こんな感じでいいの？
327:デフォルトの名無しさん
10/02/22 16:42:48
beginthreadexが返したハンドルを渡すのかと聞いているのならYES
328:デフォルトの名無しさん
10/02/22 17:44:29
_beginthreadexはなんで整数型で返すんだろう
329:デフォルトの名無しさん
10/02/22 22:11:07
Win32の型を持ち込みたくなかったからじゃないの。
330:デフォルトの名無しさん
10/02/23 00:27:00
意味も無く汚くはしないしな、いくらMSでも
331:デフォルトの名無しさん
10/02/23 00:29:08
void *じゃだめなのか
332:デフォルトの名無しさん
10/02/23 08:52:12
それだと32bitであることを強調できないからやめたんじゃないかな
333:デフォルトの名無しさん
10/02/23 14:32:40
一応今はuintptr_tだしな
まぁ毎度のレガシーの枷なんだろうし、仕方ないっつーか正直どうでもいい
334:デフォルトの名無しさん
10/03/07 15:36:02
どちらかというとマルチコア絡みの質問ですが
テンプレにある該当スレは過疎ってるぽいのでこちらで質問させていただきます
Q1. Windowsはスレッドコンテキスト切替時、汎用レジスタ同様にxmmレジスタを待避/復帰しますか？
主にWindows 7 (32 bit)とWindows 7(64 bit)について知りたいですが、他のも回答いただけると有難いです
Q2. そもそもCore i7のSIMDモジュールってコア毎に独立してますか？
独立してるっぽいけど、確証となるブロックダイアグラムみたいなのがＩｎｔｅｌのドキュメントを漁っても見つからないorz
Q3. Core i7の分岐予測メモリって、コードが共通なら全スレッドで共通？それともスレッドコンテキスト毎にきちんと別統計になるんでしょうか？
Q4. VC(2008)付属ライブラリの数学関数(おそらくコプロセッサを使うはず)はスレッドセーフですか？またそれは/fp:オプションによらず不変？
よろすくおながいしますorz
335:デフォルトの名無しさん
10/03/07 16:24:51
A1: Windows 98, 2000以降はyes
A4: yes
336:デフォルトの名無しさん
10/03/07 16:51:28
A2 コア別でしょう。たぶん。コア間共有なんて設計のほうが難しいと思うよ。
A3 コア別でしょう。たぶん。コア間共有なんて設計のほうが難しいと思うよ。
337:デフォルトの名無しさん
10/03/07 17:32:40
>>326
>CloseHandle((HANDLE)_beginthreadex());
その組み合わせはちょっちまずくね？
URLﾘﾝｸ(msdn.microsoft.com)
にメモリリークが起きると書いてある(ちなみにやねうら本(1)にもそう書いてある)
ExitThread()を明示的に呼ばなくても、スレッド関数を抜けたら同じことのはず
なお、>326の反対(CreateThread()が返したハンドルを _endthread()で開放する)は明白に危険であろうことが上のリンク先から推測できる
(確保されていないメモリを_endthread()が解放しようとするハズ)
338:デフォルトの名無しさん
10/03/07 18:07:36
何のために_beginthread()～_endthread()や_beginthreadex()～_endthreadex()があるかというと
strtol()みたいに、機能的にはマルチスレッド環境下でも動いて欲しいのだが関数仕様的にマルチスレッドと相容れないような
標準関数をマルチスレッド環境でもきちんと動くようにする目的なので(おそらくそのために内部的にスレッド局所記憶を確保している)
そういう類の関数を明示的にも暗黙的にも呼び出さないと誓うならCreateThread()～CloseHandle()で無問題
339:308
10/03/07 18:19:56
ｽﾏｿstortol()じゃなくて問題なのはstrtok()とかlocaltime()とかだった、
340:デフォルトの名無しさん
10/03/07 18:53:55
>>337
_beginthread は起動されたスレッドが終了時にハンドルのクローズを行う。
_beginthreadex は別途CloseHandleする必要がある。その代わり、
スレッドが終了していてもハンドルは有効であり、スレッドの状態を調べることができる。
ここでのリークというのはCRTの作業域のことではなくて
あくまでもスレッドを追跡するためのハンドルのこと。
341:デフォルトの名無しさん
10/03/07 22:27:39
>335, >336
レス㌧クス
A1は実験的にも確認できた(イントリンシック関数が排他を含まないこと、およびxmm0とxmm1を使う関数を64スレッドで呼び出して無問題)
A2はまあそう思う(ダイ写真でSIMDとコアの区別を確認できない＆SIMDの数＜コアの数ではマルチメディア目的に合致しない)
A4についても使用予定関数について実験的に確認できた
A3はちょっち謎
同一コードで記述され、同一コアで走る別スレッド(含HT)の場合どうなるのか？
同一コード条件とそうでない条件(コードをスレッド別コピーとする)とで速度比較すればいいんだろうけども
コードをコピーすると分岐予測以前にトレースキャッシュ容量他の要因で速度低下するかもしれないから実験では精度良くは判断できない鴨
342:デフォルトの名無しさん
10/03/08 00:36:48
pthread_cond_wait状態になるまでに
結構時間かかるのですかね？
以下のようなコードを実効すると
結構頻繁に、別のスレッドがwait状態になる前に
pthread_cond_signalを実効してしまうのですが
必ず、同期取るようにどうしたらいいのでしょうか
thread1
{
while(1){
pthread_mutex_lock(&m);
pthread_cond_wait(&c, &m);
pthread_mutex_unlock(&m);
}
}
main
{
while(1) {
pthread_mutex_lock(&m);
pthread_cond_signal(&c, &m);
pthread_mutex_unlock(&m);
}
}
343:デフォルトの名無しさん
10/03/08 00:39:08
どうやって確認したの？
344:デフォルトの名無しさん
10/03/08 00:45:01
何がしたいのかよくわからんが、
とりあえずmutex取得する前にシグナル発行してたらいかんだろう。
345:デフォルトの名無しさん
10/03/08 00:54:13
thread1がlockするまえにmainがlock->signalしちゃってるとかありそう
346:デフォルトの名無しさん
10/03/09 07:06:51
>>337-338
つーか比較するものが間違ってる
_endthread()/_endthreadex()は作られた側が（必要なら）呼び出すもので
CloseHandleは_beginthread()/_beginthreadex()呼んだ側が呼び出すもの
347:341
10/03/13 23:42:54
自己解決しますた！(いや、多分、だけど
Windowsのスレッドコンテキスト切替は、スレッドが走り続けている場合、どうがんばっても
msオーダー周期(おそらく10 msとか20 msに1回）なので、分岐予測統計の結果がその間に十分安定する(と思われ
だから分岐予測精度を上げるためにコードのコピーをスレッド別に用意しておく、みたいな神経質なことはしなくて宜しい
かと、
348:342
10/03/14 01:04:34
訂正
誤：分岐予測統計の結果がその間に十分安定する(と思われ
正：分岐予測統計の結果が現実的に安定している期間よりも桁違いに長い(と思われ
ニホンゴ、ムズカシイデス、、
349:デフォルトの名無しさん
10/03/14 02:03:43
いやいやいやいや
いまはコア間での話ではなかったのか？
350:デフォルトの名無しさん
10/03/14 08:00:00
またえらい細かいオーダーで削ってるんだなぁ。
PCのWindowsでそこまでカツカツ削っても、すぐに時代変わっちゃうと思うけどなぁ。
他のとこに力入れた方が良くね？
まぁ、トレースキャッシュとか気にしてるから、何か特殊な固定環境向けのガリガリな
チューニングなのかもしれないけど。
俺も低レベルは好きだから、とりあえず触ることで知識と感覚を深めたい、ってんなら
止めないけど。単にバランス感覚の欠けてるケースに見えてしまうが。違ったらすまん。
351:デフォルトの名無しさん
10/03/14 08:19:21
>>349
分岐予測メモリはCore i7の場合物理コアごとに持ってるからスレッドごとに物理コアを違える場合は何も悩む必要はない
問題なのはスレッドの数が物理コア数より多いとか、同一物理コア内でのHTの場合(→341の下から3行目参照)
352:デフォルトの名無しさん
10/03/14 08:30:59
ハッよく考えたら>348-349のロジックじゃあHTの場合が解決してねーじゃんorz
同一コア内で走るHT0とHT1は、ハードウェアレベルで演算ユニット、L1, L2キャッシュ、トレースメモリを奪い合うので
もし仮に分岐予測メモリのタグがアドレスのみから生成され、HT番号では区別されない作の場合問題になりえる
ただしまあ現実的には同じアドレスに配置された同じ条件分岐命令が
1. HT0とHT1でほぼ同時に（=分岐予測結果の平均寿命(おそらく数μsec)オーダーの時間差内に）実行されるという状況が
2. 片方は分岐、片方は非分岐で
3. 無視し得ない頻度で反復される
というケースでのみ問題だが
>>350
というわけでWindows非依存な話
353:デフォルトの名無しさん
10/03/14 08:32:37
>>352
いや本人がWindows7を対象にしてるって最初に言ってるから
354:デフォルトの名無しさん
10/03/22 00:57:55
>>342
亀だが、それは条件変数の使い方を間違えとる
いきなり無条件でcond_waitで待ってはいかん
cond_waitは、あくまで「共有条件が望む状態になっていない時」に使うものだ
cond_wait時に指定するmutexは、その「共有条件」をテストするためのものだ
でもってcond_signalやcond_broadcastは、共有条件の変更があったことを通知して、共有条件の再テストの機会を与えるものだ
なお、cond_signal, cond_broadcastの実行そのものには、mutexの取得は必要ない
JMなんかのpthread_cond_initのmanページを見て、使用例を確認すると良い
355:デフォルトの名無しさん
10/03/27 11:48:41
pthreadの記事を見つけたので読んでたら、
なんかコメントで色々指摘が入ってるんだけど、どうなの？
URLﾘﾝｸ(codezine.jp)
356:デフォルトの名無しさん
10/03/27 15:08:07
ここのコメント欄みづらいんだよね
最初の「必要以上に複雑になってる」という指摘は同意。
この記事って、バグのあるコードをだんだん直していくっていう
流れだけど、そもそもタイトルの条件変数関係ないバグだし、
修正内容も、なんか泥沼に入っていくような感じ
その後のやりとは、この二人にしか分からないどうでもいいことについて、
どうでもいいやりとりしてるように見えた。
357:デフォルトの名無しさん
10/03/27 15:20:18
>>338
これはわかりやすい！
358:デフォルトの名無しさん
10/03/29 23:05:41
「Java並行処理プログラミング」が増刷してる
359:デフォルトの名無しさん
10/04/18 10:57:03
va_argsってスレッドセーフですか？
360:デフォルトの名無しさん
10/04/18 21:21:11
va_list を自動変数やTLBに置いていれば、va_listをスレッド間で共有しない限りは、スレッドセーフだと思うぞ。
361:デフォルトの名無しさん
10/04/18 22:11:15
>>360
嘘ついちゃだめ
va_listはプロセスで１つだけしか持てないから
スレッドセーフじゃないよ
362:デフォルトの名無しさん
10/04/19 00:34:37
ボナンザ８コア対応を１６コア対応にする方法を教えて下さい。