Производитель-потребитель использует только 1 дополнительный семафор - PullRequest
Новая
       86

Производитель-потребитель использует только 1 дополнительный семафор

0 голосов
/ 04 сентября 2018

Решение, традиционное для производителя-потребителя

В операционных системах, как вы видите по ссылке выше для потребителя производителя, используются два семафора full и empty, почему невозможно сделать это, используя только один семафор количества fullEmpty.

Я имею в виду, что у нас есть двоичный семафор mutex и другой семафор fullEmpty, который изначально 0, потому что в буфере нет элементов, поэтому зачем нам нужен 2 семафоры (full, empty)?

Единственное, что нужно изменить - порядок wait и signal, чтобы обновление fullEmpty находилось в критической секции.

Есть мысли или причины?

Ответы [ 2 ]

0 голосов
/ 05 сентября 2018

Это потому, что вам нужно ждать 2 условия: очередь пуста и очередь заполнена. Но классический семафор позволяет вам ждать только одного условия - ждать, пока семафор не станет равным 0.

Вы можете решить эту проблему, используя один объект синхронизации, но такой объект должен быть более функциональным, чем семафор. «Ограниченный семафор» - семафора с максимальным значением должно быть достаточно, поскольку он позволяет блокировать ожидание обоих условий.

Как получить один другой вопрос:

  • Вы можете создать его, используя мьютекс и условную переменную.
  • Семафор окна уже имеет эту функцию.
  • Вы можете использовать futex в Linux (см. FUTEX_WAIT, FUTEX_WAKE) или эквиваленты в других ОС: в FreeBSD использовать _umtx_op (см. UMTX_OP_WAIT , UMTX_OP_WAKE), в Windows 8 и более поздних версиях WaitOnAddress, WakeByAddressSingle / WakeByAddressAll.

Предлагаю вам ознакомиться с интерфейсом futex - с его помощью вы можете создавать более мощные и эффективные объекты синхронизации, чем обычные. Сегодня большинство ОС предоставляют эквивалентный интерфейс, и даже C ++ может представить что-то подобное в будущем (см. std::synchronic<T>).

Несколько заметок:

Linux имеет eventfd, который может действовать как семафор при создании с флагом EFD_SEMAPHORE, но имеет максимальное значение 0xfffffffffffffffe и не может быть изменен. Возможно, когда-нибудь этот системный вызов будет расширен для поддержки максимального значения.

0 голосов
/ 05 сентября 2018

Ключевое утверждение в описании, которое относится к вашему ответу: «У нас есть буфер фиксированного размера.»

Чтобы ответить на ваш вопрос, давайте сначала предположим, что буфер может расширяться, чтобы вместить столько элементов, сколько необходимо, или, другими словами, буфер может увеличиваться до неограниченного размера. В этом случае единственная синхронизация, которая должна произойти между производителями и потребителями (кроме блокировки мьютекса, чтобы гарантировать, что вы не повредите элементы в критической секции), будет гарантировать, что потребители потребляют элементы только после * 1006. * они были произведены производителем. Вы можете решить эту проблему с помощью мьютекса и одного семафора. Вот код, который я позаимствовал и изменил по ссылке, которой вы поделились:

Производитель 

do {
    //produce an item

    wait(mutex);

    //place in buffer

    signal(mutex);
    signal(full);

} while (true);

Потребитель 

do {
    wait(full);
    wait(mutex);

    //remove item from buffer

    signal(mutex);

    //consume item

} while (true);

Как вы можете видеть выше, производитель всегда может добавлять вещи в очередь (кроме случаев, когда удерживается мьютекс), и ему не нужно ждать, пока потребители что-нибудь потребят, потому что буфер никогда не заполнится, даже если если потребители не потребляют предметы. С другой стороны, потребители не могут ничего потреблять, пока производители не произвели товары.

Чтобы ответить на ваш вопрос, вам нужно сосредоточиться на утверждении: «У нас есть буфер фиксированного размера». Это меняет проблему. Поскольку буфер больше не может расти до неограниченного размера, вам нужно заставить производителей ждать, когда буфер заполнится, прежде чем они смогут добавить больше вещей в буфер . Вот почему вам нужен второй семафор. Потребители должны не только ждать производителей, но теперь производители должны ждать потребителей. Вы заставляете производителей ждать потребителей, заставляя их звонить wait на семафор, который только потребители называют signal на

.

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

...