Я где-то читал (больше не могу найти страницу), что блокирующие структуры данных более эффективны "для определенных рабочих нагрузок", что, по-видимому, подразумевает, что иногда они на самом деле медленнее или выигрыш от них может быть нулевым в некоторых ситуациях, Принимая 100-секундный удар команды блокировки для выполнения атомарного op, мне кажется намного быстрее, чем спать, и ожидая, когда планировщик пробудит процесс резервного копирования, поэтому мне не кажется очевидным, при каких обстоятельствах блокировка данных без блокировки было бы менее предпочтительным, чем старомодные мьютексы. Если блокировка доступна в 99% случаев, и процесс не должен идти спать, значит, это мьютекс быстрее? Есть ли правильное правило большого пальца, чтобы узнать, какой способ пойти, если будет создана подходящая структура данных, свободная от блокировки?
Когда блоки данных без блокировки менее эффективны, чем взаимное исключение (мьютексы)?
Ответ 1
Обычный подход к внедрению структуры данных без блокировки заключается в том, чтобы иметь изменяемую ссылку на неизменяемый объект и иметь все, что хочет изменить структуру, захватить ссылку, создать новую версию объекта с подходящими изменениями, а затем CompareExchange ссылку для указания на новый объект. Если CompareExchange работает, отлично. Если нет, переверните новый объект, перехватите ссылку и начните.
Это может сработать, если создание нового объекта дешево, а уровень конкуренции достаточно мал, что обычно работает CompareExchange. Если есть значительный спор, и если создание нового объекта происходит медленно, одновременные попытки обновления по N потокам могут занять N ^ 2 раза. В качестве экстремального примера предположим, что 100 потоков запущены на процессоре, обновление занимает 100 мс времени процессора (чуть больше фрагмента времени), и все 100 потоков пытаются обновить объект за один раз. В течение первых десяти секунд каждый поток будет создавать новый объект на основе оригинала. Один из потоков успешно выполнит CompareExchange, в то время как другие будут терпеть неудачу. Затем в течение следующих 9.9 секунд 99 потоков будут генерировать новые версии объекта, после чего он успешно опубликует свое обновление и 98 завершится с ошибкой. Чистый эффект будет заключаться в том, что метод блокировки будет занимать 505 секунд процессорного времени, чтобы выполнить 100 обновлений, когда система блокировки могла сделать их примерно через 10 секунд.
Ответ 2
блокированные структуры данных, так или иначе, используют атомную семантику из вашей архитектуры для выполнения своих основных операций. Когда вы это сделаете, вы можете использовать механизмы всего внутреннего механизма исключения для обеспечения правильного упорядочения или ограждения данных. Мьютекс или критический раздел также делают это, но он делает это только один раз для одного флага. Если мьютекс или критическая секция медленная, это когда происходит сбой блокировки (есть конкуренция). В этом случае ОС также вызывает планировщик для приостановки потока до тех пор, пока объект исключения не будет выпущен.
Таким образом, кажется логичным, что всякий раз, когда ваша структура без блокировки использует несколько атомных операций для каждого основного метода, когда один блокирующий экран, защищающий критический раздел, может обеспечивать одну и ту же семантику. И на практике, как правило, для данных структура, о которой идет речь, то на самом деле имеет смысл использовать механизм блокировки с помощью ОС, чем пытаться создать свой собственный.
Ответ 3
Я не знаю, как сделать это медленнее, но это, конечно, усложняет право. Во многих случаях, когда два подхода практически идентичны по производительности (или когда это просто не имеет значения, если требуется 500 пикосекунд, а не 100 пикосекунд), выберите самый простой подход - обычно lock.
Есть очень мало случаев, когда этот дополнительный бит производительности является ключевым; и, если это так, я подозреваю, что вам будет полезно использовать предварительно развернутые реализации шаблонов из установленных библиотек. Неправильно работать с кодом без блокировки (и убедиться, что он работает правильно во всех условиях) часто очень сложно.
Отметим также, что в некоторых средах уровень блокировки выше мьютекса, предоставляемого OS; mutex, но без некоторых накладных расходов (например, Monitor в .NET).
Ответ 4
Я хотел бы добавить один пункт к этой части ответа: "Если мьютекс или критическая секция медленны, это когда происходит захват блокировки (есть конкуренция). В этом случае ОС также вызывает планировщик, чтобы приостановить поток до тех пор, пока объект исключения не будет выпущен".
Похоже, что разные операционные системы могут иметь разные подходы к тому, что делать, если блокировка не завершилась. Я использую HP-UX, и он, например, имеет более сложный подход к блокировке мьютексов. Вот его описание:
... С другой стороны, изменение контекста - дорогостоящий процесс. Если ожидание будет коротким, мы бы предпочли не использовать контекстный переключатель. Чтобы сбалансировать эти требования, когда мы пытаемся получить семафор и находим его заблокированным, первое, что мы делаем, это короткое ожидание вращения. Подпрограмма psema_spin_1() вызывается для вращения до 50 000 тактов, чтобы получить блокировку. Если мы не получим блокировку после 50 000 циклов, тогда мы вызываем psema_switch_1(), чтобы отказаться от процессора и позволить другому процессу взять верх.
Ответ 5
Имейте в виду, что мьютекс может быть реализован как блокирующая структура данных в том смысле, что он использует один или несколько атомных объектов для представления своего состояния. Это ложная дихотомия.
Лучше подумать, нужно ли вам разрешать нескольким потокам ждать доступа к некоторому набору операций или блокировать до тех пор, пока не будет сигнализирован. Для каждого из них требуется очередь ожидающих потоков. Первые очереди представляют собой очереди, ожидающие доступа к синхронизированной области, в то время как последний ставит в очередь потоки, ожидающие сигнала. Классы Java AbstractQueuedSynchronizer и AbstractQueuedLongSynchronizer предоставить такую очередь, в частности, CLH Queue - на которой можно создавать мьютексы, условия и другие примитивы на основе очереди.
Если ваши требования благоприятствуют вместо этого только одному потоку, выполняющему исключительный набор функций, в то время как другие потоки остаются свободными для продолжения работы, в отличие от ожидания, пока они тоже не смогут выполнить ту же самую работу, а затем используют методы блокировки возможно. Будет ли это предоставлять более быстрое время выполнения, приходится на бенчмаркинг, учитывая, как часто и сколько потоков будет бороться с этими элементами управления синхронизацией, и будет ли другая работа для потоков работать независимо.
Ответ 6
Эффективность зависит от метрики. Алгоритмы Lock- или wait-free важны в системах, где preemption может ввести тупик или повлиять на сроки составления расписания. В этих случаях обработка менее важна, чем правильность.
OP рассматривает блокировку как альтернативу мьютексам. Некоторым алгоритмам не требуется ни для доступа к общей структуре данных. В этих случаях как производитель, так и потребитель могут одновременно обращаться к одной и той же структуре данных, не обращая внимания на другую. Пример общей очереди позволяет одному читателю и одному писателю одновременно действовать на общий экземпляр. Это отвечает общей потребностям драйвера устройства, записывающего данные, которые потребительский процесс может получить по запросу.
Более сложные отношения между процессами могут быть разрешены (см. Herlihy (1991) для анализа) с различными уровнями аппаратной поддержки. Он заключает, что синхронизация без ожидания представляет собой качественный разрыв с традиционными методами блокировки для реализации параллельных объектов.
Что это значит, так это то, что остается компромисс, но не просто между выбором между мьютексами и прямыми замками.
Правило большого пальца остается сосредоточенным на правильности, а не на производительности. Производительность обычно может быть достигнута путем броска денег на проблему, в то время как требования к выполнению обычно сложнее.