並行 計算
| プログラミング・パラダイム |
|---|
イントロダクション[編集 ]
- スレッドAの
完了 後 に、スレッドBが実行 される（シリアル・シーケンシャル） - スレッドAと、スレッドBが
交互 に実行 される（シリアル・並行 ） - スレッドAと、スレッドBが
同時 に実行 される（並列 ・並行 ）
リソース共有 アクセス調整 [編集 ]
boolean withdraw(int withdrawal) {
if (balance > withdrawal) {
balance = balance - withdrawal;
return true;
}
return false;
}
ここでbalance=500としてプロセスAとプロセスBをwithdraw(300)を、Bがwithdraw(350)をコールする。Aが2trueでbalance > withdrawalはここでもtrueになってしまい、AとBのbalance=-150となり、
並行 計算 のモデル[編集 ]
一貫 性 モデル[編集 ]
並行 計算 の実装 [編集 ]
相互 作用 と通信 [編集 ]
ケース１：
同期 傾向 になる。明示 的 操作 は特別 なプログラム構文 を必要 にする。ソフトウェアトランザクショナルメモリ、クリティカルセクション同期 などのモデルに従 っての実装 になる。共有 メモリ通信 並行 コンポーネントたちは共有 メモリの内容 を更新 することで通信 を行 う。JavaやC#が用 いている。クリティカルセクションを定 めてロックオブジェクトを用 いての同期 でその範囲 を並行 性 制御 する。ロック手法 にはセマフォ、ミューテックス、モニタ、バリア、読 み書 きロックなどがある。スレッドセーフが重視 されている。
ケース２：
非同期 傾向 になる。上 の明示 的 操作 をコード評価 /呼出 しやデータ参照 /代入 といった標準 構文 でまかなえる。プロセス計算 、Futureパターンなどのモデルに従 っての実装 になる。- メッセージパッシング
通信 並行 コンポーネントたちはメッセージの交換 で通信 を行 う。Erlang、Go、Scala、OpenMPI、Occamなどが用 いている。メッセージ交換 は通常 非同期 だが、チャネルという同期 形式 もあり、こちらでの送信 側 は受信 側 がメッセージに応答 するまで待機 する双方向 通信 になる。非同期 なメッセージ交換 での送信 側 は、受信 側 がいま応答 できるかどうかに関係 なくメッセージを送 れる単 方向 通信 になる。これは送 って祈 る（send and pray）と形容 されている。ここでの送信 型 は、メッセージを送 るとすぐにfutureやpromiseと呼 ばれる抽象 的 な応答 オブジェクトを受 け取 れるので基本 的 に待機 することはない。メッセージパッシング通信 は、共有 メモリ通信 よりも平易 で堅牢 であるが、オーバーヘッドが大 きいとも考 えられている。メッセージパッシングには数々 の数学 的 理論 があり、アクターモデルやプロセス計算 などが有名 である。
並行 プログラミング言語 [編集 ]
- Ada
- Afnix – データへの
並行 アクセスは自動的 に保護 される（従来 はAlephと呼 ばれていたが、Alefとは無関係 ）。 - Alef – スレッドとメッセージパッシングを
備 えた言語 。初期 のPlan 9のシステム記述 に使 われた言語 。 - Alice – Standard ML に Future による
並行 性 サポート機能 を追加 したもの - CDL (Concurrent Description Language) – machine translatable（
機械 的 に変換 可能 ）、構成 可能 、オブジェクト指向 、ビジュアルプログラミング言語 。 - ChucK –
音響 関連 専用 のプログラミング言語 - Cilk –
並行 版 C言語 - Clojure – LISP
系 の言語 、JVM上 で動作 する。 - Concurrent C
- Concurrent Clean –
関数 型 言語 。Haskellに近 い。 - Concurrent Pascal – by Per Brinch Hansen
- Corn
- Curry
- C
ω – C オメガ。C#に非同期 通信 を追加 した研究 用 言語 。 - E – Future
機能 使用 。デッドロックを発生 させない。 - Eiffel –
契約 プログラミングに基 づいたSCOOP機構 による。 - Erlang –
共有 のない非同期 メッセージパッシングを使用 。 - Janus –
宣言 型 言語 。論理 変数 などをaskerとtellerに明確 に区別 する。 - Join Java – Javaに
基 づいた並行 プログラミング言語 。 - Joule – データフロー
言語 。メッセージパッシングによって通信 する。 - KL1 – Guarded Horn Clausesに
基 づく論理 型 言語 。第 五 世代 コンピュータプロジェクトの研究 成果 。KLICなどの実装 が利用 可能 。 - Limbo – Alefからの
派生 。Plan 9の後継 であるInfernoのシステム記述 に使 われた。 - Oz – マルチパラダイム
言語 。共有 メモリとメッセージパッシング、Futureも備 えている。 - MultiLisp – Scheme に
並列 性 サポート機能 を追加 した派生 言語 。 - Occam – Communicating Sequential Processes (CSP) の
影響 を強 く受 けている。 - Pict – ミルナーの
π 計算 の実装 に基 づいている。 - SALSA – インターネット
上 での分散 コンピューティングを指向 したメッセージパッシング式 の言語 。 - SR –
研究 用 言語 。
関連 項目 [編集 ]
脚注 [編集 ]
- ^ Operating System Concepts 9th edition, Abraham Silberschatz. "Chapter 4: Threads"
- ^ Pike, Rob (2012-01-11). "Concurrency is not Parallelism". Waza conference, 11 January 2012. Retrieved from http://talks.golang.org/2012/waza.slide (slides) and http://vimeo.com/49718712 (video).
- ^ a b Patterson & Hennessy 2013, p. 503.
- ^ “Parallelism vs. Concurrency”. Haskell Wiki. 2020
年 1月 閲覧 。 - ^ Schneider, Fred B. (1997-05-06). On Concurrent Programming. Springer. ISBN 9780387949420
- ^ Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley. ISBN 978-0-321-31283-9
- ^ Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley. ISBN 978-0-321-31283-9
参考 文献 [編集 ]
- Filman, Robert E.; Daniel P. Friedman (1984
年 ). Coordinated Computing: Tools and Techniques for Distributed Software. New York: McGraw-Hill. pp. 370. ISBN 0-07-022439-0