並行プロセス

概要

　この章では、複数のスレッドが相互に関り合いを持つときに生ずる問題と その解決法を紹介します。 また、複数のスレッドを動作させて、総合的な仕事をさせるときに不可欠な、 スレッド間通信の基礎も紹介します。

目次

• 競合問題
• 相互排除
• セマフォによる相互排除

• 複数スレッドの協調
• 同期
• 工場の生産ライン
• コンピュータ・スレッド同期
• セマフォによる同期

競合問題

　複数のスレッドがある資源を共有する場合、発生する問題があります。

　図１を使って簡単な例を示します。まず、メモリ領域Ｍに変数x,yがあります。 スレッドＡはこの(x,y)に(1,2)を書き込んでその和を計算して取り出すスレッドで、 スレッドＢは(x,y)に(2,3)を書き込んでその積を計算するスレッドとします(図２,図３)。

(図1)競合の例

thread_A(){
    x=1;
    y=2;
    return x+y;
} 

thread_B(){
    x=2;
    y=3;
    return x*y;
} 

　スレッドＡとスレッドＢが別々に実行されるならば問題ありません。 ところが、スレッドＡのx=1;の実行直後にスレッドの切り替えがおこり、 実行がスレッドＢに移った場合はどうなるでしょう。 このままスレッドＢが無事に終了し、スレッドＡに実行が戻ると、 メモリは(x,y)=(2,3)で、y=2;から実行が継続されるので、 x+yの結果として4が取り出されてしまいます。 このようにスレッドが共有資源をアクセスする際、 他のスレッドの動作が影響して期待どおりの結果が得られない場合があります。 この現象を競合といいます。

　なお、共有資源をアクセスするとき、プログラマは必ずその部分のプログラムについては 競合問題を意識しながら書かなければなりません。 このような、際どいプログラム部分のことをクリティカルセクションと呼びます。

　競合を防ぐ方法として、後述する相互排除を行う方法があります。 これは、あるスレッドが共有資源にアクセスする際、ロックという操作を行って、 他のスレッドがアクセスできないようにするものです。 次節では、相互排除について取り上げます。

相互排除

　相互排除(Mutual Exclusion)とは、競合問題を打開する方法です。 相互排除を実現するためには、一般にlockおよびunlockと呼ばれる命令を使います。 クリティカルセクションの直前でlockを実行し、必要な操作が終わったらunlockを実行するようにすると、相互排除が実現できます。

　相互排除は次のような仕組みで行われます。まず、共有資源にたいして、BOOL変数mを導入します。 ここでmは、FALSEならその資源はどのスレッドにも使われていないことを意味し、 TRUEならその資源はあるスレッドによって使用されていることを意味するようにします。 さてここで、lockとunlockを図4のように定めると、スレッドがクリティカルセクションを実行するとき(図5)、 誰も使用中でなければ使用中にし、誰かが使用中ならばそれが開放されるまで待つようになります。

lock(){
    while(m);
    m=TRUE;
}

unlock(){
    m=FALSE;
} 

thread_func(){
    lock();
    // クリティカルセクション　ここから
    ・・・
    // クリティカルセクション　ここまで
    unlock();
}
  

　相互排除でのlockの際、ポイントとなるのはmがFALSEになるのをループしながら待つということです。 この方式で待っているスレッドのことをスピンしているといい、 スピンによってスレッドが停止していることをスピンロックと言います。 スピンロックはまた、ビジーウェイトとも呼ばれ、一見ＣＰＵを浪費しているように見えますが、 クリティカルセクションの実行が短時間の場合はスレッドの切り替えを伴わないので、 スレッドを停止させて待つ方式(サスペンド・ロック)より効率が良いことがあります。

　なお、実際のlockとunlockは図4ほど単純には構成されていません。 実際のlockとunlockはピーターソンのアルゴリズムにしたがって実現されています。

セマフォによる相互排除

　セマフォ(Semaphore)は整数値sと事象発生待ちのスレッドを貯えるキューQsからなっています(図6)。 また、セマフォにはＰ命令とＶ命令があります。これら命令の動作を図7に示します。

	P(){ if(s>0){ s--; }else{ Qs <- 自スレッドをQsに入れる } } V(){ if(Qsが空でない){ Qsから一つスレッドを取り出し実行可能にする }else{ s++; } }
(図6)セマフォの構造	(図7)セマフォの動作

