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

Question

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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