並行性

並行性とは

並行性（Concurrency）とは、計算機科学における重要な概念であり、複数の計算が時間的にオーバーラップして実行されるシステムの特性を指します。これらの計算は、同一チップ上の複数のコア、単一プロセッサ上のマルチスレッド、または物理的に分離した複数のプロセッサ上で実行されることがあります。

並行計算では、複数の処理が同時に進行するように見えるため、リソースの共有や相互作用が複雑になります。この複雑さが、デッドロックやリソースの枯渇といった問題を引き起こす可能性もあります。

並行性の課題

並行システムにおける計算は、実行中に互いにやりとりすることが可能です。そのため、考えられる実行経路が非常に多くなり、システム全体が不確定な状態になることがあります。共有リソースへの並行アクセスは不確定性の源となり、デッドロックやリソースの枯渇といった問題を引き起こす可能性があります。

並行システムを設計する際には、応答時間を最小限に抑え、スループットを最大化するために、データ交換、メモリ割り当て、実行スケジューリングなどに関する信頼性の高い技術を用いる必要があります。

並行性理論

並行性理論は、1960年代にカール・アダム・ペトリが提唱したペトリネットの研究から始まり、理論[[計算機科学]]の主要な研究領域となりました。それ以来、並行システムを理解するためのさまざまな理論モデル、論理、ツールが開発されてきました。

これらの理論は、並行システムの挙動を形式的に記述し、検証するための枠組みを提供します。

並行性モデル

並行システムのモデル化と理解には、多くの形式手法が用いられています。以下に主なモデルを列挙します。

並列ランダムアクセス機械 (PRAM): 並列[[計算]]の理論モデル。
アクターモデル: 分散並行システムをモデル化するための抽象モデル。
BSPモデル: 並列[[計算]]のブリッジモデル。
ペトリネット: 並行処理をグラフで表現するモデル。
プロセス計算: 並行システムの相互作用を記述するための数学的フレームワーク。
タプルスペース (Linda): 共有メモリを用いた並行プログラミングモデル。
SCOOP (Simple Concurrent Object-Oriented Programming): オブジェクト指向プログラミングにおける並行処理のモデル。
Reo Coordination Language: 並行コンポーネント間のインタラクションを記述するための言語。

これらのモデルは、並行システムの推論、仕様記述、設計、実装、証明、テスト、シミュレーションをサポートするために使用されます。モデルが多様化する中で、これらの理論モデルを統合しようとする研究も進められています。

例えば、LeeとSangiovanni-Vincentelliは、さまざまな並行性モデルの表示的意味論を定義するための共通フレームワークとして"tagged-signal"モデルを提唱しました。また、Nielsen、Sassone、Winskelは、圏論がモデルの統合と理解に有効であると提唱しました。

アクターモデルにおけるConcurrency Representation Theoremは、外部との通信がない閉じた並行システムを汎用的に表現する方法を提供します。また、プロセス計算などの他の並行性モデルは、2相コミットプロトコルを用いてアクターモデルでモデル化できます。

閉システムSは、初期挙動⊥Sに対して挙動近似関数progressionSを適用することで、より良い近似を構築できます。Sの数学的な記述（意味）は、次のようになります。

DenoteS ≡ ⊔i∈ω progressionSi(⊥S)

この方法により、Sは可能なすべての挙動で数学的に特徴づけられます。

並行性における論理

さまざまな時相論理は、並行システムの理解を深めるために使用されます。特に、線形時相論理や計算木論理は、並行システムの各時点の状態を確認するのに役立ちます。

Action Computational Tree Logic、Hennesy-Miller Logic、レスリー・ランポートのTemporal Logic of Actionsなどは、「アクション（状態変化）」の順序を検証することができます。これらの論理の主な用途は、並行システムの仕様を記述することです。

実際の並行処理

並行プログラミングは、並行システムを実装するために使用されるプログラミング言語とアルゴリズムで構成されています。一般に、並行プログラミングは並列プログラミングよりも広い範囲をカバーし、さまざまな形式の通信と相互作用に関わります。並列システムは、事前に定義された通信パターンを持つことが多いです。

並行プログラミングの基本的な目標には、「正当性」、「性能」、「堅牢性」が含まれます。オペレーティングシステムやデータベース管理システムのような並行システムは、障害からの自動復旧などの機能を持つことが求められ、意図しない停止を避けることが重要です（並行性制御を参照）。

一部の並行システムは、透過的な並行性を備えるように実装されています。この場合、並行して動作する計算エンティティは共有リソースを使用しますが、プログラマーにはその実装の詳細が隠されています。

並行システムは共有リソースを使用するため、共有リソースへのアクセスを制御するための仲裁機能（通常はハードウェア）の実装が必要です。この仲裁プロセスは、並行計算における不確定性を生じさせる可能性があり、正当性と性能が重要な実装においては特に重要です。例えば、仲裁によって無制限の非決定性が導入されると、モデル検査においてモデルが無限の状態を持つことになり、問題を引き起こします。

一部の並行プログラミングモデルには、コプロセスやコルーチンも含まれます。これらのモデルでは、スレッドが自発的にタイムスライスをシステムまたは他のプロセスに譲ります。


並行性の概念は、現代の計算システムにおいて不可欠な要素であり、システムのパフォーマンスと信頼性を向上させるために、その理解はますます重要になっています。

もう一度検索