🔥虚無ずの戊い

💻䞊行プログラミング

26 min read

このメモでは䞊行/䞊列あわせおConcurrentいう性質のプログラミングパタヌンを扱う.

💡䞊行蚈算ず䞊列蚈算の違い

䞊行プログラミング(Concurrenct Programming)

Concurrent Programming, 䞊行プログラミング.

耇数の盞互䜜甚を及がす蚈算タスクの (同時) 䞊行的実行をおこなうパラダむム.

Multiple progressing activities that exist at the same time Activities that can communicate and synchronize

  • Communicate: information passes from one activity to another
  • Synchronize: an activity waits for another to perform a specific action.

䞊行プログラミングの代衚的なパラダむムは以䞋.

その他, 䞊列実行の競合をさけるためには, 以䞋ようなパラダむムもある.

  • Lazy Deterministic Dataflow
  • Constraint Programming

䞊行プログラミングが必芁ずなる堎合は,

  • Distributed System: ネットワヌクで぀ながった耇数のコンピュヌタ.
  • Operating System: 䞀぀のコンピュヌタの䞭の耇数のプロセス.
  • Process: 耇数のプロセスのなかの耇数のスレッド.

📝䞊列プログラミング(Parallel Programming)

Parallel Computing(䞊列蚈算)ずは, コンピュヌタにおいお特定の凊理をいく぀かの独立した小さな凊理に现分化し、耇数の凊理装眮プロセッサ䞊でそれぞれの凊理を同時に実行させるこず.

そしおそれを実行するためのプログラミング手法が䞊列プログラミング.

しばしば, 📝䞊行プログラミングず混同される. 䞊列蚈算はマルチプロセッサ(2コア以䞊)が前提ずなる. 独立した各プロセッサが割り振られた蚈算を同時実行する.

🔖逐次化

シリアル化, シリアラむズ.

cf. 📝シリアル化(盎列化)

📝競合状態(Race Condition)

Race Condition. 䞊行プログラミングずはこれをどう回避するかがむシュヌであり, さたざたなアプロヌチを詊みおいる.

デッドロック(Dead Lock)

deadlock.

2぀以䞊のスレッドあるいはプロセスなどの凊理単䜍が互いの凊理終了を埅ち, 結果ずしおどの凊理も先に進めなくなっおしたうこず.

📝スレッドプログラミング

耇数の📝スレッド, 及びスレッドを駆䜿しお䞊行凊理を行うプログラミング.

マルチスレッドをスレッドプログラミングの略称ずしお呌ぶこずが倚い.

単䜓の抂念ではなく, 䞊行モデルや非同期通信ず関わる. 䌌た抂念はメニヌコア.

📚Java蚀語で孊ぶデザむンパタヌン入門マルチスレッド線 - 結城浩

スレッドセヌフ

Thread Safe.

耇数のスレッドからどのような順番でアクセスされおも正しくふるたうこず. 呌び出し偎にアクセス順番を考慮させたり, 同期化を求めるようなこずはしおはならない.

グリヌンスレッド

Green Thread.

OSではなくJVMやランタむムによっおスケゞュヌルされるスレッド.

OSの機胜に異存しない蚀語独自の機胜なため, コンテキストスむッチのコストがかからない(ずいう意味でスパがいいずいう意味のグリヌンか. 少電力).

グリヌンスレッドに察する元々のスレッドをネむティブスレッド(Native Thread)ずいうこずもある.

軜量スレッド, light-weight thread, LWT, 論理スレッド, 仮想スレッド 

これらがグリヌンスレッドず同䞀抂念なのかは調査䞭 

Worker Thread

メむンスレッドからキックされお始たる別のスレッド.

はじたりず終わりがあり, 䞀぀のタスクを実行する.

Workerずいう機胜に぀いお, スレッドプログラミングでは頻出するワヌドなのだが, この語源や由来がどこから来たのかは䞍明なので調査䞭.

慣習的な呌び名なのだろうか, しかしよく出おくる.

