並行性

食事する哲学者の問題は、並行性とリソース共有に関する古典的問題

並行性(へいこうせい、Concurrency)とは、計算機科学において、時間的にオーバーラップして実行される計算を伴うシステムの属性であり、そのような計算ではリソースを共有することがある。エドガー・ダイクストラによれば、「2つ以上の実行の流れが同時並行して行われるとき、並行性が生まれる」としている。共有リソースの並行使用により様々な問題が発生する。共有リソースに関わる競合状態は予測不能なシステムの状態を発生させる。相互排他の導入によって競合状態は阻止できるが、デッドロックやリソーススタベーションといった問題が新たに発生する。並行システムの設計では、応答時間を最小化し、スループットを最大化するため、データ交換、メモリ割り当て、実行スケジューリングなどに関わる技術の信頼性を追求する。

理論

並行性理論は、1960年代にカール・アダム・ペトリが独創的なペトリネットの研究を行って以来、理論計算機科学の主要な研究領域となっている。以来、並行システムを理解するための様々な理論モデル、論理、ツールが開発されてきた。

モデル

モデル開発と並行システムの理解のための形式手法には様々なものが開発されてきた。以下に主なものを列挙する。

• 並列ランダムアクセス機械
• アクターモデル
• ペトリネット
• プロセス代数

これら並行性モデルの一部は、第一に推論と仕様記述を目的としている。一方、他のモデルは開発サイクル全体（並行システムの設計、実装、証明、テスト、シミュレーション）をサポートすることを目的としている。

論理

様々な時相論理が並行システムの理解を助けるために使われる。特に線形時相論理や計算木論理は、並行システムの各時点の状態を確認するのに使用可能である。Action Computational Tree Logic や Hennesy-Miller Logic、レスリー・ランポートのTemporal Logic of Actionsなどは、「アクション（状態変化）」の並びを確認することができる。これら論理の主な利用法は、並行システムの仕様を記述することである。

実際の並行処理

並行プログラミングは、並行システムを実装するのに使われるプログラミング言語とアルゴリズムから構成される。一般に並行プログラミングは並列プログラミングよりも範囲が広いとされ、様々な形態の通信および相互作用に関係する。一方、一般の並列システムは予め決められた整った構成の通信パターンを備えている。並行プログラミングの基本目標には「正当性」、「性能」、「堅牢性」が含まれる。オペレーティングシステムのような並行システムは、半永久的に動作することが求められている。一部の並行システムは透過的並行性を持つよう実装されている。その場合、並行動作する計算主体群は共有リソースを使用するものの、プログラマからはその実装は隠されている。

並行システムは共有リソースを使うため、共有リソースへのアクセスを制御するための一種の調停を行うもの（通常、ハードウェア）を実装する必要がある。これにより無制限の非決定性が導入され、並行システムの正当性と性能に影響する。

関連項目

• 並行計算
• 並行性制御
• スレッド
• プロセス
• コンピュータ・クラスターのノード群
• 分散システムのノード群
• クライアント-サーバネットワークのノード群
• OpenMP

外部リンク

• Concurrent Systems at The WWW Virtual Library