並行プログラミング

Takami Torao
  • このエントリーをはてなブックマークに追加

概要

現代の一般消費者向けコンピュータにはすべてマルチコアプロセッサとマルチタスク OS が搭載されている。また汎用プログラミング言語でも言語仕様または標準ライブラリで async/awaitFuture といった機能を積極的に取り入れる風潮が続いている。

並行プログラミングとは、そのような環境で効率的な処理を実装するために複数のタスクを同時に実行するプログラム開発のことである。並行性によりプログラムは一度に多くのタスクを処理することができるが、並行プログラムを書くことはことさら簡単なことではない。スレッドやロックなどの構造を処理し、競合状態やデッドロックなどを回避することは非常に面倒な作業であり、並行プログラミングの作成が困難である理由でもある。

Table of Contents

  1. 概要
  2. 導入
  3. 並行性プログラミング設計のパターン

導入

コンピュータに対する一連の命令はプログラム (アルゴリズム) として記述される。プロセス (process) は 1 つ以上のプロセッサ上でプログラムが実行されることによって生成される実行状態の動的なインスタンスである。並行プログラム (または並行アルゴリズム) は、共有メモリや TCP/IP などの通信媒体を介して協力する逐次的ステートマシンの集合の記述である。

並行性 (concurrency) とは 2 つ以上の処理 (計算) が同時に行われている状態でのシステム挙動の特性を表している。並行性を持つ実行形態のことを並行処理 (concurrent processing) と呼び、反対に、ある時点において実行状態となる処理がたかだか 1 つしか存在しない処理形態のことを逐次処理 (sequential processing) と呼ぶ。

\(A\) と \(B\) をそれぞれ独立した処理としたとき、逐次処理では処理 \(A\) が終了したあとでしか別の処理 \(B\) を開始できないが、並行処理では (可能であれば) 処理 \(A\) の終了を待つことなく処理 \(B\) を開始することができる。Fig 1 で例示すると、逐次処理はある時点で実行状態にあるタスク (厳密には定義しないがステップや命令のような処理単位) がたかだか 1 つしか存在しないのに対して、並行処理では同時に複数のタスクが実行状態になることができる。

Fig 1. 逐次処理と並行処理。

並行性は必ずしも複数の物理プロセッサ (演算装置) の存在を前提としていないことに注意。シングルプロセッサ環境であっても複数のタスクを実行状態として短時間で切り替えながら並行して実行することで並行性を持つことができる (このような動作をプリエンプション (preemption) やコンテキストスイッチ (CS; context switch) と呼ぶ)。反対に、複数の物理プロセッサが利用できる環境であっても、プログラムを 1 タスクごとしか実行しない/実行できないのであれば、その実行は逐次的な特性に従う。

一方で、複数の物理プロセッサが同時にタスクを実行する環境の特性並列性 (parallelism) と呼び、並列性を持つ演算処理を並列演算 (parallel computing) と呼ぶ。並行と並列はしばしば混同されるが、並列処理はマルチプロセッサやベクトルプロセッサのような環境を前提とした課題によりフォーカスしている (並行性が対象とする課題には並列性も含まれている)。この記事では並列性については深く扱わない。

ある処理をネットワークを介して複数のコンピュータで実行する計算手法を分散処理 (distributed computing) と呼ぶ。分散処理は並行/並列処理の「物理プロセッサ」にネットワーク上のコンピュータを適用したもので、その特性は並行性や並列性の課題と広く共通している。

逐次処理は線形性 (linearization) が保たれることから、並行性に起因する様々な問題が排除されている。

非同期 (asynchronous) とは、ある状態から次の状態に遷移するために時間に関する前提がないことを意味する。つまり非同期処理は任意の速度で逐次処理を進行することができる。

並行性プログラミング設計のパターン

ソフトウェア開発で一般的に利用されているプログラミング言語の中で、言語仕様と標準ライブラリのレベルでマルチスレッド機能が利用できるようになったのは Java (1996) が最初である。Win95 や Linux などのマルチタスク OS が普及する時勢に後押しされて (”エージェント指向” のような言葉が生まれるなど) 世間ではマルチスレッドを前提としたプログラミングの理解が進んだ。

当初こそ無造作にスレッドを起動するような設計が多く見られたが、x86 環境におけるコンテキストスイッチのコストの高さから、現在では限られた数のスレッド / プロセスリソースのそれぞれをなるべく wait させないで効率的に使用する設計が主流となりつつある。