メモ: 並行性はどのシステムにも該当するので、ここではその概念について説明します。ただし、リアルタイムで外部のイベントに応答する必要があるシステム、厳しい期限があることが多いシステムでは、並行性は特に重要です。このクラスのシステム特有の要求を満たすために、RUP (Rational Unified Process) には Real-Time (Reactive) System Extensions があります。

トピック

並行性とは ページの先頭へ

並行性とは、1 つのシステム内で複数の物事が同時に発生する傾向のことです。並行性はもちろん自然な現象です。現実の世界では、いつでも多くの物事が同時に発生しています。現実世界のシステムの監視と制御を行うソフトウェアを設計するには、この自然な並行性に対処しなければなりません。

ソフトウェア システムで並行性の問題に対処する場合、一般的に、2 つの重要な側面があります。1 つは、ランダムな順番で発生する外部イベントの検出と応答ができること、もう 1 つは、必要最低限の間隔でこうしたイベントに応答できることです。

それぞれの並行作業が独立して進行する、つまり本当に並行するならば、比較的単純になります。なぜなら、各作業に対処するプログラムを別個に作成するだけで済むからです。並行システムの設計が難しくなる主な原因は、並行作業の間に発生する相互作用です。並行作業が相互に作用するときに、なんらかの調整が必要になります。

図 1: 並行性が稼働している例: 並行作業が相互に作用しない場合は、並行性の問題は単純です。並行作業が相互に作用する場合、または同じリソースを共有する場合は、並行性の問題が重要になります。

車両の交通にたとえて考えるとわかりやすくなります。異なる道路を並行して走る交通の流れがほとんど相互に作用しない場合は、問題はほとんどありません。隣り合った車線を並行して走る交通の流れの場合は、安全な相互作用のために多少の調整は必要ですが、交差点のほうがはるかに重大な相互作用が発生し、注意深い調整が必要になります。

並行性に関心を持つ理由 ページの先頭へ

並行性が必要になる要因の一部は外部的なものです。つまり、環境の要求によって並行性が必要になります。現実世界のシステムでは、多くの物事が同時に発生しており、ソフトウェアによって「リアルタイム」で対処しなければなりません。そのために、多くの現実世界のソフトウェア システムは、「反応が速い」ものでなければなりません。外部で生成され、ランダムな間隔かランダムな順序またはその両方で発生するイベントに応答しなければなりません。

従来の手続き的なプログラムを設計してこれらの状況に対処すると、きわめて複雑になります。これらの各イベントに対処する並行ソフトウェア要素にシステムを分割すれば、はるかに単純にすることができます。ここで鍵となる言葉は「することができる」です。なぜなら、イベント間の相互作用の程度も複雑さに影響するからです。

並行性が必要になる理由には内部的なものもあります (参考資料 [LEA97])。複数の CPU が使用可能な場合は、並行してタスクを実行すると、システムの計算作業を大幅にスピードアップできます。プロセッサが 1 つの場合も、マルチタスキングを行うと、たとえば 1 つの作業が入出力を待つ間に別の作業を妨害しなくなるので、劇的なスピードアップが可能になります。このような状況が発生する一般的な例の 1 つが、システムの起動時です。多くの場合は多数のコンポーネントがあり、操作可能にするための時間が各コンポーネントで必要になります。これらの操作が順番に実行される場合は、苦痛なほど時間がかかる可能性があります。

システムのコントロールのしやすさも、並行性によって向上します。たとえば、1 つの機能について、ほかの並行する機能によって開始、停止、ストリーム途中でのそのほかの作用ができますが、これは並行コンポーネントを使用しないと実現がきわめて困難です。

並行ソフトウェアが困難である理由 ページの先頭へ

これまで説明したような多数の利点があっても、並行プログラミングがどこにでも使用されるわけではない理由は次のとおりです。

大部分のコンピュータとプログラミング言語は、本質的に順番に処理されるもの (順次) です。プロシージャやプロセッサは、一度に 1 つの命令を実行します。1 つの順次プロセッサの中では、異なるタスクの実行をインタリーブすることで、見せかけの並行性を実現しなければなりません。難しい点は、そのようにする仕組みではなく、相互に作用する可能性があるプログラム セグメントをいつどのようにインタリーブするかの決定にあります。

プロセッサが複数の場合、並行性の実現は容易ですが、相互作用がより複雑になります。まず、異なるプロセッサで実行されるタスク間のコミュニケーションの問題があります。通常、複数レイヤのソフトウェアが関与するので、複雑さが増し、タイミングのオーバーヘッドが増加します。決定性は、複数の CPU を持つシステムでは減少します。なぜなら、クロックとタイミングが異なる場合があり、コンポーネントが単独で失敗することがあるからです。

最後の理由は、並行システムは明示的なグローバル システム状態がないので、理解しにくくなる点です。並行システムの状態は、そのコンポーネントの状態の集約になります。

並行するリアルタイム システムの例: エレベータ システム ページの先頭へ

