並行計算

並行計算（へいこうけいさん、英: Concurrent computing）とは、複数の計算あるいはアルゴリズムを、同一期間に同時実行させつつ相互に同調（コンカレント）させて、次の期間開始までに互いに完遂させるという計算形態を意味している。非同期なメッセージパッシングではその完遂の抽象化も可能になる。対義語は順次計算（シーケンシャル）である。並行コンピューティングとも邦訳される。並行プログラミング（Concurrent programming）とも言われる。

並行計算は、コンピュータプログラムやコンピュータネットワークの重要な特性であり、各プロセスの各スレッド制御などがその要点になる。並行計算下の各スレッドは、一定の制約内で他のスレッドの完了を待つことなく同時にそれぞれ進行できる。非同期では他のスレッドの応答も一定の制約内で待たなくてよくなる。エドガー・ダイクストラやアントニー・ホーアが、並行計算のパイオニアとして名高い。

イントロダクション

並行計算は、並列計算（parallel computing）としばしば混同される。並列計算はマルチプロセッサ前提であり、独立した各プロセッサが割り振られた計算を同時実行することを指す。故にシングルプロセッサでは不可になる。分散システム内の各コンピュータが割り振られた計算を同時実行するのもそうである。並列計算はスループット・パフォーマンス向けとされる。並列計算の対義語はマルチプロセッサのシリアル計算（serial computing）であり、各プロセッサの排他的な計算順序配置が重視される。

並行計算は一つのプロセッサに複数のタスクを存在させて、各タスクに計算を割り振ることを指す。そこではタイムシェアリング技術などが使われる。マルチプロセッサならば、タスクを各プロセッサに分散できるのでより効率的になる。各タスクは協調する相手タスクが別プロセッサの並列性なのか、同プロセッサの並行性なのかを気にしない。いわゆるマルチタスクOSでは、カーネルとアプリケーションプログラムから複数のプロセスやスレッドが生成されて、それぞれがタスクの担い手になる。並行計算はレイテンシ・パフォーマンス向けとされる。並行計算の対義語はシーケンシャル計算（sequential computing）であり、タスクが一つずつ実行される。

並列計算・シリアル計算・並行計算・シーケンシャル計算の適性は下のようになる。

• スレッドAの完了後に、スレッドBが実行される（シリアル・シーケンシャル）
• スレッドAと、スレッドBが交互に実行される（シリアル・並行）
• スレッドAと、スレッドBが同時に実行される（並列・並行）

並行計算システムの設計における主要な課題は、タスク間の相互作用や通信の順序付けとタスク間で共有するリソースへのアクセスである。そこではスレッド間通信やプロセス間通信を意識して開発を行う必要があり、通信に用いるプロトコルの開発も必要となる。

リソース共有アクセス調整

並行計算の最も身近な課題になるのは、複数のプロセス/スレッドで一つのリソース共有するためのアクセス調整をする並行性制御である。ここでよく取り沙汰されるのは競合状態、デッドロック、リソース欠乏などである。下は共有リソースのコード例である。

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）はメモリモデルともよばれており、複数のプロセス/スレッドが同時にデータ領域に読み込み/書き込みを行っても、シーケンシャル計算と全く同じ結果が得られるようにするための計算モデルである。一貫性モデルの実装では、共有メモリ通信に分類されるクリティカルセクションのロック同期がよく使われる。

並行計算の実装

並行プログラムには数々の実装手法が存在する。大抵はオペレーティングシステムが提供するプロセスとスレッドの同時走行とその相互通信が実装の枠組みにされる。プロセス群とスレッド群の並行走行による複数作業の同時実行可能性はマルチタスクなどと言われる。

相互作用と通信

並行コンポーネント間の通信には、例えば以下の二通りがある。

ケース１：相互通信の明示的操作を要求する形式

同期傾向になる。明示的操作は特別なプログラム構文を必要にする。ソフトウェアトランザクショナルメモリ、クリティカルセクション同期などのモデルに従っての実装になる。

共有メモリ通信

並行コンポーネントたちは共有メモリの内容を更新することで通信を行う。JavaやC#が用いている。クリティカルセクションを定めてロックオブジェクトを用いての同期でその範囲を並行性制御する。ロック手法にはセマフォ、ミューテックス、モニタ、バリア、読み書きロックなどがある。スレッドセーフが重視されている。

ケース２：相互通信をプログラマから隠蔽する形式

非同期傾向になる。上の明示的操作をコード評価/呼出しやデータ参照/代入といった標準構文でまかなえる。プロセス計算、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も備えている。
  • Mozart Programming System – マルチプラットフォーム版 Oz
• MultiLisp – Scheme に並列性サポート機能を追加した派生言語。
• Occam – Communicating Sequential Processes (CSP) の影響を強く受けている。
  • Occam-π – Occamの派生言語。ミルナーのπ計算の考え方を導入。
• Pict – ミルナーのπ計算の実装に基づいている。
• SALSA – インターネット上での分散コンピューティングを指向したメッセージパッシング式の言語。
• SR – 研究用言語。

他の多くの言語でもライブラリの形で並行性をサポートしている（機能的にも上記リストに挙げたものと遜色ない）。

関連項目

• 並列計算
• 非同期IO
• 競合状態
• トランザクション処理
• ソフトウェアトランザクショナルメモリ
• クリティカルセクション
• 不可分操作
• 排他制御
• 並行性制御
• グローバル並行性制御
• 分散並行性制御
• スケジューリング
• マルチスレッド
• マルチタスク
• Ptolemy Project
• メッセージパッシング
• プロセス代数
• アクターモデル
• 同期
• ロック
• セマフォ
• ミューテックス
• モニタ
• バリア
• 非ブロックアルゴリズム

参考文献

• 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. http://ic.arc.nasa.gov/people/filman/text/dpl/dpl.html 

外部リンク

• Concurrent Systems Virtual Library