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

1 ：09/09/21 〜 最終レス ：11/12/14

マルチスレッドプログラミングについて語るスレ
■前スレ
マルチスレッドプログラミング相談室 その７
http://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・言語・環境は問わないが、それゆえ明記すべし。
テンプレ
【ＯＳ】
【言語】
【実行環境】
【その他特記する事項】

2 ：

■関連スレ・関連性の高いスレ
【マルチコア】並列化について語る【使いこなせ】
ttp://pc11.2ch.net/test/read.cgi/tech/1137540671/
pthread地獄 part 2
ttp://pc11.2ch.net/test/read.cgi/unix/1166620307/
ネットワークプログラミング相談室 Port24
ttp://pc12.2ch.net/test/read.cgi/tech/1246895188/

3 ：

>>993
> lock-freeをある程度かじれば分かるが、要素数もatomicじゃなくていいよ
> スレッド状態は特権リング内の管理だろうから内部の挙動はシラネ
> ユーザーレベルで言うなら、lock-free queueをスピン&スリープで待機するなら
> スレッド状態も持つ必要なし
spinlock なら普通はスリープじゃなくて再スケジュー
ルじゃないだろか。まぁいいけどさ。
でか、spinlock 使う位なら俺にとってはキュー操作と
一緒にやる作業の大きさで mutex にするか spinlock
にするかってだけの話になって、キュー自体にはやっぱ
り排他責務なんか持たせないなぁ…。
あ、「キューに特化するとキューの特性に沿ったとても
効率の良い spinlock 的な何かがある」ってこと?
それとも、生産者が一つ生産してキューに生産物を入れ
る度に上限数まで消費者スレッドを起こして、とかいう
生産時間<<消費時間な場合に使うわけ? 確かにこの場合
は有効そうだけど。

4 ：

スレ立て乙

5 ：

mutexとspinlockの使い分けが全く要らないと思ってるなら、単に畑違いだと思うよ…

6 ：

>>3
普通にlock-free queueを全く分かってなくね？
アトミック操作も要らないタイプすら作れるんだが、何でキュー自体に排他機能とか
変な話になってるんだ。

7 ：

>>6
>アトミック操作も要らないタイプすら作れるんだが
詳しく

8 ：

ぶっちゃけ、新スレまで引っ張るなよと言いたい。
低水準の要る要らないなんて、まともに終わったためしが無い。

9 ：

>>7
lock-free queueはメモリバリアだけで十分作れるよ。前提条件によるけど。

10 ：

CAS無しでやる話とかは前スレで出てたな

11 ：

>>9
大変失礼、そう言うことですね。
勘違いしておりました。

12 ：

lock-free queueでスピンってspin-waitであってspin-lockじゃなくね
そもそも"lock-free"の意味的にlockする訳が

13 ：

lock-free queueって、計算処理は非常に重いけど、スレッドモデルとしては
比較的単純なケース(マスタ-スレーブモデル)に利用されるものなのかな？
たとえば動画エンコ/3Dレンダ/科学計算といった応用のように、
親スレッドが複数の子スレッドを生成し、各子スレッドが計算処理を実行し、
結果をlock-free queueに追加していく。親スレッドはjoinですべての計算の
終了を待ち、joinから抜けたらqueueから順に計算結果を取り出す...みたいな。
このモデルだと、スレッド間の同期なんて考える必要はまったく無い。
>>3の生産者-消費者モデルというのは、スレッド間同期の代表的な題材だから、
lock-free queueの話題とするのは、そもそも畑違いであると。
lock-free queueについては分かっていないので、有識者の指摘たのむ。

14 ：

(>>13の続き)
あるいは、>>13の応用ならリアルタイム性は要求されず、しかも
計算処理が(親スレッドの処理よりも相対的に)重いという前提があるから、
親スレッドは全子スレッド群の終了を(joinで)待ってから再開しなくても、
pollingで定期的にqueueから計算結果を取り出し、ゆっくりと
計算処理の進捗状況に合わせて出力(画面表示)していく方法だってある。
これもスレッド間の同期は考えなくてもいい。
なにかlock-free queueの利用イメージが見えたような気がするのは漏れだけ？
lock-free queue専門家からすれば「何を今更、そんなの常識」な話なのかな？

15 ：

そういう使い方はたぶん一般的だろうと思う
一対一の一方通行queueを双方向に張って適当にポーリングして同期っぽいことも
やれるし
ただ、汎用性をちょっと変えただけで実装が変わるから、結局バスロックするような
queueもあるだろうし、その辺ひっくるめてまとめて語るほどの経験は無いし