並行性の概念を説明するための例として、エレベータ システムを使用します。厳密に言うと、ビルの 1 か所にある一群のエレベータを制御するように設計されたコンピュータ システムを使用します。一群のエレベータでは、多くの物事が並行して発生しているときもあれば、何も発生していないときもあります。いつでもどこかの階でエレベータが呼び出される可能性があり、そのほかの要求が処理待ちである可能性があります。待機状態のエレベータもあれば、乗客を運んでいるエレベータ、呼び出された階に向かっているエレベータ、乗客を運びながら呼び出し階に向かうエレベータもあります。適切なときに扉を開閉しなければなりません。乗客が扉の開閉の妨げになったり、扉の開閉ボタンを押したり、行き先階のボタンを押したり、押した後で行き先を変えたりします。表示の更新、モーターの制御などが必要になり、そのすべてをエレベータ制御システムの監視下で行わなければなりません。総合的に見て、エレベータ システムは並行性の概念を説明するモデルとして適しており、誰もが同程度の理解と用語知識を持っています。



図 2: 11 階に分散した 5 人がエレベータを待ち、エレベータが 2 台稼働しているシナリオ

エレベータに乗ろうとする人たちが、異なる時点でシステムに要求を送ります。システムは、総合的に最良のサービスを提供するために、エレベータの現在の状態と予想応答時間に基づいて、呼び出しに応じるエレベータを選択します。たとえば、最初にアンディが下ボタンを押してエレベータを呼び出し、2 台とも待機状態だった場合、最寄りのエレベータ 2 が応答しますが、このエレベータはアンディを乗せるためにまず上に移動しなければなりません。そのすぐ後にボブが上ボタンを押して呼び出した場合、エレベータ 2 より遠くにいたエレベータ 1 が応答します。なぜなら、エレベータ 2 は、アンディがこれから指定する階に向かってまず下に行かなければならず、それからでないと上に行く呼び出しに応じられないと認識されているからです。

単純化戦略としての並行性 ページの先頭へ

エレベータ システムが制御するエレベータが 1 台しかなく、そのエレベータが一度に 1 人しか乗せられない場合、通常の順次プログラムで処理できると考えがちです。この「単純な」場合でさえ、さまざまな状況に対応するためにプログラムに多数の分岐が必要になります。たとえば、呼び出した人がエレベータに乗らず、行き先階を選択しなかった場合は、エレベータをリセットして、別の呼び出しに応答できるようにします。

並行性が必要になる外部的な要因について前に説明しましたが、複数の呼び出し、および複数の乗客からの要求に対して通常必要な対処は、こうした要因の例といえます。エレベータを呼び出す人たちは各自の並行した生活を送っているので、エレベータの状態に関係なく、一見ランダムな間隔でエレベータを要求します。いつでもこれらの外部イベントに応答でき、過去の決定に従ってエレベータを動かし続ける順次プログラムを設計することはきわめて困難です。

並行性の抽象化 ページの先頭へ

並行システムを効果的に設計するには、システム内での並行性の役割を論理的に判断できなければなりません。それには、並行性そのものの抽象化が必要です。

並行システムの基本的な構築単位は、多少なりとも相互に独立して進行する「作業」です。Buhr の「タイムスレッド」という図による抽象化が、このような作業について考える際に役立ちます (参考資料 [BUH96])。図 3 に示したエレベータのシナリオは、実際にはこの方法の一形式を使用しています。各作業を表す際に、その作業が移動する線を使用しています。大きい点は、作業の開始場所、または先に進むために作業がイベントの発生を待っている場所を表します。1 つの作業が別の作業の進行をトリガすることができ、タイムスレッド表記法ではこれを表す際に、別のタイムスレッド上の待機場所をタッチします。

図 3: 実行スレッドの図示

ソフトウェアの基本的な構築単位は、プロシージャとデータ構造ですが、これだけでは並行性について論理的に判断するのに不十分です。プロセッサはプロシージャを実行するときに、現在の状況に応じて特定のパスに従います。このパスは「実行スレッド」または「コントロール スレッド」とも呼ばれます。このコントロール スレッドはその時点の状況に応じて異なる分岐またはループをとり、リアルタイム システムでは、指定された時間だけ一時停止するか、スケジュール設定された時間だけ待機してから再開することもあります。

プログラム設計者の観点では、実行スレッドはプログラム内の論理によってコントロールされ、オペレーティング システムによってスケジュール設定されます。1 つのプロシージャが別のプロシージャを呼び出すようにソフトウェア設計者が選択した場合、実行スレッドが 1 つのプロシージャから別のプロシージャにジャンプし、return 文が検出されたらジャンプ前の場所に戻って先に進みます。

CPU の観点では、ソフトウェア全体にわたるメインの実行スレッドは 1 つしかなく、ハードウェア割り込みに応答して実行される別個の短いスレッドによって補足されます。そのほかすべてがこのモデルに基づくので、設計者がこのモデルについて知っておくことは重要です。リアルタイム システムの設計者は、そのほかのタイプのソフトウェアの設計者よりも、システムの仕組みを非常に詳細なレベルで理解しなければなりません。ただし、このモデルは、非常に低レベルの抽象化なので、非常に粗い粒度 (CPU の粒度) でしか並行性を表すことができません。複雑なシステムを設計するには、さまざまな抽象化レベルで作業できると便利です。言うまでもなく、抽象化は、当面の問題にとって重要な点に注目できるように不要な詳細を省くビューまたはモデルを作成することです。

