test

マルチスレッドのプログラミング

第 9 章 プログラミング上の指針

この章では、スレッドを使ったプログラミングのための指針を示します。ほとんどの内容は Solaris スレッドと POSIX スレッドの両方に当てはまりますが、両者で機能的な違いがある点については、その旨を明記します。この章では、シングルスレッドとマルチスレッドの考え方の違いを中心に説明します。

広域変数の考慮

現状では大半のコード、特に C プログラムから呼び出されるライブラリルーチンは、シングルスレッドアプリケーション向けに設計されています。シングルスレッド用のコードでは、次のように仮定していました。

次に、上記の仮定が原因で生じるマルチスレッドプログラム上の問題とその対処方法を示します。

従来のシングルスレッドの C と UNIX では、システムコールで検出されたエラーの扱いに関して一定の決まりがあります。システムコールは、関数値として任意の値を戻すことができます (たとえば、write() は転送したバイト数を戻します)。ただし、値 -1 は、エラーが生じたことを示すために予約されています。つまり、システムコールから -1 が戻された場合は、システムコールが失敗したことを意味します。

例 9-1 広域変数と errno 


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 に入っていると期待しても、１つの errno に両方の値を保持することは不可能です。このように、マルチスレッドプログラムでは、広域変数による方法は使用できません。

スレッドでは、この問題を解決するために、スレッド固有データという新しい記憶クラスを導入しています。このスレッド固有データは、スレッド内の任意の手続きからアクセスできるという点で広域変数と似ています。ただし、これはそのスレッドに専用の領域です。つまり、2 つのスレッドが同じ名前のスレッド固有データをアクセスしても、それぞれ異なる変数をアクセスしていることになります。

したがって、スレッドを使用しているときは、スレッドごとに errno の専用のコピーが与えられるので、errno の参照がスレッドに固有なものとなります。この実装においては、errno をマクロにして関数呼び出しを行うことでこれを可能にしています。

静的局所変数の利用

例 9-2 は、前述の errno と同様の問題を示すものです。ただし、ここでは広域的な記憶領域ではなく静的な記憶領域が問題となります。関数 gethostbyname(3N) は、コンピュータ名を引数として与えられて呼び出されます。その戻り値はある構造体のポインタで、その構造体には指定したコンピュータと、ネットワークを通して通信するために必要な情報が入っています。

例 9-2 gethostbyname() の問題


struct hostent *gethostbyname(char *name) {
    static struct hostent result;
        /* ホストデータベースから名前を検索 */
        /* result に答えを入れる */
    return(&result);
}

一般に、局所変数へのポインタを返すというのはよい方法ではありません。上記の例では、変数が静的なために正常に動作します。しかし、2 つのスレッドが異なるコンピュータ名で同時に関数を呼び出すと、静的記憶領域の衝突が生じます。

静的記憶領域の代わりに前述の errno のように、スレッド固有データを使用するという解決方法も考えられますが、動的記憶割り当てのため処理が重くなります。

このような問題を解決する方法は、gethostbyname() の呼び出し側が結果を戻すための記憶領域を呼び出し時に指定してしまうことです。具体的には、このルーチンに出力引数を 1 つ追加して、呼び出し側から与えます。そのためには、gethostbyname() に新しいインタフェースが必要です。

Solaris スレッドでは、この種の問題の多くを解決するために、上記のテクニックが使われています。通常、新しいインタフェース名は、末尾に「_r」を付けたものです。たとえば、gethostbyname(3N) は、gethostbyname_r(3N) となります。

スレッドの同期

アプリケーション内のスレッドは、データやプロセスリソースを共有するときに相互に同期をとりながら連携して動作しなければなりません。

問題となるのは、ある特定のオブジェクトの操作を複数のスレッドが呼び出すときです。シングルスレッド環境では、そのようなオブジェクトに対するアクセスの同期上の問題は生じませんが、例 9-3 に示すように、マルチスレッドでは注意する必要があります。(Solaris の printf(3S) は「MT-安全」です。この例では、printf() がマルチスレッドに対応していないと仮定したときに生じる問題を示しています。)

例 9-3 printf() の問題


/* スレッド 1: */
    printf("go to statement reached");

/* スレッド 2: */
    printf("hello world");


ディスプレイ上の表示:
    go to hello

シングルスレッド化