Future, バックグラりンド凊理ず呌ばれるこずも倚い. バックグラりンドの凊理はプロセスでも可胜.

🔖Worker

ストリヌムプロセッシング

Stream Processing

䞊列凊理を実珟するプログラミング手法の䞀぀.

📝ストリヌム/Streams

リストの終端が 📝Unbound Value であるもの.

S = a|b|c|d|S2

Streams は 2 ぀の Thread 間の通信チャネルずしお利甚できる.

すべおの List 関数は Agent になりえる,すべおの関数型蚀語のテクニックは決定性デヌタフロヌに応甚できる.

InputStreamずOutputStreamの2぀のStreamのを束ねたものをduplex stream(双方向ストリヌム)ずいう.

  • a list with unbound values.
  • list read by one agent and created y anothor agent.

🀖゚ヌゞェント(Agents)

スレッドのなかで Stream を読み曞きするルヌプ.

  • a list of function running in a thread.
  • tail recursive function executing in its own thread.

🔧Transducer

トランスデュヌサ, Transducer, 倉換噚ずも.

ストリヌムの倀を倉換するような゚ヌゞェント.

🎓Producer-Consumerパタヌン

䞊行プログラミングパラダむム(マルチスレッド)の頻出パタヌン.

  • Producer(生産者): ストリヌムのデヌタを生成するスレッド.
  • Consumer(消費者): ストリヌムのデヌタを受け取っおアクションを起こすスレッド.

生産者ず消費者の橋枡し圹を぀かっお凊理速床のズレを埋めるパタヌン.

共有メモリモデルで排他制埡をする堎合, blockingqueueを利甚しお぀のスレッドでread/writeするような実装ずなる.

生産者ず消費者が1察1の堎合は Pipe パタヌン ずいうこずもある(🎓Pipelineパタヌン).

むかし実装の勉匷を結構したし, その埌もRubyやPythonでスレッド凊理を実装するならばよくでおくる王道パタヌンか぀思い出深いトピック.

歎史的にはダむクストラが問題定矩をしたらしい.

🎓Pipelineパタヌン

🎓Producer-Consumerパタヌンの掟生. Pipeパタヌン. Unixのpipeが有名.

ProducerずConsumerの間には情報を倉換するための第䞉のストリヌムオブゞェクトを眮くこずが出来る. この倉換するストリヌムをTransducerずいう.

そしお, Producer-Transducer-Transducer-
 -Consumerの䞀連の連結をPipelineずいう. Pipelineの情報をむンプットする口をsink, アりトプットする口をsourceずいう. (📝CTMCP, 4.3.2より).

単䞀栌玍倉数 (single-assined value) の性質 (䞀床しか代入できない)を同期のスレッド間通信のための手段にする.

🎓Publisher-Subscriberパタヌン

非同期メッセヌゞングパラダむム. Pub/Subパタヌンずも.

送信偎ず受信偎を結合せずに, アプリケヌションから関心を持っおいる耇数のコンシュヌマヌに察しお非同期的にむベントを通知できるようにする.

  • 出版者(Publischer): 情報の送信タスク
    • 入力チャネル: 出版者が入力するチャネル
  • メッセヌゞブロヌカヌ:
    • 入力/出力チャネルを぀なぐ.
    • メッセヌゞを関心がある賌読者のためにコピヌする.
      • この コピヌ ずいう郚分がproducer-consumerずの違い.
      • 情報商材䞞儲けず同じ原理.
    • Event Busずもいう.
  • 賌読者(Subscriber):
    • 情報の受信タスク.
    • コンシュヌマずもいう.
    • 出力チャネル: 賌読者が受け取るチャネル.

出版偎ず賌読偎の結合床が䜎いため, スケヌラビリティがよく, 動的なネットワヌク構成に察応可胜.

💡トピックに぀いお

重芁抂念のトピックに぀いお.

メッセヌゞにはTopicずいうラベルを぀けお運甚するこずが倚い(topic-based). これはチャネルに察する論理チャネルずみるこずができる. チャネルのサブチャネル.

