第7章　スレッドの排他制御

本章ではスレッド間の共有リソースにアクセスするための排他制御について説明します。GCで利用するスレッドはオブジェクトを共有リソースとして扱いますので、排他制御が必要になる場面が多々あります。

メモリ領域を共有するスレッドでは、同じアドレスにあるデータを複数のスレッドが同時に読み書きできてしまいます。ほかのスレッドから割り込みで変更される可能性があるデータに対し、割り込みを想定していないコードを書いてしまった場合は、思わぬところでメモリ破壊が生じてしまい、原因が特定しづらいエラーが発生してしまうかもしれません。

このように単一のリソースに対して、複数のスレッドから同時に処理が実行されるとまずい部分をクリティカルセクションと呼びます。

クリティカルセクションを扱う処理では、スレッド単体でアトミックに一連の処理を実行し、割り込みがないようにほかのスレッドの処理を排除する必要があります。このようにほかのスレッドを排除し、あるスレッドだけでリソースを独占的に利用させることを排他制御と呼びます。

排他制御の単純な実装例としてよく利用されるのがミューテックス（Mutex）です。これはmutal exclusion（相互排他）の略からきた造語です。

Javaでは言語自体にモニタ（Monitor）という同期機構が組み込まれています。そして、HotspotVMの内部の排他制御はほとんどがこのモニタを使っておこなわれます。

さて、Javaのモニタについてスノーボードのレンタルショップのたとえ話を持ちだしてみます。このレンタルショップで扱うスノーボードはすべて同じサイズ・同じデザインとします。また、店内は狭いため、一度に1人の客しか入ることができません。もし先に客が入っていた場合は、店の前に行列を作って待ちます。店内に客がいない場合は行列の先頭1人が店に入ることができます。店内に入った客は自分にあったスノーボードを借りて店をでます。もし自分にあったスノーボードがなかった場合は、店に備え付けの待合室で待ちます。

スノーボードを返しに来た客も同様に行列に並びます。返し終わった客は待合室の客の内1人、もしくは客全員を呼ぶことが可能です。呼ばれた客は店内に客がいないときに店内に入ります。店の前に行列ができていた場合は行列の後ろに並びなおします。再度入店しても、スノーボードがない場合はまた待合室に入って待ちます。

図7.1: モニタの例え: 狭いレンタルショップ

上記はモニタのたとえ話です。この場合、共有リソースはスノーボードであり、モニタはレンタルショップを指します。客がスレッドだとすると、スレッドはモニタの中に高々1スレッドしか入れません。レンタルショップに客が入っている状態は、店自体にロックがかかっている状態と言えます。客が出ると店がアンロックされ、ほかの客が入れるようになります。Javaの文化では待合室で待つことをWait、待合室内の1人を呼ぶことをNotify、全員を呼ぶことをNotifyAllといいます。

別のたとえも少し考えてみましょう。もし共有しているリソースがレンタルビデオだとしたらどうなるでしょうか。来た客は対象のビデオがなかった場合に待合室で待ちます。返却にきた客はビデオ返却後に待合室の客を呼び出しますが、呼び出された客は返されたビデオが自分の待っていたビデオとは限りません。違った場合はまた待合室に戻ることになります。このモニタのたとえで無駄な点は、待合室で待っている客が自分の欲しいビデオを店内に伝えられない点です。もし「私の欲しいビデオはこれです（太郎）」などと店内に張り紙できれば、返却しにきた客が張り紙を見て適切な待ち人を呼べます。呼ばれた客は、店内に入った後で自分の欲しいビデオがなくてがっかりすることも少なくなるでしょう。この便利な張り紙のことを条件変数（condition variable）と呼びます。

「Javaのモニタが一般的なモニタと異なる点」というのは実はこの部分で、一般的なモニタにはこの条件変数がありますが、Javaのモニタにはありません。

モニタが管理する共有リソースが例えばビデオのように客の要求に強く依存する場合は張り紙がある方が有利です。返却しにきた客は待合室にいる適切な客を選ぶことが可能で、呼び出された客も関係ないときに呼ばれることが少なくなります。一方、Javaのモニタの場合は張り紙がないので、いったん待合室の全員を呼んで、呼び出された客がリソースを判断しなければなりません。

