「並行計算」の版間の差分
編集の要約なし |
Shohei KIMURA (会話 | 投稿記録) m編集の要約なし |
||
(2人の利用者による、間の7版が非表示) | |||
1行目: | 1行目: | ||
{{プログラミング・パラダイム}} |
|||
'''並行計算'''(へいこうけいさん、{{lang-en-short|concurrent computing}})とは、コンピュータプログラムにおいて複数の相互作用を及ぼす計算タスクの(同時)[[並行性|並行的]]実行を指す。'''並行コンピューティング'''あるいは'''並行処理''' (concurrent processing) とも呼ぶ。 |
|||
'''並行計算'''(へいこうけいさん、{{lang-en-short|Concurrent computing}})とは、複数の計算あるいは[[アルゴリズム]]を、同一期間に同時実行させつつ相互に同調(コンカレント)させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非[[同期 (計算機科学)|同期]]な[[メッセージパッシング]]ではその完遂の抽象化も可能になる。対義語は順次計算(シーケンシャル)である。並行コンピューティングとも邦訳される。'''並行プログラミング'''(Concurrent programming)とも言われる。 |
|||
並行計算は、[[コンピュータプログラム]]や[[コンピュータネットワーク]]の重要な特性であり、各[[プロセス]]の各[[スレッド (コンピュータ)|スレッド]]制御などがその要点になる<ref>''Operating System Concepts'' 9th edition, Abraham Silberschatz. "Chapter 4: Threads"</ref>。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非[[同期 (計算機科学)|同期]]では他のスレッドの応答も一定の制約内で待たなくてよくなる。[[エドガー・ダイクストラ]]や[[アントニー・ホーア]]が、並行計算のパイオニアとして名高い。 |
|||
== 概要 == |
|||
汎用的なコンピュータおよび[[オペレーティングシステム]]では、ごく短時間で実行タスクを切り替えて複数のタスクを疑似的に同時実行することのできる[[マルチタスク]]システムが採用されることが多い。そして個々のタスクは、通常別々の[[プログラム (コンピュータ)|プログラム]]として実装されるか、1つのプログラムから複数の[[プロセス]]や[[スレッド (コンピュータ)|スレッド]]を生成する形で実装される。そのようなプログラムを作成することを'''並行プログラミング'''と呼ぶ。タスク群は1つのプロセッサ([[CPU]]における1つのコア)上で動作する場合、複数のプロセッサ([[マルチコア]]プロセッサもしくはマルチソケットプロセッサ)上で動作する場合 ([[マルチプロセッシング]])、あるいはネットワークを介した[[分散コンピューティング|分散システム]]で動作する場合が考えられる。並行コンピューティングは[[並列コンピューティング]]と近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。また、並列処理はスループットの改善が目的だが、並行処理は主にシステムの応答性の改善が目的である。 |
|||
== イントロダクション == |
|||
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、[[エドガー・ダイクストラ]]、Per Brinch Hansen、[[アントニー・ホーア]]が挙げられる。 |
|||
並行計算は、[[並列計算]](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}}、タスクが一つずつ実行される。 |
|||
並行計算を行うシステムの開発ではスレッド間通信やプロセス間通信を意識して開発を行う必要がある。したがって、通信に用いるプロトコルの開発も必要となる。 |
|||
並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。 |
|||
== 並行的相互作用と通信 == |
|||
並行計算システムには、並行コンポーネント間の通信を抽象化してプログラマから隠蔽するものもある([[Future パターン]]に基づいた言語機能あるいはライブラリなど)。一方、明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される: |
|||
* スレッドAの完了後に、スレッドBが実行される(シリアル・シーケンシャル) |
|||
; [[共有メモリ]]通信 |
|||
* スレッドAと、スレッドBが交互に実行される(シリアル・並行) |
|||
: 並行コンポーネント群は共有メモリの内容を更新することで通信を行う([[Java]]や[[C Sharp|C#]])。この並行プログラミング方式では、何らかの[[ロック (情報工学)|ロック]]を必要とする([[ミューテックス]]、[[セマフォ]]、[[モニタ (同期)|モニタ]]など)。 |
|||
* スレッドAと、スレッドBが同時に実行される(並列・並行) |
|||
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。 |
|||
; [[メッセージパッシング]]通信 |
|||
: 並行コンポーネント群はメッセージを交換することで通信を行う([[Erlang]]、[[Occam]])。メッセージの交換は非同期的に行われるか(「送って祈る」とも言われるが、一般にメッセージ受信が確認できないときはメッセージを再送する)、送信側がメッセージの受信を確認するまでブロック状態となって待つランデブー方式を使用する。メッセージパッシングによる並行性は共有メモリによる並行性よりも直感的に理解しやすい。また、一般にメッセージパッシングの方が頑健だが低速である。メッセージパッシングシステムを分析し理解するための数学的理論が数々存在する。例えば、[[アクターモデル]]や各種[[プロセス代数]]である。 |
|||
== リソースアクセス == |
=== リソース共有アクセス調整 === |
||
並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする[[並行性制御]]である<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>。ここでよく取り沙汰されるのは[[競合状態]]、[[デッドロック]]、[[リソーススタベーション|リソース欠乏]]などである。下は共有リソースのコード例である。 |
|||
並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソース<code>balance</code>で表される預金口座からの引き落としを行う擬似コードを以下に例として挙げる。 |
|||
<syntaxhighlight lang="java" line start="1"> |
<syntaxhighlight lang="java" line="1" start="1"> |
||
boolean withdraw(int withdrawal) { |
boolean withdraw(int withdrawal) { |
||
if (balance > withdrawal) { |
if (balance > withdrawal) { |
||
balance = balance - withdrawal; |
balance = balance - withdrawal; |
||
return true; |
return true; |
||
} |
} |
||
return false; |
|||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
<code>balance=500</code>として |
ここで<code>balance=500</code>としてプロセスAとプロセスBを走らせる。Aが<code>withdraw(300)</code>を、Bが<code>withdraw(350)</code>をコールする。Aが2行目を<code>true</code>で終えて3行目に入る前に、Bが2行目に入ると<code>balance > withdrawal</code>はここでも<code>true</code>になってしまい、AとBの双方が減算して<code>balance=-150</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=}} |
|||
*[[ソフトウェアトランザクショナルメモリ]] |
|||
*[[アトミックコミット]] |
|||
=== 一貫性モデル === |
|||
並行プログラミング言語は、[[並行性]]のための構造を備えた[[プログラミング言語]]である。具体的には、[[マルチスレッド]]、[[分散コンピューティング]]、{{仮リンク|メッセージパッシング型プログラミング|en|Message passing programming|label=メッセージパッシング}}、共有[[リソース]]([[並列ランダムアクセス機械|共有メモリ]])、[[Future パターン|Futureパターン]]のサポートなどである。 |
|||
[[一貫性モデル (ソフトウェア)|一貫性モデル]](consistency models)はメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類される[[クリティカルセクション]]の[[ロック (計算機科学)|ロック]][[同期 (計算機科学)|同期]]がよく使われる。 |
|||
== 並行計算の実装 == |
|||
並行プログラムには数々の実装手法が存在する。大抵は[[オペレーティングシステム]]が提供する[[プロセス]]と[[スレッド (コンピュータ)|スレッド]]の同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性は[[マルチタスク]]などと言われる。 |
|||
=== 相互作用と通信 === |
|||
並行コンポーネント間の通信には、例えば以下の二通りがある。 |
|||
'''ケース1''':相互通信の明示的操作を要求する形式 |
|||
:[[同期 (計算機科学)|同期]]傾向になる。明示的操作は特別なプログラム構文を必要にする。[[ソフトウェアトランザクショナルメモリ]]、[[クリティカルセクション]][[同期]]などのモデルに従っての実装になる。 |
|||
:'''[[共有メモリ]]通信''' |
|||
:並行コンポーネントたちは共有メモリの内容を更新することで通信を行う。[[Java]]や[[C Sharp|C#]]が用いている。[[クリティカルセクション]]を定めて[[ロック (情報工学)|ロック]]オブジェクトを用いての[[同期 (計算機科学)|同期]]でその範囲を[[並行性制御]]する。ロック手法には[[セマフォ]]、[[ミューテックス]]、[[モニタ (同期)|モニタ]]、[[バリア (計算機科学)|バリア]]、読み書きロックなどがある。[[スレッドセーフ]]が重視されている。 |
|||
<br/> |
|||
'''ケース2''':相互通信をプログラマから隠蔽する形式 |
|||
:非同期傾向になる。上の明示的操作をコード評価/呼出しやデータ参照/代入といった標準構文でまかなえる。[[プロセス計算]]、[[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のサポートなどである。 |
|||
{{いつ範囲|date=2019年1月|現在}}、並行性のための構造を備えた最も一般的な言語は[[Java]]と[[C Sharp|C#]]である。これらの言語は共有メモリ型並行性モデルを基本とし、[[モニタ (同期)|モニタ]]によるロックを備えている(メッセージパッシングモデルを共有メモリモデル上に構築することも可能)。メッセージパッシング型並行性モデルの言語としては、[[Erlang]]が最もよく使われている。 |
{{いつ範囲|date=2019年1月|現在}}、並行性のための構造を備えた最も一般的な言語は[[Java]]と[[C Sharp|C#]]である。これらの言語は共有メモリ型並行性モデルを基本とし、[[モニタ (同期)|モニタ]]によるロックを備えている(メッセージパッシングモデルを共有メモリモデル上に構築することも可能)。メッセージパッシング型並行性モデルの言語としては、[[Erlang]]が最もよく使われている。 |
||
63行目: | 98行目: | ||
*Joule – [[データフロー言語]]。メッセージパッシングによって通信する。 |
*Joule – [[データフロー言語]]。メッセージパッシングによって通信する。 |
||
*[[KL1]] – [[Guarded Horn Clauses]]に基づく論理型言語。[[第五世代コンピュータ]]プロジェクトの研究成果。[http://www.klic.org/software/klic/index.ja.html KLIC]などの実装が利用可能。 |
*[[KL1]] – [[Guarded Horn Clauses]]に基づく論理型言語。[[第五世代コンピュータ]]プロジェクトの研究成果。[http://www.klic.org/software/klic/index.ja.html KLIC]などの実装が利用可能。 |
||
*[[Limbo]] – Alefからの派生。Plan 9の後継である[[Inferno (オペレーティングシステム)|Inferno]]のシステム記述に使われた。 |
*[[Limbo (プログラミング言語)|Limbo]] – Alefからの派生。Plan 9の後継である[[Inferno (オペレーティングシステム)|Inferno]]のシステム記述に使われた。 |
||
*[[Oz (プログラミング言語)|Oz]] – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。 |
*[[Oz (プログラミング言語)|Oz]] – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。 |
||
**[http://www.mozart-oz.org/ Mozart Programming System] – [[クロスプラットフォーム|マルチプラットフォーム]]版 Oz |
**[http://www.mozart-oz.org/ Mozart Programming System] – [[クロスプラットフォーム|マルチプラットフォーム]]版 Oz |
||
74行目: | 109行目: | ||
他の多くの言語でもライブラリの形で並行性をサポートしている(機能的にも上記リストに挙げたものと遜色ない)。 |
他の多くの言語でもライブラリの形で並行性をサポートしている(機能的にも上記リストに挙げたものと遜色ない)。 |
||
== 並行計算モデル == |
|||
並行計算モデルはいくつか存在し、並行システムの分析と理解に使用される。以下に主なものを列挙する: |
|||
* [[アクターモデル]] |
|||
* [[ペトリネット]] |
|||
* [[プロセス代数]] |
|||
** [[アンビエント計算]] |
|||
** [[Calculus of Communicating Systems]] |
|||
** [[Communicating Sequential Processes]] |
|||
** [[π計算]] |
|||
* [[並行論理プログラミング]] |
|||
* [[並行制約プログラミング]] |
|||
== 関連項目 == |
== 関連項目 == |
||
<div style="{{column-count|2}}"> |
|||
* [[並列計算]] |
|||
*[[並列計算]] |
|||
* [[メッセージ (コンピュータ)|メッセージパッシング]] |
|||
*[[非同期IO]] |
|||
* [[:en:Ptolemy Project]] |
|||
*[[競合状態]] |
|||
*[[トランザクション処理]] |
|||
*[[ソフトウェアトランザクショナルメモリ]] |
|||
*[[クリティカルセクション]] |
|||
*[[不可分操作]] |
|||
*[[排他制御]] |
|||
*[[並行性制御]] |
|||
*[[グローバル並行性制御]] |
|||
*[[分散並行性制御]] |
|||
*[[スケジューリング]] |
|||
*[[マルチスレッド]] |
|||
*[[マルチタスク]] |
|||
*[[: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] |
*[https://web.archive.org/web/20060128114620/http://vl.fmnet.info/concurrent/ Concurrent Systems Virtual Library] |
||
{{並列コンピューティング}} |
|||
{{デフォルトソート:へいこうけいさん}} |
{{デフォルトソート:へいこうけいさん}} |
||
[[Category:オペレーティングシステムの仕組み]] |
[[Category:オペレーティングシステムの仕組み]] |
||
[[Category:並行計算|*へいこうけいさん]] |
[[Category:並行計算|*へいこうけいさん]] |
||
[[Category:エドガー・ダイクストラ]] |
[[Category:エドガー・ダイクストラ]] |
||
{{並列コンピューティング}}{{コンピュータ科学}} |
2024年7月28日 (日) 02:44時点における最新版
プログラミング・パラダイム |
---|
並行計算(へいこうけいさん、英: Concurrent computing)とは、複数の計算あるいはアルゴリズムを、同一期間に同時実行させつつ相互に同調(コンカレント)させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非同期なメッセージパッシングではその完遂の抽象化も可能になる。対義語は順次計算(シーケンシャル)である。並行コンピューティングとも邦訳される。並行プログラミング(Concurrent programming)とも言われる。
並行計算は、コンピュータプログラムやコンピュータネットワークの重要な特性であり、各プロセスの各スレッド制御などがその要点になる[1]。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非同期では他のスレッドの応答も一定の制約内で待たなくてよくなる。エドガー・ダイクストラやアントニー・ホーアが、並行計算のパイオニアとして名高い。
イントロダクション
[編集]並行計算は、並列計算(parallel computing)としばしば混同される。並列計算はマルチプロセッサ前提であり、独立した各プロセッサが割り振られた計算を同時実行することを指す。故にシングルプロセッサでは不可になる[2]。分散システム内の各コンピュータが割り振られた計算を同時実行するのもそうである。並列計算はスループット・パフォーマンス向けとされる。並列計算の対義語はマルチプロセッサのシリアル計算(serial computing)であり[3]、各プロセッサの排他的な計算順序配置が重視される。
並行計算は一つのプロセッサに複数のタスクを存在させて、各タスクに計算を割り振ることを指す[4]。そこではタイムシェアリング技術などが使われる。マルチプロセッサならば、タスクを各プロセッサに分散できるのでより効率的になる[5]。各タスクは協調する相手タスクが別プロセッサの並列性なのか、同プロセッサの並行性なのかを気にしない[6]。いわゆるマルチタスクOSでは、カーネルとアプリケーションプログラムから複数のプロセスやスレッドが生成されて、それぞれがタスクの担い手になる。並行計算はレイテンシ・パフォーマンス向けとされる。並行計算の対義語はシーケンシャル計算(sequential computing)であり[3]、タスクが一つずつ実行される。
並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。
- スレッドAの完了後に、スレッドBが実行される(シリアル・シーケンシャル)
- スレッドAと、スレッドBが交互に実行される(シリアル・並行)
- スレッドAと、スレッドBが同時に実行される(並列・並行)
並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。
リソース共有アクセス調整
[編集]並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする並行性制御である[7]。ここでよく取り沙汰されるのは競合状態、デッドロック、リソース欠乏などである。下は共有リソースのコード例である。
boolean withdraw(int withdrawal) {
if (balance > withdrawal) {
balance = balance - withdrawal;
return true;
}
return false;
}
ここでbalance=500
としてプロセスAとプロセスBを走らせる。Aがwithdraw(300)
を、Bがwithdraw(350)
をコールする。Aが2行目をtrue
で終えて3行目に入る前に、Bが2行目に入るとbalance > withdrawal
はここでもtrue
になってしまい、AとBの双方が減算してbalance=-150
となり、口座残高以上の金額が引き落とされてしまうことになる。こうしたリソース共有問題の並行性制御では、クリティカルセクションのロック(セマフォ・ミューテックス・モニタなど)同期がよく使われる。
並行システムは共有リソース(通信媒体を含む)に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの調停回路を実装する必要がある。これにより無制限の非決定性問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。だが、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな並行性問題(同期のデッドロックなど)を生じる。非ブロックアルゴリズムはそれらに対応できる並行性制御とされる。
並行計算のモデル
[編集]数々の並行計算モデルが提唱されている。
一貫性モデル
[編集]一貫性モデル(consistency models)はメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類されるクリティカルセクションのロック同期がよく使われる。
並行計算の実装
[編集]並行プログラムには数々の実装手法が存在する。大抵はオペレーティングシステムが提供するプロセスとスレッドの同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性はマルチタスクなどと言われる。
相互作用と通信
[編集]並行コンポーネント間の通信には、例えば以下の二通りがある。
ケース1:相互通信の明示的操作を要求する形式
- 同期傾向になる。明示的操作は特別なプログラム構文を必要にする。ソフトウェアトランザクショナルメモリ、クリティカルセクション同期などのモデルに従っての実装になる。
- 共有メモリ通信
- 並行コンポーネントたちは共有メモリの内容を更新することで通信を行う。JavaやC#が用いている。クリティカルセクションを定めてロックオブジェクトを用いての同期でその範囲を並行性制御する。ロック手法にはセマフォ、ミューテックス、モニタ、バリア、読み書きロックなどがある。スレッドセーフが重視されている。
ケース2:相互通信をプログラマから隠蔽する形式
- 非同期傾向になる。上の明示的操作をコード評価/呼出しやデータ参照/代入といった標準構文でまかなえる。プロセス計算、Futureなどのモデルに従っての実装になる。
- メッセージパッシング通信
- 並行コンポーネントたちはメッセージの交換で通信を行う。Erlang、Go、Scala、OpenMPI、Occamなどが用いている。メッセージ交換は通常非同期だが、チャネルという同期形式もあり、こちらでの送信側は受信側がメッセージに応答するまで待機する双方向通信になる。
- 非同期なメッセージ交換での送信側は、受信側がいま応答できるかどうかに関係なくメッセージを送れる単方向通信になる。これは送って祈る(send and pray)と形容されている。ここでの送信型は、メッセージを送るとすぐにfutureやpromiseと呼ばれる抽象的な応答オブジェクトを受け取れるので基本的に待機することはない。メッセージパッシング通信は、共有メモリ通信よりも平易で堅牢であるが、オーバーヘッドが大きいとも考えられている。メッセージパッシングには数々の数学的理論があり、アクターモデルやプロセス計算などが有名である。
並行プログラミング言語
[編集]並行プログラミング言語は、並行性のための構造を備えたプログラミング言語である。具体的には、マルチスレッド、分散コンピューティング、メッセージパッシング、共有リソース(共有メモリ)、Futureのサポートなどである。
現在[いつ?]、並行性のための構造を備えた最も一般的な言語はJavaとC#である。これらの言語は共有メモリ型並行性モデルを基本とし、モニタによるロックを備えている(メッセージパッシングモデルを共有メモリモデル上に構築することも可能)。メッセージパッシング型並行性モデルの言語としては、Erlangが最もよく使われている。
研究目的で開発された並行プログラミング言語(Pictなど)は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:
- Ada
- Afnix – データへの並行アクセスは自動的に保護される(従来はAlephと呼ばれていたが、Alefとは無関係)。
- Alef – スレッドとメッセージパッシングを備えた言語。初期のPlan 9のシステム記述に使われた言語。
- Alice – Standard ML に Future による並行性サポート機能を追加したもの
- CDL (Concurrent Description Language) – machine translatable(機械的に変換可能)、構成可能、オブジェクト指向、ビジュアルプログラミング言語。
- ChucK – 音響関連専用のプログラミング言語
- Cilk – 並行版C言語
- Clojure – LISP系の言語、JVM上で動作する。
- Concurrent C
- Concurrent Clean – 関数型言語。Haskellに近い。
- Concurrent Pascal – by Per Brinch Hansen
- Corn
- Curry
- Cω – C オメガ。C#に非同期通信を追加した研究用言語。
- E – Future機能使用。デッドロックを発生させない。
- Eiffel – 契約プログラミングに基づいたSCOOP機構による。
- Erlang – 共有のない非同期メッセージパッシングを使用。
- Janus – 宣言型言語。論理変数などをaskerとtellerに明確に区別する。
- Join Java – Javaに基づいた並行プログラミング言語。
- Joule – データフロー言語。メッセージパッシングによって通信する。
- KL1 – Guarded Horn Clausesに基づく論理型言語。第五世代コンピュータプロジェクトの研究成果。KLICなどの実装が利用可能。
- Limbo – Alefからの派生。Plan 9の後継であるInfernoのシステム記述に使われた。
- Oz – マルチパラダイム言語。共有メモリとメッセージパッシング、Futureも備えている。
- MultiLisp – Scheme に並列性サポート機能を追加した派生言語。
- Occam – Communicating Sequential Processes (CSP) の影響を強く受けている。
- Pict – ミルナーのπ計算の実装に基づいている。
- SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
- SR – 研究用言語。
他の多くの言語でもライブラリの形で並行性をサポートしている(機能的にも上記リストに挙げたものと遜色ない)。
関連項目
[編集]脚注
[編集]- ^ Operating System Concepts 9th edition, Abraham Silberschatz. "Chapter 4: Threads"
- ^ 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).
- ^ a b Patterson & Hennessy 2013, p. 503.
- ^ “Parallelism vs. Concurrency”. Haskell Wiki. 2020年1月閲覧。
- ^ Schneider, Fred B. (1997-05-06). On Concurrent Programming. Springer. ISBN 9780387949420
- ^ Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley. ISBN 978-0-321-31283-9
- ^ Ben-Ari, Mordechai (2006). Principles of Concurrent and Distributed Programming (2nd ed.). Addison-Wesley. ISBN 978-0-321-31283-9
参考文献
[編集]- Filman, Robert E.; Daniel P. Friedman (1984年). Coordinated Computing: Tools and Techniques for Distributed Software. New York: McGraw-Hill. pp. 370. ISBN 0-07-022439-0