🔥虚無との戦い

💻並行プログラミング

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