同期上の問題の解決策として、アプリケーション全域で 1 つの相互排他ロック (mutex ロック) を使用するという方法が考えられます。そのアプリケーション内で実行するスレッドは、実行時に必ず mutex をロックし、ブロックされた時に mutex を解除するようにします。このようにすれば、同時に複数のスレッドが共有データをアクセスすることはなくなるので、各スレッドから見たメモリーは整合性を保ちます。

しかし、これは事実上のシングルスレッドプログラムであり、この方法にはほとんど利点がありません。

リエントラント (再入可能)

よりよい方法として、モジュール性とデータのカプセル化の性質の利用があります。複数のスレッドから同時に呼び出されても正しく動作する関数を「リエントラント (再入可能)」関数と呼びます。再入可能な関数を作成するには、その関数にとって何が正しい動作なのかを把握することが必要です。

複数のスレッドから呼び出される可能性のある関数は、再入可能にしなければなりません。そのためには、関数のインタフェースまたは実装方法を変更する必要があります。

リエントラントの問題は、メモリーやファイルなどの広域的な状態におかれているものをアクセスする関数で生じます。それらの関数では、広域的なものをアクセスする場合、スレッドの適当な同期機構で保護する必要があります。

モジュール内の関数をリエントラントにする基本的な方法は、コードをロックする方法とデータをロックする方法の 2 通りがあります。

コードロック

コードロックは関数の呼び出しのレベルで行うロックで、その関数の全体がロックの保護下で実行されることを保証するものです。コードロックが成立するためには、すべてのデータアクセスが関数を通して行われることが前提となります。また、データを共有する関数が複数あるとき、それらを同じロックの保護下で実行することも必要です。

一部の並列プログラミング言語では、モニタという構造が用意されています。モニタは、その対象範囲内に定義されている関数に対して、暗黙の内にコードロックを行います。相互排他ロック (mutex ロック) によって、モニタを実装することも可能です。

同じ相互排他ロックの保護下にある関数または同じモニタの対象範囲内にある関数は、互いに原子操作的に実行されることが保証されます。

データロック

データロックは、データ集合へのアクセスが一貫性をもって行われることを保証します。データロックも、基本的な概念はコードロックと同じです。しかし、コードロックは共有される (広域的な) データのみへの参照を囲むようにかけます。相互排他ロックでは、各データ集合に対応する危険領域を同時に実行できるスレッドはせいぜい 1 つです。

一方、複数読み取り単一書き込みロックでは、それぞれのデータ集合に対して複数スレッドが同時に読み取り操作を行うことができ、1 つのスレッドが書き込み操作を行うことができます。複数読み取り単一書き込みロックのように、それぞれ異なるデータ集合を操作するか、同じデータ集合で衝突を起こさないようにすれば、同一モジュール内で複数のスレッドを実行できます。つまり、通常はコードロックよりもデータロックの方が、並行度を高くすることができます。(Solaris には読み取り / 書き込みロック機能が組み込まれていることに注意してください。)

プログラムで、(相互排他ロック、条件変数、セマフォなどの) さまざまなロックを使用するときの方針を説明します。できる限り並列性を高めるためにきめ細かくロックする、つまり必要なときだけロックして不要になったらすぐ解除するという方法と、ロックと解除に伴うオーバヘッドをできる限り小さくするため長期間ロックを保持する、つまりきめの粗いロックを行うという方法が考えられます。

ロックをどの程度きめ細かくかけるべきかは、保護の対象となるデータの量によって異なります。最もきめの粗いロックは、全データを 1 つのロックで保護します。保護対象のデータをいくつに分割してロックするかは、非常に重要な問題です。ロックのきめが細かすぎても、性能に悪影響を及ぼします。それぞれのロックと解除に伴うオーバヘッドは、ロックの数が多いと無視できなくなるからです。

通常、ロックを使用する方針は次のとおりです。最初は、きめを粗くロックします。次にボトルネックを特定したら、それが緩和されるようにロックのきめを細かくしていきます。これは妥当な解決策ですが、並列性を最大にすることとロックに伴うオーバヘッドを最小にすることのどちらをどの程度優先させるかは、ユーザが判断してください。

不変式

コードロックとデータロックについて、複雑なロックを制御するためには「不変式」が重要な意味をもちます。不変式とは、常に真である条件または関係のことです。

不変式は、並行実行環境に対して次のように定義されます。すなわち不変式とは、関連するロックが行われるときに条件や関係が真になっていることです。ロックが行われた後は偽になってもかまいません。ただし、ロックを解除する前に真に戻す必要があります。

あるロックが行われるときに真となるような条件または関係も不変式です。条件変数では、条件という不変式を持っていると考えることができます。

