並行性とメモリモデル
並行性とメモリモデルは、並行プログラムの構造と、相互作用するスレッドが共有メモリをどのように観測するかを定義し、正しい並列ソフトウェアの基盤をなします。
PaperMindでテーマを探す近日公開Find papers & topics
Tools & resources
Learn & explore
動画近日公開
Definition
並行性モデルは、独立して実行される計算がどのように構成され、通信するかを記述する一方、メモリモデルは、並行スレッドが共有メモリにアクセスする際に読み取りが観測できる値を指定し、プログラマ、言語、ハードウェア間の契約を定義します。
Scope
この分野は、並行性の言語と理論を扱います。具体的には、通信と同期のためのプロセス計算と並行性モデル、メモリ操作の許容される順序付けを規定するメモリ一貫性モデル、同期メカニズムとデータ競合の排除、セッション型などの並行性のための型システムが含まれます。また、言語が同時に実行され状態を共有するプログラムにどのように意味を与えるかについても扱います。
Sub-topics
Core questions
- 並行する通信プロセスはどのようにモデル化され、推論できるか？
- プログラムはメモリ操作のどのような順序付けを観測できるか？
- データ競合からの自由はどのように保証または指定されるか？
- 型はどのように通信を統制し、並行性エラーを防ぐことができるか？
Key theories
- プロセス計算
- ホーアのCSP、ミルナーのCCS、およびπ-計算は、並行する通信プロセスの代数理論を提供し、合成と同期のための演算子、および双模倣性などの振る舞いの等価性の概念を含みます。
- 逐次一貫性
- ランポートは、逐次一貫性を、マルチプロセッサの実行が、各プロセッサの操作がプログラム順序に従って何らかの形でインターリーブされたものとして現れるという要件として定義しました。これは、より弱いメモリモデルと比較される際の基準となります。
- メモリ一貫性モデル
- アドベとガラチョルルーは、共有メモリ一貫性モデルのスペクトルを体系化し、緩和された順序付けがどのようにパフォーマンスを可能にする一方で、並行プログラムに関する推論を複雑にするかを説明しています。
Clinical relevance
マルチコアハードウェアによって緩和された順序付けが観測可能になったため、メモリモデルは現在、主流の言語仕様（例えばC++やJava）の一部となっています。これらを正しく理解することは、正確で移植性の高い並行ソフトウェアにとって不可欠です。プロセス計算とセッション型は、メッセージパッシング言語とプロトコルの設計に情報を提供します。
History
並行性理論は、ペトリネットと、1970年代のホーア（CSP）とミルナー（CCS）の研究から発展し、後にモバイルプロセス向けのπ-計算へと続きました。ランポートは1979年に逐次一貫性を定義しました。緩和されたハードウェアが普及するにつれて、2000年代にはJavaやC++などの言語向けにメモリモデルが形式化され、弱いメモリセマンティクスが活発な研究分野となりました。
Debates
- 強いメモリ一貫性と緩和されたメモリ一貫性
- 設計者は、逐次一貫性のような強いモデルの直感的な単純さと、順序変更を許容する緩和されたモデルのパフォーマンスとの間でトレードオフを行います。緩和されたモデルは推論を複雑にし、慎重な言語レベルのセマンティクスを必要とします。
Key figures
- C. A. R. Hoare
- Robin Milner
- Leslie Lamport
- Sarita Adve
Related topics
Seminal works
- hoare1978
- milner1989
- lamport1979
- adve1996
Frequently asked questions
- メモリモデルとは何ですか？
- メモリモデルとは、複数のスレッドが共有メモリにアクセスする際に、読み取りがどの値を返すことができるかを指定する正式な契約であり、コンパイラとハードウェアがどのような順序変更を実行できるか、そしてプログラマが何に依存できるかを定義します。
- 逐次一貫性とは何ですか？
- 逐次一貫性とは、並行実行が、各スレッドのプログラム順序を尊重するスレッドの操作の単一のインターリーブとして振る舞うことを要求するもので、最も直感的（しかししばしば緩和される）なメモリモデルです。