　セマフォはスレッド間の協調で良く使われるシステムですが、相互排除にも適用できます。 相互排除を行うには、セマフォの値として0と1をとる２値セマフォを用います。 すると、このときＰ命令がlockに相当し、Ｖ命令がunlockに相当します。

　ただし、セマフォによるロックはサスペンドロックなので、 スピンロックと比べて、少々動作に鈍りが生じる可能性があります。

複数スレッドの協調

　まず人間の世界で考えてみましょう。 人間が仕事を遂行するとき、単純な仕事であれば一人ででも実行できるでしょう。 ところが複雑な仕事の場合は、一人でやると混乱してしまうので、 通常は数人で仕事を分担します。

　これと同じように、単純な作業であれば単一スレッドでも実行できますが、 複雑な作業を行いたいときなど、仕事を分割して複数のスレッドで役割を分担するという手法があります。 これが複数スレッドの協調です。

　ところが、スレッドが複数になると様々な問題が生じます。 例えば、スレッドとスレッドの間で情報を行き来させなければならないので、 必ず共有資源が存在することになります。したがって、相互排除を行わなければなりません。 また、他のスレッドで情報が生成されるのを待って、自スレッドの動作を開始したい場合もあります。 このような制御のことを同期をとるといい、 複数のスレッドを並行して実行する場合に、必要な技術です。

　同期をとる方法としてよく利用されるのが、セマフォを使う方法です。 次節ではセマフォを使ってスレッドの同期をとる方法を説明します。

同期

工場の生産ライン

　スレッド間で同期をとって情報を伝達する方法として、 まず、工場の生産ラインについて考えてみましょう。 工場の生産ラインにおいて、プロセスＡを部品組み立てる行程とし、 プロセスＢをプロセスＡが組み立てた部品を箱づめする行程とします(図8)。 このとき、プロセスＡからプロセスＢに向かって、部品を送る伝送路があり、 プロセスＡはここに組み立てた部品を置き、プロセスＢはここから部品を取り出します。 もし、この伝送路が空であれば、 プロセスＢはプロセスＡによって部品組み立てられるまで、動作を停止しなければならないし、 また、この伝送路が満杯であればプロセスＡは部品の組み立てを一時的に停止(生産ラインを停止)しなければなりません。

(図8)工場の生産ライン プロセスＡ: 部品を組み立てる行程 プロセスＢ: 部品を箱詰めする行程

コンピュータ・スレッド同期

　上の議論は「部品」を「情報」に置き換えることで、 そのままコンピュータのスレッド制御に置き換えることができます。

　すなわち、スレッドＡとスレッドＢの間に情報伝送路(バッファ)を置き、 バッファが空ならばスレッドＢを停止させ、 バッファが満杯ならばスレッドＡを停止させる、となります。

　バッファが空のときスレッドＢは、スレッドＡが情報を生産するのを待ちます そして、スレッドＡが情報を生産したら、スレッドＢが動作可能状態になります。

　また上の例では、プロセスＡ(スレッドＡ)が部品(情報)の生産者、 プロセスＢ(スレッドＢ)が部品(情報)の消費者と見ることができるので、 生産者・消費者同期と呼ばれます。

セマフォによる同期

　バッファが有限長(Ｎ)の場合、二つのセマフォＸ,Ｙを用いて同期をとる方法が用いられます。 そして、セマフォＸはバッファにある情報の量を保持し、 セマフォＹはバッファの空きの量を保持するようにします。 すると、セマフォＸが0(=バッファが空)のときは、消費スレッドを停止させることができます。 同様に、セマフォＹが0(=バッファが満杯)のときは、生産スレッドを停止させることができます。 以上の動作を実現させるためには、次の３つを満たせばよいです。

1. セマフォＸ,Ｙの初期値をそれぞれ0,Nに設定
2. 生産スレッドで、バッファに書き込む前にP(Y)を実行、書き込んだ後V(X)を実行
3. 消費スレッドで、バッファから読み込む前にP(X)を実行、読み込んだ後V(Y)を実行

　なお、バッファは共有資源なので、ここにアクセスする際は相互排除を行う必要もあります。

　以上の議論をまとめたアルゴリズムが図9,10です。

produce_thread(){
    P(Y);
    lock();
    // バッファに情報を書き込む

    unlock();
    V(X);
} 

consume_thread(){
    P(X);
    lock();
    // バッファから情報を取り出す

    unlock();
    V(Y);
}  

参考文献