Какой самый быстрый метод без гонки для опроса очереди без блокировки?

Question

Скажем, у нас есть очередь без блокировки с одним потоком-производителем и без блокировки с потоком-потребителем, и что производитель может работать долго, не производя никаких данных.Было бы полезно оставить потребительский поток спящим, когда в очереди ничего нет (для экономии энергии и освобождения ЦП для других процессов / потоков).Если очередь не была без блокировки, простой способ решить эту проблему - заставить производящий поток блокировать мьютекс, выполнять свою работу, сигнализировать переменную условия и разблокировать, а поток чтения должен заблокировать мьютекс, подождать переменную условияПрочти, затем разблокируй.Но если мы используем очередь без блокировки, то использование мьютекса точно таким же образом уменьшит производительность, которую мы получаем в первую очередь от использования очереди без блокировки.

Наивное решение - иметь производителя после каждой вставкив очередь блокирует мьютекс, сигнализирует переменную условия, затем разблокирует мьютекс, сохраняя фактическую работу (вставку в очередь) полностью за пределами блокировки, и чтобы потребитель делал то же самое, блокируя мьютекс, ожидая условияпеременная, разблокируя ее, вытаскивая все из очереди, затем повторяя, сохраняя чтение очереди за пределами блокировки.Однако здесь есть условие гонки: между читателем, срывающим очередь и засыпающим, продюсер мог вставить элемент в очередь.Теперь читатель перейдет в спящий режим и может оставаться так до бесконечности, пока производитель не вставит другой элемент и снова не сообщит переменную условия.Это означает, что вы можете иногда сталкиваться с определенными предметами, которые, по-видимому, занимают очень много времени, чтобы пройти через очередь.Если ваша очередь всегда постоянно активна, это не может быть проблемой, но если бы она всегда была активной, вы, вероятно, могли бы полностью забыть переменную условия.

AFAICT, решение для производителя - вести себя так же, как если бы это былоработа с обычной очередью блокировки потребностей.Он должен блокировать мьютекс, вставлять в очередь без блокировки, сигнализировать переменную условия, разблокировать.Однако потребитель должен вести себя по-другому.Когда он проснется, он должен немедленно разблокировать мьютекс, а не ждать, пока он прочитает очередь.Затем он должен вытянуть как можно большую часть очереди и обработать ее.Наконец, только когда потребитель думает о том, чтобы идти спать, он должен заблокировать мьютекс, проверить, есть ли какие-либо данные, затем, если это так, разблокировать и обработать их, или, если нет, то подождать переменную условия.Таким образом, мьютекс утверждается реже, чем в случае блокировки очереди, но нет риска засыпать с данными, оставшимися в очереди.

Это лучший способ сделать это?Есть ли альтернативы?

Примечание : под «быстрым» я действительно подразумеваю «самый быстрый», не выделяя ядра для проверки очереди снова и снова », но это не вписывается в название;p

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

Answer 1

Я предполагаю, что вы используете свободную от единственного производителя очередь без блокировки из статьи Dr Dobbs - или что-то подобное - поэтому я буду использовать терминологию оттуда.

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

• У потребителя - как вы говорите, когда потребитель исчерпал очередь и рассматривает вопрос о сне (и только потом), он блокирует мьютекс, снова проверяет очередь, а затем либо
  • освобождает мьютекс и продолжает работать, если в очереди появился новый элемент
  • или блокирует переменную условия (освобождая мьютекс, когда он пробуждается, чтобы найти непустую очередь, естественно).
• у производителя:
  • Сначала возьмите копию last, назовите ее saved_last
  • Добавьте элемент new_item как обычно, затем возьмите копию указателя divider, назовите его saved_divider.
  • Если значение saved_divider равно new_item, объект, который вы только что вставили, тогда ваш объект уже израсходован, и ваша работа выполнена.
  • В противном случае, если значение saved_divider не равно saved_last, вам не нужно будить потребителя. Это потому что:
    • В момент, когда вы строго добавили новый объект, вы знаете, что divider еще не достиг ни new_item, ни saved_last
    • Поскольку вы начали вставку, last имеет только эти два значения
    • Потребитель останавливается только тогда, когда divider равно last
    • Следовательно, потребитель все еще не спит и достигнет вашего нового предмета перед сном.
  • В противном случае заблокируйте мьютекс, подайте сигнал condvar, затем отпустите мьютекс. (Получение мьютекса гарантирует, что вы не дадите сигнал кондару за время между потребителем, заметившим, что очередь пуста, и фактически блокирующим кондвар.)

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

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

Конечно, стоит ли это делать на самом деле, зависит от многих вещей, и я бы посоветовал вам измерить, насколько важна для вас производительность. Хорошие реализации примитивов mutex / condvar внутренне используют атомарные операции для большинства случаев, поэтому они, как правило, делают вызов ядра (самый дорогой бит!), Если есть необходимость - то есть, если есть необходимость блокировать, или определенно есть ожидание потоков - поэтому время, сэкономленное за счет отсутствия вызова функций мьютекса, может составлять только издержки библиотечных вызовов.