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

■前スレ
マルチスレッドプログラミング相談室 その7
http://pc12.2ch.net/test/read.cgi/tech/1215253576/

■過去スレ
その1 ttp://pc3.2ch.net/tech/kako/997/997345868.html
その2 ttp://pc5.2ch.net/test/read.cgi/tech/1037636153/
その3 ttp://pc8.2ch.net/test/read.cgi/tech/1098268137/
その4 ttp://pc8.2ch.net/test/read.cgi/tech/1130984585/
その5 ttp://pc11.2ch.net/test/read.cgi/tech/1157814833/
その6 ttp://pc11.2ch.net/test/read.cgi/tech/1187008532/

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

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

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

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

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

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

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

13 :デフォルトの名無しさん:2009/09/22(火) 00:08:35
lock-free queueって、計算処理は非常に重いけど、スレッドモデルとしては
比較的単純なケース(マスタ-スレーブモデル)に利用されるものなのかな?

たとえば動画エンコ/3Dレンダ/科学計算といった応用のように、
親スレッドが複数の子スレッドを生成し、各子スレッドが計算処理を実行し、
結果をlock-free queueに追加していく。親スレッドはjoinですべての計算の
終了を待ち、joinから抜けたらqueueから順に計算結果を取り出す...みたいな。
このモデルだと、スレッド間の同期なんて考える必要はまったく無い。

>>3の生産者-消費者モデルというのは、スレッド間同期の代表的な題材だから、
lock-free queueの話題とするのは、そもそも畑違いであると。

lock-free queueについては分かっていないので、有識者の指摘たのむ。

14 :13:2009/09/22(火) 01:44:44
(>>13の続き)

あるいは、>>13の応用ならリアルタイム性は要求されず、しかも
計算処理が(親スレッドの処理よりも相対的に)重いという前提があるから、
親スレッドは全子スレッド群の終了を(joinで)待ってから再開しなくても、
pollingで定期的にqueueから計算結果を取り出し、ゆっくりと
計算処理の進捗状況に合わせて出力(画面表示)していく方法だってある。
これもスレッド間の同期は考えなくてもいい。

なにかlock-free queueの利用イメージが見えたような気がするのは漏れだけ?
lock-free queue専門家からすれば「何を今更、そんなの常識」な話なのかな?

15 :デフォルトの名無しさん:2009/09/22(火) 02:22:42
そういう使い方はたぶん一般的だろうと思う
一対一の一方通行queueを双方向に張って適当にポーリングして同期っぽいことも
やれるし

ただ、汎用性をちょっと変えただけで実装が変わるから、結局バスロックするような
queueもあるだろうし、その辺ひっくるめてまとめて語るほどの経験は無いし

32 :デフォルトの名無しさん:2009/09/22(火) 21:59:00
もしかして、lock-free, wait-freeの "wait" を
sleep()とかyield()とかのことだと勘違いしている奴がいるんじゃないか?

35 :デフォルトの名無しさん:2009/09/22(火) 23:35:51
>>32
lock-free queueとは、スレッド間で共有するキューがあっても、
そのアクセスに「lock操作そのものが不要(free)」なキューである。

これは分かる。

では、wait-free queueとは、スレッド間で共有するキューがあり、
たとえそのキューが空であっても「wait操作そのものが不要(free)」な
キューである。

うーみゅ、どうやって実装しているんだ?それとも何か勘違いしてる?
分かんねーーーヨ....orz

40 :デフォルトの名無しさん: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なの?

43 :35:2009/09/23(水) 06:49:21
>>40
レスありがトン。詳しい解説は、とても助かる。

欲しいのは、待機が可能なwait-free queueの実装クラスです。

この場合には、ConcurrentLinkedQueueでキューを生成し、
nullあるいは例外発生であればスレッドを(たとえばwait操作で)待機させるよう
アプリケーション側で実装することになるのでしょうか?
スレッドを待機させる方法はwait操作以外にもいろいろあるから、
どの方法を選ぶかはアプリケーションにまかせる、という考え方になります。

wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、
「wait操作を実装していないキュー」の意味に思えてきました。

こんな感じで合っていますか?

45 :デフォルトの名無しさん: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()でもない。

55 :35: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 :デフォルトの名無しさん:2009/09/23(水) 13:37:41

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

