Я использовал подход с подсчетом ожидания к блокировкам на основе фьютекса: рядом с фьютексом int
, имея второй int
, который является счетчиком ожидания, который официанты, борющиеся за блокировку, атомарно увеличивают перед выполнением операции ожидания фьютекса и атомарно уменьшают по возвращении из системного вызова futex. Однако я заметил, что это имеет патологически плохие свойства с точки зрения количества бесполезных системных вызовов пробуждения, выполняемых, когда количество запущенных потоков превышает количество процессоров, что выглядит следующим образом:
Поток A приостановлен в ожидании фьютекса, и, таким образом, количество ожидающих увеличено, но он не собирается снова получать квант времени в ближайшее время, потому что все процессоры заняты. Тем временем поток B быстро выполняет операции, которые моментально захватывают и освобождают блокировку. Каждый раз он видит, что есть ожидающий, и поэтому делает системный вызов пробуждения фьютекса, несмотря на то, что поток А уже отправил пробуждение и просто еще не успел запуститься и уменьшить себя от счетчика ожидающих.
Есть ли хороший способ обойти это? Я чувствую, что должен быть какой-то безопасный способ для потока, отправляющего событие пробуждения, сделать эквивалент уменьшения счетчика ожидания (сделать это напрямую не представляется возможным, так как было бы трудно договориться, чтобы множественные декременты не происходили ). При необходимости можно добавить одно или несколько дополнительных полей int
в состояние блокировки.
Один альтернативный дизайн, о котором я знаю, отказывается от подсчета официантов и вместо этого имеет только флаг конкуренции на самой атомарной блокировке int
. Как это происходит, операции разблокировки сбрасывают флаг, а попытки (успешные или нет) получить блокировку после того, как было обнаружено, что она удерживается, устанавливают флаг. При разблокировке, если флаг установлен, выполняется операция пробуждения. Я считаю, что этот дизайн позволяет избежать проблемы, с которой я сталкиваюсь, но у него есть другая проблема: при низкой конкуренции официант, который прибывает, когда блокировка удерживается, безоговорочно выполнит системный вызов пробуждения фьютекса, когда он освобождает блокировку, даже если нет никаких другие официанты. Возможно, этот дизайн можно было бы совместить с подсчетом ожидающих, чтобы устранить некоторые или все ложные системные вызовы пробуждения?
futex
это опечатка?mutex
возможно? - person Fiddling Bits   schedule 31.07.2014futex
. См.man 7 futex
иman 2 futex
. - person Nominal Animal   schedule 31.07.2014yield()
, когда счетчик ожидания высок, когда поток достигает блокировки? т.е.if (__atomic_fetch_add(&waiter_count, 1) > SOME_CONSTANT) sched_yield();
в надежде, что поток держателя блокировки получит свой квант времени раньше? Я помню, как читал некоторые обсуждения о направленномyield()
в LKML - тот, который позволил бы текущему потоку уступить непосредственно держателю блокировки/пробуждающемуся потоку - но я думаю, что беспорядок, который он сделал бы с приоритетами планирования, отбросил его. посмотри, смогу ли я найти его. - person Nominal Animal   schedule 31.07.2014int 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.2014waiters
с младшим битом, указывающим, чтоFUTEX_WAKE
уже находится в состоянии ожидания (увеличение и уменьшение счетчика на 2), но для манипулирования им затем требуются атомарные сравнения-обмены, которые имеют тенденцию зацикливаться в спорном случае (и набор потоков может попасть в война до следующего переноса); в спорном случае это было намного медленнее, чем простой счетчик и отдельный флаг. Я не знаю, поможет ли это вам вообще, но, по крайней мере, я пытался :). Не могли бы вы показать свои реализации_lock()
и_unlock()
? - person Nominal Animal   schedule 02.08.2014