並行性（コンピュータサイエンス）

コンピュータサイエンスにおいて、並行性とは、プログラム、アルゴリズム、または問題の異なる部分または単位を、結果に影響を与えることなく、順序どおりにまたは部分的な順序で実行する能力です。これにより、同時実行単位の並列実行が可能になり、マルチプロセッサおよびマルチコアシステムでの実行速度全体を大幅に向上させることができます。より技術的な用語では、並行性とは、プログラム、アルゴリズム、または問題を、順序に依存しない、または部分的に順序付けられたコンポーネントまたは計算単位に分解できることを指します。 ^[1]

コンピュータサイエンスでは、並列性と同時実行性は2つの異なるものであることに注意してください。並列プログラムは複数のCPUコアを使用し、各コアは独立してタスクを実行します。一方、同時実行性により、プログラムは単一のCPUコア上でも複数のタスクを処理できます。コアは、必ずしも各タスクを完了する必要はなく、タスク（つまりスレッド）を切り替えます。プログラムは、並列性と同時実行性の両方の特性を持つことも、どちらも持たないことも、組み合わせることもできます。^[2]

一般的な並行計算用に、ペトリネット、プロセス計算、並列ランダムアクセスマシンモデル、アクターモデル、Reoコーディネーション言語など、数多くの数学モデルが開発されてきました。

並行システムにおける計算は実行中に相互に作用する可能性があるため、システム内で実行可能なパスの数は非常に多くなり、結果が不確定になる可能性があります。共有リソースの同時使用は不確定性の原因となり、デッドロックやリソース不足などの問題を引き起こす可能性があります。^[3]

並行システムの設計には、応答時間を最小限に抑え、スループットを最大化するために、実行、データ交換、メモリ割り当て、実行スケジュールを調整するための信頼性の高い手法を見つけることがしばしば必要になります。^[4]

並行性理論は、理論計算機科学において活発に研究されている分野です。最初の提案の 1 つは 、1960 年代初頭のCarl Adam PetriによるPetri ネットに関する独創的な研究でした。それ以来、並行性のモデル化と推論のためのさまざまな形式論が開発されてきました。

並行システムをモデル化し理解するための形式論が数多く開発されており、その中には次のようなものがある: ^[5]

• 並列ランダムアクセスマシン[ ^6]
• 俳優モデル
• バルク同期並列（BSP）モデルなどの計算ブリッジングモデル
• ペトリネット
• プロセス結石
  • 通信システムの微積分(CCS)
  • 通信シーケンシャルプロセス（CSP）モデル
  • π計算
• タプルスペース、例：Linda
• シンプルな並行オブジェクト指向プログラミング(SCOOP)
• レオ調整言語
• トレースモノイド

これらの並行性モデルの一部は、主に推論と仕様をサポートすることを目的としていますが、他のモデルは並行システムの設計、実装、証明、テスト、シミュレーションを含む開発サイクル全体を通じて使用できます。これらのモデルの一部はメッセージ パッシングに基づいていますが、並行性のための異なるメカニズムを持つモデルもあります。

並行性に関するさまざまなモデルが急増したことで、一部の研究者はこれらの異なる理論モデルを統一する方法を開発するようになりました。たとえば、Lee と Sangiovanni-Vincentelli は、いわゆる「タグ付きシグナル」モデルを使用して、さまざまな並行性モデルの表示的意味を定義するための共通のフレームワークを提供できることを実証しました。 ^[7]一方、Nielsen、Sassone、Winskel は、カテゴリ理論を使用して、さまざまなモデルを同様に統一的に理解できることを実証しました。^[8]

アクターモデルの並行性表現定理は、外部からの通信を受け取らないという意味で閉じた並行システムを表現する、かなり一般的な方法を提供します。（他の並行システム、例えばプロセス計算は、 2相コミットプロトコルを使用してアクターモデルでモデル化できます。^{[9] ）閉じたシステム}Sで表される数学的表記は、動作近似関数進行_Sを使用して、 ⊥Sと呼ばれる初期の動作から、Sの表記（意味）を構築するための、次のようにより良い近似を構築し_ます。 [ 10 ^]

_S ≡ ⊔ _i∈ω 進行_S ⁱ (⊥ _S )と表記する。

このようにして、S は、そのすべての可能な動作に関して数学的に特徴付けることができます。

