[過去ﾛｸﾞ]
マルチスレッドプログラミング相談室 その8 (1001ﾚｽ)
マルチスレッドプログラミング相談室 その8 http://peace.5ch.net/test/read.cgi/tech/1253521167/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
35: デフォルトの名無しさん [sage] 2009/09/22(火) 23:35:51 >>32 lock-free queueとは、スレッド間で共有するキューがあっても、 そのアクセスに「lock操作そのものが不要(free)」なキューである。 これは分かる。 では、wait-free queueとは、スレッド間で共有するキューがあり、 たとえそのキューが空であっても「wait操作そのものが不要(free)」な キューである。 うーみゅ、どうやって実装しているんだ？それとも何か勘違いしてる？ 分かんねーーーヨ....orz http://peace.5ch.net/test/read.cgi/tech/1253521167/35
40: デフォルトの名無しさん [sage] 2009/09/23(水) 00:45:03 >>35 キューが空ならnullを返したり例外を投げたりすればいい。 たとえばJavaでは、要素が空のときにnullを返したりする Queue と、 要素が空のときに新たな要素が来るまで待機する操作がある BlockingQueue とが、 ちゃんと区別されている。 で、Queueにはwait-freeな実装クラス ConcurrentLinkedQueue があるけど、 BlockingQueueの実装クラスである LinkedBlockingQueue や ArrayBlockingQueue とかは wait-freeでもlock-freeでもない。 で、君が欲しいのは Queue なの? BlockingQueueなの? http://peace.5ch.net/test/read.cgi/tech/1253521167/40
43: 35 [sage] 2009/09/23(水) 06:49:21 >>40 レスありがトン。詳しい解説は、とても助かる。 欲しいのは、待機が可能なwait-free queueの実装クラスです。 この場合には、ConcurrentLinkedQueueでキューを生成し、 nullあるいは例外発生であればスレッドを(たとえばwait操作で)待機させるよう アプリケーション側で実装することになるのでしょうか？ スレッドを待機させる方法はwait操作以外にもいろいろあるから、 どの方法を選ぶかはアプリケーションにまかせる、という考え方になります。 wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、 「wait操作を実装していないキュー」の意味に思えてきました。 こんな感じで合っていますか？ http://peace.5ch.net/test/read.cgi/tech/1253521167/43
45: デフォルトの名無しさん [sage] 2009/09/23(水) 11:23:13 >>43 > 欲しいのは、待機が可能なwait-free queueの実装クラスです。 「待機が可能な」ってことは BlockingQueue が欲しいってことだね。 BlockingQueueの実装方法は2つ。 ・待機しないQueueを用意し、要素が空だったらスピンしまくる。 ・「キューが空でない」という条件変数を用いたモニタ同期を組み込む。 前者は明らかにCPUの無駄遣い。 後者はlock-freeでもwait-freeでもない。 てことで、>>40にも書いたようにJavaのBlockingQueueの実装クラスが wait-freeでもlock-freeでもないのは、手抜きしているわけではなく そのように実装するのが不可能だからだ。 > wait-free queueの意味が「wait操作そのものが不要なキュー」(>>35)ではなく、 > 「wait操作を実装していないキュー」の意味に思えてきました。 だからそれは "wait-free" って言葉の意味を誤解してるって。 "wait-free" の wait とは、モニタ同期のwait()操作とかとは別物。 もちろん、sleep()とかyield()でもない。 http://peace.5ch.net/test/read.cgi/tech/1253521167/45
55: 35 [sage] 2009/09/23(水) 13:27:30 >>45 >てことで、>>40にも書いたようにJavaのBlockingQueueの実装クラスが >wait-freeでもlock-freeでもないのは、手抜きしているわけではなく >そのように実装するのが不可能だからだ。 明解な説明です。理解できました。 >だからそれは "wait-free" って言葉の意味を誤解してるって。 >"wait-free" の wait とは、モニタ同期のwait()操作とかとは別物。 そのモニタ同期のwaiti()操作をイメージしていました。間違っていたんですね。 でわ、wait-freeの意味は、単純に「待ちが発生しない」へ改めます。 となると、lock-freeの意味も「待ちが発生する」に変わります。 ただし、どちらも「lock操作は不要」という特徴は共通している、と。 これでスッキリしました。 実は>>13,14,23のカキコ主だったのですが、lock-freeでは生産者-消費者モデルを 実現できない(畑違いである)ことが分かったので、次はwait-freeをと考えていましたが、 それも同様に誤解であることが理解できました。lock-free/wait-freeはスレッド間同期を 実現するプリミティブではない。それを実現するには、(lock操作を伴う)mutexや モニタ同期(signal/wait)などを導入する必要がある、と。 lock-free/wait-freeの使い方について、ここ数日で急速にイメージが掴めてきた感覚です。 たいへんありがとうございました。>>all(特に>>15,32,40,45) 後は、Javaだけでなく、C/C++でも利用できる一般的なlock-free/wait-freeの実装技法が 確立し、標準ライブラリとして仕様化されることを願っています。 http://peace.5ch.net/test/read.cgi/tech/1253521167/55
57: 35 [sage] 2009/09/23(水) 14:30:47 >>56 lock-free queueは「待ちが発生する」キューなので、スレッド間同期に 利用できるように見えるのですが、実際にはスピンによる実装なので、 「一般的な」アプリケーションでは利用できないと考えました。 言い換えると、lock-free queueだけで(mutexやモニタを一切使わずに) 「一般的な」アプリケーションを開発することは、現実的ではないという判断です。 もちろん、スピンが許されるケースや、mutexなどのオーバヘッドさえも 問題視される環境下では、lock-free queueを使わざるをえないケースも 存在していることは承知しています。あるいは、パフォーマンスクリティカルな 部分だけをlock-free queueで同期させ、残る大半ではmutexを使う設計も あるでしょう。論理的にlock-free queueが同期に利用できないと 考えているわけではありません。 http://peace.5ch.net/test/read.cgi/tech/1253521167/57
58: 35 [sage] 2009/09/23(水) 14:39:25 (>>57に追記) >>57の「一般的なアプリケーション」というのは、 生産者-消費者モデルで設計された、言い換えるとスレッド間同期が 前提となるマルチスレッドアプリケーションのことを指します。 たとえば>>13,14のアプリケーションではスレッド間同期が 必要ありませんから、lock-free queueを使用することができます。 （もちろんwait-free queueも使用できます。） http://peace.5ch.net/test/read.cgi/tech/1253521167/58
69: 35 [sage] 2009/09/23(水) 23:21:08 >>59 CASとスピンとで内部の実装方法が異なるのは分かります。 # その意味では、>>57は以下のように訂正したほうがよいかもしれませんね。 # # Ｘ：利用できるように見えるのですが、実際にはスピンによる実装なので、 # Ｏ：利用できるように見えるのですが、実際にはCASやスピンによる実装なので、 # # Ｘ：もちろん、スピンが許されるケースや、 # Ｏ：もちろん、CASやスピンが許されるケースや、 ただ、>>3が指摘した生産者-消費者モデルで生産時間<<消費時間な場合を除き、 言い換えると生産時間>消費時間な場合、大半の状態でキューは空(から)のままです。 その場合、(キューを読み出す側の)消費者スレッドは、どのようにして待てば よいのでしょうか？CPUを無駄にせず、いかにリトライをループさせるのでしょうか？ たとえば一般的なアプリケーションのキー入力「待ち」はCASやスピンで実装できますか？ 実は、生産者-消費者モデルに関する同じような疑問は>>3だけでなく、前スレでも たびたびカキコされていたのですが、レスがないか、あっても消費者スレッドを 待たせる方法に関する説明が無く、ずっと考え込んでいました。それが、>>45のレスで クリアになったので、生産者-消費者モデル実現の前提となるスレッド間の「同期」に ついては、lock-free/wait-freeは使えないと判断できました。 もちろん生産者-消費者モデルであっても、スレッド間の共有キューへの「排他(競合対策)」 については、lock-free/wait-freeを使用できます。一時的な待ちへの対応ですから。 スレッド間の「同期」と「排他」を意識的に区別して使い分けていることに注意してください。 http://peace.5ch.net/test/read.cgi/tech/1253521167/69
79: 35 [sage] 2009/09/24(木) 11:56:35 >>60 記事の紹介、ありがとうございます。読んでみました。 記事では、C++でlock-freeを使って生産者-消費者モデルを実現していますね。 以下はすべてC++のWaitFreeQueueクラスとして実装されています。 ・まずlock-freeで「排他」を実現するキューを実装。 この時点では「排他」だけですから、スレッド間の「同期」は実現できていません。 ・次に、キューが空である間、消費者スレッドをループさせ続けることで「同期」を実現。 この方式では、キューが空であればCPUを100%消費します。 ==> NATIVE_POOLING方式 ・続いて、キューが空である間、消費者スレッドをスリープさせ続けるループを 組むことで「同期」を実現。 ==> SLEEP方式 ・最後に、BOOSTのcondition(timed_wait/notify操作)を使う事で、 「同期」を実現。==> TIME_WAIT方式 (続く) http://peace.5ch.net/test/read.cgi/tech/1253521167/79
80: 35 [sage] 2009/09/24(木) 11:59:49 (>>79の続き) このC++ by DDJ実装と、>>40が紹介してくれたJavaの実装とを比較すると、 lock-free/wait-freeの意味に違いがあるように感じられました。 C++ by DDJ実装のTIME_WAIT方式は、JavaであればBlockingQueueクラスに相当しますが、 >>40では、BlockingQueueクラスは(同期の実現はモニタ使用が前提だから) lock-free/wait-freeではない、と定義しています。 これらの一見矛盾しているように見える事柄を、自分なりに以下のように解釈してみました。 ・lock-free/wait-free単独では「同期を実現できない」 ・ただし、lock-free/wait-freeとスリープ(あるいはモニタ/conditionなど)とを組み合わせた制御を アプリケーション側で(たとえばクラスとして)実装することで「同期を実現できる」 誰も皆「排他」に関しては「実現できる」と見解は一致していますが、 この「同期」が「実現できる/できない」という解釈に関しては、人によって見解が 分かれているように思えます。違いは、「スリープ/モニタ/conditionなど」の使用を含めて 「できる」とする考え方と、それらは純粋なlock-free/wait-freeではない、とする考え方です。 難しい論争で、技術的な課題でもありませんから、私もこれ以上の考察は止めにします。 http://peace.5ch.net/test/read.cgi/tech/1253521167/80
81: 35 [sage] 2009/09/24(木) 12:10:08 >>70 レスありがとうございます。 >>80の最後で書いたように、lock-free/wait-freeとスリープとを組み合わせた制御を アプリケーション側で実装することによって「同期」は実現できますね。 # せっかく>>60がDDJの記事を紹介してくれていたのに、それを読まずに>>69を # カキコしてたのが、まずかったと反省しています。余計な手間をとらせてごめんなさい。 http://peace.5ch.net/test/read.cgi/tech/1253521167/81
83: 35 [sage] 2009/09/24(木) 14:21:36 >>82 (CASやスピンを用いた)lock-free単独による同期については、メニーコア、 あるいはその先(未来)にある超並列な世界であれば、並列システム全体から 見ると個々のコア(CPU)の無駄は無視できます。だから、その時代になれば 「lock-free単独による同期が常識」となっている可能性は十分に予測できます。 もしかすると、現在でも>>82が主張されているMP(?)向け用途、それに HPC(High Preformance Computing)やCELLのプログラマにとっては、 既に「lock-free単独による同期は常識」なのかもしれませんね。 ただし、現在のPC向け汎用CPUはシングルコアかせいぜい4コアが主流です。 その世界では、いかに個々のコアを無駄無く使いつぶすかが、 性能設計上の大きな課題になります。ですから、現時点では、 「lock-free単独による同期は一般的ではない」、言い換えると、 一般アプリケーションにおいては「スリープなどと組み合わせない限り (単独の)lock-freeでは同期は実現できない」と解釈しています。 論理的にはCASやスピンでも同期は実現可能である(立派な同期である)。ただし、 一般的な多くのケースにおいては、その方式は現実的ではないということです。 これもまた「できる/できない論争」の一種ですよね。 http://peace.5ch.net/test/read.cgi/tech/1253521167/83
85: 35 [sage] 2009/09/24(木) 14:51:24 >>84 同じ「待ち」でも、「排他(ロック)」と「同期」は別のものです。 「排他」による待ちは一時的です。もしもそれが長時間継続するようであれば、 それは「設計が悪い」のです(一般にはバグとして扱う)。 それに対して「同期」の継続時間は不定です。 最も長いケースでは、システム全体が終了するまで「待ち」状態が継続します。 また、共有キューを用いた「同期」を実現するには「排他」も必要です。 ただし、だからといって「排他」だけでは「同期」は実現できません。 「排他(ロック)」と「同期」を区別して、考え直してみてください。 lock-freeには「排他」機能があります。ですから「デュアルコアでさえ スピンを使う」ことはあります。でも、lock-freeを単独で「同期」に 用いるのは現実的ではないと言っています。 というか「できる/できない論争」は止めにしませんか？私はこれで降ります。 http://peace.5ch.net/test/read.cgi/tech/1253521167/85
99: 35 [sage] 2009/09/25(金) 02:21:30 >>87 lock-free queueを実装する視点であれば、その認識は間違っていないと思うよ。 >>90 >単純に、スピンロックやmutex等の排他制御、CASはそれぞれどういう時に便利ですか？ >って議論だったりする？ 自分はlock-free queueを使う立場だから、そういう視点で>>81まで議論を続けてきました。 で、その後から議論が拗れてしまったわけですね。 何が原因かを考えました。自分は、(共有キューの競合による破壊を防ぐ為の)「排他」制御の為に スピンを「使う」ことは「一般的である」けれど、キューが空の場合に「待つ」、いわゆる 「同期」の為にスピンを「使う」のは(汎用PC/CPUの世界では)「一般的ではない」という立場。 それに対して、いや、キューが空で「待つ」場合にも、スピンを「使う」のは(汎用PC/CPUの 世界であっても)「一般的である」というのが、相手の立場。 ある事柄に対して、それが「一般的である/ではない」という解釈は、一般常識論ですから、 それぞれの立場によって異なるのが当たり前です。そんな両者が納得できる結論を導くのは難しい。 だから、>>85では、これ以上議論を続けても不毛なので止めることを提案しました。 http://peace.5ch.net/test/read.cgi/tech/1253521167/99
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.027s