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

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

1:デフォルトの名無しさん
09/09/21 17:19:27
マルチスレッドプログラミングについて語るスレ

■前スレ
マルチスレッドプログラミング相談室その７
ｽﾚﾘﾝｸ(tech板)

■過去スレ
その１ URLﾘﾝｸ(pc3.2ch.net)
その２ｽﾚﾘﾝｸ(tech板)
その３ｽﾚﾘﾝｸ(tech板)
その４ｽﾚﾘﾝｸ(tech板)
その５ｽﾚﾘﾝｸ(tech板)
その６ｽﾚﾘﾝｸ(tech板)

OS・言語・環境は問わないが、それゆえ明記すべし。
テンプレ
【ＯＳ】
【言語】
【実行環境】
【その他特記する事項】

2:デフォルトの名無しさん
09/09/21 17:19:50
■関連スレ・関連性の高いスレ

【マルチコア】並列化について語る【使いこなせ】
ｽﾚﾘﾝｸ(tech板)

pthread地獄 part 2
ｽﾚﾘﾝｸ(unix板)

ネットワークプログラミング相談室 Port24
ｽﾚﾘﾝｸ(tech板)

3:デフォルトの名無しさん
09/09/21 20:58:08
>>993
> lock-freeをある程度かじれば分かるが、要素数もatomicじゃなくていいよ
> スレッド状態は特権リング内の管理だろうから内部の挙動はシラネ
> ユーザーレベルで言うなら、lock-free queueをスピン&スリープで待機するなら
> スレッド状態も持つ必要なし

spinlock なら普通はスリープじゃなくて再スケジュー
ルじゃないだろか。まぁいいけどさ。

でか、spinlock 使う位なら俺にとってはキュー操作と
一緒にやる作業の大きさで mutex にするか spinlock
にするかってだけの話になって、キュー自体にはやっぱ
り排他責務なんか持たせないなぁ…。

あ、「キューに特化するとキューの特性に沿ったとても
効率の良い spinlock 的な何かがある」ってこと?

それとも、生産者が一つ生産してキューに生産物を入れ
る度に上限数まで消費者スレッドを起こして、とかいう
生産時間<<消費時間な場合に使うわけ? 確かにこの場合
は有効そうだけど。

4:デフォルトの名無しさん
09/09/21 21:37:19
スレ立て乙

5:デフォルトの名無しさん
09/09/21 23:32:10
mutexとspinlockの使い分けが全く要らないと思ってるなら、単に畑違いだと思うよ…

6:デフォルトの名無しさん
09/09/21 23:34:52
>>3
普通にlock-free queueを全く分かってなくね？
アトミック操作も要らないタイプすら作れるんだが、何でキュー自体に排他機能とか
変な話になってるんだ。

7:デフォルトの名無しさん
09/09/21 23:43:16
>>6
>アトミック操作も要らないタイプすら作れるんだが
詳しく

8:デフォルトの名無しさん
09/09/21 23:47:28
ぶっちゃけ、新スレまで引っ張るなよと言いたい。
低水準の要る要らないなんて、まともに終わったためしが無い。

9:デフォルトの名無しさん
09/09/21 23:48:36
>>7
lock-free queueはメモリバリアだけで十分作れるよ。前提条件によるけど。

10:デフォルトの名無しさん
09/09/21 23:53:04
CAS無しでやる話とかは前スレで出てたな

11:デフォルトの名無しさん
09/09/21 23:53:42
>>9
大変失礼、そう言うことですね。
勘違いしておりました。

12:デフォルトの名無しさん
09/09/21 23:58:07
lock-free queueでスピンってspin-waitであってspin-lockじゃなくね
そもそも"lock-free"の意味的にlockする訳が

13:デフォルトの名無しさん
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 を教えるのかな？

次ページ