「並行計算」の版間の差分
削除された内容 追加された内容
編集の要約なし |
82chidnoels (会話 | 投稿記録) |
||
| (同じ利用者による、間の5版が非表示) | |||
1行目:
{{プログラミング・パラダイム}}
'''並行計算'''（へいこうけいさん、{{lang-en-short|Concurrent computing}}）とは、複数の計算あるいは[[アルゴリズム]]を、同一期間に同時実行させつつ相互に同調（コンカレント）させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非[[同期 (計算機科学)|同期]]な[[メッセージパッシング]]ではその完遂の抽象化も可能になる。対義語は順次計算（シーケンシャル）である。並行コンピューティングとも邦訳される。'''並行プログラミング'''（Concurrent programming）とも言われる。
並行計算は、[[コンピュータプログラム]]や[[コンピュータネットワーク]]の重要な特性であり、各[[プロセス]]の各[[スレッド (コンピュータ)|スレッド]]制御などがその要点になる<ref>''Operating System Concepts'' 9th edition, Abraham Silberschatz. "Chapter 4: Threads"</ref>。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非[[同期 (計算機科学)|同期]]では他のスレッドの応答も一定の制約内で待たなくてよくなる。[[エドガー・ダイクストラ]]や[[アントニー・ホーア]]が、並行計算のパイオニアとして名高い。
== イントロダクション ==
並行計算は、[[並列計算]]（parallel computing）としばしば混同される。並列計算は[[マルチプロセッサ]]前提であり、独立した各プロセッサが割り振られた計算を同時実行することを指す。故にシングルプロセッサでは不可になる<ref name="waza">[[Rob Pike|Pike, Rob]] (2012-01-11). "Concurrency is not Parallelism". ''Waza conference'', 11 January 2012. Retrieved from http://talks.golang.org/2012/waza.slide (slides) and http://vimeo.com/49718712 (video).</ref>。[[分散システム]]内の各コンピュータが割り振られた計算を同時実行するのもそうである。並列計算は[[スループット]]・パフォーマンス向けとされる。並列計算の対義語はマルチプロセッサのシリアル計算（serial computing）であり{{sfn|Patterson|Hennessy|2013|p=503}}、各プロセッサの排他的な計算順序配置が重視される。
並行計算は一つのプロセッサに複数のタスクを存在させて、各タスクに計算を割り振ることを指す<ref>{{cite web|url=https://wiki.haskell.org/Parallelism_vs._Concurrency|title=Parallelism vs. Concurrency|work=Haskell Wiki|accessdate=2020-1}}</ref>。そこでは[[タイムシェアリングシステム|タイムシェアリング]]技術などが使われる。マルチプロセッサならば、タスクを各プロセッサに分散できるのでより効率的になる<ref>{{cite book|first=Fred B.|last=Schneider|title=On Concurrent Programming|publisher=Springer|isbn=9780387949420|date=1997-05-06}}</ref>。各タスクは協調する相手タスクが別プロセッサの並列性なのか、同プロセッサの並行性なのかを気にしない<ref name="benari2006">{{cite book|last=Ben-Ari|first=Mordechai|title=Principles of Concurrent and Distributed Programming|publisher=Addison-Wesley|year=2006|edition=2nd|isbn=978-0-321-31283-9}}</ref>。いわゆる[[マルチタスク]][[オペレーティングシステム|OS]]では、[[カーネル]]と[[アプリケーションソフトウェア|アプリケーション]]プログラムから複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]が生成されて、それぞれがタスクの担い手になる。並行計算は[[レイテンシ]]・パフォーマンス向けとされる。並行計算の対義語はシーケンシャル計算（sequential computing）であり{{sfn|Patterson|Hennessy|2013|p=503}}、タスクが一つずつ実行される。
並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。
* スレッドAの完了後に、スレッドBが実行される（シリアル・シーケンシャル）
* スレッドAと、スレッドBが交互に実行される（シリアル・並行）
* スレッドAと、スレッドBが同時に実行される（並列・並行）
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。
=== リソース共有アクセス調整 ===
並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする[[並行性制御]]である<ref name="benari20062">{{cite book|last=Ben-Ari|first=Mordechai|title=Principles of Concurrent and Distributed Programming|publisher=Addison-Wesley|year=2006|edition=2nd|isbn=978-0-321-31283-9}}</ref>。ここでよく取り沙汰されるのは[[競合状態]]、[[デッドロック]]、[[リソーススタベーション|リソース欠乏]]などである。下は共有リソースのコード例である。
<syntaxhighlight lang="java" line="1" start="1">
boolean withdraw(int withdrawal) {
if (balance > withdrawal) {
balance = balance - withdrawal;
return true;
}
return false; }
</syntaxhighlight>
ここで<code>balance=500</code>として
並行システムは共有リソース（通信媒体を含む）に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの[[調停回路]]を実装する必要がある。これにより[[無制限の非決定性]]問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな[[並行性]]問題（[[同期 (計算機科学)|同期]]の[[デッドロック]]など）を生じる。[[Lock-freeとWait-freeアルゴリズム|非ブロックアルゴリズム]]はそれらに対応できる[[並行性制御]]とされる。
== 並行計算のモデル ==
数々の並行計算モデルが提唱されている。
* [[ペトリネット]]
*[[プロセス代数]]
**{{仮リンク|通信システム計算|en|Calculus of Communicating Systems|label=}}
**[[Communicating Sequential Processes|通信シーケンシャルプロセス]]
*[[アクターモデル]]
**{{仮リンク|アクターモデル理論|en|Actor model theory|label=}}
*{{仮リンク|π-計算|en|π-calculus|label=}}
**{{仮リンク|アンビエント計算|en|Ambient calculus|label=}}
*{{仮リンク|入力/出力オートマトン|en|Input/output automaton|label=}}
*[[ソフトウェアトランザクショナルメモリ]]
*[[アトミックコミット]]
=== 一貫性モデル ===
[[一貫性モデル (ソフトウェア)|一貫性モデル]]（consistency models）はメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類される[[クリティカルセクション]]の[[ロック (計算機科学)|ロック]][[同期 (計算機科学)|同期]]がよく使われる。
== 並行計算の実装 ==
並行プログラムには数々の実装手法が存在する。大抵は[[オペレーティングシステム]]が提供する[[プロセス]]と[[スレッド (コンピュータ)|スレッド]]の同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性は[[マルチタスク]]などと言われる。
=== 相互作用と通信 ===
並行コンポーネント間の通信には、例えば以下の二通りがある。
'''ケース１'''：相互通信の明示的操作を要求する形式
:[[同期 (計算機科学)|同期]]傾向になる。明示的操作は特別なプログラム構文を必要にする。[[ソフトウェアトランザクショナルメモリ]]、[[クリティカルセクション]][[同期]]などのモデルに従っての実装になる。
:'''[[共有メモリ]]通信'''
:並行コンポーネントたちは共有メモリの内容を更新することで通信を行う。[[Java]]や[[C Sharp|C#]]が用いている。[[クリティカルセクション]]を定めて[[ロック (情報工学)|ロック]]オブジェクトを用いての[[同期 (計算機科学)|同期]]でその範囲を[[並行性制御]]する。ロック手法には[[セマフォ]]、[[ミューテックス]]、[[モニタ (同期)|モニタ]]、[[バリア (計算機科学)|バリア]]、読み書きロックなどがある。[[スレッドセーフ]]が重視されている。
<br/>
'''ケース２'''：相互通信をプログラマから隠蔽する形式
:非同期傾向になる。上の明示的操作をコード評価/呼出しやデータ参照/代入といった標準構文でまかなえる。[[プロセス計算]]、[[Future パターン|Futureパターン]]などのモデルに従っての実装になる。
:'''[[メッセージパッシング]]通信'''
:並行コンポーネントたちはメッセージの交換で通信を行う。[[Erlang]]、[[Go (プログラミング言語)|Go]]、[[Scala]]、[[Open MPI|OpenMPI]]、[[Occam]]などが用いている。メッセージ交換は通常非同期だが、{{仮リンク|チャネル（計算機科学）|en|Channel (programming)|label=チャネル}}という同期形式もあり、こちらでの送信側は受信側がメッセージに応答するまで待機する双方向通信になる。
:非同期なメッセージ交換での送信側は、受信側がいま応答できるかどうかに関係なくメッセージを送れる単方向通信になる。これは送って祈る（send and pray）と形容されている。ここでの送信型は、メッセージを送るとすぐにfutureやpromiseと呼ばれる抽象的な応答オブジェクトを受け取れるので基本的に待機することはない。メッセージパッシング通信は、共有メモリ通信よりも平易で堅牢であるが、オーバーヘッドが大きいとも考えられている。メッセージパッシングには数々の数学的理論があり、[[アクターモデル]]や[[プロセス計算]]などが有名である。
== 並行プログラミング言語 ==
並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には、[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング型プログラミング|en|Message passing programming|label=メッセージパッシング}}、共有[[リソース]]（[[並列ランダムアクセス機械|共有メモリ]]）、[[Future パターン|Futureパターン]]のサポートなどである。
74 ⟶ 109行目:
他の多くの言語でもライブラリの形で並行性をサポートしている（機能的にも上記リストに挙げたものと遜色ない）。
== 関連項目 ==
<div style="{{column-count|2}}">
*[[並列計算]]
*[[非同期IO]]
*[[競合状態]]
*[[トランザクション処理]]
*[[ソフトウェアトランザクショナルメモリ]]
*[[クリティカルセクション]]
*[[不可分操作]]
*[[排他制御]]
*[[並行性制御]]
*[[グローバル並行性制御]]
*[[分散並行性制御]]
*[[スケジューリング]]
*[[マルチスレッド]]
*[[マルチタスク]]
*[[:en:Ptolemy Project|Ptolemy Project]]
*[[メッセージ (コンピュータ)|メッセージパッシング]]
*[[プロセス代数]]
*[[アクターモデル]]
*[[同期 (計算機科学)|同期]]
*[[ロック (計算機科学)|ロック]]
*[[セマフォ]]
*[[ミューテックス]]
*[[モニタ (同期)|モニタ]]
*[[バリア (計算機科学)|バリア]]
*[[Lock-freeとWait-freeアルゴリズム|非ブロックアルゴリズム]]
</div>
==脚注==
{{Reflist}}
==参考文献==
98 ⟶ 147行目:
== 外部リンク ==
*[https://web.archive.org/web/20060128114620/http://vl.fmnet.info/concurrent/ Concurrent Systems Virtual Library]
{{並列コンピューティング}}
{{デフォルトソート:へいこうけいさん}}
[[Category:オペレーティングシステムの仕組み]]
[[Category:並行計算|*へいこうけいさん]]
[[Category:エドガー・ダイクストラ]]
| |||