Гибридное решение алгоритма потребительского производителя

Question

Я пытаюсь показать, что следующее решение проблемы производителя / потребителя не работает, показывая, что, когда потребитель находится в начале M1, есть случай, когда он не сможет удалить из очереди конечный элемент время и / или есть случай, когда производитель находится в начале L2, и он не сможет поставить в очередь элемент в течение конечного времени. Я просто не могу найти ни одного примера, чтобы доказать это.

Алгоритм предполагает наличие 10 производителей, 10 потребителей и размер буфера 10.

nf = 0; // counting semaphore, # of items in queue
bm = 1; // binary semaphore, ensures mutex

Режиссер

L1: Produce(item);
L2: P(bm);
If (queue_is_full) {
  V(bm);
  GoTo L2;
} else {
  Enqueue(item);
  V(bm);
  V(nf);
  GoTo L1;
}

потребитель

M1: P(nf);
P(bm);
Dequeue(item);
V(bm);
Consume(item);
GoTo M1;

Answer 1

Если мое понимание верно, P(x) блокируется до x!= 0 и v(x) всегда делает x++.

В коде выше M1: P(nf); пропустит потребителя, только если элемент доступен в очереди. Затем он всегда получает и снимает блокировку на bm. Так что я уверен, что код не может зайти в тупик с другими потребителями или производителями.

В продюсере он приобретает БМ, а затем работает в списке. Он не получает никакой другой блокировки до v (bm) и выполняет v (bm) в обеих ветвях, поэтому это гарантированно произойдет. Поскольку v (bm) в конечном итоге произойдет, потребитель может в конечном итоге потребить предмет. Таким образом, после того, как v (bm) av (nf) гарантировано, когда один элемент произведен, один потребитель будет пытаться в конечном итоге потреблять его.

Поэтому код выглядит хорошо, если нет чего-то глупого, например listcapacity == 0.

были бы проблемы, если бы потребитель сделал P(bm)-> P(nf)-> V(bm), но приведенный выше код выглядит хорошо