57 :35: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が同期に利用できないと
考えているわけではありません。

59 :デフォルトの名無しさん:2009/09/23(水) 17:49:20
CASとスピンは違うよ。スピンはロック解除待ちのループ。CASは更新中に割り込まれた場合のリトライ。
lock-freeの待ち時間は、よっぽどの酷い競合が起きたときに発生するにすぎない。一般的なアプリでは問題にならない。
そのような競合が起きるのは設計が悪いと思われる。


60 :デフォルトの名無しさん:2009/09/23(水) 18:05:46
>>55
http://www.ddj.com/hpc-high-performance-computing/208801974 これは?
俺はよく解んないからboost.threadのshared_mutexでmultiple-reader/single-writerやってるよ
マルチスレッドは奥が深いなぁ

69 :35:2009/09/23(水) 23:21:08
>>59
CASとスピンとで内部の実装方法が異なるのは分かります。

# その意味では、>>57は以下のように訂正したほうがよいかもしれませんね。
#
# X:利用できるように見えるのですが、実際にはスピンによる実装なので、
# O:利用できるように見えるのですが、実際にはCASやスピンによる実装なので、
#
# X:もちろん、スピンが許されるケースや、
# O:もちろん、CASやスピンが許されるケースや、

ただ、>>3が指摘した生産者-消費者モデルで生産時間<<消費時間な場合を除き、
言い換えると生産時間>消費時間な場合、大半の状態でキューは空(から)のままです。
その場合、(キューを読み出す側の)消費者スレッドは、どのようにして待てば
よいのでしょうか?CPUを無駄にせず、いかにリトライをループさせるのでしょうか?
たとえば一般的なアプリケーションのキー入力「待ち」はCASやスピンで実装できますか?

実は、生産者-消費者モデルに関する同じような疑問は>>3だけでなく、前スレでも
たびたびカキコされていたのですが、レスがないか、あっても消費者スレッドを
待たせる方法に関する説明が無く、ずっと考え込んでいました。それが、>>45のレスで
クリアになったので、生産者-消費者モデル実現の前提となるスレッド間の「同期」に
ついては、lock-free/wait-freeは使えないと判断できました。

もちろん生産者-消費者モデルであっても、スレッド間の共有キューへの「排他(競合対策)」
については、lock-free/wait-freeを使用できます。一時的な待ちへの対応ですから。
スレッド間の「同期」と「排他」を意識的に区別して使い分けていることに注意してください。

79 :35: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: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ではない、とする考え方です。
難しい論争で、技術的な課題でもありませんから、私もこれ以上の考察は止めにします。

