並行計算

出典: フリー百科事典『ウィキペディア（Wikipedia）』

並行計算（へいこうけいさん、Concurrent Computing）とは、複数の相互作用を及ぼす計算タスクの（同時）並行的実行を指す。並行コンピューティングとも呼ぶ。個々のタスクは通常別々のプログラムとして実装されるか、1つのプログラムから複数のプロセスやスレッドを生成する形で実装される。そのようなプログラムを作成することを並行プログラミングと呼ぶ。タスク群は1つのプロセッサ上で動作する場合、複数プロセッサ上で動作する場合、ネットワークを介した分散システムで動作する場合が考えられる。並行コンピューティングは並列コンピューティングと近い概念だが、タスク間の相互作用を重視する点が後者とは異なる。並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。並行計算のパイオニアとしては、エドガー・ダイクストラ、Per Brinch Hansen、アントニー・ホーアが挙げられる。

[編集] 並行的相互作用と通信

並行計算システムには、並行コンポーネント間の通信をプログラマから隠蔽するものもある（ Future という言語機能など）。一方、明示的に通信を行わなければならないものもある。明示的通信は次の2種類に分類される:

共有メモリ通信: 並行コンポーネント群は共有メモリの内容を更新することで通信を行う（Java言語やC#）。この並行プログラミング方式では、何らかのロックを必要とする（ミューテックス、セマフォ、モニタなど）。

メッセージパッシング通信: 並行コンポーネント群はメッセージを交換することで通信を行う（Erlang、Occam）。メッセージの交換は非同期的に行われるか（「送って祈る」とも言われるが、一般にメッセージ受信が確認できないときはメッセージを再送する）、送信側がメッセージの受信を確認するまでブロック状態となって待つランデブー方式を使用する。メッセージパッシングによる並行性は共有メモリによる並行性よりも直感的に理解しやすい。また、一般にメッセージパッシングの方が頑健だが低速である。メッセージパッシングシステムを分析し理解するための数学的理論が数々存在する。例えば、アクターモデルや各種プロセス代数である。

[編集] リソースアクセス

並行計算の主要な課題の1つは、並行プロセスが互いの邪魔をしないようにすることである。共有リソース balance で表される預金口座からの引き落としを行う以下の擬似コードを例として掲げる:

1  bool withdraw(int withdrawal) {
2     if( balance > withdrawal ) {
3         balance = balance - withdrawal;
4         return true;
5     } else return false;
6  }

balance=500 として、2つの並行プロセスがそれぞれ withdraw(300) と withdraw(350) という引き落としを行ったとする。両方の処理の 2行目が両方の 3行目の処理の前に行われると、balance > withdrawal はどちらも true となり、両方の処理で減算に進む。しかし、そうすると総引き落とし額は口座残高を超えてしまう。このような共有リソースにからむ問題は並行性制御を必要とするか、Lock-freeとWait-freeアルゴリズムのようなノンブロッキング・アルゴリズムを必要とする。

並行システムは共有リソース（通信媒体を含む）に依存しているため、並行計算は一般にリソースへのアクセスに関する何らかの調停回路を実装する必要がある。これにより無制限の非決定性問題が生じる可能性が出てくるが、調停回路を注意深く設計すればその可能性を限りなくゼロに近づけることができる。

残念なことに、リソース上の衝突問題への解決策は数々あるが、それら解決策は複数のリソースが関わってきたときに、新たな並行性問題（デッドロックなど）を生じる。

[編集] 並行プログラミング言語

並行プログラミング言語は、並行性のための構造を備えたプログラミング言語である。具体的には、マルチスレッド、分散コンピューティング、メッセージパッシング、共有リソース（共有メモリ）、Futureなどである。

現在、並行性のための構造を備えた最も一般的な言語はJava言語とC#である。これらの言語は共有メモリ型並行性モデルを基本とし、モニタによるロックを備えている（メッセージパッシングモデルを共有メモリモデル上に構築することも可能）。メッセージパッシング型並行性モデルの言語としては、Erlang が最もよく使われている。

研究目的で開発された並行プログラミング言語（Pictなど）は実用を目的としたものより多い。しかし、Erlang、Limbo、Occam といった言語は過去20年間、何度も商用に使われてきた実績がある。並行プログラミング言語として重要と思われるものを以下に列挙する:

Ada
Afnix – データへの並行アクセスは自動的に保護される（従来は Aleph と呼ばれていたが、Alef とは無関係）。
Alef – スレッドとメッセージパッシングを備えた言語。初期の Plan 9 のシステム記述に使われた言語。
Alice – Standard ML に Future による並行性サポート機能を追加したもの
CDL (Concurrent Description Language) – 機械翻訳可能、構成可能、オブジェクト指向、ビジュアルプログラミング言語。
ChucK – 音響関連専用のプログラミング言語
Cilk – 並行版C言語
Cω – C オメガ。C# に非同期通信を追加した研究用言語。
Concurrent C
Concurrent Clean – 関数型言語。Haskell に近い。
Concurrent Pascal – by Per Brinch Hansen
Corn
Curry
E – Future機能使用。デッドロックを発生させない。
Eiffel – 契約プログラミングに基づいたSCOOP機構による。
Erlang – 共有のない非同期メッセージパッシングを使用。
Janus – 宣言型言語。論理変数などを asker と teller に明確に区別する。
Join Java – Java言語に基づいた並行プログラミング言語。
Joule – データフロー言語。メッセージパッシングによって通信する。
KL1 – Guarded Horn Clausesに基づく論理型言語。第五世代コンピュータプロジェクトの研究成果。KLICなどの実装が利用可能。
Limbo – Alef からの派生。Plan 9 の後継である Inferno のシステム記述に使われた。
Oz – マルチパラダイム言語。共有メモリとメッセージパッシング、Future も備えている。
- Mozart Programming System – マルチプラットフォーム版 Oz
MultiLisp – Scheme に並列性サポート機能を追加した派生言語。
Occam – Communicating Sequential Processes (CSP) の影響を強く受けている。
- Occam-π – Occamの派生言語。ミルナーのπ計算の考え方を導入。
Pict – ミルナーのπ計算の実装に基づいている。
SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
SR – 研究用言語。