﻿ 生産者・消費者問題 2 - Think Stitch - PRINCIPIA
Think Stitch
﻿

0  条件変数の共有

```void *producer(void *arg)
{
while (true) {
while (count == N) {
}
count++;
}
return NULL;
}

void *consumer(void *arg)
{
while (true) {
while (count == 0) {
}
count--;
}
return NULL;
}
```

1  検査

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

```------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
0 main 1
------------------------
#1 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
0 main 2
i = 0
------------------------
#2 main tau
57: for (i = 0; i < NP; ++i) {
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
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>
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>
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>
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>
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>
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>
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>
0 main 9
i = 0
1 pthp[0] 28
arg = 0
2 pthc[0] 19
------------------------
#10 pthc[0] lock mutex
------------------------
global vars:
count = 0
mutex:
mutex pthc[0]
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]
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]
0 main 7
i = 1
1 pthp[0] 28
arg = 0
2 pthc[0] 20
------------------------
40: while (count == 0) {
------------------------
global vars:
count = 0
mutex:
mutex pthc[0]
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]
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]
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]
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
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
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
------------------------
global vars:
count = 0
mutex:
mutex pthc[1]
0 main 9
i = 1
1 pthp[0] 28
arg = 0
2 pthc[0] 24 wait cv
3 pthc[1] 20
------------------------
40: while (count == 0) {
------------------------
global vars:
count = 0
mutex:
mutex pthc[1]
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]
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]
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
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
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
------------------------
global vars:
count = 0
mutex:
mutex pthp[0]
0 main 9
i = 1
1 pthp[0] 30
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
22: while (count == N) {
------------------------
global vars:
count = 0
mutex:
mutex pthp[0]
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]
0 main 9
i = 1
1 pthp[0] 33
2 pthc[0] 24 wait cv
3 pthc[1] 24 wait cv
------------------------
27: count++;
------------------------
global vars:
count = 0
mutex:
mutex pthp[0]
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]
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
------------------------
global vars:
count = 1
mutex:
mutex pthp[0]
0 main 9
i = 1
1 pthp[0] 37
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#29 pthp[0] unlock mutex
------------------------
global vars:
count = 1
mutex:
mutex <unlocked>
0 main 9
i = 1
1 pthp[0] 29
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
#30 pthp[0] lock mutex
------------------------
global vars:
count = 1
mutex:
mutex pthp[0]
0 main 9
i = 1
1 pthp[0] 30
2 pthc[0] 24 wait cv
3 pthc[1] 24
------------------------
22: while (count == N) {
------------------------
global vars:
count = 1
mutex:
mutex pthp[0]
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]
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
------------------------
global vars:
count = 1
mutex:
mutex <unlocked>
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
------------------------
global vars:
count = 1
mutex:
mutex pthc[1]
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 20
------------------------
40: while (count == 0) {
------------------------
global vars:
count = 1
mutex:
mutex pthc[1]
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]
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24 wait cv
3 pthc[1] 23
------------------------
45: count--;
------------------------
global vars:
count = 1
mutex:
mutex pthc[1]
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]
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
------------------------
global vars:
count = 0
mutex:
mutex pthc[1]
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 27
------------------------
#40 pthc[1] unlock mutex
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 19
------------------------
#41 pthc[1] lock mutex
------------------------
global vars:
count = 0
mutex:
mutex pthc[1]
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 24
3 pthc[1] 20
------------------------
40: while (count == 0) {
------------------------
global vars:
count = 0
mutex:
mutex pthc[1]
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]
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
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
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
------------------------
global vars:
count = 0
mutex:
mutex pthc[0]
0 main 9
i = 1
1 pthp[0] 34 wait cv
2 pthc[0] 20
3 pthc[1] 24 wait cv
------------------------
40: while (count == 0) {
------------------------
global vars:
count = 0
mutex:
mutex pthc[0]
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]
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]
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]
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]
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]
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
------------------------
global vars:
count = 0
mutex:
mutex <unlocked>
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
#17 pthc[0] wait cv mutex       (1)

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

#23 pthp[0] lock mutex
#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
#33 pthp[0] wait cv mutex       (4)

#34 pthc[1] lock mutex
#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
#44 pthc[1] wait cv mutex       (6)

#45 pthc[0] lock mutex
#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