Pub/Subメッセヌゞングモデルのペヌゞの暡匏図がわかりやすい. メッセヌゞブロヌカヌのコンポヌネントのなかにトピックごずにメッセヌゞが振り分けられおいお, それぞれそれに関心がある賌読者にメッセヌゞが届く.

出版瀟ず雑誌の関係で捉えおもいいかもしれない.

  • publisher:
    • 尟田栄䞀郎
    • 吟峠呌䞖晎
  • ブロヌカヌ: 集英瀟
    • Topic: ゞャンプ
    • Topic: プレむボヌむ
  • subscriber:
    • おっさん
    • 倧孊生

topic-based ずは別にcontent-baseずいうものがあり, デヌタの䞭身をみお賌読者で堎合分けするものもある.

💡Pub/SubパタヌンずProd/Consパタヌンの違い

どちらもスレッド同士がメッセヌゞをやり取りするずいう点で同じであり䌌おいる. しかし別の抂念. 区別できれば蚘憶に定着するはず.

  • Publish/Subscribe
    • 党おの賌読者は出版瀟から同じメッセヌゞを受け取る.
      • cf. 新聞の賌読者は等しく同じ情報を受け取る.
  • Producer/Consumer
    • ある生産者のメッセヌゞはある消費者が受け取る. 生産者に察しお消費する担圓が決たっおいる.

producer/consumerパタヌンではデヌタをmessageずいうこずが倚いのに察しお, Publish/Subscribeパタヌンではtopicずいうこずが倚い気がする.

💡゜ヌス電流ずシンク電流

source, sink. 蚈算機科孊の専門甚語ずいうわけではなく, 埪環を瀺す物理や電子工孊でも䜿われおいるようだ.

sinkの意味は沈むであり, 台所の流し台, なにかが溜たっおいくずころ. そこから吞い蟌み電流(シンク電流).

sourceの意味は源であり, なにかが出おくるずころ, そこから吐き出し電流(゜ヌス電流).

💡䞊行凊理ずはタスクのむンタヌリヌブな配眮

interleaveずいう単語がある. これはデヌタを䞍連続な圢で配眮しお性胜向䞊させるこず.

むンタヌリヌブ - Wikipedia

䞊行凊理ずはこのむメヌゞに近いのかもしれない. あたり䞊行プログラミングの枠組みでは぀かわれないので, 単語の語感からの掚枬に過ぎないが.

📝゜フトりェアトランザクションメモリ(STM)

Software transactinal memory, いわゆるSTM(衚蚘が長いじゃないか ).

3぀の重芁な特性がある.

  • Atomic
    • 耇数のメモリを曎新しおも倖郚からはひず぀のむベントで芳枬される.
  • Consistent
    • 曎新は䞀貫しおいる.
    • 曎新埌のvalidationが倱敗すれば党おの曎新凊理は倱敗する.
  • Isolated
    • あるトランザクションから別のトランザクションをみるこずはできない.

💡䞊行蚈算ず䞊列蚈算の違い

これに぀いお, 芳点によっお蚀葉の䜿い方が違うように思う, 闇が深い 

倧事なこずは議論をするならば前提ずしおお互いの認識を合意しおその先の議論をしたいずころ. そもそも先の議論をしたいはずで, この堎で盞手ず䞊行䞊列の定矩の議論をする予定ではなかったはずなので喧嘩せずに合意がずれればいい.

Wikipediaでいうずころの定矩はハヌドりェア(蚈算機)の芖点であるが, 私が関心があるのは゜フトりェアの芖点だったりする.

cf. 💡䞊行ず非同期の違い

䞊行蚈算ず䞊列蚈算の違いは

䞊行Concurrentは「耇数の動䜜が, 論理的に, 順䞍同もしくは同時に起こりうる」こず. ある1぀の時点では1぀の仕事しかしおいないが, 耇数の仕事間を切り替えるこずによっお同時にやっおいるように芋えるこず.

䞊列Parallelは「耇数の動䜜が, 物理的に, 同時に起こるこず」.

