Каков наиболее эффективный способ управления отслеживающими официантами с блокировками на основе фьютексов?

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

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

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

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


person R.. GitHub STOP HELPING ICE    schedule 31.07.2014    source источник
comment
futex это опечатка? mutex возможно?   -  person Fiddling Bits    schedule 31.07.2014
comment
@FiddlingBits: Нет, это futex. См. man 7 futex и man 2 futex.   -  person Nominal Animal    schedule 31.07.2014
comment
Глупый вопрос: пробовали ли вы добавить yield(), когда счетчик ожидания высок, когда поток достигает блокировки? т.е. if (__atomic_fetch_add(&waiter_count, 1) > SOME_CONSTANT) sched_yield(); в надежде, что поток держателя блокировки получит свой квант времени раньше? Я помню, как читал некоторые обсуждения о направленном yield() в LKML - тот, который позволил бы текущему потоку уступить непосредственно держателю блокировки/пробуждающемуся потоку - но я думаю, что беспорядок, который он сделал бы с приоритетами планирования, отбросил его. посмотри, смогу ли я найти его.   -  person Nominal Animal    schedule 31.07.2014
comment
Нашел его. Это тема Управление упреждением для пользовательского пространства за март 2014 года в списке рассылки linux-kernel. Два потока могут быть прочитаны, например. здесь и здесь.   -  person Nominal Animal    schedule 31.07.2014
comment
@NominalAnimal: Системный вызов ожидания фьютекса блокируется, поэтому явная уступка вновь прибывшему официанту была бы в лучшем случае бесполезной и, вероятно, контрпродуктивной, если только я не понимаю, что вы говорите. С другой стороны, может быть аргумент в пользу того, чтобы поток освобождал блокировку, если есть ожидающие, надеющиеся дать одному из них шанс получить блокировку.   -  person R.. GitHub STOP HELPING ICE    schedule 31.07.2014
comment
Кажется, вам нужен какой-то флаг ожидания пробуждения, который очищается, когда официант действительно получает свою очередь. Что мне не ясно, так это то, что вы в порядке с активными циклами кражи потоков для дополнительной блокировки удерживаемых операций, пока пробуждение еще не завершено.   -  person jxh    schedule 31.07.2014
comment
@jxh: я не возражаю, если активный поток продолжает блокировать - тем самым он выполняет полезную работу. Что мне не нравится, так это то, что он тратит более 2000 циклов на операцию, создавая бесполезный системный вызов фьютекса.   -  person R.. GitHub STOP HELPING ICE    schedule 31.07.2014
comment
Если бы существовал какой-то способ перевернуть контекст вашего текущего активного потока, чтобы вместо этого передать прямое управление ожидающему потоку, вы бы предпочли сделать это или предпочли бы продолжать разрешать текущему активному потоку обрабатывать работу?   -  person jxh    schedule 31.07.2014
comment
@jxh: я не уверен. Это может быть предпочтительным поведением, но это действительно большой молот, и я хотел бы думать, что это отдельное соображение от рассматриваемой темы, которое просто позволяет избежать избыточных системных вызовов пробуждения для потоков, которые уже разблокированы (концептуально), но просто ждут своего включите планировщик, чтобы сообщить, что они были разблокированы.   -  person R.. GitHub STOP HELPING ICE    schedule 31.07.2014
comment
Я пробовал простую структуру int locked_flag; int waiter_count; char wake_sent;, очищая wake_sent и увеличивая waiter_count перед FUTEX_WAIT, очищая wake_sent и уменьшая waiter_count после FUTEX_WAIT в пути блокировки контента. В пути разблокировки тестирую и ставлю wake_sent; если оно было чистым и waiter_count отличным от нуля, то FUTEX_WAKE. Он работает очень хорошо, но иногда зависает; где-то гоняется - или моя реализация дерьмовая (я подозреваю, что это так). Вероятно, флаг и счетчик нуждаются в строгом порядке, чтобы не участвовать в гонках ... следует сделать временную диаграмму для проверки.   -  person Nominal Animal    schedule 02.08.2014
comment
Я также попробовал составной waiters с младшим битом, указывающим, что FUTEX_WAKE уже находится в состоянии ожидания (увеличение и уменьшение счетчика на 2), но для манипулирования им затем требуются атомарные сравнения-обмены, которые имеют тенденцию зацикливаться в спорном случае (и набор потоков может попасть в война до следующего переноса); в спорном случае это было намного медленнее, чем простой счетчик и отдельный флаг. Я не знаю, поможет ли это вам вообще, но, по крайней мере, я пытался :). Не могли бы вы показать свои реализации _lock() и _unlock()?   -  person Nominal Animal    schedule 02.08.2014