1 レベル上がる場合、通常はレイヤによってソフトウェアを考えます。最も基本的なレベルでは、オペレーティング システム (OS) はハードウェアとアプリケーション ソフトウェアの間でレイヤ化されています。OS は、メモリ、タイミング、入出力などのハードウェア ベースのサービスをアプリケーションに提供しますが、実際のハードウェア構成から独立した仮想マシンを作成するように CPU を抽象化します。

並行性の実現: メカニズム ページの先頭へ

コントロール スレッドの管理ページの先頭へ

並行性をサポートするには、システムが複数のコントロール スレッドに備えていなければなりません。コントロール スレッドの抽象化は、ハードウェアとソフトウェアによってさまざまな方法で実装できます。最も一般的なメカニズムは、次のいずれかのバリエーションです (参考資料 [DEI84]、参考資料 [TAN86])。

  • マルチプロセシング — 複数の CPU を並行して実行する
  • マルチタスキング — オペレーティング システムが、
    異なるタスクの実行をインタリーブすることで、1 つの CPU 上で並行性をシミュレーションする
  • アプリケーション ベースの解決法 — 適切な時点での異なる分岐コード間の切り替えを
    アプリケーション ソフトウェアが行う

マルチタスキング ページの先頭へ

オペレーティング システムがマルチタスキングを提供する場合、一般的な並行性の単位はプロセスです。プロセスとは、プログラムを実行する環境の提供を唯一の目的とするオペレーティング システムが提供、サポート、管理するエンティティです。プロセスは、アプリケーション プログラムが排他的に使用するメモリ空間、アプリケーション プログラムを実行するための実行スレッド、そしておそらくほかのプロセッサとの間でメッセージを送受信するなんらかの方法を提供します。つまり、プロセスとは、並行するアプリケーションの部分を実行するための仮想の CPU です。

各プロセスは、次の 3 つの状態になります。

  • 停止中 — 入力を待っているか、リソースのコントロールの取得を待っている
  • 準備完了 — オペレーティング システムから実行の順番が与えられるのを待っている
  • 実行中 — 実際に CPU を使用している

プロセスには多くの場合、相対的な優先順位も割り当てられます。オペレーティング システムのカーネルは、どの時点にどのプロセスを実行するかを、状態、優先順位、なんらかのスケジューリング ポリシーに基づいて決定します。マルチタスキング オペレーティング システムは、実際にはすべてのプロセスで 1 つのコントロール スレッドを共有します。

メモ: 「タスク」と「プロセス」という用語は、多くの場合、互いに置き換えて使用できます。しかし、「マルチタスキング」という用語は、複数のプロセスを一度に管理できることという意味で一般に使用されていますが、「マルチプロセシング」は複数のプロセッサ (CPU) を持つシステムを指します。この定義が最も一般的に受け入れられているので、本書はこの定義に従います。ただし、「タスク」という用語を乱用しないようにします。使用する場合は、行われる作業の単位 (タスク) と、そのためのリソースと環境を提供するエンティティ (プロセス) とを明確に区別することを目的としています。

前に示したように、CPU の観点では、実行スレッドは 1 つしかありません。アプリケーション プログラムがサブルーチンを呼び出して 1 つのプロシージャから別のプロシージャにジャンプできるのと同様に、オペレーティング システムは、割り込みの発生やプロシージャの完了などのイベントの発生時に、1 つのプロセスから別のプロセスにコントロールを移すことができます。プロセスによって与えられるメモリ保護のために、この「タスク切り替え」は多大なオーバーヘッドをもたらす可能性があります。さらに、スケジューリング ポリシーとプロセスの状態はアプリケーションの観点とほとんど関係がないので、プロセスのインタリーブは、アプリケーションに重要な種類の並行性を考えるための抽象化としては、通常はレベルが低すぎます。

並行性を論理的に明確に判断するには、実行スレッドの概念とタスク切り替えの概念とを明確に区別することが重要です。各プロセスは各自の実行スレッドを維持すると考えることができます。オペレーティング システムがプロセスを切り替えるときに、1 つの実行スレッドが一時的に割り込みされ、別の実行スレッドが開始されるか、以前に停止した場所から再開されます。

マルチスレッディング ページの先頭へ

多くのオペレーティング システム、特にリアルタイム アプリケーションに使用されるオペレーティング システムは、「スレッド」や「軽量スレッド」と呼ばれる、プロセスの「軽量」の代替を提供します。

スレッドは、プロセスの中でやや細かい粒度の並行性を実現するための方法の 1 つです。それぞれのスレッドは 1 つのプロセスに属し、1 つのプロセス内のすべてのスレッドが 1 つのメモリ空間を共有し、そのプロセスがコントロールするそのほかのリソースも共有します。

通常は、実行するプロシージャが各スレッドに割り当てられます。