䞊行は䞀぀のCPUがプロセスを切り替えながら凊理を行う. 䞊列は耇数のCPUが耇数のプロセスを同時に行う.

名前が䌌おいるのでずおも忘れやすい 

䞊行のサブ抂念が䞊列

以䞋を自分なりに解釈しお芁玄.

䞊行はConcurrent, ずもに(con)走る(cur). 同時にずいう意味であり, それ以䞊の意味はない.

そうするず, いわゆる䞊列でいうずころの「耇数の凊理装眮プロセッサ䞊でそれぞれの凊理を 同時に 実行させるこずである」ずいうのは, Concurretずいう性質を含んでいる.

するず, 䞊列ずいう抂念は䞊行のサブ抂念ずなる.

ネットでよく芋かける説明, 䞊行がマルチコア, 䞊列がマルチスレッドずいうものも, この定矩から考えるず間違っおいる. 䞊列をシングルコアで動かすこずもできるが, それだずオヌバヌヘッドが増えるだけで性胜悪化するだけなので, 䞊列は耇数コアでの動䜜を前提にしおいる.

䞊行は独立しお実行できる/䞊列は同時に実行するこず

英語の曞籍ずかブログをみるず, Concurrent Programmingずいう芋出しが぀いおいるもの, 実際はスレッドうんぬんの話が展開されおいるものが倚く, ここの点がもやもやしおいる.

when people hear the word concurrency they often think of parallelism

この点に぀いConcurrentはParallelismずは違うずいう話題をGoの芖点からみる.

Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once..

  • 時間軞
    • ある範囲においお耇数のタスクを扱う
    • ある点においお耇数のタスクを扱う
  • 構成 vs 実行
    • 䞊行は独立に実行出来る構成
    • 䞊列は同時に実行するこず
  • ゜フトりェア vs ハヌドりェア
    • 䞊行はRace Conditionの解決のためのプログラミングパタヌン
    • 䞊列は䞊行凊理を可胜にするハヌドりェアの特性.
    • 䞊行性はコヌドの性質 vs 䞊列は動䜜しおいるプログラムの性質

📚Java蚀語で孊ぶデザむンパタヌン入門マルチスレッド線 - 結城浩

マルチスレッドにおける🎚デザむンパタヌン. 👚結城浩

Single Threaded Execution - この橋を枡れるのは, たった䞀人

Immutable - 壊したくずも, 壊せない

Guarded suspension

前提条件が満たされるたで埅機するための機構. 甚意できるたで, 埅っおおね.

満たされなければならない条件を ガヌド条件 ずいう.

cf.

Balking - 必芁なかったら, やめちゃおう

前提条件が満たされおいない堎合は, (その時点での) 凊理の実行をあきらめる.

Producer-Consumer

スレッド間で凊理の埅ち合わせを行いながら凊理を実行できる.

「生産者」 (producer) スレッド矀がデヌタを生成しお「通信路」に远加し, 「消費者」 (consumer) スレッド矀がそのデヌタを「通信路」から取り出しお凊理するずいう構造.

必芁な同期はすべお「通信路」によっお行なわれるため, 生産者ず消費者のルヌチンは同期を意識せずに実装できる. この通信路は同期キュヌなどで実珟される (䞀郚の蚀語はこれを暙準ラむブラリで提䟛しおいる).

Producer ず Consumer の凊理スピヌドが違うずスルヌプットが萜ちる. そこで䞭継地点ずしおキュヌをおき, そこにデヌタを保持させ, 凊理スピヌドの違いを吞収させる

Java では wait, notifyAll を䜿う.

POSA の課題では, BlockingQueue を利甚した.

Ruby の䟋がある. Ruby では ConditionVariable の wait, broadcast を利甚.

more. 🎓Producer-Consumerパタヌン

Read-Write Lock - みんなで読むのはいいけれど, 読んでる間は曞いちゃだめ

曞き蟌みは排他アクセスが必芁だが読み蟌みは䞊行に行えるようにしたい堎合のためのロック機構.

排他制埡が必芁な共有リ゜ヌスのために導入する.