ただし、モニタが管理するリソースがスノーボードの例のように客の要求に依存しないものであればJavaのモニタでも問題ありません。ボード自体に個性がないため、待っている客は借りるものは何でもよく、単純に空きがでるのを待っているだけですから、張り紙は必要ないのです。

このように、Javaでは条件変数をなくしたシンプルなモニタを提供しています。

ここで気になるのはモニタの実装方法です。ただ、この話題はGCの話から脱線しすぎる予感がしますので、実装の重要な部分をかいつまんで説明します。また、ここで取り上げる実装方法はHotspotVMの例です。モニタ実装の一例として捉えてください。

まず、行列や待合室での一時停止・再起動処理を見てみましょう。それぞれの処理は次のメンバ関数で実装されています。

• os::PlatformEvent::park() - 待つ
• os::PlatformEvent::unpark() - 再起動

parkは「駐車する」、unparkは「発車する」という意味があります。それぞれのメンバ関数はそれぞれのOS用に実装されていますが、今回はLinuxのものを簡単に見ていきます。

park()では次のようにpthread_cond_wait()を利用して待つ処理を実現しています。

4916: void os::PlatformEvent::park() {

4928:      int status = pthread_mutex_lock(_mutex);

4933:         status = pthread_cond_wait(_cond, _mutex);

4948: }

os::PlatformEventのインスタンスは_condと_mutexのメンバ変数を保持しています。_condは条件変数、_mutexはミューテックスであり、それぞれPthreadsで利用される変数です。4928行目でpthread_mutex_lock()を使って、_mutexをロックします。その後、4933行目でpthread_cond_wait()を使って、現在のスレッドを一時停止状態にします。pthread_cond_wait()には_condと、ロック状態の_mutexを指定します。_mutexはpthread_cond_wait()内部で一時停止状態になった際にアンロックされます。

unpark()は次のようにpthread_cond_signal()を利用してスレッドを再起動します。

5011: void os::PlatformEvent::unpark() {

5028:      int status = pthread_mutex_lock(_mutex);

5034:         pthread_cond_signal (_cond);

5049: }

5034行目で登場するpthread_cond_signal()では引数に取った条件変数で待っている1つのスレッドに対してシグナルを送り、再起動します。ここではos::PlatformEventインスタンスの_cond変数で待っているスレッドに対してシグナルを送ります。

ちなみに、Windowsでは上記とほぼ同じことをWaitForSingleObject()、SetEvent()を利用して実装しています。

Threadクラスはos::PlatformEventクラスを継承したParkEventクラスのインスタンスをメンバ変数として保持しています。