16 ：

>>6
> 普通にlock-free queueを全く分かってなくね？
> アトミック操作も要らないタイプすら作れる
lock-free と wait-free を混同してね?

17 ：

wait-freeが作れるならlock-freeでもあるからいいんじゃね？

18 ：

>>6
是非作り方を教えてくれ。
アトミック操作もいらないなんて、君にとっては些細なことでも俺にとっては非常に大きな一歩なんだ。

19 ：

どう見ても「本当は知らないんだろ？」と煽ってるようにしか見えないが…
ちょっと真面目に考えてみろよ。書き手が単数の場合、アトミック操作は要るか？
メモリバリアだけで書けるだろ。wait-freeじゃなくてlock-freeなんだから、準備
できてない間は待ってて貰っていいんだぞ。
複数の書き手を作るには、ハブのようなスレッドを作ってスター型トポロジーに
すればいい。
つーか、コードを全部示さないと信用できないってんなら、信用されなくていい。
勝手に妄想家とでも思っててくれ。いちいち何から何まで言うつもりは無い。

20 ：

顔真っ赤にすんなよ＾＾；

21 ：

妄想乙

22 ：

>>19
> ちょっと真面目に考えてみろよ。書き手が単数の場合、アトミック操作は要るか？
ん、「書き手が単数」ってのはどこからわいてきた話だ?
こういうのは設計・実装に大きく影響する話なんだから、
勝手に仮定されると議論が成り立たないと思うぞ。
というか、読み手と書き手がそれぞれ一つずつって前提が置けるのであれば、
CASなしでwait-freeなキューを作るのは難しくないし。

23 ：

>>14
レスありがとうございます。まずは、マスタ-スレーブモデルは一般的だろうと
いうことで、lock-free queue勉強の一歩を進めることができます。
あと、>>14のポーリング方式はスレッドプールモデルにも適用できますね。
スレッドプールとポーリングの組み合わせたキーワードで考えると、
更にlock-free queueの応用範囲が広がる気がします。

24 ：

>>22
書き手が複数の場合どうするかも書いてあるだろ…

25 ：

>>24
「ハブのようなスレッドを作ってスター型トポロジー」みたいな構造は
もはや「書き手複数で使えるキュー」とは言えないと俺は思うがねえ…
「ハブのようなスレッド」がそれぞれの書き手と繋がったキューを
順次ぐるぐるとチェックして回るんだろ?
それだけでCPUの1コアの使用率が100%になっちまうじゃねえか。
で、読み手が複数の場合はどのように対処するんで?

26 ：

>>25
横だけど「ハブのようなスレッド」が渡して回るんじゃないの？
ほとんど(まったく？)lock-freeの利点が活きていないけど。

27 ：

前スレからの元々の流れ忘れてる奴多くね？
俺も忘れたけど

28 ：

まとめると、
書き手がひとつならアトミック不要、複数ならアトミック必要ですね。
読み手も同様

29 ：

>>27
そんな君たちに僕の質問を再度コピペしておこう
| メモリとかキャッシュとかレジスターとかバスとかマルチコア/プロセッサーが絡むと
| どうなっているのかよくわからないからいつもmutex頼みです
| これらのHW関連とマルチスレッドについて詳しく知りたい場合のよい方法を教えてください

30 ：

アセンブラでアトミック命令使ってみることをお勧めするであります。

31 ：

>>26
> 横だけど「ハブのようなスレッド」が渡して回るんじゃないの？
キューだよ? FIFOだよ?
2つの読み手R1とR2がいて、R1はガリガリ計算中、
R2がキューから次の要素が来るのを待っているって状態なら、
次の要素はR2に渡さないといけないんだよ?

32 ：

もしかして、lock-free, wait-freeの "wait" を
sleep()とかyield()とかのことだと勘違いしている奴がいるんじゃないか?

33 ：

と、このような有様ですので、lock-freeのライブラリなんかそうそう出回らないって訳です

34 ：

ｗｗｗ
俺以外全員馬鹿ｗｗｗｗｗ
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

35 ：

>>32
lock-free queueとは、スレッド間で共有するキューがあっても、
そのアクセスに「lock操作そのものが不要(free)」なキューである。
これは分かる。
では、wait-free queueとは、スレッド間で共有するキューがあり、
たとえそのキューが空であっても「wait操作そのものが不要(free)」な
キューである。
うーみゅ、どうやって実装しているんだ？それとも何か勘違いしてる？
分かんねーーーヨ....orz