111 :デフォルトの名無しさん:2009/10/01(木) 09:08:46
見よう見まねでスピンロック実装して動作テストしたら標準のCriticalSectionより劇おそだったのは苦い思い出:プライスレス(´・ω・`)

112 :デフォルトの名無しさん:2009/10/01(木) 10:15:16
Win32のCriticalSectionの激速の理由は
プロセッサを判定して、可能ならばunlockにmovを使ってバスロックを避けているから

と俺は勝手に想像している。

114 :234:2009/10/01(木) 20:17:23
>>112
コンテキストスイッチが無いときはカーネルに入らずに、単にロックカウントをアップしてるだけだからだよ。


115 :デフォルトの名無しさん:2009/10/01(木) 21:48:37
>>114
いやそんなの当たり前だし。

「単純なスピンロックより速い(>>111)」理由が何故か?だよ。論点は。

193 :デフォルトの名無しさん:2009/11/05(木) 12:32:06
win32のインターロックをクリティカルセクションと
同じように使ったら早くて驚いた。

両者の内部的な違い・利点・欠点てなんですかね?

226 :デフォルトの名無しさん:2009/12/22(火) 22:31:16
読み込みと書き込みが1スレッドずつの場合でもメモリ破壊って起きるのでしょうか?

たとえば、ある変数をメインスレッドで読み込み続け、
複数のサブスレッドで、クリティカルセクションを用い、書き込むといった場合です

234 :デフォルトの名無しさん:2009/12/23(水) 11:15:37
昔使ったタイマ LSI でラッチ→lo-read→hi-readって
いう約束ごとのあるやつがあったな。hi-readでラッチ
が外れる奴。word-read 命令が使えるかどうかは CPU
次第。

235 :デフォルトの名無しさん:2009/12/23(水) 12:47:17
>>226
ハードや操作による。
つーか、まずは「アトミックな操作」という概念をどっかで調べとけ。

例えば、x86のCPUなんかだと、どういう操作がアトミックかはIntelが規定している。
アトミックな書き込みなら、別のコアからの読み込みが割り込む可能性は無い。逆に
アトミックでない書き込みなら、例えば半分くらい書き込んだところで別のコアが
読み込む可能性があるということ。
x86なら、厳密な規定はIntelの英語版サイトに落ちてる。32bitアラインドなreadや
writeは確実にアトミックだ。相当古いx86以外はキャッシュアラインドなら大丈夫。
read-modify-writeはLOCKプリフィクスが無い限りアトミックではないが、xchg
命令はLOCK#が自動的にアサートされるのでアトミックだ。
まぁ、アセンブラを直接叩くんじゃなければ、イントリンシック命令を調べておけば
十分だが、その裏でどういうCPUの動きをしているかは理解しといた方がいい。

つーか、低水準の話と高水準の話で全然違いすぎるんだよな。俺はどっちの話でも
構わんけど、分けた方がいいのか?

249 :デフォルトの名無しさん:2009/12/31(木) 15:09:39
何をもって高性能とするかをはっきりさせたいな
シングルコア100%アイドル3コアでできることを4コア25%ずつで処理することに意味はあるの?

326 :デフォルトの名無しさん:2010/02/22(月) 16:37:56
begintreadexを使ったときはclosehandleを使わないといけないらしいけど
CloseHandle((HANDLE)_beginthreadex());
こんな感じでいいの?

465 :デフォルトの名無しさん:2010/10/02(土) 10:56:16
たぶん、データが化ける可能性があると思う。
386SX以外にも、68000とか8088とかがその系統だったと思うし
今後も組み込み向けとかにそういうのが出てこないとは言い切れない。

だから、「intなら大丈夫」じゃなくて「intなら普通は大丈夫」程度。

とはいえ、組み込み向けのバス幅制限があるような環境では
マルチスレッドはともかく、
マルチプロセッサ/マルチコアはまずありえないと考えて良いんじゃないかな。

606 : ◆0uxK91AxII :2011/06/25(土) 18:39:30.70
Win32のCRTにある_beginthread。
生成は0.1[ms]未満、実行開始はコンパイラかライブラリに依存で0.1[ms]台からに訂正。

#include <Windows.h>
#include <stdio.h>
#include <process.h>
struct perf {LARGE_INTEGER freq;LARGE_INTEGER t0;};void __cdecl thread(void *
pArg){perf *pperf;LARGE_INTEGER t1, d;QueryPerformanceCounter(&t1);pperf = (perf
*)pArg;printf("thread: %I64d\n",t1.QuadPart-pperf->t0.QuadPart);}int main(){
LARGE_INTEGER f={0}, t0, t1, d;perf perf;QueryPerformanceFrequency(&f);printf(
"freq: %I64d\n", f.QuadPart);perf.freq = f;QueryPerformanceCounter(&t0);perf.t0
= t0;_beginthread(thread, 0, &perf);QueryPerformanceCounter(&t1);printf(
"main: %I64d\n", t1.QuadPart-t0.QuadPart);Sleep(1000);return 0;}

607 :デフォルトの名無しさん:2011/06/25(土) 22:55:22.93
>>606
5764ticks/272758=2.1ms。
一桁違ってないか?どんだけ速いマシン使ってんの

678 :デフォルトの名無しさん:2011/09/15(木) 12:18:55.76
C# よく分かんないけど、変数をまとめたクラス

class Vars {
  int a, b, c, ...;
  static Vars instance;
}

があって、更新側

Vars v = new Vars();
v.a = aaa;  // 1
v.b = bbb;  // 2
v.c = ccc;  // 3
...
Vars.instance = v;  // 4

これで 1 ?? 3 の順番が入れ替わるのは許せるけど、
1 ?? 3 と 4 の順番が入れ替わるのってありなの? まじ???


http://hibari.2ch.net/test/read.cgi/tech/1253521167/l50人気ブログランキングへ