lockfree

без блокировки

lockfree — это набор структур данных без блокировки, написанных на стандарте C++11 и подходящих для всех платформ — от глубоко встроенных до HPC.

Что такое структуры данных без блокировок?

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

Зачем использовать lockfree

• Написан на стандарте C++11, совместим со всеми поддерживающими его платформами.
• Все структуры данных являются потокобезопасными и безопасными по прерываниям в соответствующих случаях использования.
• Нет динамического распределения
• Оптимизирован для высокой производительности
• Лицензия MIT
• Дополнительные API для новых версий C++

Какие структуры данных доступны?

Структуры данных одного производителя и одного потребителя

• Очередь — лучше всего подходит для операций с одним элементом, чрезвычайно быстрый, простой API, состоящий всего из двух методов.
• Кольцевой буфер — более общая структура данных с возможностью одновременной обработки нескольких элементов, использует копии стандартной библиотеки, что делает ее очень быстрой для массовых операций.
• Двудольный буфер — вариант кольцевого буфера с возможностью всегда обеспечивать линейное пространство в буфере, обеспечивающий обработку внутри буфера.
• Очередь приоритетов — вариант очереди с возможностью предоставления различных приоритетов для элементов, что очень полезно для таких вещей, как сигналы, события и пакеты связи.

Эти структуры данных более производительны и, как правило, их следует использовать всякий раз, когда есть только один поток/прерывание, отправляющий данные, а другой их извлекающий.

Структуры данных с несколькими производителями и несколькими потребителями

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

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

Как получить

Получить библиотеку можно тремя основными способами:

• Использование CMake FetchContent()
• Как подмодуль git
• Загрузив релиз с GitHub

Конфигурация

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

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

Кроме того, некоторые системы имеют нетипичную длину кэша (например, процессоры Apple M1/M2 имеют длину кэша 128 байт), и в этих случаях необходимо установить LOCKFREE_CACHELINE_LENGTH соответствующим образом.

Известные ограничения

Все структуры данных в lockfree предназначены для использования только с тривиальными типами.

Часто задаваемые вопросы

Зачем мне использовать это вместо блокировки структур данных на размещенной машине?

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

Кроме того, lockfree предоставляет возможность создавать приложения и библиотеки, которые можно скомпилировать для работы как в средах POSIX, так и в средах, не поддерживающих POSIX, без #ifdef или полиморфизма.

Зачем использовать это вместо механизмов IPC, предоставляемых RTOS, во встроенной системе?

Хотя блокировка обычно не требует больших затрат во встроенных системах, таких как микроконтроллеры, существует большое разнообразие ОСРВ и нет стандартизированного API для блокировки. Тот факт, что присутствует несколько архитектур от 8051 до RISC-V, означает, что методы управления прерываниями также не стандартизированы.

lockfree предоставляет способ создания переносимого встроенного кода с незначительными затратами производительности в отличие от блокировки. Код, использующий lockfree можно скомпилировать для запуска на любой встроенной платформе, поддерживающей C++11. Кроме того, код можно легко протестировать на хост-компьютере без необходимости создания макетов.

Какие преимущества дает для библиотеки использование C++ по сравнению с C?

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

Какова формальная классификация структур данных в lockfree ?

Все структуры в lockfree являются ограниченными , основанными на массивах и без блокировок , структуры данных spsc также не требуют ожидания и безопасны для завершения .

Теория и ссылки

Для получения более подробной информации о программировании без блокировки взгляните на:

• Эта блестящая серия докладов от Херба Саттера
• Серия докладов Live Lock-Free или Deadlock от Федора Пикуса
• Отличный блог Дмитрия Вьюкова