Когда структуры данных без блокировок менее эффективны, чем взаимное исключение (мьютексы)?

Question

Я где-то читал (больше не могу найти страницу), что структуры данных без блокировки более эффективны "для определенных рабочих нагрузок", что, по-видимому, подразумевает, что иногда они на самом деле медленнее или выигрыш от них может быть нулевым в некоторых ситуациях.Выполнение команды блокировки за ~ 100 циклов для выполнения атомарной операции звучит для меня намного быстрее, чем переход в спящий режим и ожидание, пока планировщик снова запустит процесс, поэтому для меня не очевидно, при каких обстоятельствах структура данных без блокировки была бы менее предпочтительной, чем старомодные мьютексы.Если блокировка доступна в 99% случаев и процессу не нужно переходить в спящий режим, является ли мьютекс тогда более быстрым?Существует ли хорошее эмпирическое правило для определения того, в какую сторону идти, предполагая, что доступна подходящая структура данных без блокировки?

Answer 1

Общий подход к реализации структуры данных без блокировки заключается в том, чтобы иметь изменяемую ссылку на неизменяемый объект и чтобы все, что хочет изменить структуру, захватывало ссылку, создавало новую версию объекта с примененными подходящими изменениями, а затем сравнивало ссылку, чтобы указать на новый объект.Если CompareExchange работает, отлично.Если нет, удалите новый объект, повторно возьмите ссылку и начните все сначала.

Это может хорошо сработать, если создание нового объекта обходится дешево, а уровень конкуренции достаточно низок, чтобы CompareExchange обычно работал.Если существует значительная конкуренция и если создание нового объекта происходит медленно, одновременные попытки обновления N потоками могут занять N ^ 2 времени для завершения.В качестве крайнего примера предположим, что на процессоре запущено 100 потоков, обновление занимает 100 мс процессорного времени (чуть больше временного интервала), и все 100 потоков пытаются обновить объект одновременно.В течение первых десяти секунд каждый поток создаст новый объект, основанный на исходном.Один из потоков успешно выполнит CompareExchange, в то время как все остальные завершатся неудачей.Затем в течение следующих 9,9 секунд 99 потоков сгенерируют новые версии объекта, после чего один из них успешно опубликует свое обновление, а 98 завершатся сбоем.Конечным результатом будет то, что методу без блокировки потребуется 505 секунд процессорного времени для выполнения 100 обновлений, в то время как система блокировки могла бы выполнить их примерно за 10 секунд.

Answer 2

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

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

Answer 3

Я не знаю, как это сделать медленнее, но это, безусловно, затрудняет получение права.Во многих случаях, когда два подхода практически идентичны по производительности (или когда просто не имеет значения, займет ли это 500 пикосекунд вместо 100 пикосекунд), выберите самый простой подход - обычно lock.

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

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

Answer 4

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

Похоже, что разные операционные системы могут иметь разные подходы к тому, что делать, когда не удалось получить блокировку.Я использую HP-UX, и он, например, имеет более сложный подход к блокировке мьютексов.Вот его описание:

...С другой стороны, изменение контекста - дорогостоящий процесс.Если ожидание будет коротким, мы бы предпочли не выполнять переключение контекста.Чтобы сбалансировать эти требования, когда мы пытаемся получить семафор и обнаруживаем, что он заблокирован, первое, что мы делаем, - это короткое ожидание вращения.Процедура psema_spin_1() вызывается для вращения до 50 000 тактов, пытаясь получить блокировку.Если нам не удается получить блокировку после 50 000 циклов, мы затем вызываем psema_switch_1(), чтобы отказаться от процессора и позволить другому процессу взять управление на себя.

Answer 5

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

Лучше подумать, нужно ли вам разрешить нескольким потокам ожидать доступа к некоторому набору операций или блокировать до получения сигнала.Для каждого из них требуется очередь ожидающих потоков.Первый ставит в очередь потоки, ожидающие доступа к синхронизированной области, в то время как второй ставит в очередь потоки, ожидающие сигнала.Классы Java AbstractQueuedSynchronizer и AbstractQueuedLongSynchronizer обеспечить такую очередь — в частности, Очередь CLH—на основе которого можно создавать мьютексы, условия и другие примитивы, основанные на очереди.

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

Answer 6

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

ОП рассматривает блокировка как альтернатива мьютексам.Некоторые алгоритмы не требуют ни того, ни другого для доступа к общей структуре данных.В этих случаях и производитель, и потребитель могут одновременно обращаться к одной и той же структуре данных, не обращая внимания на другого.Пример того, как общая очередь позволяет одному читателю и одной записи одновременно работать с общим экземпляром.Это удовлетворяет общую потребность драйвера устройства в записи данных, к которым потребительский процесс может получить доступ по требованию.

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

Это означает, что остается компромисс, но это не просто выбор между мьютексами и спин-блокировками.

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