メモ: 残念なことに、「スレッド」という用語には多くの意味が詰め込まれすぎています。「スレッド」という用語を単独で使用する場合は、本書で使用しているように、オペレーティング システムが提供と管理をする「物理的なスレッド」を意味しています。前に示した「実行スレッド」、「コントロール スレッド」、「タイムスレッド」という用語では、物理的なスレッドに必ずしも関連していない抽象化を意味しています。

マルチプロセシング ページの先頭へ

マルチプロセシングは複数のプロセッサを持つシステムを指し、複数のプロセッサは、真に並行する実行の機会を提供します。通常は、特定プロセッサ内のプロセスに各タスクが永続的に割り当てられますが、状況によっては、次に使用可能なプロセッサにタスクを動的に割り当てることができます。これを実現する最も容易な方法は、「対称的マルチ プロセッサ」を使用することです。このようなハードウェア構成では、複数の CPU が共通のバスによってメモリにアクセスできます。

対称的マルチプロセッサをサポートするオペレーティング システムは、使用可能な任意の CPU にスレッドを動的に割り当てることができます。対称的マルチプロセッサをサポートするオペレーティング システムには、SUN の Solaris、Microsoft の Windows NT などがあります。

並行ソフトウェアの基本的な問題 ページの先頭へ

並行性によってソフトウェアの複雑さが増したり軽減したりするという一見矛盾する説明を、前に示しました。並行ソフトウェアが複雑な問題に単純な解決法を提供する主な理由は、並行作業間での「問題の分離」を可能にするからです。この点で、並行性はソフトウェアのモジュール性を高めるツールの 1 つにすぎません。あるシステムが、顕著に独立している作業を実行しなければならない場合、または顕著に独立しているイベントに応答しなければならない場合、個別の並行コンポーネントに作業を割り当てると、自然に設計が単純になります。

並行ソフトウェアに関連して複雑さが増す原因のほとんどは、これらの並行作業がほぼ独立しているが完全には独立していない状況です。言い換えると、作業の相互作用によって複雑さが生じます。実際的観点では、非同期の作業の相互作用では、なんらかのシグナルまたは情報の交換が常に必要になります。並行するコントロール スレッドの相互作用によって、並行システムに固有のさまざまな問題が発生します。システムが正しく作動するにはこの問題に対処しなければなりません。

非同期相互作用と同期相互作用 ページの先頭へ

プロセス間コミュニケーション (IPC) または スレッド間コミュニケーションのメカニズムには、さまざまな具体的な実現方法がありますが、最終的にすべてを次の 2 つのカテゴリに分類できます。

非同期コミュニケーションでは、受信側に受信の準備ができているかどうかに関係なく、送信作業が情報を転送します。情報を送り出した後は、送信側は次に必要な作業に進みます。受信側に情報を受信する準備ができていない場合は、受信側が後で取り出せるようにその情報がキューに入れられます。送信側と受信側の両方が相互に非同期に動作するので、相互の状態を想定することができません。非同期コミュニケーションは多くの場合、メッセージ パッシングと呼ばれます。

同期コミュニケーションには、送信側と受信側の同期、そして情報の交換が含まれます。情報の交換の間、2 つの並行作業が相互にマージし、事実上共有されたセグメントのコードを実行し、コミュニケーションが完了すると再度分解します。したがって、その間は 2 つの作業が相互に同期し、相互の並行性の競合には影響されません。コミュニケーションの準備が一方の作業 (送信側または受信側) でできても他方でできていない場合は、他方でも準備ができるまで作業が一時停止されます。このため、同期コミュニケーションはランデブーと呼ばれることもあります。

同期コミュニケーションに発生する可能性のある問題は、ある作業が他方の準備ができるまで待っている間は、ほかのイベントに反応できないことです。多くのリアルタイム システムでは、この問題が受け入れられるとは限りません。なぜなら、重要な状況に対するタイミングのよい応答が保証できなくなるからです。もう 1 つの欠点は、デッドロックになりやすいことです。デッドロックは、複数の作業が相互に待ち続ける悪循環に陥った場合に発生します。

並行作業の間で相互作用が必要な場合、設計者は同期と非同期のいずれかの方法を選択しなければなりません。同期の場合、複数の並行するコントロール スレッドが 1 つの時点でランデブーしなければなりません。その場合、通常、1 つのコントロール スレッドは、別のコントロール スレッドが要求に応答するまで待たなければなりません。最も単純でよくある同期相互作用は、並行作業 A が自分の処理を進めるために並行作業 B に情報を要求する場合に発生します。

もちろん、同期相互作用は、並行でないソフトウェアのコンポーネントにとっては標準です。通常のプロシージャ コールは、同期相互作用の主な例の 1 つです。1 つのプロシージャが別のプロシージャを呼び出すと、呼び出し元は、呼び出し先のプロシージャに瞬時にコントロールを移し、コントロールが戻ってくるのを効果的に「待ち」ます。ただし、並行する世界では、そのままでは独立しているコントロール スレッドを同期するのに追加の機構が必要です。

非同期相互作用では、ランデブーがタイミングよく行われる必要はありませんが、2 つのコントロール スレッド間のコミュニケーションをサポートする追加の機構は必要です。多くの場合、この機構は、メッセージ キューとのコミュニケーション チャネルの形式をとるので、メッセージを非同期に送受信できます。

