Почему название lockFREE? это предполагает, что нельзя (мьютекс) заблокировать?
Конечно, все можно заблокировать; вы помещаете мьютекс вне структуры данных, и каждый поток, который касается структуры данных, использует его.
boost::lockfree::queue предоставляет unsynchronized_pop и unsynchronized_push для использования в случаях, когда вы уверены, что только один поток может получить доступ к очереди.
Но главная цель lockfree::queue и алгоритмов/структур данных без блокировки заключается в том, что их не нужно блокировать: несколько потоков могут безопасно писать и/или читать одновременно.
lock-free имеет 2 значения в программировании, что приводит к потенциально запутанным, но верным утверждениям, например, этот lockless-алгоритм не является lock-free.
Случайное использование: синоним слова "без блокировки" — реализовано без мьютексов, с использованием атомарных загрузок, хранилищ и операций RMW, таких как CAS или std::atomic::atomic_fetch_add. См., например, Введение в программирование без блокировки ( Джефф Прешинг). И, возможно, Что каждый системный программист должен знать о параллелизме.
std::shared_ptr использует атомарные операции без блокировки для управления своим блоком управления. C++11 std::atomic<> предоставляет примитивы без блокировки для пользовательских алгоритмов. См. раздел stdatomic. Обычно в C++11 несинхронизированный доступ к одной и той же переменной несколькими потоками является поведением undefined. (Если только они все не доступны только для чтения.) Но std::atomic дает вам четко определенное поведение с вашим выбором последовательной согласованности, захвата/освобождения или расслабленного порядка памяти.
Техническое значение информатики: вечно спящий или убитый поток не блокирует остальные потоки. т. е. гарантированное продвижение вперед для программы в целом (по крайней мере, один поток). (Wait-free — это когда потоки никогда не должны повторять попытки). См. https://en.wikipedia.org/wiki/Non-blocking_algorithm. Цикл повторных попыток CAS — классический пример отсутствия блокировки, но не ожидания. Без ожидания — это такие вещи, как потоки чтения RCU (чтение-копирование-обновление) или, в зависимости от определений, atomic_fetch_add на оборудовании, которое реализует его как примитив (например, x86 xadd), а не с точки зрения цикла повторных попыток LL/SC или CAS. .
Большинство безблокировочных очередей с несколькими операциями чтения/записи не являются безблокировочными в техническом смысле. Обычно они используют циклический буфер, и модуль записи каким-то образом требует запись (фиксируя ее порядок в очереди). . но его нельзя прочитать, пока модуль записи закончит запись в саму запись.
См. Гарантии прогресса без блокировки в качестве примера с анализом его возможного блокирующего поведения. Модуль записи атомарно увеличивает индекс записи, а затем записывает данные в элемент массива. Если автор спит между выполнением этих действий, другие авторы могут заполнить более поздние записи, пока читатели застревают в ожидании заявленной, но не написанной записи. (Я не смотрел на boost::lockfree::queue<T>, но предположительно он похож1.)
На практике производительность превосходна, а конкуренция между авторами и читателями очень низкая. Но теоретически писатель может заблокировать в самый неподходящий момент и затормозить всю очередь.
Сноска 1: Другим возможным вариантом очереди является связанный список. В этом случае вы можете полностью создать новый узел, а затем попытаться добавить его в список CAS. Поэтому, если вам удастся добавить его, другие потоки смогут сразу его прочитать, потому что вы правильно установили его указатели.
Но проблема восстановления (безопасное освобождение памяти, которую могут читать другие потоки, чтобы увидеть, не забрал ли их уже другой читатель) чрезвычайно сложна за пределами языков/сред со сборкой мусора. (например, Ява)
boost::lockfree::queue<int> queue(128); Почему 128?
Это максимальный (максимальный) размер очереди в записях. Из int в данном случае, потому что вы использовали queue<int>, да. Как упоминалось выше, большинство очередей без блокировки используют круговой буфер фиксированного размера. Он не может перераспределять и копировать, как std::vector, когда ему нужно расти, потому что другие потоки могут читать его одновременно.
Как описано в руководстве ( первое попадание в Google для boost::lockfree::queue), конструктор explicit queue(size_type) принимает размер.
Вы также можете запечь емкость в тип, используя ее в качестве параметра шаблона. (Поэтому емкость становится константой времени компиляции везде, где используется очередь, а не только там, где возможно распространение констант из вызова конструктора.)
Класс, по-видимому, не применяет / не требует размера степени 2, поэтому параметр размера шаблона может быть оптимизирован значительно лучше, позволяя % capacity операциям компилироваться в И с маской вместо деления.
person
Peter Cordes
schedule
15.03.2019