例 9-4 assert(3X) による不変式のテスト


    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(3T) を呼び出します。これで他のスレッドが実行され、そのスレッドはロックを獲得できるようになります。

必要なタイムスライスの大きさはアプリケーションに依存するため、スレッドライブラリでは特に制限していません。thr_yield() を呼び出して、スレッドが共有する時間を設定してください。

ロックに関する指針

次に、ロックのための簡単な指針を示します。

その他の基本的な指針


      thr_exit();
       /* NOT REACHED */

スレッドの生成と使用

スレッドパッケージは、スレッドのデータ構造、スタック、および LWP をキャッシュするので、非結合スレッドを繰り返し生成してもシステムに対する負荷は大きくなりません。

プロセスや結合スレッドの生成と比べて、非結合スレッドの生成にはかなりのオーバヘッドがあります。実際そのオーバヘッドは、1 つのスレッドを停止して他のスレッドを開始するといったコンテキストスイッチを行う場合の非結合スレッドでの同期を行うのにかかる負荷と同程度です。

したがって、必要に応じてスレッドを生成したり削除したりするほうが、専用の処理要求を待つスレッドを維持管理するより効率的です。

たとえば、RPC サーバがよい例です。RPC サーバは要求が送られてきたらスレッドを生成し、応答を返したらスレッドを削除します。要求を処理するためのスレッドを、常に維持管理しません。

スレッドの生成のオーバヘッドがプロセス生成のオーバヘッドと比べて小さいといっても、数個の命令を実行するのにかかる負荷に比べると効率的ではありません。少なくとも数千の機械語命令が続くような処理を対象にして、スレッドを生成してください。

軽量プロセス (LPW)

図 9-1 に LWP、ユーザレベル、およびカーネルレベルの関係を示します。

図 9-1 マルチスレッドのレベルと関係

Graphic

ユーザレベルのスレッドライブラリは、適切なプログラミングが行われていて、オペレーティング環境が正常に動作している限り、現在実行可能なユーザレベルのスレッド数に対して適切な数の利用可能な LWP が存在することを保証しています。しかし、ユーザレベルのスレッドと LWP の間には一対一の関係は存在しないので、ユーザレベルのスレッドはある LWP から別の LWP へと自由に移動できます。

Solaris スレッドでは、プログラマは同時にいくつのスレッドを実行させるかをスレッドライブラリに指定できます。

たとえば、最大 3 個のスレッドを同時に実行させるように指定すると、少なくとも 3 個の LWP が必要になります。3 個のプロセッサが利用可能なら、それらのスレッドは並列に実行されます。しかし、プロセッサが 1 つしか存在しないときは、オペレーティング環境が単一のプロセッサ上で 3 つの LWP を並行化します。すべての LWP がブロックされた場合は、もう 1 つ別の LWP がスレッドライブラリによって実行リソースに追加されます。

同期をとるためにユーザスレッドがブロックすると、そのスレッドが接続している LWP は、実行可能な別のスレッドと接続します。この移行にはコルーチンリンケージが使われ、システムコールは使われません。

オペレーティング環境は、どの LWP をどのプロセッサでいつ実行させるかを決定します。各プロセスにあるユーザスレッドや、ユーザスレッドがいくつ実行可能になっているかなどをオペレーティング環境は認識していません。

カーネルは、LWP のスケジューリングクラスと優先順位に従って、LWP を CPU リソースに割り当てます。同様に、スレッドライブラリはスレッドを LWP に割り当てます。

各 LWP はカーネルによって独立に振り分けられ、独立したシステムコールを実行し、独立したページフォルトを引き起こし、マルチプロセッサのシステム上では並列に動作します。

LWP の機能の中には、特別なスケジューリングクラスなどのように、スレッドからは直接には参照できないものがあります。

非結合スレッド

スレッドライブラリは、必要に応じて LWP を生成し、実行可能なスレッドを LWP に割り当てます。スレッドが割り当てられた LWP はスレッドの状態を引き継ぎ、スレッドの一連の命令を実行します。スレッドが同期機構によりブロック状態になるか、別のスレッドを実行しなければならないような状態が生じると、現在のスレッドの状態はプロセスのメモリーに退避され、スレッドライブラリはその LWP に別のスレッドを割り当てて実行します。

結合スレッド

非結合スレッドで起こりがちなことですが、スレッド数を LWP 数よりも大きくすると不利な場合があります。

