Think Stitch
  最近の更新


ワークスチール

ワークスチール型のスレッドプールのモデルを作って,終了する部分を Pthread Model Checker で検査してみます.

グラフや木の探索を複数のワーカスレッドで並列に行うことを考えます.各ワーカはキューを持っていて,調べる必要のあるノードが入っているとします.各ワーカはおおまかに次のことを繰り返します:

わかりやすく(だといいんですが)するために少しラフな説明にしました.

ワーカはノードをキューに入れるとき (*) ,寝ているワーカを起こすようにします.こうすると,調べるべきノードがたくさんあるときは全員フル稼働で,そうでないときは何人か休んでいるという感じになります.

もし1人を除いて全員が wait していて,最後の1人も wait しようとした場合は,すべて調べつくして発見できなかったということですから,やはりフラグを立てて全員を起こし,順次終了します.

0  モデル

いつものように wait 状態にあるワーカスレッドを数えるために count を用意します.それから完了フラグ b_done を用意します.

探索しているグラフや木の形状が具体的にどうなっているかとか,探しているものはあるのかないのか,あるならどこにあるのかといったことは抽象化してしまって,そういった選択肢をすべて非決定的選択で表します.

選択肢は4つあります.

#define N 4

pthread_t pth[N];
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
int8_t count;
int8_t b_done;

void *worker(void *arg)
{
    while (true) {
        AMB {
            pthread_cond_signal(&cv);           // *A
        } OR AMB {
            if (b_done) {                       // *B
                break;
            }
        } OR AMB {
            pthread_mutex_lock(&m);             // *C
            b_done = 1;
            pthread_cond_broadcast(&cv);
            pthread_mutex_unlock(&m);
            break;
        } OR {
            pthread_mutex_lock(&m);             // *D
            if (b_done) {
                pthread_mutex_unlock(&m);
                break;
            } else {
                count++;
                if (count == N) {
                    b_done = 1;
                    pthread_cond_broadcast(&cv);
                    pthread_mutex_unlock(&m);
                    break;
                } else {
                    pthread_cond_wait(&cv, &m);
                    if (b_done) {
                        pthread_mutex_unlock(&m);
                        break;
                    } else {
                        count--;
                        pthread_mutex_unlock(&m);
                    }
                }
            }
        }
    }
    return NULL;
}

int main(void)
{
    for (int i = 0; i < N; ++i) {
        pthread_create(&pth[i], NULL, &worker, NULL);
    }
    for (int i = 0; i < N; ++i) {
        pthread_join(pth[i], NULL);
    }
    return 0;
}

A はノードを調べたけれど探しているものではなく,枝をたどって他のノードをキューに入れたときで,かつ十分なノードが溜まったので他のスレッドを起こしているところです.

B は仕事の合間に終了フラグを調べています.フラグが立っていたら終了します.

C は探しているものを見つけた場合です.ロックをかけてフラグを立て,寝ているワーカを起こし,自分は終了します.

D は自分のキューが空になったので他のワーカのキューから盗もうとしたけどできなくて wait しようとする場合です.

  1. wait する前に終了フラグをチェックして,立っていれば終了します.
  2. そうでなければ count をインクリメントします.
  3. 最後のワーカだった場合は終了します.
  4. 最後でなければ wait します.
  5. 起こされたらまずフラグをチェックして,立っていれば終了します.
  6. そうでなければ自分の分のカウントを減らし,仕事に戻ります.

検査をしてみると問題ないことがわかります.

pthread_cond_wait は裸ですけど,起きてきてからキューをチェックするので問題ありません.spurious wakeups オプションをつけても問題ありません.

1  終了フラグ

マルチスレッドを確実に終了させるのは難しいと思うことがよくあります.たまに1個だけ残っちゃったりするからです.どうしてそんなことが起こるのか,ちょっと例を見てみましょう.

今回使った終了フラグは1度 ON になるだけで,二度と OFF になることはありません.こういうフラグはロックをかけなくてもいいという誤った認識が若い頃の自分にはありました.それは正しいでしょうか?

(メモリモデルの話ではありません).

1.0  修正モデル その 1

終了フラグを立てている (*C) の部分からロックを取り除いてみます.するとデッドロックが見つかります.レポートのサマリは次のとおりです:

#14 pth[0] lock m
#16 pth[0] load b_done          (1)
#24 pth[0] load count
#26 pth[1] store b_done         (2)
    b_done = 1
#28 pth[0] store count
#29 pth[3] store b_done
#30 pth[0] load count
#31 pth[3] broadcast cv
#33 pth[3] exit
#35 pth[2] store b_done
#37 pth[2] broadcast cv
#38 pth[1] broadcast cv
#39 pth[0] wait cv m            (3)
#41 pth[2] exit
#42 pth[1] exit

フラグを立てているのはスレッド 1 で (2) のところです.ところがその前にスレッド 0 がロックをかけて,終了フラグが立っていないことを確認してしまっています (1).結果としてスレッド 0 は (3) で wait に入り,他のスレッドは皆終了して取り残されてしまいました.

ロックは必要ですね.

1.1  修正モデル その 2

逆にフラグをチェックしているところはどうでしょうか.(*D) のところをロックの外に出してみます.そうするとやはりデッドロックします.

#20 pth[2] lock m
#21 pth[0] load b_done        (1)
#26 pth[2] store b_done
    b_done = 1
#28 pth[2] broadcast cv
#30 pth[2] unlock m
#31 pth[1] load b_done
#32 pth[0] lock m
#34 pth[0] load count
#36 pth[0] store count
#38 pth[0] load count
#39 pth[3] load b_done
#41 pth[2] exit
#44 pth[3] exit
#45 pth[1] exit
#46 pth[0] wait cv m

スレッド 2 がきちんとロックをしてから終了フラグを立てようとしているのに,スレッド 0 はその隙間にフラグを検査してそのまま wait まっしぐらです.

やはりロックは必要なんですね.

2017/10/11

© 2013-2017 PRINCIPIA Limited