Терминnon-blockingобозначает параллельные структуры данных, которые не используют традиционные примитивы синхронизации, такие как защитные устройства, для обеспечения безопасности потока. Морис Херлихи и Нир Шавит (сравните)«Искусство многопроцессорного программирования»различает 3 типа неблокирующих структур данных, каждая из которых обладает различными свойствами:
- Структуры данных являютсяне требующими ожидания, если каждая одновременная операция гарантированно завершается конечным числом шагов. Таким образом, можно дать наихудшие гарантии по количеству операций.
- Структуры данных являютсянезапираемыми, если некоторые параллельные операции гарантированно завершаются конечным числом шагов. Хотя теоретически возможно, что некоторые операции никогда не достигают какого-либо прогресса, это вряд ли произойдет в практическом применении.
- Структуры данных являютсяне имеющими препятствий, если одновременная операция гарантированно завершается конечным числом этапов, если только другая одновременная операция не мешает.
Некоторые структуры данных могут быть реализованы только без блокировки, если они используются при определенных ограничениях. Соответствующими аспектами реализации<boost.lockfree>являются количество ниток производителя и потребителя.Однопроизводительныйspилимножественный производительmpозначает, что только один поток или несколько одновременных потоков могут добавлять данные в структуру данных.ОднопользовательскийscилиМногопользовательскиймк) обозначает эквивалент для удаления данных из структуры данных.
Неблокирующие структуры данных не полагаются на замки и мутексы для обеспечения безопасности потока. Синхронизация осуществляется полностью в пользовательском пространстве без какого-либо прямого взаимодействия с операционной системой. Это означает, что они не склонны к таким проблемам, как инверсия приоритета (низкоприоритетная нить должна ждать высокоприоритетную нить).
Вместо того, чтобы полагаться на предохранители, неблокирующие структуры данных требуютатомных операций(конкретные инструкции ЦП, выполняемые без прерывания). Это означает, что любая нить либо видит состояние до, либо после операции, но никакого промежуточного состояния не наблюдается. Не все аппаратные средства поддерживают один и тот же набор атомных инструкций. Если он не доступен в аппаратном обеспечении, его можно эмулировать в программном обеспечении с помощью защитных устройств. Однако это имеет очевидный недостаток потери имущества без блокировки.
При обсуждении производительности неблокирующих структур данных следует различатьамортизированныеинаихудшие затраты. Определение «без замков» и «без ожидания» упоминает только верхнюю границу операции. Поэтому структуры данных без блокировки не обязательно являются лучшим выбором для каждого варианта использования. Чтобы максимизировать пропускную способность приложения, следует рассмотреть высокопроизводительные одновременные структуры данных.
Структуры данных без блокировки будут лучшим выбором для оптимизации задержки системы или для предотвращения инверсии приоритета, которая может потребоваться в приложениях реального времени. В общем, мы советуем рассмотреть, являются ли структуры данных, свободные от блокировок, необходимыми или достаточными параллельные структуры данных. В любом случае мы рекомендуем выполнять тесты с различными структурами данных для конкретной рабочей нагрузки.
Помимо замков и мутексов (которые мы все равно не используем в<boost.lockfree>), есть еще три аспекта, которые могут нарушать свободу замков:
- Atomic Operations
Некоторые архитектуры не обеспечивают необходимые атомные операции в аппаратных средствах. Если это не так, они эмулируются в программном обеспечении с помощью шпинлоков, которое само по себе блокируется.
- Memory Allocations
Выделение памяти из операционной системы не является бесплатным. Это делает невозможным реализацию истинных динамических неблокирующих структур данных. Структуры данных на основе узлов<boost.lockfree>используют пул памяти для распределения внутренних узлов. Если этот пул памяти исчерпан, память для новых узлов должна быть выделена из операционной системы. Однако все структуры данных<boost.lockfree>могут быть сконфигурированы так, чтобы избежать выделения памяти (вместо этого конкретные вызовы потерпят неудачу). Это особенно полезно для систем реального времени, которые требуют выделения памяти без блокировки.
- Exception Handling
Обработка исключений C++ не дает никаких гарантий относительно его поведения в реальном времени. Поэтому мы не поощряем использование исключений и обработку исключений в коде без блокировки.
<boost.lockfree>реализует три структуры данных без блокировки:
Структуры данных могут быть сконфигурированы с помощью шаблоновBoost.Parameter:
boost::lockfree::fixed_sizedКонфигурирует структуру данных какфиксированного размера. Внутренние узлы хранятся внутри массива, и они рассматриваются путем индексации массива. Это ограничивает возможный размер очереди количеством элементов, которые могут быть адресованы по типу индекса (обычно 2**16-2), но на платформах, которые не имеют двухширотных инструкций сравнения и обмена, это лучший способ добиться свободы блокировки.
boost::lockfree::capacityУстанавливаетемкостьструктуры данных во время компиляции. Это означает, что структура данных имеет фиксированный размер.
boost::lockfree::allocatorОпределяет распределителя.<boost.lockfree>поддерживает государственный распределитель и совместим сBoost. Интерпроцессыраспределители.