36 ：

lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。
wait-freeはロックがかからないし、一定時間で完了する。
でいいのかな？

37 ：

>>36
いいんじゃないかな

38 ：

>>36
> lock-freeはロック（mutexとか）がかからないけどCASなど無限時間の可能性がある。
CASで失敗したときは操作を繰り返す、ってのは lock-free なの？
だとしたら、スピンロックは lock-free ってことになるよね？

39 ：

>>38
ロック変数をspinlockするのなら、それはlock-freeとは言えない

40 ：

>>35
キューが空ならnullを返したり例外を投げたりすればいい。
たとえばJavaでは、要素が空のときにnullを返したりする Queue と、
要素が空のときに新たな要素が来るまで待機する操作がある BlockingQueue とが、
ちゃんと区別されている。
で、Queueにはwait-freeな実装クラス ConcurrentLinkedQueue があるけど、
BlockingQueueの実装クラスである LinkedBlockingQueue や ArrayBlockingQueue とかは
wait-freeでもlock-freeでもない。
で、君が欲しいのは Queue なの? BlockingQueueなの?

41 ：

>>39
ロック変数をCASで変更しようとして失敗したらリトライってのはlock-freeではない。
リンクリストのポインタ変数とかをCASで変更しようとして失敗したらリトライってのはlock-freeである。
ってこと？

42 ：

>>41
うん

43 ：

>>40
レスありがトン。詳しい解説は、とても助かる。
欲しいのは、待機が可能なwait-free queueの実装クラスです。
この場合には、ConcurrentLinkedQueueでキューを生成し、
nullあるいは例外発生であればスレッドを(たとえばwait操作で)待機させるよう
アプリケーション側で実装することになるのでしょうか？
スレッドを待機させる方法はwait操作以外にもいろいろあるから、
どの方法を選ぶかはアプリケーションにまかせる、という考え方になります。
wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、
「wait操作を実装していないキュー」の意味に思えてきました。
こんな感じで合っていますか？

44 ：

LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。
もし読み手をwaitでブロックさせるなら文字通りlock-freeでもwait-freeにもならない。
その場合、書き手はブロックした読み手を起こすためにカーネルの世話になるのでlockが発生するかもしれない。

45 ：

>>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 ：

>>44
> LinkedListを使ってキューを作るならCASを使うのでlock-freeだがwait-freeにならない。
CASを使った wait-free なQueueの実装はあるよ。
http://java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html

47 ：

連結リスト使うくらいなら別にmutexでも、と思いかけたが、mutexは格段に重いから
そうも言えないか

48 ：

>>47
> mutexは格段に重いから
Win32のmutexが無駄に重いだけ。
最近のOSが用意しているmutexなら、競合がない場合のコストは
ロックとアンロックそれぞれで高々CAS一回分程度。

49 ：

なら連結リストよりmutexの方がいい場面は多そうだな、Windows以外は

50 ：

Win32のmutexはプロセスレベルじゃなくてシステムレベル？
で排他してるから重いのはしょうがないかと・・

51 ：

>>50
ですな。
というか、一般的に言う "mutex" に相当するものを、
Win32では "Critical Section" と呼んでいるから
混乱を招いているだけなんだけど。

52 ：

W32はCSもMutexも両方Mutexで特性が違うと考えるのが自然

53 ：

プロセスレベルで排他するからじゃなくて、
カーネルオブジェクトなのが原因なんじゃね？

54 ：

目的がそうだからしょうがない

55 ：

>>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 ：

え
lock-free queueは同期にも使えるよね？

57 ：

>>56
lock-free queueは「待ちが発生する」キューなので、スレッド間同期に
利用できるように見えるのですが、実際にはスピンによる実装なので、
「一般的な」アプリケーションでは利用できないと考えました。
言い換えると、lock-free queueだけで(mutexやモニタを一切使わずに)
「一般的な」アプリケーションを開発することは、現実的ではないという判断です。
もちろん、スピンが許されるケースや、mutexなどのオーバヘッドさえも
問題視される環境下では、lock-free queueを使わざるをえないケースも
存在していることは承知しています。あるいは、パフォーマンスクリティカルな
部分だけをlock-free queueで同期させ、残る大半ではmutexを使う設計も
あるでしょう。論理的にlock-free queueが同期に利用できないと
考えているわけではありません。

58 ：