並行システムの推論には、さまざまな種類の時相論理^{[11]を利用できます。}線形時相論理や計算木論理などの論理では、並行システムが通過する状態のシーケンスについてアサーションを行うことができます。アクション計算木論理、ヘネシー・ミルナー論理、ランポートの アクションの時相論理などの他の論理では、アクションのシーケンス（状態の変化）からアサーションを構築します。これらの論理の主な用途は、並行システムの仕様を記述することです。^[3]

並行プログラミング^{には、並行システムを実装するために使用されるプログラミング言語とアルゴリズムが含まれます。並行プログラミングは、通常、並列プログラミングよりも一般的であると考えられています。これは、並行プログラミングが通信と相互作用の任意で動的なパターンを含むことができるためです。一方、並列システムは一般に、定義済み}で適切に^構造化^{された通信パターンを持ちます。並行プログラミング}の基本目標には、正確性、パフォーマンス、堅牢性^などがあります。オペレーティングシステムやデータベース管理システムなどの並行システムは一般に、障害からの自動回復を含め、無期限に動作し、予期せず終了しないように設計されます⁽並行制御を参照)。一部の^{並行システムでは、}透過的な並行性の形式が実装されています。透過的な並行性では、並行する計算エンティティが単一のリソースを競い合って共有する場合がありますが、この競争と共有の複雑さはプログラマから隠されています。

並行システムは共有リソースを使用するため、一般的に^{[誰によると? ]}、それらのリソースへのアクセスを制御するために、実装のどこか (多くの場合、基盤となるハードウェア) に何らかの^{[例が必要]}種類のアービターを組み込む必要があります。アービターを使用すると、並行計算に不確定性が生じる可能性があり、正確性やパフォーマンスなどの実践に大きな影響を与えます。たとえば、アービトレーションによって無制限の非決定性が生じ、状態空間が爆発的に増加し、モデルに無限の数の状態が生じる可能性があるため、 モデル チェックで問題が発生します。

一部の並行プログラミング モデルには、コプロセスと決定論的並行性が含まれます。これらのモデルでは、制御スレッドは、システムまたは別のプロセスにタイムスライス を明示的に譲渡します。

• チュースペース
• クライアント・サーバーネットワークノード
• クロージュア
• クラスターノード
• 同時実行制御
• 同時実行コンピューティング
• 並行オブジェクト指向プログラミング
• 並行性パターン
• 分散プロセスの構築と分析(CADP)
• D（プログラミング言語）
• 分散システム
• Elixir (プログラミング言語)
• Erlang (プログラミング言語)
• Go（プログラミング言語）
• ゴードン・パスク
• 並行性理論に関する国際会議(CONCUR)
• オープンMP
• 並列コンピューティング
• 分割されたグローバルアドレス空間
• プロセス
• プトレマイオスプロジェクト
• Rust（プログラミング言語）
• 束（数学）
• スレッド
• X10 (プログラミング言語)
• 構造化された同時実行

• リンチ、ナンシー A. (1996)。分散アルゴリズム。モーガン カウフマン。ISBN 978-1-55860-348-6。
• Tanenbaum, Andrew S.; Van Steen, Maarten (2002)。分散システム: 原理とパラダイム。Prentice Hall。ISBN 978-0-13-088893-8。
• Kurki-Suonio, Reino (2005).反応システムの実践理論. Springer. ISBN 978-3-540-23342-8。
• Garg, Vijay K. (2002).分散コンピューティングの要素. Wiley-IEEE 出版. ISBN 978-0-471-03600-5。
• Magee, Jeff; Kramer, Jeff (2006)。並行性: 状態モデルと Javaプログラミング。Wiley。ISBN 978-0-470-09355-9。
• Distefano, S., Bruneo, D. (2015).分散システムの定量的評価: 方法論とテクニック(第 1 版). サマセット: John Wiley & Sons Inc. ISBN 9781119131144 
• Bhattacharyya, SS (2013;2014;).信号処理システムハンドブック(第 2 版、2013 年、第 2 版)。ニューヨーク、NY: Springer.10.1007/978-1-4614-6859-2 ISBN 9781461468592 
• ウォルター、K. (2012;2014;)。コンピューティング システムの回復力の評価と評価(1. Aufl.;1; ed.)。ロンドン;ベルリン;: スプリンガー。ISBN 9783642290329 

• プロセス代数日記 - ルカ・アセト教授の並行性理論に関するブログ
• WWW 仮想ライブラリの並行システム
• scaleconf で行われた並行性パターンのプレゼンテーション