Когда тупиковой произойдет в этом производитель-потребитель кода

Question

Я читал о Producer Consumer проблемы с 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 }             | 
+----------------------------------------------------+-------------------------------------------------------+ 

Затем говорит, что (со ссылкой на номера строк в таблице ниже):

Если потребительский буфер выхлопных газов от 0 до 0 (строка 8), производитель увеличил его до 1 (строка 11 таблицы), до проверки потребителем n и ожидания на линии 14. Строка 14 должна была блокировать потребителя, поскольку буфер был исчерпан, но этого не произошло, так как продюсер увеличил n тем временем. Хуже, потребитель может сразу же запустить снова, чтобы потреблять не существует пункт, чтобы уменьшить п -1 (строка 20)

Тогда он говорит:

Мы не можем переместить условный оператор внутри критический раздел, поскольку это может привести к тупиковой ситуации (например, после строки 8 таблицы выше).

Он по-прежнему предлагает различные решения.

Но я не могу понять, как это приведет к тупику. Учитывая следующий измененный код потребителя:

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 } 

я придумал следующее:

Как вы можете видеть, в конце концов, значение ого, п и задержки сбрасываются на те, перед запуском. Итак, как это может привести к тупиковой ситуации? (На самом деле я считаю, что это может быть точным решением.)

Answer 1

Это, безусловно, приведет к тупику. Рассмотрим последовательность операций:

Производитель успешно производит 1 предмет. Это приводит к следующим значениям sempaphores:

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. Это тупик