Каков наиболее эффективный способ управления отслеживанием официантов с помощью блокировок на основе futex?
Я использую подход подсчета официантов для блокировок на основе futex: рядом с futex intимея вторую int это число официантов, которое официанты, борющиеся за блокировку, атомарно увеличивают перед выполнением операции ожидания futex и атомарно уменьшают по возвращении из системного вызова futex. Тем не менее, я заметил, что это имеет патологически плохие свойства с точки зрения количества бесполезных системных вызовов, которые выполняются, когда число запущенных потоков больше, чем число процессоров, что выглядит следующим образом:
Поток A приостанавливается в ожидании на futex, и, таким образом, счетчик официантов увеличивается, но вскоре он не получит временный интервал, потому что все процессоры используются. Тем временем поток B быстро выполняет операции, которые на мгновение получают и снимают блокировку. Каждый раз он видит, что есть официант, и, следовательно, делает системный вызов пробуждения futex, несмотря на тот факт, что поток A уже отправил пробуждение и просто еще не имел возможности запустить и убрать себя из числа официантов.
Есть ли хороший способ обойти это? Я чувствую, что должен быть какой-то безопасный способ для потока, отправляющего событие wake, сделать эквивалент уменьшения числа официантов (делать это напрямую не представляется возможным, так как было бы трудно договориться, чтобы не происходило многократное уменьшение)). Добавление одного или нескольких дополнительных int поля в состояние блокировки были бы приемлемы при необходимости.
Один альтернативный дизайн, о котором я знаю, заключается в том, чтобы опередить счетчик официантов и вместо этого иметь только флаг конфликта на атомарной блокировке. int сам. Таким образом, операции разблокировки сбрасывают флаг и пытаются (успешно или нет) получить блокировку после того, как было обнаружено, что она удерживается, и установить флаг. При разблокировке, если установлен флаг, выполняется операция пробуждения. Я полагаю, что этот дизайн позволяет избежать проблемы, с которой я сталкиваюсь, но у него есть другая проблема: в условиях низкой конкуренции официант, который прибывает, пока удерживается блокировка, безоговорочно сделает системный вызов пробуждения futex, когда он снимет блокировку, даже если нет другие официанты. Возможно, этот дизайн можно было бы гибридизировать с подсчетом официантов, чтобы устранить некоторые или все ложные системные вызовы?
1 ответ
Я полагаю, что поток, отправляющий событие wake, может выполнить декремент и при этом поддерживать точное число официантов. Ключевые детали:
FUTEX_WAIT возвращает указание на то, был ли он разбужен FUTEX_WAKE (ноль) или чем-то еще (ненулевым). Официант, которого разбудил FUTEX_WAKE, не должен уменьшать счетчик официантов (он должен предполагать, что вейкер сделал это от своего имени); официант, проснувшийся по какой-либо другой причине, должен уменьшить счет (если, конечно, он сразу не будет ждать снова).
FUTEX_WAKE возвращает количество проснувшихся потоков: waker должен уменьшить число официантов на это число.
Важным моментом является то, что обе стороны знают, была ли ответственность за уменьшение числа официантов успешно передана.
Конечно, дьявол всегда в деталях, и то, является ли эта схема строго наиболее эффективным способом управления официантами, будет зависеть от того, насколько хорошо она интегрируется с остальной частью рассматриваемой схемы блокировки - но это, безусловно, заслуживает рассмотрения.