応答を待つ必要があるか、メッセージの受信側がメッセージを処理している間にほかのことができるかに応じて、1 つのアプリケーションで同期と非同期のコミュニケーションを混在させることができます。

プロセスまたはスレッドの真の並行性は、プロセスまたはスレッドを並行して実行するマルチプロセッサでのみ可能になります。プロセッサが 1 つの場合は、オペレーティング システムのスケジューラによってスレッドまたはプロセスを同時に実行するように見せかけています。つまり、使用可能な処理リソースを細かく分けているので、複数のスレッドまたはプロセスを同時に実行しているように見えます。設計があまり良くない場合、同期して頻繁にコミュニケーションする複数のプロセスまたはスレッドを作成し、プロセスまたはスレッドが別のプロセスまたはスレッドからの応答を効果的に妨害することと応答を待つことに「タイム スライス」の大部分を費やすことになり、このタイム スライシングが機能しません。

共有リソースの競合 ページの先頭へ

並行作業は、相互に共有が必要な数少ないリソースに依存することがあります。その典型的な例は入出力デバイスです。ある作業で、別の作業が使用中のリソースを必要な場合は、順番を待たなければなりません。

競合状態: 一貫状態の問題ページの先頭へ

おそらく並行システムの設計の最も基本的な問題は、「競合状態」を避けることです。状態依存の機能 (つまり、システムの現在の状態に応じて結果が異なる機能) をシステムの一部が実行しなければならない場合、操作の間は状態が安定していることが確実でなければなりません。言い換えると、特定の操作が「最小」でなければなりません。複数のコントロール スレッドが同じ状態情報を使用できる場合は、1 つのスレッドが状態依存の最小の操作を実行している間に別のスレッドが状態を変更しないようにするために、常になんらかの「並行性コントロール」が必要になります。同じ状態情報を同時に使用しようとして、内部で状態の一貫性がとれなくなる可能性があることを、「競合状態」といいます。

エレベータ システムで乗客が停止階を選択したときに、競合状態の典型的な例の 1 つが容易に発生します。前に示したエレベータは、上と下の各方向に移動するときの停止階のリストに基づいて動きます。エレベータが階に停止するたびに、1 つのコントロール スレッドが、該当方向のリストからその階を削除し、次の停止階をリストから取得します。リストが空の場合、もう一方のリストに停止階がある場合は方向を変え、両方のリストが空の場合は待機状態になります。もう 1 つのコントロール スレッドは、乗客が停止階を選択したときにその要求を上または下方向のリストに入れています。それぞれのスレッドは、本質的に最小でないリスト上の操作の組み合わせを実行します。たとえば、次に使用可能なスロットをチェックしてからそのスロットを埋めます。2 つのスレッドがもし操作をインタリーブした場合、リスト内の同じスロットを容易に上書きする可能性があります。

デッドロック ページの先頭へ

デッドロックとは、2 つのコントロール スレッドが相互に妨害し合い、それぞれに相手がなんらかのアクションを実行するのを待つ状態です。皮肉なことに、デッドロックは多くの場合、競合状態を防止するために同期メカニズムを適用することで発生します。

エレベータでの競合状態の例では、害が比較的少ないデッドロックが容易に生じる可能性があります。エレベータの制御のスレッドは、リストが空だと判断するので、別の階に移動しません。停止階の要求のスレッドは、エレベータがリストを空にするために稼働中なので待機状態を解除するようにエレベータに通知する必要がないと判断します。

そのほかの実際的問題 ページの先頭へ

「基本的」な問題のほかにも、並行ソフトウェアの設計時に明示的に対処しなければならないいくつかの実際的問題があります。

性能のトレードオフ ページの先頭へ

1 つの CPU の中では、タスクの切り替えで並行性をシミュレーションするために必要なメカニズムが、CPU サイクルを使用し、その分をアプリケーション自身が使用できなくなります。その反面、たとえばソフトウェアが入出力デバイスを待たなければならない場合、並行性によって可能になる性能の向上がオーバーヘッドの増加をはるかに上回ることがあります。

複雑さのトレードオフ ページの先頭へ

並行ソフトウェアでは、順次プログラミングのアプリケーションでは不要な調整メカニズムとコントロール メカニズムが必要になります。したがって、並行ソフトウェアのほうが複雑になり、エラーが起きやすくなります。また、並行システムでは複数のコントロール スレッドがあるので、問題の診断が本質的に困難です。その反面、前に示したように、外部的な要因そのものが並行している場合、異なるイベントを独立して処理する並行ソフトウェアは、イベントを任意の順番で処理しなければならない順次プログラムに比べてはるかに単純になります。

非決定性 ページの先頭へ

並行コンポーネントの実行のインタリーブは多数の要素によって決定されるので、同じソフトウェアが同じ連続イベントに異なる順番で応答することがあります。設計によっては、このような順番の変更で結果が異なる可能性があります。

並行性コントロールでアプリケーション ソフトウェアが果たす役割 ページの先頭へ