(>>57に追記)
>>57の「一般的なアプリケーション」というのは、
生産者-消費者モデルで設計された、言い換えるとスレッド間同期が
前提となるマルチスレッドアプリケーションのことを指します。
たとえば>>13,14のアプリケーションではスレッド間同期が
必要ありませんから、lock-free queueを使用することができます。
（もちろんwait-free queueも使用できます。）

59 ：

CASとスピンは違うよ。スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。
lock-freeの待ち時間は、よっぽどの酷い競合が起きたときに発生するにすぎない。一般的なアプリでは問題にならない。
そのような競合が起きるのは設計が悪いと思われる。

60 ：

>>55
http://www.ddj.com/hpc-high-performance-computing/208801974 これは？
俺はよく解んないからboost.threadのshared_mutexでmultiple-reader/single-writerやってるよ
マルチスレッドは奥が深いなぁ

61 ：

>>59
> スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。
スピンロックは観察対象がロックオブジェクトで、CAS
は操作対象そのもの。
スピンロックは失敗時にはクリティカル領域に居る競合
相手の処理を促進する意味もあって普通ディスパッチす
ると思う（悪くすると飢餓状態に陥る）けど、CAS は領
域がそもそも小さいのですぐにリトライして ok ってこと?
相当限定的な使い方しか出来ない気がするなぁ…。「ス
レッドの状態を気にしなくて良い」んじゃなくて、気に
できないんじゃないの?

62 ：

>>60
boostのshared_ptrもlock-freeで実装されていなかったっけ？
ヘッダ見ると幸せになれるかもね

63 ：

スピン(に限らず)ロックは、ロックされていたら解放されるまでただ待つしかない
ロック保持者が何か処理に手間取って (ページングとか、割り込みとかで) 時間を取られたら、
それに引きずられて後続が全部渋滞してしまう
lock freeは、相手がすでに処理に入ってても我関せずで自分も処理に入ってしまい、
相手が何か手間取ってたら自分の方が先にCASを勝ち取り、次の処理に進めるというのが強み
負けた方は残念ながら最初からやり直し、今までやったことが無駄になるが、
今戦ってた相手はもう去ったし、次はたぶん成功するんじゃね？
次々に相手が現れていつまでも負け続けるようなひどい競合状態なら、普通のロックの方が良いらしい
負けたら同じ処理をもう一度やり直さないといけないという無駄がどうしてもあるし

64 ：

>>63
そういうlock-freeもあるけど、単純にアトミックアクセスだけで済ます場合もlockが
無いならlock-freeって呼ぶし（boost::shared_ptrとかがまさにそれ）、その場合は
lock-freeと言ってもバスロックを使ったりしてるからややこしいんだが、要するに、
何があってもデッドロックしないアルゴリズムならlock-free、ということだと思って
いるんだが

65 ：

デッドロックはまたややこしい話になると思うから置いとくとして
そういうのはやっぱりwait freeに分類すべきじゃないかな
wait freeもlock freeの一種といえばそうなんだけど

66 ：

lock-free : ロックせずにアクセスできる
wait-free : lock-freeの条件を満たしており定数時間で処理が完了する事が保証される
だけでそれ以外の要素は各実装による・・・じゃねーの

67 ：

まぁ>>63と全然違う仕組みのlock-freeも色々あるよってことで

68 ：

> 何があってもデッドロックしないアルゴリズムならlock-free
俺はこれが一番合点がいった。(dead)lock-free なわけ
ね。
…しかし「たまたま動いてたプログラムがより堅実に動
くようになります」っていうのはかなり微妙なメリット
な気もする（w

69 ：

>>59
CASとスピンとで内部の実装方法が異なるのは分かります。
# その意味では、>>57は以下のように訂正したほうがよいかもしれませんね。
#
# Ｘ：利用できるように見えるのですが、実際にはスピンによる実装なので、
# Ｏ：利用できるように見えるのですが、実際にはCASやスピンによる実装なので、
#
# Ｘ：もちろん、スピンが許されるケースや、
# Ｏ：もちろん、CASやスピンが許されるケースや、
ただ、>>3が指摘した生産者-消費者モデルで生産時間<<消費時間な場合を除き、
言い換えると生産時間>消費時間な場合、大半の状態でキューは空(から)のままです。
その場合、(キューを読み出す側の)消費者スレッドは、どのようにして待てば
よいのでしょうか？CPUを無駄にせず、いかにリトライをループさせるのでしょうか？
たとえば一般的なアプリケーションのキー入力「待ち」はCASやスピンで実装できますか？
実は、生産者-消費者モデルに関する同じような疑問は>>3だけでなく、前スレでも
たびたびカキコされていたのですが、レスがないか、あっても消費者スレッドを
待たせる方法に関する説明が無く、ずっと考え込んでいました。それが、>>45のレスで
クリアになったので、生産者-消費者モデル実現の前提となるスレッド間の「同期」に
ついては、lock-free/wait-freeは使えないと判断できました。
もちろん生産者-消費者モデルであっても、スレッド間の共有キューへの「排他(競合対策)」
については、lock-free/wait-freeを使用できます。一時的な待ちへの対応ですから。
スレッド間の「同期」と「排他」を意識的に区別して使い分けていることに注意してください。

