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

Question

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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