Think Stitch
  最近の更新


生産者・消費者問題 2

今回も Pthread Model Checker を使って生産者・消費者問題を調べます.

0  条件変数の共有

生産者・消費者問題では条件変数を2つ使いますよね. 1つは生産者が待つためのもの,もう1つは消費者が待つためのものです.これを1つにまとめてしまったらどうなるのか,というのが今回の問題です.

変更した部分だけ示します.

void *producer(void *arg)
{
    while (true) {
        pthread_mutex_lock(&mutex);
        while (count == N) {
            pthread_cond_wait(&cv, &mutex);     // *A
        }
        count++;
        pthread_cond_signal(&cv);               // *B
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

void *consumer(void *arg)
{
    while (true) {
        pthread_mutex_lock(&mutex);
        while (count == 0) {
            pthread_cond_wait(&cv, &mutex);     // *C
        }
        count--;
        pthread_cond_signal(&cv);               // *D
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

1  検査

バッファ長および生産者,消費者の数をいくつか変えて検査してみると,デッドロックが起こる組み合わせがあります.起こらない組み合わせもあります.デッドロックが起こるできるだけ小さい値の組み合わせを探して,バッファ長1, 生産者1, 消費者2を見つけました.値が小さい方が分析しやすいからです.

------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 1
------------------------
#1 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 2
    i = 0
------------------------
#2 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 3
    i = 0
------------------------
#3 main create pthp[0]
58: pthread_create(&pthp[i], NULL, &producer, (void *)(intptr_t)i);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 5
    i = 0
1 pthp[0] 28
    arg = 0
------------------------
#4 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 2
    i = 1
1 pthp[0] 28
    arg = 0
------------------------
#5 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 4
1 pthp[0] 28
    arg = 0
------------------------
#6 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 6
    i = 0
1 pthp[0] 28
    arg = 0
------------------------
#7 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 7
    i = 0
1 pthp[0] 28
    arg = 0
------------------------
#8 main create pthc[0]
62: pthread_create(&pthc[i], NULL, &consumer, (void *)(intptr_t)i);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 0
1 pthp[0] 28
    arg = 0
2 pthc[0] 18
    arg = 0
------------------------
#9 pthc[0] tau
38: while (true) {
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 0
1 pthp[0] 28
    arg = 0
2 pthc[0] 19
------------------------
#10 pthc[0] lock mutex
39: pthread_mutex_lock(&mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 0
1 pthp[0] 28
    arg = 0
2 pthc[0] 20
------------------------
#11 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 6
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 20
------------------------
#12 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 7
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 20
------------------------
#13 pthc[0] load count
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 7
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 21
    t14 = 0
------------------------
#14 main create pthc[1]
62: pthread_create(&pthc[i], NULL, &consumer, (void *)(intptr_t)i);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 21
    t14 = 0
3 pthc[1] 18
    arg = 1
------------------------
#15 pthc[0] tau
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 22
3 pthc[1] 18
    arg = 1
------------------------
#16 pthc[1] tau
38: while (true) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 22
3 pthc[1] 19
------------------------
#17 pthc[0] wait cv mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 24 wait cv
3 pthc[1] 19
------------------------
#18 pthc[1] lock mutex
39: pthread_mutex_lock(&mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 24 wait cv
3 pthc[1] 20
------------------------
#19 pthc[1] load count
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 24 wait cv
3 pthc[1] 21
    t14 = 0
------------------------
#20 pthc[1] tau
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 28
    arg = 0
2 pthc[0] 24 wait cv
3 pthc[1] 22
------------------------
#21 pthp[0] tau
20: while (true) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 29
2 pthc[0] 24 wait cv
3 pthc[1] 22
------------------------
#22 pthc[1] wait cv mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 29
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#23 pthp[0] lock mutex
21: pthread_mutex_lock(&mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 30
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#24 pthp[0] load count
22: while (count == N) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 31
    t16 = 0
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#25 pthp[0] tau
22: while (count == N) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 33
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#26 pthp[0] load count
27: count++;
------------------------
global vars:
    count = 0
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 35
    t17 = 0
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#27 pthp[0] store count
27: count++;
------------------------
global vars:
    count = 1
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 36
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
#28 pthp[0] signal cv
29: pthread_cond_signal(&cv);
------------------------
global vars:
    count = 1
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 37
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#29 pthp[0] unlock mutex
30: pthread_mutex_unlock(&mutex);
------------------------
global vars:
    count = 1
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 29
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#30 pthp[0] lock mutex
21: pthread_mutex_lock(&mutex);
------------------------
global vars:
    count = 1
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 30
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#31 pthp[0] load count
22: while (count == N) {
------------------------
global vars:
    count = 1
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 31
    t16 = 1
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#32 pthp[0] tau
22: while (count == N) {
------------------------
global vars:
    count = 1
mutex:
    mutex pthp[0]
thread:
0 main 9
    i = 1
1 pthp[0] 32
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#33 pthp[0] wait cv mutex
24: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 1
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#34 pthc[1] lock mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 1
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 20
------------------------
#35 pthc[1] load count
40: while (count == 0) {
------------------------
global vars:
    count = 1
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 21
    t14 = 1
------------------------
#36 pthc[1] tau
40: while (count == 0) {
------------------------
global vars:
    count = 1
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 23
------------------------
#37 pthc[1] load count
45: count--;
------------------------
global vars:
    count = 1
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 25
    t15 = 1
------------------------
#38 pthc[1] store count
45: count--;
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 26
------------------------
#39 pthc[1] signal cv
47: pthread_cond_signal(&cv);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 27
------------------------
#40 pthc[1] unlock mutex
48: pthread_mutex_unlock(&mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 19
------------------------
#41 pthc[1] lock mutex
39: pthread_mutex_lock(&mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 20
------------------------
#42 pthc[1] load count
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 21
    t14 = 0
------------------------
#43 pthc[1] tau
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[1]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 22
------------------------
#44 pthc[1] wait cv mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 24 wait cv
------------------------
#45 pthc[0] lock mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 20
3 pthc[1] 24 wait cv
------------------------
#46 pthc[0] load count
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 9
    i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 21
    t14 = 0
3 pthc[1] 24 wait cv
------------------------
#47 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 6
    i = 2
1 pthp[0] 34 wait cv
2 pthc[0] 21
    t14 = 0
3 pthc[1] 24 wait cv
------------------------
#48 main tau
61: for (i = 0; i < NC; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 8
1 pthp[0] 34 wait cv
2 pthc[0] 21
    t14 = 0
3 pthc[1] 24 wait cv
------------------------
#49 main tau
65: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 10
    i = 0
1 pthp[0] 34 wait cv
2 pthc[0] 21
    t14 = 0
3 pthc[1] 24 wait cv
------------------------
#50 main tau
65: for (i = 0; i < NP; ++i) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 11
    i = 0
1 pthp[0] 34 wait cv
2 pthc[0] 21
    t14 = 0
3 pthc[1] 24 wait cv
------------------------
#51 pthc[0] tau
40: while (count == 0) {
------------------------
global vars:
    count = 0
mutex:
    mutex pthc[0]
thread:
0 main 11
    i = 0
1 pthp[0] 34 wait cv
2 pthc[0] 22
3 pthc[1] 24 wait cv
------------------------
#52 pthc[0] wait cv mutex
42: pthread_cond_wait(&cv, &mutex);
------------------------
global vars:
    count = 0
mutex:
    mutex <unlocked>
thread:
0 main 11
    i = 0
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------

前回と同じようにサマリーを作りました.

#10 pthc[0] lock mutex
#13 pthc[0] load count
#17 pthc[0] wait cv mutex       (1)

#18 pthc[1] lock mutex
#19 pthc[1] load count
#22 pthc[1] wait cv mutex       (2)

#23 pthp[0] lock mutex
#26 pthp[0] load count
#27 pthp[0] store count
    count = 1
    3 pthc[1] 24 wait cv
#28 pthp[0] signal cv           (3)
    3 pthc[1] 24
#29 pthp[0] unlock mutex
#30 pthp[0] lock mutex
#31 pthp[0] load count
#33 pthp[0] wait cv mutex       (4)

#34 pthc[1] lock mutex
#37 pthc[1] load count
#38 pthc[1] store count
    count = 0
    2 pthc[0] 24 wait cv
#39 pthc[1] signal cv           (5)
    2 pthc[0] 24
#40 pthc[1] unlock mutex
#41 pthc[1] lock mutex
#42 pthc[1] load count
#44 pthc[1] wait cv mutex       (6)

#45 pthc[0] lock mutex
#46 pthc[0] load count
#52 pthc[0] wait cv mutex       (7)
    1 pthp[0] 34 wait cv
    2 pthc[0] 24 wait cv
    3 pthc[1] 24 wait cv
  1. 最初バッファは空なので消費者 pthc[0] が待ちに入ります.
  2. 消費者 pthc[1] も待ちに入ります.
  3. 生産者がデータを1個置いて,消費者 pthc[1] を起こします.
  4. 生産者はそのまま動きますが,バッファがいっぱいなので待ちに入ります.
  5. 起こされた消費者 pthc[1] はデータを取り出して signal を発行します.これは生産者ではなくもう1つの消費者 pthc[0] を起こしています.
  6. 消費者 pthc[1] はそのままバッファが空であることを見出して待ちに入ります.
  7. 消費者 pthc[0] は起きてきますが,バッファは空なので待ちに入ります.

これを見て少し考えるとデッドロックが起こる十分条件の1つがわかります.バッファの長さを N, 消費者の数を NC とすると,2 * N <= NC のときにはデッドロックが起こります.そのシナリオは次のとおりです:

  1. バッファが空なのですべての消費者が wait
  2. 生産者がバッファフルまでデータを格納し,その際に発行する signal で N 個の消費者が起きる.その後生産者はすべて wait
  3. 起きた N 個の消費者がそれぞれデータを消費し,その際に発行する signal がすべて消費者を起こす.消費者は 2 * N 以上いるので,N 個以上が wait しているからこれが可能.起こした方の消費者はすべて wait
  4. 起こされた N 個の消費者はバッファが空なのですべて wait

バッファ長を大きくすると,消費者以外に生産者もかならず起こされるようになるのでデッドロックは消えます.他にも pthread_cond_signalpthread_cond_broadcast に替えるという方法があります.そうすると無駄に起こされるスレッドは増えますが,デッドロックは消えます.確かめてみてください.

上の条件以外でデッドロックはないのかというと実はあります.調べてみてはいかがでしょうか.そして一般的な条件がわかったら教えてください :P

2017/10/10

© 2013-2017 PRINCIPIA Limited