94: class Thread: public ThreadShadow {

       // 内部のMutex/Monitorに利用される
582:   ParkEvent * _MutexEvent ;

そのため、図7.2のように、HotspotVMが管理する1スレッド（Threadインスタンス）の_MutexEventに対して、park()・unpark()を呼ぶことで、対象のスレッドを一時停止・再起動させることが可能です。モニタで説明した「待合室で待つ」「待合室から出る」「行列を作って待つ」などはこのpark()・unpark()を利用して実装されます。

図7.2: 1スレッドに対してpark()を呼ぶとスレッドは一時停止する。一時停止中はCPUを無駄に利用しない。unpark()を呼ぶとスレッドは再起動する。

次にモニタのロック・アンロックについて見ていきましょう。ここからは実装が複雑なので概要だけを紹介します。

モニタの状態の一例を図7.3に図示しました。このモニタでは行列（EntryList）にスレッドB,Cが並んで待っています。モニタの前には小さな前室（OnDeck）があります。そして、モニタ内のロックはスレッドAが現在は保持しています。

図7.3: モニタの状態の一例。モニタはロックされているため、EntryListのスレッドBはロックを取ることができない。

まずはロックのフローについて説明しましょう。ロック取得時、モニタに入っているスレッドがいなければ、すぐにモニタに入りロックを取得します（図7.3のスレッドA参照）。モニタにすでにスレッドが入っていれば、ロックを取得したいスレッドはEntryListに並び、モニタが空くのを待ちます（図7.3のスレッドB・C参照）。

次にアンロックのフローについて説明します。モニタのアンロック時にはEntryListにいるスレッドにロックをとらせる処理が入ります。スレッドAのアンロック時の、手順を具体的に以下に示しました。

1. モニタをアンロックしたスレッドAがEntryListの先頭をOnDeckに格納
2. スレッドAはOnDeckのスレッドBを起こす（unpark()）
3. スレッドBはOnDeckに自分がいるのを確認
4. スレッドBがモニタに入り、ロックする

まずはWaitの実装を考えてみましょう。モニタ内のスレッドがwaitする場合もモニタをアンロックすることになりますので、基本的には前節のモニタのアンロックの処理と同じになります。ただし、Waitではpark()を使って自身のスレッドを待たせる処理が必要になります。

次にNotifyAllの実装を考えてみましょう。図7.4に複数のスレッドが待合室（WaitSet）で待っている図を示しました。EntryListにスレッドが並んでおらず、モニタのロックはスレッドAが握っています。

図7.4: スレッドB,CがWaitSetでpark()された状態になっている。スレッドAはモニタのロックを保持。EntryListは空。

ここでスレッドAがモニタ内でNotifyAllをおこなったとします。

NotifyAllでは、WaitSet内のスレッドをWaitSetから取り出し、unpark()を呼び出します。WaitSetにいたスレッドは外に出た後でほぼ同時に動き出します。その後、図7.5のように、お互いに競争しながら1つキューを作ります。これをContentionQueueと呼びます。キューを作ったあとはスレッド自身がpark()を呼び出し、一時停止状態に入ります。

図7.5: WaitSetから出たスレッドB,Cは競争し合いながら1つのキューを作る。この際の並び順は競争に勝った順にならんでいく

最後にスレッドAがモニタをアンロックします。その際、スレッドAはEntryListの先頭をOnDeckに格納しようと思いますが、EntryListは空であるため、ContentionQueueをEntryListに昇格します。その後、EntryListの先頭をOnDeckに格納し、unpark()を呼び出します。以降の処理は以前説明したアンロックの処理と同じです。

図7.6: モニタをアンロックするスレッドAはContentionQueueをEntryListに昇格し、先頭をOnDeckに格納する

最後のNotifyの実装ですが、これはWaitSetから呼び出されるのが全スレッドか、1スレッドであるかの違いしかありません。処理の流れはNotifyAllと同じです。

HotspotVMにはMonitorというクラスが実装されており、VM内部で利用するスレッドはこのクラスを利用して排他制御します。

Monitorクラスには次のようにメンバ関数が定義されています。

87: class Monitor : public CHeapObj {

177:  public:
185:   bool wait(bool no_safepoint_check = !_no_safepoint_check_flag,
186:             long timeout = 0,
187:             bool as_suspend_equivalent = !_as_suspend_equivalent_flag);
188:   bool notify();
189:   bool notify_all();

193:   void lock(Thread *thread);
194:   void unlock();

このMonitorクラスの1インスタンスが例として取り上げたレンタルショップのモニタに相当します。たとえば、10個Monitorのインスタンスを作れば、10個のレンタルショップのモニタが作られたことになります。そして、それぞれの店はそれぞれの共有リソースを管理します。また、客（スレッド）はモニタのしきたりに則って、どの店にも入店できます。

実際にコードを見てみないとイメージをつかめないと思いますので、次にMonitorクラスのサンプルコードを示しました。

 1: // new Monitor(Mutex::safepoint, "Test Monitor"); で初期化される
 2: Monitor* shop_monitor;
 3: // レンタルショップを表すグローバル変数
 4: RentalShop* rental_shop;
 5: 
 6: class Client {
 7:   Board* _snowboard;
 8: 
 9:   // ...
10: }

2行目にはMonitorインスタンスへのポインタを保持するグローバル変数のshop_monitorを定義します。4行目にはレンタルショップを表すrental_shopグローバル変数を定義します。これらのグローバル変数はどこか別の関数で初期化されると想定します。

6行目にClientクラスを定義します。Clientクラスはレンタルショップを訪問する客を表現しており、shop_monitorはレンタルショップのモニタを表現しています。Clientは_snowboardメンバ変数を持っており、ここに借りたボードを格納します。

次に、ボードをレンタルするメンバ関数をClientクラスのrent()として定義します。

 1:   void rent() {
 2:     // ロック
 3:     shop_monitor.lock();
 4:     // ボードがある状態になるまで待つ
 5:     while (rental_shop.snowboards.empty()) {
 6:       shop_monitor.wait();
 7:     }
 8:     // 借りる
 9:     _snowboard = rental_shop.snowboards.pop();
10:     shop_monitor.unlock();
11:   }

3行目でshop_monitor.lock()を呼び出し、モニタのロックを取得します。すでにモニタがロックされていた場合は、ロックが取得できるまで待つことになります。5,6行目でボードが空になるまでモニタをアンロックして待ちます。別の客に起こされたら、9行目でボードを取り出し、_snowboardに格納します。そして、10行目でモニタをアンロックします。

次に、ボードを返却するメンバ関数をreturn()として定義します。

 1:   void return() {
 2:     shop_monitor.lock();
 3:     // ボードを返す
 4:     rental_shop.snowboards.push(_snowboard);
 5:     _snowboard = NULL;
 6:     // 待っているスレッドを1つだけ呼び出す
 7:     shop_monitor.notify();
 8:     shop_monitor.unlock();
 9:   }

こちらもrent()と同じくロックを取得した後で、ボードを返却します。返却したら7行目で待っている客を1人だけ呼び出し、8行目でモニタをアンロックします。呼び出された客（rent()で待っていた客）はモニタをロックしてボードを借ります。

ミューテックスを表現するMutexクラスもHotspotVMには実装されています。MutexクラスはMonitorクラスを継承して作られ、Monitorクラスの機能をほぼそのまま使います。

262: class Mutex : public Monitor {
263:  public:
264:    Mutex (int rank, const char *name, bool allow_vm_block=false);
265:    ~Mutex () ;
266:  private:
267:    bool notify ()    { ShouldNotReachHere(); return false; }
268:    bool notify_all() { ShouldNotReachHere(); return false; }
269:    bool wait (bool no_safepoint_check,
                   long timeout,
                   bool as_suspend_equivalent) {
270:      ShouldNotReachHere() ;
271:      return false ;
272:    }
273: };

ミューテックスはロックとアンロックだけあればよいので、267〜272行目でnotify(),notify_all(),wait()を呼び出せないように再定義しています。

MutexLockerクラスはロックの範囲をわかりやすく定義するのに役立つクラスです。

156: class MutexLocker: StackObj {
157:  private:
158:   Monitor * _mutex;
159:  public:
160:   MutexLocker(Monitor * mutex) {
163:     _mutex = mutex;
164:     _mutex->lock();
165:   }

175:   ~MutexLocker() {
176:     _mutex->unlock();
177:   }
178:
179: };

このクラスがおこなうことはコンストラクタでメンバ変数の_mutexをロックし、デストラクタで_mutexをアンロックすることだけです。

定義自体はシンプルですが、MutexLockerクラスを利用すれば、「7.5 Monitorクラス」で紹介したrent()関数は次のように記述できます。

 1:   void rent() {
 2:     {
 3:       MonitorLocker locker(shop_monitor);
 4:       while (rental_shop.snowboards.empty()) {
 5:         shop_monitor.wait();
 6:       }
 7:       _snowboard = rental_shop.snowboards.pop();
 8:     }
 9:   }

3行目でMonitorLockerインスタンスを生成する際に、コンストラクタによってshop_monitorがロックされます。8行目ではスタックに割り当てられたMonitorLockerインスタンスが解放されますので、デストラクタによってshop_monitorがアンロックされます。

上記のように、MutexLockerクラスを利用するとロックが必要な処理の範囲がわかりやすくなります。また、大域脱出の際（例外発生時など）にモニタのアンロックをし忘れる、といった凡ミスも防げます。そのため、HotspotVM内のコードではこのMutexLockerクラスや、Nullチェックの拡張を加えたMutexLockerExクラスが多用されています。