第8章 GCスレッド(並列編)

本章ではHotspotVMに実装されている複数のスレッドによる並列なタスク実行の枠組みを説明し、それが並列GCにどのように利用されているかを見ていきます。

8.1 並列実行の流れ

HotspotVMには複数のスレッドで並列に「何かのタスク」を実行する仕組みが実装されています。それを構成する主な登場人物は次のとおりです。

では、上記の登場人物が並列にタスクを実行する際の一連の流れを説明しましょう。

まず、AbstractWorkGangは1つだけモニタを持っており、モニタの待合室にはAbstractWorkGangに所属するGangWorkerを待たせます(図8.1)。

1. <tt class="inline-code">AbstractWorkGang</tt>はモニタを1つだけ持ち、<tt class="inline-code">GangWorker</tt>を待合室に待たせている。

図8.1: 1. AbstractWorkGangはモニタを1つだけ持ち、GangWorkerを待合室に待たせている。

モニタが排他制御する共有リソースはタスク情報の掲示板です。掲示板には次の情報が書きこまれます。

次に、クライアントがタスクを並列実行して欲しいタスクの情報を書き込みに来ます(図8.2)。

2. クライアントがモニタのロックを取り、タスクの情報を書き込む。

図8.2: 2. クライアントがモニタのロックを取り、タスクの情報を書き込む。

クライアントが持ってくる実際のタスクはAbstractGangTaskを継承した任意のクラスのインスタンスです。クライアントはタスクの場所としてインスタンスのアドレスを書き込みます。タスクの通し番号は前回のものから+1したものを書き込みます。この場合は1になります。実行ワーカー総数・実行完了ワーカー総数は0に初期化します。

次に、クライアントは待っているワーカーをすべて呼び出して、自身は待合室に入ります(図8.3)。

3. ワーカーは1つずつモニタに入り、掲示板の情報を手持ちの紙に書き写し、出ていく。

図8.3: 3. ワーカーは1つずつモニタに入り、掲示板の情報を手持ちの紙に書き写し、出ていく。

呼び出されたワーカーは1つずつモニタに入り、掲示板の情報を確認します。ワーカーは自分が前回に実行したタスクの通し番号を記録しており、もし掲示板の通し番号と記録した番号が同じだった場合は、重複した実行を避けるためにタスクを無視して待合室に入ります。通し番号が異なる場合は新しいタスクとみなし、手持ちの紙に掲示板の情報(タスクの場所・通し番号)を書き込みます。その後、掲示板の実行ワーカー総数を+1して、モニタの外に出てタスクを実行します。

次に、タスクの実行が終わるとワーカーは再度モニタに入り、タスクが終了したことを伝えるため、掲示板の実行完了ワーカー総数を+1します。(図8.4)。

4. タスクを終えたワーカーは再度モニタに入り、掲示板の情報を書き換えた後で待合室に入る。

図8.4: 4. タスクを終えたワーカーは再度モニタに入り、掲示板の情報を書き換えた後で待合室に入る。

そして、待合室の全員(クライアントを含む)を呼び出し、自分は待合室に入ります。ワーカーのタスク実行がすべて終了すると、実行ワーカー総数は実行完了ワーカー総数と同じになります。

クライアントはモニタに入ると、掲示板ですべてのワーカーが終了したか確認します(図8.5)。

5. クライアントはモニタに入った後、すべてのワーカーがタスクを終えたことを確認し、モニタを出ていく。

図8.5: 5. クライアントはモニタに入った後、すべてのワーカーがタスクを終えたことを確認し、モニタを出ていく。

もし、終えていないタスクがあれば、待合室でワーカーがタスクを終えるまで待ちます。すべてのワーカーがタスクを終えていれば、クライアントは満足してモニタから出て行きます。

以上が並列実行の流れです。

8.2 AbstractWorkGangクラス

ここからはそれぞれの登場人物の詳細を述べていきます。

AbstractWorkGangクラスの継承関係を図8.6に示します。

<tt class="inline-code">AbstractWorkGang</tt>クラスの継承関係

図8.6: AbstractWorkGangクラスの継承関係

AbstractWorkGangクラスはWorkGangに必要なインタフェースを定義するクラスです。

share/vm/utilities/workgroup.hpp