たとえば、行列を並列に計算するために、行列の行を複数のスレッドに振り分ける場合を考えます。各プロセッサに 1 つの LWP が存在するが各 LWP に複数のスレッドを割り当てる場合は、各プロセッサの時間がスレッドの切り替えのために費やされます。このような場合は、各 LWP には単一のスレッドを割り当てて、行列の行を振り分けるスレッドの数を減らし、スレッドを切り替える回数を減らすほうが効果的です。

LWP に固定的に結合されたスレッドと非結合スレッドを混在させると都合がよい場合もあります。

たとえば、リアルタイムアプリケーションでは、一部のスレッドにシステム全体での優先順位を与えてリアルタイムでスケジューリングし、他のスレッドにバックグラウンドで計算を実行させます。もう 1 つの例はウィンドウシステムです。ウィンドウシステムでは大半の処理を非結合スレッドで実行し、マウスに関する処理を優先順位の高いリアルタイムの結合スレッドで実行します。

ユーザレベルのスレッドがシステムコールを発行すると、そのスレッドを実行している LWP はカーネル内部に入り、少なくともシステムコールが完了するまでの間はスレッドに接続されたままの状態となります。

結合スレッドは、非結合スレッドより負荷がかかります。結合スレッドは、結合している LWP の属性を変更することがあるので、終了時に LWP がキャッシュされることはありません。オペレーティング環境は、結合スレッドに対して生成時に新しい LWP を与え、終了時にその LWP を削除します。

結合スレッドを使用するのは、次の場合に限ってください。すなわち、結合している LWP を通してのみ利用可能なリソース (たとえば、仮想時間インタバルタイマ、代替スタック) をスレッドが必要としている場合か、スレッドをカーネルから参照可能にしてシステム内のすべての実行可能なスレッドとの関係でスケジューリングされるようにする (たとえば、リアルタイムスケジューリング) 場合です。

すべてのスレッドが同時に実行可能になることが期待される場合は、非結合スレッドを使用してください。そうすれば LWP とスレッドのリソースが効率的にキャッシュされるので、スレッドの生成と削除が高速で行われるようになります。thr_setconcurrency(3T) を使用すると、Solaris スレッドに対して同時に有効にしたいスレッド数 (目標値) を伝えることができます。

スレッドの並行度 (Solaris スレッドの場合のみ)

特に指定しなければ Solaris のスレッドは、非結合スレッドを実行するためのシステム実行リソース (LWP) の数を実行可能なスレッドの数と同じになるように調整します。この調整は完全なものではありませんが、少なくともプロセスの処理が進行することは保証されます。

同時に実行可能にすべき (コードやシステムコールを実行する) 非結合スレッドの数がわかっている場合は、thr_setconcurrency(3THR) によって、その値をスレッドライブラリに指示してください。

例

各スレッドの生成時に THR_NEW_LWP フラグを指定して、並行度を 1 つ増やす方法もあります。

スレッドの並行度を計算するときは、プロセス間 (USYNC_PROCESS) 同期変数でブロックされている非同期スレッドも、実行可能なスレッドとして数えてください。結合スレッドは LWP と等価で、Solaris スレッドの並行度のサポートを必要としないので、実行可能なスレッドには数えません。

効率

すでにあるスレッドを再起動するよりも、thr_create(3T) で新しく生成した方が短時間ですみます。つまり、使用しないスレッドをそのまま残しておいて後で再起動するより、必要に応じて新しいスレッドを生成し使い終わったら thr_exit(3T) で終了させる方が効率的です。

スレッドの生成に関する指針

次に、スレッドを使用するときの簡単な指針を示します。

マルチプロセッサへの対応

マルチスレッドでは、主に並列性とスケーラビリティという点でマルチプロセッサを活用できます。プログラマは、マルチプロセッサと単一プロセッサのメモリーモデルの違いを考慮に入れておかなければなりません。

メモリーの一貫性は、メモリーを問い合わせるプロセッサと直接的な相関関係にあります。単一プロセッサの場合、メモリーを参照するプロセッサは 1 つしかないのでメモリーは一貫しています。

マルチプロセッサの性能を高めようとすると、メモリーの一貫性が緩められることになります。あるプロセッサによるメモリーへの変更が、他のプロセッサから見たメモリーイメージにただちに反映されるとは限りません。

共有される広域変数を使用するときに同期変数を使用すれば、この複雑さを回避できます。

バリア同期を使用すると、マルチプロセッサ上での並列性をうまく制御できる場合があります。付録 B 「Solaris スレッドの例 − barrier.c」「Solaris スレッドの例 − barrier.c」にバリアの一例を示しています。

