並行性
並行性（へいこうせい、英: concurrency）とは、計算機科学において、時間的にオーバーラップして実行される計算を伴うシステムの属性であり、そのような計算ではリソースを共有することがある。並行計算は、同一チップ上の複数のコア、単一プロセッサ上のプリエンプションを伴うマルチスレッド、物理的に分離した複数プロセッサ上などで行われる。並行計算のための数学的モデルとして、ペトリネット、プロセス計算、並列ランダムアクセス機械モデル、アクターモデル、Reo Coordination Language などが開発された。
問題
[編集]並行システムにおける計算は実行中に互いにやりとりできるため、考えられる実行経路は極めて多くなり、結果としてシステム全体が不確定となる。共有リソースの並行使用が不確定性の源となる可能性もあり、デッドロックやリソーススタベーションといった問題を引き起こす[1]。
並行システムの設計では応答時間を最小化しスループットを最大化するため、データ交換、メモリ割り当て、実行スケジューリングなどに関わる技術の信頼性を追求する[2]。
理論
[編集]並行性理論は、1960年代にカール・アダム・ペトリが独創的なペトリネットの研究を行って以来、理論計算機科学の主要な研究領域となっている。以来、並行システムを理解するための様々な理論モデル、論理、ツールが開発されてきた。
モデル
[編集]モデル開発と並行システムの理解のための形式手法には様々なものが開発されてきた。以下に主なものを列挙する[3]。
- 並列ランダムアクセス機械[4]
- アクターモデル
- BSPモデルなどの計算ブリッジモデル
- ペトリネット
- プロセス計算
- タプルスペース（例えばLinda）
- SCOOP (Simple Concurrent Object-Oriented Programming)
- Reo Coordination Language
これら並行性モデルの一部は、第一に推論と仕様記述を目的としている。一方、他のモデルは開発サイクル全体（並行システムの設計、実装、証明、テスト、シミュレーション）をサポートすることを目的としている。
並行性モデルが乱立したことから、一部の研究者はそれら理論モデル群を統合する方法を模索することを考えた。例えば Lee と Sangiovanni-Vincentelli は各種並行性モデルの表示的意味論を定義する共通フレームワークを提供すべく "tagged-signal" モデルを提唱した[5]。一方、Nielsen、Sassone、Winskel は各種モデルを統合理解するのに圏論が有効であるとした[6]。
アクターモデルにおける Concurrency Representation Theorem は、外部からの通信を受け付けないという意味で閉じている並行システムを汎用的に表現する方法を提供している。プロセス計算などの他の並行性システムは、2相コミットプロトコルを使ってアクターモデルでモデル化できる[7]。閉システム S は、その初期挙動 ⊥S に対して挙動近似関数 progressionS を適用することでよりよい近似を構築でき、S の数学的記述（意味）は次のようになる[8]。
- DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
このようにすると、S は全てのとりうる挙動で数学的に特徴付けられることができる。
論理
[編集]様々な時相論理[9]が並行システムの理解を助けるために使われる。特に線形時相論理や計算木論理は、並行システムの各時点の状態を確認するのに使用可能である。Action Computational Tree Logic や Hennesy-Miller Logic、レスリー・ランポートのTemporal Logic of Actionsなどは、「アクション（状態変化）」の並びを確認することができる。これら論理の主な利用法は、並行システムの仕様を記述することである[1]。
実際の並行処理
[編集]並行プログラミングは、並行システムを実装するのに使われるプログラミング言語とアルゴリズムから構成される。一般に並行プログラミングは並列プログラミングよりも範囲が広いとされ、様々な形態の通信および相互作用に関係する。一方、一般の並列システムは予め決められた整った構成の通信パターンを備えている。並行プログラミングの基本目標には「正当性」、「性能」、「堅牢性」が含まれる。オペレーティングシステムやデータベース管理システムのような並行システムは、障害からの自動復旧など半永久的に動作することが求められ、不意な停止をしないことが期待されている（並行性制御参照）。一部の並行システムは透過的並行性を持つよう実装されている。その場合、並行動作する計算主体群は共有リソースを使用するものの、プログラマからはその実装は隠されている。
並行システムは共有リソースを使うため、共有リソースへのアクセスを制御するための一種の調停を行うもの（通常、ハードウェア）を実装する必要がある。調停者を使用することで並行計算における不確定性が生じるおそれがあり、正当性と性能が求められる実装では重要な意味を持つ。例えば調停によって無制限の非決定性が導入されると、モデル検査においてモデルが無限個の状態を持つことになり、問題が生じる。
並行プログラミングモデルによっては、コプロセスやコルーチンも含んでいる。そういったモデルでは、スレッドが自発的にタイムスライスをシステムまたは他のプロセスに対して譲る。
脚注
[編集]- ^ a b Cleaveland, Rance; Scott Smolka (December, 1996). “Strategic Directions in Concurrency Research”. ACM Computing Surveys 28 (4): 607. doi:10.1145/242223.242252.
- ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (August 2010). Parallel Programming with Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3
- ^ Filman, Robert; Daniel Friedman (1984). Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill. ISBN 0-07-022439-0
- ^ Keller, Jörg; Christoph Keßler, Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons
- ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (December, 1998). “A Framework for Comparing Models of Computation”. IEEE Transactions on CAD 17 (12): 1217–1229. doi:10.1109/43.736561.
- ^ Nielsen, Mogens; Vladimiro, Sassone; Glynn, Winskel (1993). "Relationships Between Models of Concurrency" (PDF). REX School/Symposium.
- ^ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
- ^ William Clinger (June 1981). Foundations of Actor Semantics. Mathematics Doctoral Dissertation. MIT.
- ^ Roscoe, Colin (2001). Modal and Temporal Properties of Processes. Springer. ISBN 0-387-98717-7
参考文献
[編集]- Lynch, Nancy A. (1996). Distributed Algorithms. Morgan Kauffman. ISBN 1-55860-348-4
- Tanenbaum, Andrew S.; Van Steen, Maarten (2002). Distributed Systems: Principles and Paradigms. Prentice Hall. ISBN 0-13-088893-1
- Kurki-Suonio, Reino (2005). A Practical Theory of Reactive Systems. Springer. ISBN 3-540-23342-3
- Garg, Vijay K. (2002). Elements of Distributed Computing. Wiley-IEEE Press. ISBN 0-471-03600-5
- Magee, Jeff; Kramer, Jeff (2006). Concurrency: State Models and Java Programming. Wiley. ISBN 0-470-09355-2
関連項目
[編集]- クライアントサーバモデル
- コンピュータ・クラスター
- Communicating Sequential Processes
- 並行性制御
- 並行計算
- 分散コンピューティング
- OpenMP
- 並列計算
- 区分化大域アドレス空間
- プロセス
- 層 (数学)
- スレッド (コンピュータ)
- X10 (プログラミング言語)
