2
$\begingroup$

I was reading about Producer Consumer problem from Operating Systems by William Stallings where following code was given:

+----------------------------------------------------+-------------------------------------------------------+
|               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  }                                                 |
+----------------------------------------------------+-------------------------------------------------------+

It then says that (referring to the line numbers in table below):

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)

enter image description here

Then it says:

We cannot move the conditional statement inside the critical section as this could lead to deadlock (e.g. after line 8 of above table).

It continues to give different solution.

But I am not able to understand how it will lead to the deadlock. Considering following modified consumer code:

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  }

I came up with following:

enter image description here

As you can see, at the end, the values of mx, n and delay are reset to the ones before start. So how this could lead to deadlock? (In fact I feel this could be precise solution.)

$\endgroup$
2
$\begingroup$

It will be caused as follows:

enter image description here

Both processes blocked at the end, hence deadlocked.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.