70 ：

適当にスリープに落とせばいいんじゃ？
カーネルにスケジューリングを任せるより効率は若干落ちるが、高負荷時を見れば
lock-freeの恩恵が受けられるから悪くないかと。
スレッド間通信がボトルネックの外にあるなら、好きな方法でいいと思われ。

71 ：

すみません初歩的な質問で申し訳ないのですが，ｍｕｔｅｘで排他制御された場合、例えば
ｍｕｔｅｘｌｏｃｋ()；
Ａ［0］ = 0;
mutexunlock();
の様な場合、スレッドＡはA[0]をアクセスして、スレッドBはA[100]をアクセスするとします。
その場合、スレッドBはスレッドAの処理が終わるまで配列Aにアクセスできないのでしょうか？

72 ：

>>71
そうなるね

73 ：

「の様な場合」なんていう他人に通じない省略しないで、
スレッドBの処理も書けばいいのに

74 ：

>>71
//ｍｕｔｅｘｌｏｃｋ()；
Ａ［100］ = ~0;
//mutexunlock();
:b

75 ：

>>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 ：

>>61
> 相当限定的な使い方しか出来ない気がするなぁ…。
> 「スレッドの状態を気にしなくて良い」んじゃなくて、
> 気にできないんじゃないの?
これ書いたの俺だけど、malloc() の内部処理辺りには
使えそうだと思った。それと類似して C++ の new() を
オーバーライドしといて予め準備しといたメモリプール
から取ってくるとかいうよくある奴。
例としてはそんなのでいいだろか? > 例を要求してた人

77 ：

>>75
その例の場合は素通り
配列が自動的にアクセス禁止になるわけではない
ThreadBもThreadCもmutexをロックしてどこからどこまで保護するのか明確にしなければならない

78 ：

>>77
ロックする範囲が限定されていれば、
他のスレッドは進行を妨げられずに処理できるのですね。
ありがとうございました。

79 ：

>>60
記事の紹介、ありがとうございます。読んでみました。
記事では、C++でlock-freeを使って生産者-消費者モデルを実現していますね。
以下はすべてC++のWaitFreeQueueクラスとして実装されています。
・まずlock-freeで「排他」を実現するキューを実装。
　この時点では「排他」だけですから、スレッド間の「同期」は実現できていません。
・次に、キューが空である間、消費者スレッドをループさせ続けることで「同期」を実現。
　この方式では、キューが空であればCPUを100%消費します。
　==> NATIVE_POOLING方式
・続いて、キューが空である間、消費者スレッドをスリープさせ続けるループを
　組むことで「同期」を実現。 ==> SLEEP方式
・最後に、BOOSTのcondition(timed_wait/notify操作)を使う事で、
　「同期」を実現。==> TIME_WAIT方式
(続く)

80 ：

