この章では、スレッドを使ったプログラミングのための指針を示します。ほとんどの内容は Solaris スレッドと POSIX スレッドの両方に当てはまりますが、両者で機能的な違いがある点については、その旨を明記します。この章では、シングルスレッドとマルチスレッドの考え方の違いを中心に説明します。
現状では大半のコード、特に C プログラムから呼び出されるライブラリルーチンは、シングルスレッドアプリケーション向けに設計されています。シングルスレッド用のコードでは、次のように仮定していました。
同期をとるべきものがないので、同期は必要ない。
次に、上記の仮定が原因で生じるマルチスレッドプログラム上の問題とその対処方法を示します。
従来のシングルスレッドの C と UNIX では、システムコールで検出されたエラーの扱いに関して一定の決まりがあります。システムコールは、関数値として任意の値を戻すことができます (たとえば、write() は転送したバイト数を戻します)。ただし、値 -1 は、エラーが生じたことを示すために予約されています。つまり、システムコールから -1 が戻された場合は、システムコールが失敗したことを意味します。
extern int errno; ... if (write(file_desc, buffer, size) == -1) { /* システムコールが失敗 */ fprintf(stderr, “something went wrong, “ “error code = %d\n”, errno); exit(1); } ... |
戻り値と混同されがちですが、実際のエラーコードは広域変数 errno に格納されます。システムコールが失敗した場合は、errno を調べればエラーの内容を知ることができます。
ここで、マルチスレッド環境において 2 つのスレッドが同時に失敗し、異なるエラーが発生したと仮定します。このとき、両方のスレッドがエラーコードは errno に入っていると期待しても、1つの errno に両方の値を保持することは不可能です。このように、マルチスレッドプログラムでは、広域変数による方法は使用できません。
スレッドでは、この問題を解決するために、スレッド固有データという新しい記憶クラスを導入しています。このスレッド固有データは、スレッド内の任意の手続きからアクセスできるという点で広域変数と似ています。ただし、これはそのスレッドに専用の領域です。つまり、2 つのスレッドが同じ名前のスレッド固有データをアクセスしても、それぞれ異なる変数をアクセスしていることになります。
したがって、スレッドを使用しているときは、スレッドごとに errno の専用のコピーが与えられるので、errno の参照がスレッドに固有なものとなります。この実装においては、errno をマクロにして関数呼び出しを行うことでこれを可能にしています。
例 9–2 は、前述の errno と同様の問題を示すものです。ただし、ここでは広域的な記憶領域ではなく静的な記憶領域が問題となります。関数 gethostbyname(3NSL) は、コンピュータ名を引数として与えられて呼び出されます。その戻り値はある構造体のポインタで、その構造体には指定したコンピュータと、ネットワークを通して通信するために必要な情報が入っています。
struct hostent *gethostbyname(char *name) { static struct hostent result; /* ホストデータベースから名前を検索 */ /* result に答えを入れる */ return(&result); } |
一般に、局所変数へのポインタを返すというのはよい方法ではありません。上記の例では、変数が静的なために正常に動作します。しかし、2 つのスレッドが異なるコンピュータ名で同時に関数を呼び出すと、静的記憶領域の衝突が生じます。
静的記憶領域の代わりに前述の errno のように、スレッド固有データを使用するという解決方法も考えられますが、動的記憶割り当てのため処理が重くなります。
このような問題を解決する方法は、gethostbyname() の呼び出し側が結果を戻すための記憶領域を呼び出し時に指定してしまうことです。具体的には、このルーチンに出力引数を 1 つ追加して、呼び出し側から与えます。そのためには、gethostbyname() に新しいインタフェースが必要です。
Solaris スレッドでは、この種の問題の多くを解決するために、上記のテクニックが使われています。通常、新しいインタフェース名は、末尾に「_r」を付けたものです。たとえば、gethostbyname(3NSL) は、gethostbyname_r(3NSL) となります。
アプリケーション内のスレッドは、データやプロセスリソースを共有するときに相互に同期をとりながら連携して動作しなければなりません。
問題となるのは、ある特定のオブジェクトの操作を複数のスレッドが呼び出すときです。シングルスレッド環境では、そのようなオブジェクトに対するアクセスの同期上の問題は生じませんが、例 9–3 に示すように、マルチスレッドでは注意する必要があります。(Solaris の printf(3S) は「MT-安全」です。この例では、printf() がマルチスレッドに対応していないと仮定したときに生じる問題を示しています。)
/* スレッド 1: */ printf("go to statement reached"); /* スレッド 2: */ printf("hello world"); printed on display: go to hello |
同期上の問題の解決策として、アプリケーション全域で 1 つの相互排他ロック (mutex ロック) を使用するという方法が考えられます。そのアプリケーション内で実行するスレッドは、実行時に必ず mutex をロックし、ブロックされた時に mutex を解除するようにします。このようにすれば、同時に複数のスレッドが共有データをアクセスすることはなくなるので、各スレッドから見たメモリーは整合性を保ちます。
しかし、これは事実上のシングルスレッドプログラムであり、この方法にはほとんど利点がありません。
よりよい方法として、モジュール性とデータのカプセル化の性質の利用があります。複数のスレッドから同時に呼び出されても正しく動作する関数を「リエントラント (再入可能)」関数と呼びます。再入可能な関数を作成するには、その関数にとって何が正しい動作なのかを把握することが必要です。
複数のスレッドから呼び出される可能性のある関数は、再入可能にしなければなりません。そのためには、関数のインタフェースまたは実装方法を変更する必要があります。
リエントラントの問題は、メモリーやファイルなどの広域的な状態におかれているものをアクセスする関数で生じます。それらの関数では、広域的なものをアクセスする場合、スレッドの適当な同期機構で保護する必要があります。
モジュール内の関数をリエントラントにする基本的な方法は、コードをロックする方法とデータをロックする方法の 2 通りがあります。
コードロックは関数の呼び出しのレベルで行うロックで、その関数の全体がロックの保護下で実行されることを保証するものです。コードロックが成立するためには、すべてのデータアクセスが関数を通して行われることが前提となります。また、データを共有する関数が複数あるとき、それらを同じロックの保護下で実行することも必要です。
一部の並列プログラミング言語では、モニターという構造が用意されています。モニターは、その対象範囲内に定義されている関数に対して、暗黙の内にコードロックを行います。相互排他ロック (mutex ロック) によって、モニターを実装することも可能です。
同じ相互排他ロックの保護下にある関数または同じモニターの対象範囲内にある関数は、互いに不可分操作的に実行されることが保証されます。
データロックは、データ集合へのアクセスが一貫性をもって行われることを保証します。データロックも、基本的な概念はコードロックと同じです。しかし、コードロックは共有される (広域的な) データのみへの参照を囲むようにかけます。相互排他ロックでは、各データ集合に対応する危険領域を同時に実行できるスレッドはせいぜい 1 つです。
一方、複数読み取り単一書き込みロックでは、それぞれのデータ集合に対して複数スレッドが同時に読み取り操作を行うことができ、1 つのスレッドが書き込み操作を行うことができます。複数読み取り単一書き込みロックのように、それぞれ異なるデータ集合を操作するか、同じデータ集合で衝突を起こさないようにすれば、同一モジュール内で複数のスレッドを実行できます。つまり、通常はコードロックよりもデータロックの方が、多重度を高くすることができます。
プログラムで、(相互排他ロック、条件変数、セマフォなどの) さまざまなロックを使用するときの方針を説明します。できる限り並列性を高めるためにきめ細かくロックする、つまり必要なときだけロックして不要になったらすぐ解除するという方法と、ロックと解除に伴うオーバヘッドをできる限り小さくするため長期間ロックを保持する、つまりきめの粗いロックを行うという方法が考えられます。
ロックをどの程度きめ細かくかけるべきかは、保護の対象となるデータの量によって異なります。最もきめの粗いロックは、全データを 1 つのロックで保護します。保護対象のデータをいくつに分割してロックするかは、非常に重要な問題です。ロックのきめが細かすぎても、性能に悪影響を及ぼします。それぞれのロックと解除に伴うオーバーヘッドは、ロックの数が多いと無視できなくなるからです。
通常、ロックを使用する方針は次のとおりです。最初は、きめを粗くロックします。これは妥当な解決策ですが、並列性を最大にすることとロックに伴うオーバーヘッドを最小にすることのどちらをどの程度優先させるかは、ユーザが判断してください。
コードロックとデータロックについて、複雑なロックを制御するためには「不変式」が重要な意味をもちます。不変式とは、常に真である条件または関係のことです。
不変式は、並行実行環境に対して次のように定義されます。すなわち不変式とは、関連するロックが行われるときに条件や関係が真になっていることです。ロックが行われた後は偽になってもかまいません。ただし、ロックを解除する前に真に戻す必要があります。
あるロックが行われるときに真となるような条件または関係も不変式です。条件変数では、条件という不変式を持っていると考えることができます。
mutex_lock(&lock); while((condition)==FALSE) cond_wait(&cv,&lock); assert((condition)==TRUE); . . . mutex_unlock(&lock); |
上記の assert() 文は、不変式を評価しています。cond_wait() 関数は、不変式を保存しません。このため、スレッドが戻ったときに不変式をもう一度評価しなければなりません。
他の例は、双方向リンクリストを管理するモジュールです。双方向リンクリストでは、直前の項目の前向きポインタと直後の項目の後ろ向きポインタが同じものを指すという条件が成立します。これは不変式のよい例です。
このモジュールでコードロックを使用するものと仮定し、1 つの広域的な相互排他ロック (mutex ロック) でモジュールを保護することにします。項目を削除したり追加したりするときは相互排他ロックを獲得し、ポインタの変更後に相互排他ロックを解除します。明らかに、この不変式はポインタの変更中のある時点で偽になります。しかし、相互排他ロックを解除する前に真に戻されています。
ある一組のスレッドが一連のリソースの獲得で競合したまま、永久にブロックされた状態に陥っているとき、その状態をデッドロックと呼びます。実行可能なスレッドがあるからといって、デッドロックが発生していないという証拠にはなりません。
代表的なデッドロックは、「自己デッドロック」です (「再帰的なデッドロック」とも言います)。自己デッドロックは、すでに保持しているロックをスレッドがもう一度獲得しようとしたとき発生します。これは、ちょっとしたミスで簡単に発生してしまいます。
たとえば、一連のモジュール関数で構成されるコードモニターを考えます。各モジュール関数が実行中に保持する相互排他ロックがどれも同じであると、このモジュール内の相互排他ロックの保護下にある関数間で呼び出しが行われた場合に、たちまちデッドロックが発生します。また、ある関数がこのモジュールの外部のコードを呼び出し、そこから再び同じ相互排他ロックで保護されているモジュールを呼び出した場合にもデッドロックが発生します。
この種のデッドロックを回避するには、モジュールの外部の関数を呼び出す場合、その関数が再び元のモジュールを呼び出さないことを確認できないときは各不変式を再び真にして、すべてのモジュール内のロックを解除してから呼び出すようにします。次に、その呼び出しを終了してもう一度ロックを獲得した後、所定の状態を評価して、意図している操作がまだ有効であるか確認します。
もう 1 つ別の種類のデッドロックがあります。スレッド 1、2 がそれぞれ mutex A、B のロックを獲得しているものと仮定します。次に、スレッド 1 が mutex B を、スレッド 2 が mutex A をロックしようとすると、スレッド 1 は mutex B を待ったままブロックされ、スレッド 2 は mutex A を待ったままブロックされます。結局、両方のスレッドは身動きがとれなくなって永久にブロックされ、デッドロック状態となります。
この種のデッドロックを回避するには、ロックを行う順序を一定に保ちます。この方法を「ロック階層」と呼びます。すべてのスレッドが常に一定の順序でロックを行う限り、この種のデッドロックは生じません。
しかし、ロックを行う順序を一定に保つという規則を守っていればよいとは必ずしも言えません。たとえば、スレッド 2 が mutex B を保持している間に、モジュールの状態に関して数多くの仮定条件を立てた場合、次に mutex A のロックを獲得するために mutex B のロックを解除し、規則通り mutex A のロックを獲得した後にもう一度 mutex B のロックを獲得しても先の仮定は無駄になり、モジュールの状態をもう一度評価しなければならなくなります。
通常、ブロックを行う同期プリミティブには、ロックを獲得しようとしてできなかった場合にエラーとなる類似のプリミティブ (たとえば、mutex_trylock()) が用意されています。これを使うと、競合がなければロック階層を守らないという方法でロックを実行できます。競合があるときは、通常は保持しているロックをいったん解除してから、順番にロックを実行しなければなりません。
マルチスレッドプログラムでは、ロックが獲得される順序がシステム的に不定であることが原因で、特定のスレッドがロック (通常は条件変数) を獲得できるように見えても、実際にはロックを獲得できないという問題があります。
通常、この問題は次のような状況で起こります。スレッドが、保持していたロックを解除し、少し時間をおいてからもう一度ロックを獲得するものとします。このとき、ロックはいったん解除されたので、他のスレッドがロックを獲得したと考えがちです。しかし、ロックを保持していたスレッドは、ブロックされなければロック解除後も引き続き実行され、もう一度ロックを獲得するので、結局その間に他のスレッドは実行されません。
通常、この種の問題を解決するには、もう一度ロックを獲得する前に thr_yield(3THR) を呼び出します。これで他のスレッドが実行され、そのスレッドはロックを獲得できるようになります。
必要なタイムスライスの大きさはアプリケーションに依存するため、スレッドライブラリでは特に制限していません。thr_yield() を呼び出して、スレッドが共有する時間を設定してください。
ロックを長期間保持しないでください。たとえば、入出力時にロックを保持したままにすると性能が低下することがあります。
モジュールから外部の関数を呼び出す場合、その関数が元のモジュールを呼び出す可能性があるときはロックを解除してください。
一般に、初めは大まかに調べるというやり方で臨み、ボトルネックを見つけます。そして、ボトルネックを軽減するのに必要なら、きめ細かなロックを追加していきます。ロックが保持される時間は通常はそれほど長くなく、競合もめったに起こりません。実際に競合のあったロックだけを調整してください。
複数のロックを使用する場合は、デッドロックを回避するために、すべてのスレッドで同じ順序でロックを獲得するようにしてください。
外部から手続きなどを流用する場合、その安全性を確認してください。
マルチスレッドプログラムから、マルチスレッド化されていないコードをそのまま呼び出すことはできません。
マルチスレッドプログラムでは、初期スレッドからのみ「MT-安全ではない」コードに安全にアクセスできます。
これは初期スレッドに対応する静的記憶領域が、初期スレッドによってだけ使用されることを保証します。
Sun から提供されるライブラリは、「安全」であると明記されていなければ、「安全ではない」とみなされます。
リファレンスマニュアルのエントリにインタフェースが「MT-安全」であると明示的に記載されていない場合は、そのインタフェースは「安全ではない」と考えるべきです。
コンパイルフラグでソースのバイナリレベルでの非互換性を解消してください (詳細は、第 7 章「コンパイルとデバッグ」「コンパイルとデバック」を参照してください。)
-D_REENTRANT を使用すると-lthread ライブラリによるマルチスレッドが有効になります。
-D_POSIX_C_SOURCE と -lpthread を使用すると、POSIX スレッドの動作になります。
-D_POSIX_PTHREADS_SEMANTICS と -lthread を使用すると、Solaris スレッドと pthread の両方のインタフェースが有効になりますが、2 つのインタフェースが衝突したときは POSIX インタフェースが優先されます。
ライブラリを「MT-安全」にする場合、プロセスの広域的な操作はスレッド化しないでください。
広域的な操作 (または広域的な副作用のある処理) をスレッド化しないでください。たとえば、ファイル入出力をスレッド単位の操作に変更しても、複数のスレッドがファイルに同時にアクセスできません。
スレッド特有の動きやスレッドとして認識される動きは、スレッド機能を使って実現してください。たとえば、main() の終了時に main() のスレッドだけを終了したい場合は、main() の最後を次のようにします。
thr_exit(); /*NOTREACHED*/ |
スレッドパッケージは、スレッドのデータ構造およびスタックをキャッシュするので、スレッドを繰り返し生成してもシステムに対する負荷は大きくなりません。
ただし、必要に応じてスレッドを生成したり削除したりする方が、専用の処理要求を待つスレッドを維持管理するより付加が大きくなります。
たとえば、RPC サーバがよい例です。RPC サーバは要求が送られてきたらスレッドを生成し、応答を返したらスレッドを削除します。
スレッドの生成のオーバーヘッドがプロセス生成のオーバーヘッドと比べて小さいといっても、数個の命令を実行するのにかかる負荷に比べると効率的ではありません。少なくとも数千の機械語命令が続くような処理を対象にして、スレッドを生成してください。
図 9–1 に LWP、ユーザーレベル、およびカーネルレベルの関係を示します。
ユーザーレベルのスレッドライブラリで利用できる LWP の数は、現在アクティブなユーザーレベルのスレッドに応じて決定されます。オペレーティング環境は、どの LWP をどのプロセッサでいつ実行させるかを決定します。このとき、ユーザースレッドは考慮されません。カーネルは、LWP のスケジューリングクラスと優先順位に従って、LWP を CPU リソースに割り当てます。
各 LWP はカーネルによって独立に振り分けられ、独立したシステムコールを実行し、独立したページフォルトを引き起こし、マルチプロセッサのシステム上では並列に動作します。
LWP の機能の中には、特別なスケジューリングクラスなどのように、スレッドからは直接には参照できないものがあります。
Solaris 9 で導入された新しいスレッドライブラリでは、スレッドごとに 1 つの LWP が割り当てられます。このスレッドライブラリは、Solaris 8 の代替 libthread と同じ機能を持ちます。
この新しい実装によって、従来のスレッドライブラリ設計で発生していた問題 (主に、シグナル処理と多重度) の多くが解決されます。新しいスレッドライブラリには、 thr_setconcurrency(3THR) を使用して目標多重度を設定する必要はありません。すべてのスレッドが LWP 上で実行されるためです。
今後の Solaris リリースのスレッドライブラリでは、複数の LWP 上で非結合スレッドが多重化されるようになる可能性があります。ただし、次にあげる、Solaris 9 で現在有効な制約は保持されます。
すべての実行可能スレッドは LWP に接続される。
ライブラリ自体は隠しスレッドを生成しない。
1 つのスレッドだけで動作するマルチスレッドプロセスと従来のシングルスレッドプロセスは、同じセマンティクスを持つ。
スレッドライブラリは、必要に応じて LWP を生成し、実行可能なスレッドを LWP に割り当てます。スレッドが割り当てられた LWP はスレッドの状態を引き継ぎ、スレッドの一連の命令を実行します。非結合スレッドが同期機構に基づいてブロックされると、スレッドライブラリはそのスレッドの状態をプロセスメモリに保存し、ほかのスレッドを LWP に割り当てて実行します。
結合スレッドは、スレッドの生成から終了まで、同一 LWP 上で実行されます。
次に、スレッドを使用するときの簡単な指針を示します。
十分な仕事量をもつ独立した活動にスレッドを使用してください。
結合スレッドは、スレッドが結合する LWP のリソースを利用しなければならないときにだけ使用してください。たとえば、リアルタイムスケジューリングなど、スレッドをカーネルから参照可能にしなければならないときなどに使用します。
マルチスレッドでは、主に並列性とスケーラビリティという点でマルチプロセッサを活用できます。プログラマは、マルチプロセッサと単一プロセッサのメモリーモデルの違いを考慮に入れておかなければなりません。
メモリーの一貫性は、メモリーを問い合わせるプロセッサと直接的な相関関係にあります。単一プロセッサの場合、メモリーを参照するプロセッサは 1 つしかないのでメモリーは一貫しています。
マルチプロセッサの性能を高めようとすると、メモリーの一貫性が緩められることになります。あるプロセッサによるメモリーへの変更が、他のプロセッサから見たメモリーイメージにただちに反映されるとは限りません。
共有される広域変数を使用するときに同期変数を使用すれば、この複雑さを回避できます。
バリア同期を使用すると、マルチプロセッサ上での並列性をうまく制御できる場合があります。「Solaris スレッドの例 — barrier.c」にバリアの一例を示しています。
マルチプロセッサに関して、もう 1 つの問題があります。共通の実行ポイントに到達するまで全スレッドが待たなければならないようなケースでは、同期の効率が問題となります。
共有メモリーにアクセスするためにスレッドの同期プリミティブを必ず使用する場合は、上記の項目は重要ではありません。
スレッドが、Solaris のスレッド同期ルーチンを使用して共有記憶領域へのアクセスの同期をとるときは、共有メモリー型のマルチプロセッサ上でプログラムを実行することと、単一プロセッサ上でプログラムを実行することは同じことになります。
しかし、プログラマはあえてマルチプロセッサ特有の機能を活用したり、同期ルーチンを迂回する「トリック」を使用したりすることがあります。例 9–5 と 例 9–6では、そうしたトリックの危険性を示しています。
通常のマルチプロセッサアーキテクチャがサポートしているメモリーモデルを理解することは、この危険性を理解する助けとなります。
マルチプロセッサの主な構成要素は、次のとおりです。
プロセッサ
ストアバッファ (プロセッサとキャッシュを接続する)
メモリー (全プロセッサによって共有される主記憶領域)
従来の単純なモデルでは、各プロセッサがメモリーに直接接続されているかのように動作します。つまり、あるプロセッサが特定の位置にデータを格納すると同時に別のプロセッサが同じ位置からデータをロードした場合、2 番目のプロセッサは最初のプロセッサが格納したデータをロードします。
キャッシュは、メモリーアクセスの高速化のために使われ、キャッシュ間の整合性が維持されているときは、データの整合性も保たれます。
この単純なモデルの問題点は、データの整合性を保つためプロセッサをしばしば遅延させなければならないことです。最新のマルチプロセッサでは、各種の手法でそうした遅延を回避していますが、メモリーデータの整合性を失わせています。
次の 2 つの例で、それらの手法と効果を説明します。
例 9–5 は、「生産者 / 消費者」問題の代表的な解決方法です。
このプログラムは、現在の SPARC ベースのマルチプロセッサでは正しく動作しますが、すべてのマルチプロセッサが強く順序付けられたメモリーをもつことを想定しています。したがって、このプログラムには移植性がありません。
char buffer[BSIZE]; unsigned int in = 0; unsigned int out = 0; void char producer(char item) { consumer(void) { char item; do ;/* 処理なし */ do while ;/* 処理なし */ (in - out == BSIZE); while (in - out == 0); buffer[in%BSIZE] = item; item = buffer[out%BSIZE]; in++; out++; } } |
このプログラムは、生産者と消費者がそれぞれ 1 つしか存在せず、かつ共有メモリー型のマルチプロセッサ上で動作するときは正しく動作します。in と out の差が、バッファ内のデータ数となります。
生産者はバッファに空きができるまで、この差を繰り返し計算しながら待ちます。消費者は、バッファにデータが入れられるのを待ちます。
強く順序付けられたメモリー (たとえば、あるプロセッサのメモリーへの変更が他のプロセッサにただちに伝わるようなメモリー) では、この方法は成立します (BSIZEが 1 ワードで表現できる最大整数より小さい限り、in と out が最終的にオーバーフローしても成立します) 。
共有メモリー型のプロセッサは、必ずしも強く順序付けられたメモリーをもつ必要はありません。つまり、あるプロセッサによるメモリーへの変更が、他のプロセッサにただちに伝わるとは限りません。あるプロセッサによって、メモリーに 2 つの変更が加えられた場合、メモリーの変更がただちに伝わらないので、他のプロセッサから検出できる変更の順序は最初の順序と同じであるとは限りません。
変更内容は、まず「ストアバッファ」に入れられます。このストアバッファは、キャッシュからは参照できません。
プロセッサは、データの整合性を保証するためにストアバッファをチェックします。しかし他のプロセッサから、このストアバッファは参照できません。つまり、あるプロセッサが書き込んだ内容は、キャッシュに書き込まれるまで他のプロセッサから参照できません。
同期プリミティブ (第 4 章「同期オブジェクトを使ったプログラミング」「同期オブジェクトを使ったプログラミング」を参照) は、特別な命令でストアバッファの内容をキャッシュにフラッシュしています。したがって、共有データをロックで保護すればメモリーの整合性が保証されます。
メモリーの順序付けが非常に弱い場合は、例 9–5で問題が生じます。消費者は、生産者によって in が 1 つ増やされたことを、対応するバッファスロットへの変更を知る前に知る場合があるからです。
あるプロセッサのストア順序が、別のプロセッサからは違った順序で見えることがあるため、これを「弱い順序付け」と呼びます (ただし、同じプロセッサから見たメモリーは常に整合性を保っています)。この問題を解決するには、相互排他ロックを使用して、ストアバッファの内容をキャッシュにフラッシュしなければなりません。
最近は、メモリーの順序付けが弱くされる傾向にあります。このため、プログラマは広域データや共有データをロックで保護することに一層注意してください。
例 9–6 は、Peterson のアルゴリズムの実装例です。これは 2 つのスレッド間での相互排他を扱うアルゴリズムです。このコードでは、危険領域に同時に複数のスレッドが存在しないことを保証しようとしています。さらに、スレッドが mut_excl() を呼び出すと、危険領域に「素早く」入ることを保証しています。
ここで、スレッドは危険領域に入ると素早く抜け出るものとします。
void mut_excl(int me /* 0 または 1 */) { static int loser; static int interested[2] = {0, 0}; int other; /* 局所変数 */ other = 1 - me; interested[me] = 1; loser = me; while (loser == me && interested[other]) ; /* 危険領域 */ interested[me] = 0; } |
このアルゴリズムは、マルチプロセッサのメモリーが強く順序付けられているときは成立します。
ストアバッファを装備したマルチプロセッサでは、(一部の SPARC ベースのマルチプロセッサも装備しています)、スレッドがストア命令を実行すると、データがストアバッファに入れられます。このバッファの内容は最終的にキャッシュに送られますが、すぐに送られるとは限りません。各プロセッサのキャッシュはデータの整合性を維持していますが、変更されたデータはキャッシュにすぐには送られません。
複数のデータが格納されたとき、その変更はキャッシュ (およびメモリー) に正しい順序で伝わりますが、通常は遅延を伴います。SPARC ベースのマルチプロセッサでは、この性質のことを「トータルストア順序 (TSO) をもつ」と言います。
あるプロセッサが A 番地にデータを格納して次に B 番地からデータをロードして、別のプロセッサが B 番地にデータを格納して次に A 番地からデータをロードした場合、「最初のプロセッサが B 番地の新しい値を得る」と「2 番目のプロセッサが A 番地の新しい値を得る」の一方または両方が成立し、かつ「両方のプロセッサが以前の値を得る」というケースは起こりえないはずです。
さらに、ロードバッファとストアバッファの遅延が原因で、上記の起こりえないケースが起こることがあります。
このとき Peterson のアルゴリズムでは、それぞれ別のプロセッサで実行されている 2 つのスレッドが特定の配列の自分のスロットにデータを格納し、別のスロットからデータをロードしています。両方のスレッドは以前の値 (0) を読み取り、相手がいないものと判定し、両方が危険領域に入ってしまいます。(この種の問題は、プログラムのテスト段階では発生せず、後になって発生することがあるので注意してください。)
この問題は、スレッドの同期プリミティブを使用すると回避できます。それらのプリミティブには、ストアバッファをキャッシュに強制的にフラッシュする特別な命令が含まれているからです。
多くのアプリケーション、特に数値計算関係のアプリケーションでは、他の部分が本質的に逐次的であっても、while 部分のアルゴリズムを並列化できます (詳細は、次の例を参照してください)。
|
|
||
|
|
たとえば、完全な線型計算で一組の行列を作成し、それらの行列に対する操作を並列アルゴリズムで実行し、操作結果からもう一組の行列を作成し、それらの行列を並列的に操作するといった処理が考えられます。
こうした計算の並列アルゴリズムの特徴は、計算中はほとんど同期をとる必要はありませんが、並列計算を始める前に逐次計算が終了していることを確認するために、関連するすべてのスレッドの同期をとる必要があることです。
バリアには、並列計算を行なっているすべてのスレッドを、関係しているすべてのスレッドがバリアに達するまで待たせるという働きがあります。スレッドは全部がバリアに達したところで解放され、一斉に計算を開始します。
このマニュアルでは、スレッドのプログラミングに関する重要な問題を幅広く取り上げて説明しました。「アプリケーションの例 — マルチスレッド化された grep」には、pthread プログラムの例が記載されています。この例の中で、今までに説明した多くの機能やスタイルが使用されています。また、付録 B 「Solaris スレッドの例 — barrier.c」「Solaris スレッドの例」には、Solaris スレッドを使用したプログラムの例が記載されています。
マルチスレッドについてさらに詳しく知りたい方は、次の書籍をお読みください。
『Programming with Threads』(Steve Kleiman、Devang Shah、Bart Smaalders 共著、Prentice-Hall 発行、1995年)