並行性コントロールの実装にはアプリケーション ソフトウェアが関与することも、関与しないこともあります。アプリケーション ソフトウェアが果たすさまざまな役割を、関与の程度の順に示します。

  1. アプリケーション タスクが、オペレーティング システムによっていつでも割り込まれます (プリエンプティブ マルチタスキング)。
  2. アプリケーション タスクが、割り込まれない処理の最小単位 (クリティカル セクション) を定義でき、その開始時と終了時をオペレーティング システムに通知できます。
  3. アプリケーション タスクが、ほかのタスクに CPU のコントロールを明け渡す時点を決定できます (連携マルチタスキング)。
  4. アプリケーション ソフトウェアが、さまざまなタスクの実行のスケジューリングとコントロールを全面的に担当します。

これらの役割は、完全なセットになっているのでもなければ、相互に排他的でもありません。どのシステムでも、これらを組み合わせて使用できます。

並行性の抽象化 ページの先頭へ

並行システムの設計でよくある間違いは、並行性を実現するメカニズムを、設計プロセスのきわめて初期に選択してしまうことです。どのメカニズムにも長所と短所があり、特定の状況に「最適な」メカニズムの選択が、微妙なトレードオフや妥協によって決定されることも珍しくありません。メカニズムを早期に選択するほど、選択時に使用できる情報も少なくなります。メカニズムを決定すると、さまざまな状況に対する設計の柔軟性と適合性も減少する傾向があります。

最も複雑な設計タスクと同様に、並行性は、複数レベルの抽象化を採用することで最もよく理解されます。まず、望ましい振る舞いについて、システムの機能要求をよく理解しなければなりません。次に、並行性の可能な役割を調査する必要があります。そのための最良の方法は、特定の実装にこだわらずに、スレッドの抽象化を使用することです。可能なかぎり、並行性を実現するためのメカニズムの最終的な選択は未定にしておき、性能の微調整と、製品構成に応じてコンポーネントの配布を変える柔軟な対応ができるようにします。

問題ドメイン (例: エレベータ システム) と解決法ドメイン (ソフトウェア構造) との「概念的な距離」は、依然としてシステム設計の最大の難問の 1 つです。「視覚的な形式性」は、並行する振る舞いなどの複雑なアイデアの理解とコミュニケーションに、そして実際にはその概念的なギャップを埋めるためにきわめて役立ちます。このような問題の解決に役立つことが実証されているツールには、たとえば次のようなものがあります。

  • 並行して作動するコンポーネントの構想を立てるためのモジュール ダイアグラム
  • 相互に作用する並行作業の構想を立てるためのタイムスレッド (コンポーネントと直交する可能性あり)
  • コンポーネントの相互作用を視覚化するためのシーケンス図
  • コンポーネントの状態と状態依存の振る舞いを定義するための状態遷移ダイアグラム チャート

並行コンポーネントとしてのオブジェクト ページの先頭へ

並行ソフトウェア システムを設計するには、ソフトウェアの構築単位 (プロシージャとデータ構造) を並行性の構築単位 (コントロール スレッド) と組み合わせなければなりません。並行作業の概念については前に示しましたが、システムは作業からは作成しません。システムはコンポーネントから作成し、並行コンポーネントから並行システムを作成することは道理に適っています。単独では、プロシージャ、データ構造、コントロール スレッドのいずれも、並行コンポーネントの非常に自然なモデルにはなりませんが、オブジェクトは、これらの必要な要素のすべてを組み合わせて 1 つのまとまったパッケージにする非常に自然な方法に見えます。

オブジェクトは、プロシージャとデータ構造をパッケージにし、独自の状態と振る舞いを持つまとまったコンポーネントを作成します。オブジェクトは、その状態と振る舞いの特定の実装をカプセル化し、ほかのオブジェクトまたはソフトウェアとの相互作用を可能にするインターフェイスを定義します。オブジェクトは通常は、現実世界のエンティティまたは概念をモデリングし、メッセージの交換によってほかのオブジェクトと相互に作用します。現在では、オブジェクトは複雑なシステムを構築する最良の方法として多くの設計者から受け入れられています。

図 4: エレベータ システムのための単純なオブジェクトのセット


エレベータ システムのオブジェクト モデルを考えてみます。各階の呼び出し取り次ぎオブジェクトは、その階での上下の呼び出しボタンを監視します。ボタンが押されると、呼び出し取り次ぎオブジェクトはエレベータ派遣オブジェクトにメッセージを送信することで応答します。エレベータ派遣オブジェクトは、最も速くサービスを提供できる可能性が最も高いエレベータを選択し、そのエレベータを派遣し、呼び出しに対して肯定応答をします。各エレベータ オブジェクトは、並行かつ独立してそれぞれの物理的なエレベータを制御し、停止階の選択や派遣の呼び出しに応答します。