(>>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 ：

>>70
レスありがとうございます。
>>80の最後で書いたように、lock-free/wait-freeとスリープとを組み合わせた制御を
アプリケーション側で実装することによって「同期」は実現できますね。
# せっかく>>60がDDJの記事を紹介してくれていたのに、それを読まずに>>69を
# カキコしてたのが、まずかったと反省しています。余計な手間をとらせてごめんなさい。

82 ：

リング遷移よりはスピンした方がいいとか、ある程度待っても何も来なかったら
スリープとか、待機時の特性をアプリケーションがチューニングするやり方に
なるのは、ハイパフォーマンス向けだと利点と言えるのでは。
まぁ、リング遷移が気にならない状況ならカーネルに任せていいと思うけど。
とりあえず、スピン待機は立派な同期だよ。CPU使用率をやけに気にしてるけど、
MP向けだとスピンじゃないと話にならないことも多い。

83 ：

>>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 ：

デュアルコアでさえスピンは使うって。
lock-free queueのcalleeが同期の機能を持ってるか、にこだわってるの？
callerが同期処理をしなきゃならない、だとしても、lock-freeで同期してることに
なると思うけど。そうじゃないなら、シーケンスロックはロックの機能を持たない
とかいう変な話になるぞ？
つーか、ノンブロッキング同期の一種だぞ、lock-freeもwait-freeも。

85 ：

>>84
同じ「待ち」でも、「排他(ロック)」と「同期」は別のものです。
「排他」による待ちは一時的です。もしもそれが長時間継続するようであれば、
それは「設計が悪い」のです(一般にはバグとして扱う)。
それに対して「同期」の継続時間は不定です。
最も長いケースでは、システム全体が終了するまで「待ち」状態が継続します。
また、共有キューを用いた「同期」を実現するには「排他」も必要です。
ただし、だからといって「排他」だけでは「同期」は実現できません。
「排他(ロック)」と「同期」を区別して、考え直してみてください。
lock-freeには「排他」機能があります。ですから「デュアルコアでさえ
スピンを使う」ことはあります。でも、lock-freeを単独で「同期」に
用いるのは現実的ではないと言っています。
というか「できる/できない論争」は止めにしませんか？私はこれで降ります。

86 ：

> 一般的な多くのケースにおいては、その方式は現実的ではないということです。
ここの認識が勘違いしてると思うけどなぁ。
まぁ降りるならどうぞ。

87 ：

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 ：

if(v.empty()){/*待機コード*/}
int i=v.pop();
例えばこれも同期

89 ：

ifじゃなくてwhileだった

90 ：

>>88
それって、Queueを使うためにmutexやスピンロック等を使った同期であって、
Queueを使った同期ではないような…
もし仮にそのことをQueueを使った同期と言っているのであれば、それとlock-free queueとは
関連性薄くない？(べつにbool値のflagだとしても議論できるし)
もしかしてQueueとかもう話題的にあんまり関係なくて、
単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？
って議論だったりする？

91 ：

>>88
empty()とpop()が別だから、複数スレッドだとrace conditionになるね。

92 ：

どう見てもmutexもスピンロックも使ってないし、empty()じゃなくなった後に
empty()がtrueにならないことが保証されてるqueueなら競合もしないよ

93 ：

お互いに勝手なコンテキストを想定して話すから、会話が成り立ってない。

94 ：

・読み手／書き手は単数なのか複数なのか
・一般例なのか状況限定の例なのか
・empty()はロックしないことを保証しているか（lock-freeならしているだろうけど）
こういう重要な条件をお互いに伝える気も読み取る気も感じられない。

95 ：

while (v.empty()){}
↑こういうコード(ある状態が真になるまでループする)がスピンロックなのかと思ってた。
>>92みると違うみたい？

96 ：

> こういう重要な条件をお互いに伝える気も読み取る気も感じられない。
念

97 ：

>>95
それロックじゃないでしょ

98 ：

空気読まずに lock-free C++ vector の論文貼るね。既出ならメンゴ。
ttp://www.research.att.com/~bs/lock-free-vector.pdf
2006 年、Bjarne Stroustrup も噛んでる。なかなか性能いいみたい。

99 ：

>>87
lock-free queueを実装する視点であれば、その認識は間違っていないと思うよ。
>>90
>単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？
>って議論だったりする？
自分はlock-free queueを使う立場だから、そういう視点で>>81まで議論を続けてきました。
で、その後から議論が拗れてしまったわけですね。
何が原因かを考えました。自分は、(共有キューの競合による破壊を防ぐ為の)「排他」制御の為に
スピンを「使う」ことは「一般的である」けれど、キューが空の場合に「待つ」、いわゆる
「同期」の為にスピンを「使う」のは(汎用PC/CPUの世界では)「一般的ではない」という立場。
それに対して、いや、キューが空で「待つ」場合にも、スピンを「使う」のは(汎用PC/CPUの
世界であっても)「一般的である」というのが、相手の立場。
ある事柄に対して、それが「一般的である/ではない」という解釈は、一般常識論ですから、
それぞれの立場によって異なるのが当たり前です。そんな両者が納得できる結論を導くのは難しい。
だから、>>85では、これ以上議論を続けても不毛なので止めることを提案しました。

100read 1read

1read 100read

TOP カテ一覧 スレ一覧 削除依頼 ▲
・　次のスレ
くだすれC++/CLI（初心者用）part2
Google NaCl プログラミング 2mol
【関数】Erlang Part 2【エリクソン】
【Scheme】Schemeインタプリタ Mosh Part1【Lisp】