119: class AbstractWorkGang: public CHeapObj {

127:   virtual void run_task(AbstractGangTask* task) = 0;

139:   // 以降に定義されたデータを保護、
140:   // また変更を通知するモニタ
141:   Monitor*  _monitor;

146:   // この集団に属するワーカーの配列。
148:   GangWorker** _gang_workers;
149:   // この集団に与えるタスク
150:   AbstractGangTask* _task;
151:   // 現在のタスクの通し番号
152:   int _sequence_number;
153:   // 実行ワーカー総数
154:   int _started_workers;
155:   // 実行完了ワーカー総数
156:   int _finished_workers;

127行目に定義されている仮想関数のrun_task()は、タスクをworkerに渡して実行させる処理です。run_task()の実体は子クラスのWorkGangクラスに定義されています。

139〜156行目まではWorkGangに必要な属性が定義されています。これは「8.1 並列実行の流れ」で説明した「タスク情報の掲示板」のデータに相当します。

図8.6で示したFlexibleWorkGangクラスは実行可能なワーカー数を後から柔軟に(Flexible)変更できる機能を持つクラスです。並列GCにはこのFlexibleWorkGangクラスがよく利用されます。

8.3 AbstractGangTaskクラス

AbstractGangTaskクラスの継承関係を図8.7に示します。

<tt class="inline-code">AbstractGangTask</tt>クラスの継承関係

図8.7: AbstractGangTaskクラスの継承関係

AbstractGangTaskは並列実行されるタスクとして必要なインタフェースを定義するクラスです。

share/vm/utilities/workgroup.hpp

64: class AbstractGangTask VALUE_OBJ_CLASS_SPEC {
65: public:

68:   virtual void work(int i) = 0;

もっとも重要なメンバ関数は68行目のwork()です。work()はワーカーの識別番号(連番)を受け取り、タスクを実行する関数です。

タスクの詳細な処理は、G1ParTaskのようなそれぞれの子クラスでwork()として定義します。クライアントはAbstractGangTaskの子クラスのインスタンスをAbstractWorkGangに渡して、並列実行してもらうわけです。

8.4 GangWorkerクラス

GangWorkerクラスはタスクを実際に実行するクラスで、Threadクラスを祖先に持ちます。

<tt class="inline-code">GangWorker</tt>クラスの継承関係

図8.8: GangWorkerクラスの継承関係

GangWorkerのインスタンスは1つのスレッドと対応しているため、ワーカースレッドと呼ばれます。

share/vm/utilities/workgroup.hpp

264: class GangWorker: public WorkerThread {

278:   AbstractWorkGang* _gang;

GangWorkerは自分が所属するAbstractWorkGangをメンバ変数に持っています。

8.5 並列GCの実行例

では、実際のコードを読みながら「8.1 並列実行の流れ」の内容を振り返りましょう。

リスト8.1にクライアントとなるメインスレッドが実行する並列GCの実行サンプルを示しました。

リスト8.1: 並列GC実行のサンプルコード

 1: /* 1. ワーカーの準備 */
 2: workers = new FlexibleWorkGang("Parallel GC Threads", 8, true, false);
 3: workers->initialize_workers();
 4: 
 5: /* 2. タスクの生成 */
 6: CMConcurrentMarkingTask marking_task(cm, cmt);
 7: 
 8: /* 3. タスクの並列実行 */
 9: workers->run_task(&marking_task);

1. ワーカの準備

まず、リスト8.1の1.に示した部分でFlexibleWorkGangのインスタンスを生成・初期化し、図8.1の状態にします。

FlexibleWorkGangの生成・初期化のシーケンス図は次のとおりです。

<tt class="inline-code">WorkGang</tt>の生成・初期化のシーケンス図

図8.9: WorkGangの生成・初期化のシーケンス図

上から順番に見ていきましょう。最初はAbstractWorkGangのコンストラクタです。

share/vm/utilities/workgroup.cpp

33: AbstractWorkGang::AbstractWorkGang(const char* name,
34:                                    bool  are_GC_task_threads,
35:                                    bool  are_ConcurrentGC_threads) :
36:   _name(name),
37:   _are_GC_task_threads(are_GC_task_threads),
38:   _are_ConcurrentGC_threads(are_ConcurrentGC_threads) {


     _monitor = new Monitor(Mutex::leaf,
                            "WorkGroup monitor",
                            are_GC_task_threads);

48:   _terminate = false;
49:   _task = NULL;
50:   _sequence_number = 0;
51:   _started_workers = 0;
52:   _finished_workers = 0;
53: }

上記のコードからはモニタの初期化とデータの初期化がおこなわれることがわかれば充分です。それ以外の箇所はあまり関係ないので無視しましょう。

AbstractWorkGangクラスのインスタンスが生成された後、initialize_workers()メンバ関数でワーカーの初期化をします。

share/vm/utilities/workgroup.cpp

74: bool WorkGang::initialize_workers() {

81:   _gang_workers = NEW_C_HEAP_ARRAY(GangWorker*, total_workers());

92:   for (int worker = 0; worker < total_workers(); worker += 1) {
93:     GangWorker* new_worker = allocate_worker(worker);
95:     _gang_workers[worker] = new_worker;
96:     if (new_worker == NULL || !os::create_thread(new_worker, worker_type)) {
          /* 省略: エラー処理 */
98:       return false;
99:     }
101:       os::start_thread(new_worker);
103:   }
104:   return true;
105: }

81行目で生成したいワーカー分の配列を作成し、92〜103行目でワーカーを生成します。

93行目でallocate_worker()を使ってGangWorkerを生成します。96行目でワーカースレッドを生成し、101行目でワーカースレッドの処理を開始します。

93行目のallocate_worker()のソースコードは次のとおりです。

share/vm/utilities/workgroup.cpp

64: GangWorker* WorkGang::allocate_worker(int which) {
65:   GangWorker* new_worker = new GangWorker(this, which);
66:   return new_worker;
67: }

this(自分の所属するAbstractWorkGang)と、ワーカーの識別番号を引数にして、GangWorkerのインスタンスを作っています。

initialize_workers()内のos::start_thread()によって、スレッドの処理は実行されます。GangWorkerThreadを継承したクラスですので、スレッドは処理を開始するrun()メソッドを呼び出します。GangWorkerクラスのrun()を見てみましょう。

share/vm/utilities/workgroup.cpp

222: void GangWorker::run() {

224:   loop();
225: }

run()ではloop()を呼び出しています。ここではGangWorkerがモニタの待合室に入る部分のみに絞って解説したいと思います。

share/vm/utilities/workgroup.cpp

241: void GangWorker::loop() {
243:   Monitor* gang_monitor = gang()->monitor();
247:     {

249:       MutexLocker ml(gang_monitor);

268:       for ( ; /* break or return */; ) {
             /*
              * 省略: タスクがあるかチェック
              *       あれば break でループを抜ける
              */

283:         // ロックを解除して待合室に入る
284:         gang_monitor->wait(/* no_safepoint_check */ true);

             /* 省略: 待合室から出た後の処理 */
300:       }

302:     }

323: }

まず、243行目で自分の所属するAbstractWorkGangのモニタを取得します。249行目でロックを掛けてモニタに入ります。その後、268行目のループのはじめの方でタスクがあるかチェックします。スレッド起動時にはタスクがないことが多いので、このタイミングではたいていが284行目のwait()を呼び出します。

2. タスクの生成

ワーカーの準備ができたら、次に実行させるタスクを生成します。リスト8.1の2.の部分を参照してください。ここではAbstractGangTaskを継承したCMConcurrentMarkingTaskという、G1GCのマーキングタスクを実例として取り上げています。

share/vm/gc_implementation/g1/concurrentMark.cpp

1089: class CMConcurrentMarkingTask: public AbstractGangTask {
1090: private:
1091:   ConcurrentMark*       _cm;
1092:   ConcurrentMarkThread* _cmt;

1094: public:
1095:   void work(int worker_i) {

        /* 省略: マーキング処理 */

1153:   }

1155:   CMConcurrentMarkingTask(ConcurrentMark* cm,
1156:                           ConcurrentMarkThread* cmt) :
1157:       AbstractGangTask("Concurrent Mark"), _cm(cm), _cmt(cmt) { }

1155〜1157行目に定義されているCMConcurrentMarkingTaskのコンストラクタでは、work()を実行するのに必要な変数を引数として受け取るようにしています。work()の引数は決められているので、それぞれのタスク実行に必要な情報はタスクインスタンスのメンバ変数として保持しなければなりません。

1095〜1153行目がCMConcurrentMarkingTaskが実行するタスクの内容です。生成されたそれぞれのGangWorkerはこのwork()を呼び出すことになります。

3. タスクの並列実行

最後にタスクをワーカーに渡します。

リスト8.1の3.の部分ではFlexibleWorkGangrun_task()を呼び出しています。

share/vm/utilities/workgroup.cpp:run_task()前半

129: void WorkGang::run_task(AbstractGangTask* task) {

132:   MutexLockerEx ml(monitor(), Mutex::_no_safepoint_check_flag);

139:   _task = task;
140:   _sequence_number += 1;
141:   _started_workers = 0;
142:   _finished_workers = 0;

タスクを引数に受け取ったrun_task()は、まず132行目でモニタのロックを取ります。その後、139行目でタスク情報を書き込み、140〜142行目でそのほかの情報も更新します。これは図8.2と対応する部分です。

share/vm/utilities/workgroup.cpp:run_task()後半

144:   monitor()->notify_all();

146:   while (finished_workers() < total_workers()) {

152:     monitor()->wait(/* no_safepoint_check */ true);
153:   }
154:   _task = NULL;

160: }

その後、144行目でモニタの待合室にいるワーカーを呼び出します。146〜153行目のwhileループの終了条件は「すべてのワーカーがタスクを終了すること」です。条件に合わない場合、152行目でクライアントはwait()し続けます。この部分は図8.5と対応しています。

それぞれのワーカーはGangWorkerloop()wait()を呼び出し、実行可能なタスクが与えられることを待っていました。もう少しloop()を詳細に見ていきましょう。

share/vm/utilities/workgroup.cpp:loop()前半

241: void GangWorker::loop() {
242:   int previous_sequence_number = 0;
243:   Monitor* gang_monitor = gang()->monitor();
244:   for ( ; /* タスク実行ループ */; ) {
245:     WorkData data;
246:     int part;
247:     {
249:       MutexLocker ml(gang_monitor);

268:       for ( ; /* タスク取得ループ */; ) {

276:         if ((data.task() != NULL) &&
277:             (data.sequence_number() != previous_sequence_number)) {
278:           gang()->internal_note_start();
279:           gang_monitor->notify_all();
280:           part = gang()->started_workers() - 1;
281:           break;
282:         }

284:         gang_monitor->wait(/* no_safepoint_check */ true);
285:         gang()->internal_worker_poll(&data);
300:       }

302:     }

308:     data.task()->work(part);

242行目のprevious_sequence_numberは名前のとおり、以前のタスクの通し番号を記録するローカル変数です。

244行目からのforループが一度回るたびにワーカーは1つのタスク実行をこなします。245行目のWorkDataWorkerGangにあるタスクの情報(掲示板の情報)を記録するローカル変数です。また、246行目のpartはワーカーの順番を記録するローカル変数です。これらはタスク実行ループのスコープに定義されたローカル変数ですので、タスク実行ループが一回終了するたびに破棄されます。

268行目からのforループはWorkerGangからタスクを取得するループです。通常は284行目で待っている状態で止まっていて、notify_all()によって動き出します。動き出すと、285行目のinternal_worker_poll()でローカル変数にタスクの情報をコピーします。情報を取得したら、276,277行目の条件分岐で実行すべきタスクがあるかどうかチェックします。チェックに合格したら、278行目で自分が起動したことをGangWorkerに書きこみ、279行目でnotify_all()して、ワーカーの順番をpartに格納してからループを脱出します。ループを抜けるときに一緒にモニタをアンロックしていることに注意してください。

その後、308行目でタスクのwork()partを引数として呼び出しています。ここで実際にタスクを実行します。

ここまで部分は図8.3と対応しています。

share/vm/utilities/workgroup.cpp:loop()後半

309:     {

314:       // ロック
315:       MutexLocker ml(gang_monitor);
316:       gang()->internal_note_finish();
317:       // 終了したことを伝える
318:       gang_monitor->notify_all();

320:     }
321:     previous_sequence_number = data.sequence_number();
322:   }
323: }

次にタスクの実行が終わると、再度ロックを取って実行完了したことをGangWorkerに書き込みます。その後、notify_all()して、previous_sequence_numberに完了したタスクの通し番号をコピーし、forループの先頭に戻ります。ここまで部分は図8.4と対応しています。

これでワーカーのタスク実行は終了です。すべてのワーカーのタスク実行が完了すると、クライアントはGangWorkerの情報を見て完了を検知し、run_task()の実行が完了します。


御意見・御感想・誤植の指摘などは@nari3もしくはauthorNari/g1gc-impl-book - GitHubまでお願いします。

Webサイトのトップページ

(C) 2011-2012 Narihiro Nakamura