並行性は、このようなオブジェクト モデルで 2 つの形式をとることができます。オブジェクト間並行性は、複数のオブジェクトが別個のコントロール スレッドによって独立して作業を実行している場合に発生します。オブジェクト内並行性は、複数のコントロール スレッドが 1 つのオブジェクト内でアクティブ (能動的) である場合に発生します。現在の大部分のオブジェクト指向言語では、オブジェクトは「パッシブ (受動的)」であり、自分のコントロール スレッドを持っていません。コントロール スレッドが外部の環境によって提供されなければなりません。通常、この環境は、C++ や Smalltalk などの言語で作成されたオブジェクト指向「プログラム」を実行するために作成された標準的な OS プロセスです。OS がマルチスレッディングをサポートする場合、同じオブジェクトまたは異なるオブジェクト内で複数のスレッドをアクティブにできます。

次の図では、パッシブ オブジェクトを円形の要素で表しています。各オブジェクトの影付きの内側の領域は、そのオブジェクトの状態情報であり、分割された外側の輪は、オブジェクトの振る舞いを定義するプロシージャ (メソッド) のセットです。


図 5: オブジェクトの相互作用の説明図

オブジェクト内並行性は、並行ソフトウェアの問題をすべて伴います。たとえば、複数のコントロール スレッドが同じメモリ空間 (この場合はオブジェクト内にカプセル化されたデータ) を使用できる場合に、競合状態が生じる可能性があります。データのカプセル化がこの問題の解決法を提供するように思えるかもしれません。もちろん、問題はオブジェクトがコントロール スレッドをカプセル化しないことにあります。オブジェクト間並行性は、これらの問題をおおむね回避しますが、面倒な問題が 1 つ残ります。2 つの並行オブジェクトがメッセージの交換によって相互に作用するには、少なくとも 2 つのコントロール スレッドがメッセージを処理し、それを渡すために同じメモリ空間を使用できなければなりません。関連する (がさらに困難な) 問題は、異なるプロセス間、または異なるプロセッサ間でさえもオブジェクトを配布するという問題です。異なるプロセス内のオブジェクト間のメッセージには、プロセス間コミュニケーションのサポートが必要であり、通常は、メッセージのエンコードとデコードによって、プロセスの境界を越えて渡すことができるデータにする必要があります。

もちろん、これらの問題はどれも克服可能です。実際、前に示したとおり、すべての並行システムはこれらの問題に対処しなければならないので、実証済みの解決法があります。「並行性コントロール」によって追加の作業が必要になり、エラーの機会が増えるというだけのことです。さらに、アプリケーションの問題の本質があいまいになります。これらのすべての理由から、アプリケーション プログラマが明示的にこの問題に対処する必要性を最低限にしたいと思います。その方法の 1 つは、並行オブジェクト間でのメッセージ パッシング (並行性コントロールを含む) をサポートするオブジェクト指向環境を構築し、1 つのオブジェクト内での複数のコントロール スレッドの使用を最低限にするか排除することです。要するに、これによってコントロール スレッドがデータと共にカプセル化されます。

アクティブ オブジェクト モデル ページの先頭へ

自分のコントロール スレッドを持つオブジェクトは、「アクティブ オブジェクト」と呼ばれます。ほかのアクティブ オブジェクトとの非同期コミュニケーションをサポートするために、各アクティブ オブジェクトにはメッセージ キュー、すなわち「メールボックス」が提供されます。オブジェクトが作成されると、そのオブジェクト独自のコントロール スレッドが環境から与えられ、オブジェクトは停止するまでこのコントロール スレッドによってカプセル化されます。パッシブ オブジェクトと同様に、アクティブ オブジェクトも外部からメッセージが到着するまで遊休状態になっています。このオブジェクトは、到着したメッセージの処理に適切なコードを実行します。オブジェクトがビジー状態の間に到着したメッセージは、メールボックスに入れられます。オブジェクトはメッセージの処理を 1 つ完了すると、メールボックス内で待機している次のメッセージを取り出すか、新しいメッセージの到着を待ちます。エレベータ システムでアクティブ オブジェクトに適した候補は、エレベータそのもの、各階の呼び出し取り次ぎ、派遣などです。

アクティブ オブジェクトは、実装によってはかなり効率的にできます。ただし、アクティブ オブジェクトはパッシブ オブジェクトよりオーバーヘッドが大きくなります。したがって、すべての操作を並行させる必要はないので、普通は同一システム内にアクティブ オブジェクトとパッシブ オブジェクトを混在させます。アクティブ オブジェクトとパッシブ オブジェクトはコミュニケーションのスタイルが異なるので、ピアにすることは困難ですが、アクティブ オブジェクトは、前に使用した OS プロセス に置き換わってパッシブ オブジェクトの理想的な環境になります。実際、アクティブ オブジェクトがすべての作業をパッシブ オブジェクトに委譲すると、プロセス間コミュニケーション機能を持つ OS プロセスまたはスレッドと基本的には等しくなります。ただし、アクティブ オブジェクトのほうが興味深いのは、作業の一部を行う独自の振る舞いを持ち、残りの作業をパッシブ オブジェクトに委譲する点です。

図 6: パッシブ クラスに環境を提供する「アクティブ」オブジェクト

アクティブ エレベータ オブジェクトの中でパッシブ オブジェクトに適した候補は、エレベータが上に移動するときに停止する階のリストと、下に移動するときに停止する階のリストです。エレベータは、次の停止階をこのリストから取得し、新しい停止階をこのリストに追加し、既に停止した階を削除する必要があります。

