这个生产者消费者代码什么时候会出现死锁
When will deadlock occur in this producer-consumer code
我正在阅读 Operating Systems by William Stallings 中的生产者消费者问题,其中给出了以下代码:
+----------------------------------------------------+-------------------------------------------------------+
| Producer | Consumer |
+------------------------------------------------------------------------------------------------------------+
| 1 int n; | 1 void consumer() |
| 2 binary_semaphore mx = 1, delay = 0; | 2 { semWaitB(delay); //wait till first data item |
| 3 void producer() | 3 //is produced |
| 4 { | 4 while (true) |
| 5 while (true) | 5 { |
| 6 { | 6 semWaitB(mx); //continue if producer is not |
| 7 produce(); | 7 //producing |
| 8 semWaitB(mx); //continue if consumer | 8 take(); |
| 9 //is not consuming | 9 n--; |
| 10 append(); | 10 semSignalB(mx);//signal done with consuming |
| 11 n++; | 11 consume(); |
| 12 if (n==1) semSignalB(delay); //unblocks | 12 if (n==0) semWaitB(delay); //block self if |
| 13 //consumer | 13 //no data item |
| 14 semSignalB(mx); //signal done with | 14 } |
| 15 //producing | 15 } |
| 16 } | 16 void main() |
| 17 } | 17 { n = 0; |
| | 18 parbegin (producer, consumer); |
| | 19 } |
+----------------------------------------------------+-------------------------------------------------------+
然后说(参考下面table中的行号):
If consumer exhaust buffer setting n to 0 (line 8), producer has incremented it to 1 (line 11 of table), before consumer checking n and waiting on line 14. Line 14 should have blocked consumer since buffer was exhausted, but it did not, since producer incremented n meanwhile. Worst, consumer can immediately run again to consume non existent item to reduce n to -1 (line 20)
然后它说:
We cannot move the conditional statement inside the critical section as this could lead to deadlock (e.g. after line 8 of above table).
它继续给出不同的解决方案。
但我无法理解它会如何导致僵局。考虑以下修改后的消费者代码:
1 void consumer()
2 { semWaitB(delay); //wait till first data item
3 //is produced
4 while (true)
5 {
6 semWaitB(mx); //continue if producer is not
7 //producing
8 take();
9 n--;
10 if (n==0) semWaitB(delay); //block self if
11 //no data item
12 semSignalB(mx);//signal done with consuming
13 consume();
14 }
15 }
16 void main()
17 { n = 0;
18 parbegin (producer, consumer);
19 }
我得出以下结论:
可以看到,在最后,mx、n和delay的值被重置为start之前的值。那么这怎么会导致僵局呢? (事实上我觉得这可能是精确的解决方案。)
肯定会死锁。考虑操作顺序:
生产者成功生产了1件商品。这导致信号量的以下值:
mx = 1 and delay = 1
现在消费者执行它的代码并到达第 10 行
if (n==0) semWaitB(delay);
因为 delay
设置为 0
因为消费者的第 2 行
semWaitB(delay);
第 10 行将阻塞消费者,此时我们有 mx = 0
因为第 6 行消费者 semWaitB(mx);
由于第 8 行 semWaitB(mx);
为 mx = 0
,消费者已经被阻塞,生产者将被阻塞。 这是一个死锁
我正在阅读 Operating Systems by William Stallings 中的生产者消费者问题,其中给出了以下代码:
+----------------------------------------------------+-------------------------------------------------------+
| Producer | Consumer |
+------------------------------------------------------------------------------------------------------------+
| 1 int n; | 1 void consumer() |
| 2 binary_semaphore mx = 1, delay = 0; | 2 { semWaitB(delay); //wait till first data item |
| 3 void producer() | 3 //is produced |
| 4 { | 4 while (true) |
| 5 while (true) | 5 { |
| 6 { | 6 semWaitB(mx); //continue if producer is not |
| 7 produce(); | 7 //producing |
| 8 semWaitB(mx); //continue if consumer | 8 take(); |
| 9 //is not consuming | 9 n--; |
| 10 append(); | 10 semSignalB(mx);//signal done with consuming |
| 11 n++; | 11 consume(); |
| 12 if (n==1) semSignalB(delay); //unblocks | 12 if (n==0) semWaitB(delay); //block self if |
| 13 //consumer | 13 //no data item |
| 14 semSignalB(mx); //signal done with | 14 } |
| 15 //producing | 15 } |
| 16 } | 16 void main() |
| 17 } | 17 { n = 0; |
| | 18 parbegin (producer, consumer); |
| | 19 } |
+----------------------------------------------------+-------------------------------------------------------+
然后说(参考下面table中的行号):
If consumer exhaust buffer setting n to 0 (line 8), producer has incremented it to 1 (line 11 of table), before consumer checking n and waiting on line 14. Line 14 should have blocked consumer since buffer was exhausted, but it did not, since producer incremented n meanwhile. Worst, consumer can immediately run again to consume non existent item to reduce n to -1 (line 20)
然后它说:
We cannot move the conditional statement inside the critical section as this could lead to deadlock (e.g. after line 8 of above table).
它继续给出不同的解决方案。
但我无法理解它会如何导致僵局。考虑以下修改后的消费者代码:
1 void consumer()
2 { semWaitB(delay); //wait till first data item
3 //is produced
4 while (true)
5 {
6 semWaitB(mx); //continue if producer is not
7 //producing
8 take();
9 n--;
10 if (n==0) semWaitB(delay); //block self if
11 //no data item
12 semSignalB(mx);//signal done with consuming
13 consume();
14 }
15 }
16 void main()
17 { n = 0;
18 parbegin (producer, consumer);
19 }
我得出以下结论:
可以看到,在最后,mx、n和delay的值被重置为start之前的值。那么这怎么会导致僵局呢? (事实上我觉得这可能是精确的解决方案。)
肯定会死锁。考虑操作顺序:
生产者成功生产了1件商品。这导致信号量的以下值:
mx = 1 and delay = 1
现在消费者执行它的代码并到达第 10 行
if (n==0) semWaitB(delay);
因为 delay
设置为 0
因为消费者的第 2 行
semWaitB(delay);
第 10 行将阻塞消费者,此时我们有 mx = 0
因为第 6 行消费者 semWaitB(mx);
由于第 8 行 semWaitB(mx);
为 mx = 0
,消费者已经被阻塞,生产者将被阻塞。 这是一个死锁