マルチプロセッサに関して、もう 1 つの問題があります。共通の実行ポイントに到達するまで全スレッドが待たなければならないようなケースでは、同期の効率が問題となります。

注 -

共有メモリーにアクセスするためにスレッドの同期プリミティブを必ず使用する場合は、上記の項目は重要ではありません。

アーキテクチャ

スレッドが、Solaris のスレッド同期ルーチンを使用して共有記憶領域へのアクセスの同期をとるときは、共有メモリー型のマルチプロセッサ上でプログラムを実行することと、単一プロセッサ上でプログラムを実行することは同じことになります。

しかし、プログラマはあえてマルチプロセッサ特有の機能を活用したり、同期ルーチンを迂回する「トリック」を使用したりすることがあります。例 9-5 と例 9-6では、そうしたトリックの危険性を示しています。

通常のマルチプロセッサアーキテクチャがサポートしているメモリーモデルを理解することは、この危険性を理解する助けとなります。

マルチプロセッサの主な構成要素は、次のとおりです。

従来の単純なモデルでは、各プロセッサがメモリーに直接接続されているかのように動作します。つまり、あるプロセッサが特定の位置にデータを格納すると同時に別のプロセッサが同じ位置からデータをロードした場合、2 番目のプロセッサは最初のプロセッサが格納したデータをロードします。

キャッシュは、メモリーアクセスの高速化のために使われ、キャッシュ間の整合性が維持されているときは、データの整合性も保たれます。

この単純なモデルの問題点は、データの整合性を保つためプロセッサをしばしば遅延させなければならないことです。最新のマルチプロセッサでは、各種の手法でそうした遅延を回避していますが、メモリーデータの整合性を失わせています。

次の 2 つの例で、それらの手法と効果を説明します。

共有メモリー型のマルチプロセッサ

例 9-5 は、「生産者 / 消費者」問題の代表的な解決方法です。

このプログラムは、現在の SPARC ベースのマルチプロセッサでは正しく動作しますが、すべてのマルチプロセッサが強く順序付けられたメモリーをもつことを想定しています。したがって、このプログラムには移植性がありません。

例 9-5 「生産者 / 消費者」問題 − 共有メモリー型のマルチプロセッサ


                    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-5 と例 9-6 で示すようにロックは重要です。

Peterson のアルゴリズム

例 9-6 は、Peterson のアルゴリズムの実装例です。これは 2 つのスレッド間での相互排他を扱うアルゴリズムです。このコードでは、危険領域に同時に複数のスレッドが存在しないことを保証しようとしています。さらに、スレッドが mut_excl() を呼び出すと、危険領域に「素早く」入ることを保証しています。

ここで、スレッドは危険領域に入ると素早く抜け出るものとします。

例 9-6 2 つのスレッド間での相互排他が成立するか


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 部分のアルゴリズムを並列化できます (詳細は、次の例を参照してください)。 

スレッド1

スレッド2 〜 スレッド n

while(many_iterations) {

    sequential_computation
    --- バリア ---
    parallel_computation
}
 
while(many_iterations) {


    --- バリア ---
    parallel_computation
}

たとえば、完全な線型計算で一組の行列を作成し、それらの行列に対する操作を並列アルゴリズムで実行し、操作結果からもう一組の行列を作成し、それらの行列を並列的に操作するといった処理が考えられます。

こうした計算の並列アルゴリズムの特徴は、計算中はほとんど同期をとる必要はありませんが、並列計算を始める前に逐次計算が終了していることを確認するために、関連するすべてのスレッドの同期をとる必要があることです。

バリアには、並列計算を行なっているすべてのスレッドを、関係しているすべてのスレッドがバリアに達するまで待たせるという働きがあります。スレッドは全部がバリアに達したところで解放され、一斉に計算を開始します。

まとめ

このマニュアルでは、スレッドのプログラミングに関する重要な問題を幅広く取り上げて説明しました。付録 A 「アプリケーションの例 − マルチスレッド化された grep」「アプリケーションの例 − マルチスレッド化された grep」には、pthread プログラムの例が記載されています。この例の中で、今までに説明した多くの機能やスタイルが使用されています。また、付録 B 「Solaris スレッドの例 − barrier.c」「Solaris スレッドの例」には、Solaris スレッドを使用したプログラムの例が記載されています。

参考資料

マルチスレッドについてさらに詳しく知りたい方は、次の書籍をお読みください。