ほとんどの複雑なシステムは、リーフレベルのコンポーネントに到達するまでの複数レベルのサブシステムで作成されるので、アクティブ オブジェクトがほかのアクティブ オブジェクトを包含できるようにすることはアクティブ オブジェクトの自然な拡張です。

単独スレッドのアクティブ オブジェクトは真のオブジェクト内並行性をサポートしませんが、包含されているアクティブ オブジェクトへの作業の委譲は、多数のアプリケーションの妥当な代用です。オブジェクトごとの状態、振る舞い、コントロール スレッドの完全なカプセル化という重要な利点を維持しているので、並行性コントロールの問題が単純化されます。

図 7: ネストされたアクティブ オブジェクトを示すエレベータ システム

たとえば、この図に示したエレベータ システムの一部で考えてみます。各エレベータには、扉、巻き上げ機、操作盤があります。これらの各コンポーネントは並行アクティブ オブジェクトによって明確にモデリングされます。扉オブジェクトはエレベータの扉の開閉を制御し、巻き上げ機オブジェクトは巻き上げ機によってエレベータの位置を制御し、操作盤オブジェクトは停止階の選択ボタンと扉の開閉ボタンを監視します。並行するコントロール スレッドをアクティブ オブジェクトとしてカプセル化すると、このすべての振る舞いを 1 つのコントロール スレッドで管理する場合にくらべてはるかに単純なソフトウェアになります。

オブジェクト内の「一貫状態」の問題 ページの先頭へ

競合状態の説明で言及したように、システムが正確で予測可能な振る舞いをするためには、特定の状態依存の操作が最小でなければなりません。

オブジェクトが正しい振る舞いをするためには、メッセージの処理の前後でオブジェクトの状態が内部で一貫していることが絶対条件です。操作が部分的にしか完了していないために、メッセージの処理中に、オブジェクトの状態が一時的であったり、不確定の場合があります。

オブジェクトが常に 1 つのメッセージの応答を完了してから次のメッセージに応答する場合は、状態が一時的でも問題はありません。1 つのオブジェクトに割り込んで別のオブジェクトを実行する場合も、各オブジェクトの状態が厳重にカプセル化されているので、問題ありません (厳密に言えば、後に示すように、これは完全には正しくありません)。

オブジェクトがメッセージの処理に割り込んで別のメッセージを処理する場合は、競合状態が発生する可能性があるので、並行性コントロールを使用する必要があります。並行性コントロールを使用すると、今度はデッドロックが生じる可能性があります。

したがって、オブジェクトが各メッセージの処理を完了してから別のメッセージを受け入れる場合は、並行設計のほうが通常は単純になります。この振る舞いは、前に示した特定の形式のアクティブ オブジェクト モデルでは暗黙です。

一貫状態の問題は、並行システムでは 2 種類の形式で現れます。これらの形式はオブジェクト指向並行システムの観点で見ると理解しやすいと思います。第 1 の形式については既に説明しています。1 つのオブジェクト (パッシブまたはアクティブ) の状態を複数のコントロール スレッドが使用可能な場合は、基本の CPU 操作の自然な最小単位によって、または並行性コントロール メカニズムによって、最小の操作を保護しなければなりません。

第 2 の形式の一貫状態の問題は、より微妙な問題です。複数のオブジェクト (アクティブまたはパッシブ) に同じ状態情報が含まれる場合、これらのオブジェクトは、最低でも短い間隔は、状態について一致しないことが避けられません。設計があまり良くない場合は、一致しない間隔が長くなり、永遠に続く場合さえあります。この一貫性がとれない状態の現れは、もう一方の形式の数学的な「双数」と見なすことができます。

たとえば、エレベータの動作制御システム (巻き上げ機) は、扉が閉じていて開かないようになっていることを確認してから、エレベータを動かすことができます。適切な安全装置がない設計では、エレベータが動き始めたときに開扉ボタンを押すと、応答して扉が開くおそれがあります。

状態情報が 1 つのオブジェクト内のみにとどまるようにすれば、この問題が簡単に解決するように思えるかもしれません。この方法は役立つかもしれませんが、性能に悪影響が及ぶおそれもあり、特に分散システムでその傾向が顕著になります。さらに、これは絶対確実な解決法ではありません。1 つのオブジェクトのみに特定の状態情報が含まれる場合でも、ある特定時点でその状態に基づいてほかの並行オブジェクトが決定を下すかぎり、状態の変化がほかのオブジェクトの決定を無効にする可能性があります。

一貫状態の問題には魔法のような解決法は存在しません。すべての実際的な解決法では、最小の操作を識別し、許容できる程度の短時間だけ並行アクセスを阻止するなんらかの同期メカニズムによってこの最小操作を保護する必要があります。「許容できる程度の短時間」は、状況に応じて大きく異なります。CPU がすべてのバイトを浮動小数点数で格納するために必要な時間であったり、エレベータが次の停止階まで移動する時間であったりします。



Rational Unified Process   2003.06.15