Ответы (1)


Я считаю, что поток, отправляющий событие пробуждения, может выполнять декремент и при этом поддерживать точный подсчет ожидающих. Ключевые детали:

  • FUTEX_WAIT возвращает индикацию того, был ли он разбужен FUTEX_WAKE (ноль) или чем-то другим (ненулевым). Официант, разбуженный FUTEX_WAKE, не должен уменьшать счетчик ожидания (он должен предполагать, что пробуждающий сделал это от его имени); официант, разбуженный по какой-либо другой причине, должен уменьшить счетчик (если, конечно, он сразу же не собирается ждать снова).

  • FUTEX_WAKE возвращает количество пробужденных потоков: пробуждающий должен уменьшить счетчик ожидающих на это число.

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

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

person psmears    schedule 18.09.2014
comment
Проблема в том, что в этой схеме вы подвержены ложным пробуждениям, которые заставляют официанта думать, что он был разбужен намеренно, тогда как на самом деле он был разбужен другим потоком, слепо отправившим FUTEX_WAKE после внесения атомарного изменения для разблокировки объекта, который был впоследствии освобождается, а его память переназначается новому объекту, который теперь видит ложный след. Единственный способ, которым я могу обойти это, - это иметь глобальный контракт, согласно которому фьютексы никогда не будут использоваться таким образом, который может привести к этому, но это невозможно обеспечить, если различные модули приложений и библиотек используют фьютексы. - person R.. GitHub STOP HELPING ICE; 18.09.2014
comment
Также обратите внимание, что единственный способ избежать проблемы, даже если вы приложите усилия, чтобы избежать ее, — это воздержаться от использования атомарных чисел, за которыми следует FUTEX_WAKE, когда есть официанты, и вместо этого использовать FUTEX_WAKE_OP для пробуждения (эффективно) атомарный по отношению к операции с атомарной памятью. - person R.. GitHub STOP HELPING ICE; 18.09.2014
comment
ОК, из исходного вопроса мне не было ясно, насколько точно вы контролируете среду в целом :) На мой взгляд, атомарная разблокировка структуры, а затем вызов FUTEX_WAKE для нее является ошибкой, потому что разблокировка структуры вы отказались от права на любой доступ к ней (память может быть даже не размечена к моменту вызова FUTEX_WAKE); обычно решение состоит в том, чтобы отделить защиту доступа к самому объекту (блокировка объекта) от защиты существования объекта (например, с помощью счетчика ссылок). - person psmears; 18.09.2014
comment
Но если вам нужно работать в среде, где существуют такие ошибки, простая схема, подобная этой, определенно не идеальна, хотя режим отказа (т. е. всегда вызывать FUTEX_WAKE) по крайней мере не катастрофичен, если вы осторожно обрабатываете целочисленное переполнение на официант считает - но это начинает доставлять больше хлопот, чем того стоит! - person psmears; 18.09.2014
comment
Это не так просто — если вы отделяете защиту доступа к самому объекту (блокировку объекта) от защиты существования объекта, вы просто переносите проблему на другой объект, уничтожение которого также необходимо синхронизировать. И подсчет ссылок не является решением этой проблемы; на самом деле это канонический пример, где возникает эта проблема - поток видит, что у него есть последняя ссылка, и тем самым уничтожает объект, когда он с ним покончил, но другой поток, который только что освободил свою ссылку, может быть готов отправить пробуждение фьютекса для него. - person R.. GitHub STOP HELPING ICE; 18.09.2014
comment
К счастью, FUTEX_WAKE не имеет семантического доступа к указанному объекту; скорее, он обращается к очереди ожидающих, которая обязательно (при условии отсутствия условий гонки в программе пользовательского пространства) пуста, если объект, на который указывает, уже уничтожен, связанный с текущей поддержкой (если есть) для виртуального адреса. Таким образом, нет ничего формально недопустимого в отправке этих ложных пробуждений фьютекса, но если что-то в программе их отправляет, это затрудняет использование возвращаемого значения FUTEX_WAIT и FUTEX_WAKE каким-либо осмысленным образом. - person R.. GitHub STOP HELPING ICE; 18.09.2014
comment
Хм, тяжело обсуждать это внятно по комментариям и при отсутствии конкретного примера! Да, вы можете перенести проблему на другой объект, но (в зависимости от конкретной проблемы) это может быть проще, потому что второй объект может иметь время жизни, отличное от первого (например, статический и, следовательно, без блокировки). - person psmears; 18.09.2014
comment
Да, я знаю, как работает FUTEX_WAKE... но разве тот факт, что память может использоваться кем-то другим или даже не отображаться, не означает, что что-то не так с тем, чтобы делать это с памятью, которой вы не владеете? ? Я предполагаю, что часть проблемы заключается в том, что не существует (насколько мне известно) каких-либо письменных правил о том, как вызовы фьютексов должны использоваться процессами Linux, поэтому становится предметом соглашения то, что приемлемо в данном конкретном случае. процесс. - person psmears; 18.09.2014
comment
На мой взгляд, тот факт, что функция FUTEX_WAKE по произвольному адресу семантически разрешена, не делает ее приемлемой — точно так же, как в некотором смысле допустимо вызывать munmap() для памяти, которую вы только что освободили, — но вы не должны этого делать. Не удивлюсь, если это плохо повлияет на всех, кто его использует :) Для меня тот факт, что вы в противном случае делаете возвращаемое значение FUTEX_WAIT непригодным для использования, является достаточной причиной, чтобы наложить правило, согласно которому вы явно владеете только памятью FUTEX_WAKE! - person psmears; 18.09.2014
comment
В случае refcount: нет, поток, который уменьшил refcount, не должен вызывать FUTEX_WAKE для объекта, потому что, уменьшая refcount, он отказывается от любых прав на доступ к объекту. Вместо этого он должен разблокировать объект, FUTEX_WAKE, если необходимо, и затем атомарно уменьшить счетчик ссылок (освобождая объект, если счетчик упадет до нуля). - person psmears; 18.09.2014
comment
Я согласен, что было бы неплохо иметь соглашение о том, что FUTEX_WAKE не отправляется на адреса, не принадлежащие вызывающей стороне, но я думаю, что это делает большинство случаев использования FUTEX_WAKE недействительными. Большинство из них можно было спасти, заменив их на FUTEX_WAKE_OP, но некоторые — нет. Поскольку историческая практика заключалась в неправильном использовании FUTEX_WAKE таким образом (например, это делается во всем glibc), я думаю, что было бы трудно добиться консенсуса от всех, кто использует интерфейс, чтобы исправить неправильное использование. - person R.. GitHub STOP HELPING ICE; 19.09.2014
comment
Кстати, я согласен с тем, что ваш дизайн пересчета с атомарным счетчиком, доступ к которому осуществляется после любой потенциальной разблокировки, должен работать. Невозможность, о которой я говорил, касалась использования неатомарного счетчика, защищенного мьютексом, на который повлияла бы проблема ложного пробуждения. - person R.. GitHub STOP HELPING ICE; 19.09.2014
comment
Можно заставить дизайн счетчика ссылок работать даже с неатомарным счетчиком, защищенным мьютексом: ключ в том, что мьютекс, защищающий счетчик, должен быть тем, который не хранится в объекте. Одна из работающих схем — это иметь один глобальный мьютекс, который защищает все счетчики ссылок — если объекты (и ссылки) создаются/уничтожаются нечасто, это может быть приемлемым (и если нет, то есть способы повысить эффективность). Что касается использования в glibc, я не могу это прокомментировать - прошло много времени с тех пор, как я смотрел на внутреннюю блокировку glibc. Если это плохое использование стало нормой, это печально... - person psmears; 19.09.2014
comment
Да, но очевидно, что размещение мьютекса в объекте (или в связанном объекте, который одновременно уничтожается) — единственный способ масштабирования. Что касается glibc, то здесь произошло то, что Ульрих Дреппер даже не понял (или, по крайней мере, не принял), что объекты pthread могут использоваться для синхронизации окончания их собственного существования, когда он их реализовывал, и фактически давал им доступ к хранение после операции атомарного выпуска. Теперь Торвальд Ригель и другие пытаются их исправить, но они столкнулись с вопросом, имеют ли значение и ложные FUTEX_WAKE... - person R.. GitHub STOP HELPING ICE; 19.09.2014
comment
единственный способ масштабирования скорее зависит от решаемой проблемы и от того, как именно это масштабируется :) например. как я уже упоминал, возможно, что объекты создаются/уничтожаются очень редко; вы можете улучшить один мьютекс, используя несколько мьютексов и хеширование идентификатора объекта (или адреса) и т. д. Что касается объектов pthread, используемых для синхронизации их собственного времени жизни, это интересно, так как я не уверен, что сталкивался случай, когда это было бы полезно; у вас есть ссылки? - person psmears; 19.09.2014
comment
Я думаю, что в программах, которые избегают глобального состояния, такое использование является нормой, а не исключением. Каноническим примером является подсчет ссылок в упомянутой мной форме (или в любой форме без глобального состояния и атомарности). В общем, если объект является частью более крупной структуры данных, вы можете использовать блокировку контейнера для синхронизации уничтожения, но в противном случае вам не повезло. Другой важный вариант использования — это объекты синхронизации для передачи данных в функцию запуска потока; часто вы хотите, чтобы они жили в стеке вызывающей стороны pthread_create. - person R.. GitHub STOP HELPING ICE; 19.09.2014
comment
Хм, все еще не уверен, что понимаю. Если у вас есть объект, защищенный содержащимся в нем мьютексом, и на мьютексе есть ожидающие, когда объект вот-вот будет уничтожен, это явно свидетельствует о серьезной ошибке: если один из потоков, блокирующийся в pthread_mutex_wait, вместо этого был descheduled как раз перед вызовом pthread_mutex_wait, то объект мог быть уничтожен, а мьютекс не отображен/заменен другим объектом до того, как был введен pthread_mutex_wait. Или вы имеете в виду другой сценарий? (Может быть, уместно продолжить эту дискуссию в другом месте?) - person psmears; 19.09.2014
comment
В сценарии, где это происходит, на мьютексе нет ожидающих в момент его уничтожения. Проблема в том, что разблокирующий поток не может знать об этом, потому что он наблюдал, были ли ожидающие в момент разблокировки мьютекса; к тому времени, когда он отправляет FUTEX_WAKE, объект не существует, и нет возможности прочитать, есть ли у него официанты или нет. Если вам интересно, как такой официант наблюдается, но уходит без FUTEX_WAKE, это соответствует случаю, когда поток, выполняющий уничтожение, отмечает, что он ожидает, но затем получает EAGAIN из FUTEX_WAIT. - person R.. GitHub STOP HELPING ICE; 19.09.2014