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

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

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

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

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

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

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


multithreading queue mutex condition-variable lockless
person Joseph Garvin    schedule 21.11.2010    source источник
comment
Разве вы не можете сделать так, чтобы производитель сигнализировал переменную условия каждый раз, когда он что-то производит? Зачем нужен мьютекс?   -  person Gabe    schedule 21.11.2010
comment
@Gabe: Две причины. Во-первых, в этом случае, потому что производитель может что-то создать и подать сигнал в промежутке между моментом, когда потребитель заканчивает обработку элемента, и моментом, когда он решает подождать с переменной условия. Затем потребитель перейдет в спящий режим, а элемент, созданный производителем, застрянет в очереди до следующего запуска сигнала. Во-вторых, потому что, по крайней мере, в API pthreads вы не можете использовать условные переменные без мьютексов. На самом деле вам нужно передать мьютекс функции ожидания. Я не знаю, действительно ли они требуются для всех реализаций условных переменных.   -  person Joseph Garvin    schedule 21.11.2010
comment
@Gabe: одно заблуждение, которое может привести вас к мысли, что если сигнал срабатывает, когда ничего не ожидает в условной переменной, то в следующий раз, когда что-то ожидает в условной переменной, оно будет немедленно разбужено, но это не так. т дело. Если вы не ждете переменной условия, когда срабатывает сигнал, насколько вы знаете, этого никогда не происходило. В этом смысле ожидание условной переменной отличается от использования опроса/выбора в файле/сокете/канале.   -  person Joseph Garvin    schedule 21.11.2010
comment
Извините, я думал, что ваш вопрос был более общим. Вы должны отредактировать вопрос, указав, что вы используете pthreads.   -  person Gabe    schedule 21.11.2010
comment
@Gabe: он должен быть универсальным, я просто не могу проверить каждый API потоковой передачи для каждой ОС. Однако я достаточно уверен, что почти все API требуют использования мьютекса с условной переменной. Это также верно для потокового API boost и потоков win32. Я думаю, что вы удерживаете блокировку, когда просыпаетесь от условной переменной, является частью их определения, что означает, что должен быть задействован мьютекс.   -  person Joseph Garvin    schedule 21.11.2010
comment
Какая ОС? думаю есть решение под винду.   -  person    schedule 18.01.2011
comment
Я помню, что Windows 7 разрешает потоки на уровне пользователя, которые вы можете контролировать в своей программе - например, приостановить. Вы можете очень легко написать мьютекс без блокировки, проблема не в мьютексе, а в проблеме приостановки потоков. Операционные системы обычно не предоставляют API для этого. Поскольку теперь это предусмотрено, вы можете написать облегченный мьютекс без блокировки и приостановить свои собственные потоки, когда они должны быть бездействующими.   -  person    schedule 21.01.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

  • In the consumer - as you say, when the consumer has exhausted the queue and is considering sleeping (and only then), it locks the mutex, checks the queue again, and then either
    • releases the mutex and carries on working, if there was a new item in the queue
    • или блокирует условную переменную (освобождая мьютекс, когда он просыпается, чтобы найти непустую очередь, естественно).
  • In the producer:
    • First take a copy of last, call it saved_last
    • Добавьте элемент new_item как обычно, затем возьмите копию указателя divider, назовите его saved_divider.
    • Если значение saved_divider равно new_item, объект, который вы только что вставили, значит, ваш объект уже использован, и ваша работа выполнена.
    • Otherwise, if the value of saved_divider is not equal to saved_last, then you don't need to wake up the consumer. This is because:
      • At a time strictly after you added your new object, you know that divider had not yet reached either new_item or saved_last
      • С тех пор, как вы начали вставку, last имело только эти два значения.
      • Потребитель останавливается только тогда, когда divider равно last.
      • Поэтому потребитель должен еще бодрствовать и доберется до вашего нового товара перед сном.
    • В противном случае заблокируйте мьютекс, сигнализируйте condvar, затем освободите мьютекс. (Получение мьютекса здесь гарантирует, что вы не сигнализируете condar в то время, когда потребитель замечает, что очередь пуста, и фактически блокирует condvar.)

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

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

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

person psmears    schedule 09.12.2010