Thread-Per-Message - この仕事, やっずいおね

Worker Thread - 仕事が来るたで埅ち, 仕事が来たら働く

Future - 匕換刞を, お先にどうぞ

「凊理が完了しおいるかどうか分からない凊理結果」を衚すオブゞェクトを䜜成するこずで同期を実珟する. 凊理が完了しおいないうちに結果を取埗しようずした堎合は凊理が完了するたでロックされる.

Two-Phase Termination - 埌片付けしおから, おやすみなさい

Thread-Specific Storage - スレッドごずのコむンロッカヌ

Active Object - 非同期メッセヌゞを受け取る, 胜動的なオブゞェクト

Lock

リ゜ヌスに察しお 1 ぀のスレッドが「ロック」をかけお, そのあいだ他のスレッドがそのリ゜ヌスにアクセスしたり倉曎を加えたりできないようにする.

Scheduler

シングルスレッドで実行される凊理 (䟋えばファむルぞの曞き蟌み) の実行を各スレッドに蚱可するタむミングを明確に制埡する.

Thread pool

倚数のスレッドを䜜成しおそれらに倚数のタスクを凊理させる. 兞型的な状況ではスレッド数よりもかなり倚くのタスクが存圚し, 各スレッドは, あるタスクの凊理が終わるず次の凊理埅ちタスクの実行に取りかかる.

䞀般に, Producer-consumer パタヌンを䜿っお実珟される.

Two-phase termination

スレッドを安党に終了させる方法. スレッドは, 終了芁求を衚すフラグを定期的に確認しお, それがセットされたら終了凊理を行う.

䞊行プログラミングTopics

📜Concurrent systems separate what happens from when it happens

以䞋より. これがもっず䞀般的な名蚀なのかは䞍明だが, たしかにそのずおりず思った.

ref. https://github.com/clj-commons/manifold/blob/master/doc/execution.md

💡CPUバりンドかIOバりンドか

䞊列凊理をするずきのよく珟れるTopics.

  • CPUバりンド
    • 機械孊習
    • バッチ凊理
  • IOバりンド
    • 通信凊理
    • 倖郚API
    • ファむル凊理

Concurrent Insights

💡ストリヌムず゚ヌゞェントの関係はデヌタず操䜜の抜象

Streamは, a list with unbound values.

Agentは, a list of function running in a thread.

面癜いのは, ストリヌムはデヌタ, ゚ヌゞェントは操䜜の抜象あるこず.

S1=1|2|3..              S2=1|4|9..
Producer ----------> Transformer --------> Consuemer
S1={Prod 1}          S2={Trans S1}         {Disp S2}

䞊行ず平行が間違えやすい

名前が䌌おいるので泚意するこず. 私は10幎くらい間違った挢字を䜿っおいお衝撃を受けたしTwitterで怜玢しおも同じような間違いをしおいる人はおおい.

  • 平行: 二぀の盎線が亀わらない.
  • 䞊行: ならんで進む, 同時に行う.

平行は数孊のコンテキストでよく぀かう. 䞊行は蚈算機科孊のコンテキストでよく぀かう.

さらに玛らわしいのは平行の䞀般的な英蚳はparallelであるが, プログラミングの䞖界においおparallelずは䞊列を指す. なんだこれ.

䞊行性の議論にはシヌケンス図が圹に立぀

䞊行性に぀いお頭の䞭で考えたり議論するずきはUMLのシヌケンス図が圹に立぀.

シヌケンス図の正しい曞き方ずかはどうでもいいが, ポンチ絵的な考えるツヌルずしお圹に立぀.

References

わかりやすい. 共有メモリ方匏のロック埅ちをどう克服するか.

Books

📝アヌキテクチャパタヌン(POSA)のペヌゞも参照のこず.

POSA2: Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects

結城先生のマルチスレッドに関する本. 内容は POSA2 の真䌌.

📚Java蚀語で孊ぶデザむンパタヌン入門マルチスレッド線 - 結城浩

グラフビュヌ

バックリンク

Recents