Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
С нетерпением жду продолжения, потому что lock-free структуры для меня — все еще темный лес.
Тема очень важная. Спасибо за статью и особенно за ссылки.
Весьма полезный цикл намечается, хотя пока не совсем понятно, что есть gc::Guard::protect() и что за дополнительные аргументы у функций вроде compare_exchange_strong.
Картинка намекает на то, что lock-free структуры на самом деле не существуют и ломают мозг? :)
Да, Вы верно угадали посыл картинки ;) Но Вы правы только во втором — действительно, ломают мозг. Насчет первого — существуют, так же как и невозможные фигуры
В похожей статье: habrahabr.ru/post/174369/ в комментариях предложили использовать SpinLock вместо Mutex-а. По графикам это получается какая-то панацея? Нет?
Действительно, во многих случаях spin-lock может дать значительный выигрыш. Но ничего бесплатного не бывает. Я планирую подробно остановиться на spin-lock'ах в одной из следующих статей, так как это хороший и простой пример, сейчас же отмечу: spin-lock хорош, когда он защищает очень короткую часть кода, — буквально несколько ассемблерных инструкций (где-то на форумах Intel проскальзывала оценка в 1 — 8 asm insn). Если же spin-lock защищает нечто бОльшее по размеру — велика вероятность «верчения» при высокой загрузке (high contention): процессоры/ядра будут заняты на 100%, но никакой полезной работы делать не будут, будут вертеться на spin-lock'е.
В общем, вывод таков: только вы сами, для своей конкретной задачи и железа, можете сказать, подойдет ли вам spin-lock или нет.
В общем, вывод таков: только вы сами, для своей конкретной задачи и железа, можете сказать, подойдет ли вам spin-lock или нет.
Спасибо за ответ. Ждем статью).
В .NET, например, SpinWait.SpinOnce после определённого количества вызовов усыпляет поток — вроде довольно полезно.
Заставляете меня забегать вперед ;-)
Согласен, не только полезно, но и нужно! Не безусловно усыплять конечно же, а проводить какие-то действия. Это называется back-off стратегией, — что делать, когда не получается захватить ресурс. Одна из стратегий — переключение на другой поток (sched_yield, Sleep(0)), — на практике показывает себя с довольно хорошей стороны, хотя не очень популярна в академическом мире, где властвует экспоненциальный back-off (это, грубо говоря — попытка захвата ресурса с экспоненциально увеличивающимся интервалом ожидания). SpinWait/SpinOnce, думаю, гибрид этих двух методик.
Согласен, не только полезно, но и нужно! Не безусловно усыплять конечно же, а проводить какие-то действия. Это называется back-off стратегией, — что делать, когда не получается захватить ресурс. Одна из стратегий — переключение на другой поток (sched_yield, Sleep(0)), — на практике показывает себя с довольно хорошей стороны, хотя не очень популярна в академическом мире, где властвует экспоненциальный back-off (это, грубо говоря — попытка захвата ресурса с экспоненциально увеличивающимся интервалом ожидания). SpinWait/SpinOnce, думаю, гибрид этих двух методик.
> велика вероятность «верчения» при высокой загрузке (high contention)
тут очень много зависит от реализации spin-lock. Ticket based spin lock (используется в linux kernel) страдает этой проблемой, да.
Тут немного по этой тематике pdos.csail.mit.edu/papers/linux:lock.pdf
тут очень много зависит от реализации spin-lock. Ticket based spin lock (используется в linux kernel) страдает этой проблемой, да.
Тут немного по этой тематике pdos.csail.mit.edu/papers/linux:lock.pdf
В Win32 есть функция InitializeCriticalSectionAndSpinCount. Она посредством объекта CriticalSection использует для ожидания сначала спинлок, и только если после заданного числа итераций объект не освободился — то используется «тяжелый» семафор.
правило такое — если вы защищаете спинлоком код, который выполняется дольше чем два переключения контекста (плюс наполнение кэша и TLB) — вам нужно использовать мютекс. В противном случае спинлок будет эффективен. НО:
есть проблема масштабирования. куча статей на эту тему гласит — на малом кол-ве ядер/процессоров спинлок хорош. где-то после 5 и далее хорош только mutex.
есть проблема масштабирования. куча статей на эту тему гласит — на малом кол-ве ядер/процессоров спинлок хорош. где-то после 5 и далее хорош только mutex.
Спасибо очень интересно
Будет обо что почесать руки )
Будет обо что почесать руки )
Будущее здесь. Спасибо ;)
Спасибо! Очень интересно! Поддержка ARM'ов в вашей библиотеке планируется?
Да, планируется. В принципе, если компилятор поддерживает C++11 (конкретно — <atomic>), то структуры данных из libcds уже сейчас поддерживают ARM. Осталось избавиться от жесткой привязке к архитектуре/ОС в либе. Ну и потестить. Надеюсь к новому году (как у меня принято :) выпустить новую версию без такой привязки.
Продолжайте, очень интересно как без блокировок организован доступ к данным. И, если можно про паттерны, когда потоки помогают друг другу можно что-нибудь отдельное рассказать.
Продолжайте, и интересно, и полезно! Думаю, для многих это полностью новый взгляд на вещи!
По Lock-Free (и далее Wait-Free) синхронизации могу порекомендовать книгу Concurrent and Distributed Computing in Java (Vijay K. Garg), в частности, главу 5 — Wait-Free Synchronization. Несмотря на наличие Java в названии, книга в основном посвящена теории, алгоритмам и их анализу.
Эта книга была настольной при подготовке к экзамену по параллельному программированию. Не уверен, есть ли более полезная книга по обозначенной теме.
Эта книга была настольной при подготовке к экзамену по параллельному программированию. Не уверен, есть ли более полезная книга по обозначенной теме.
Слушайте, очень-очень-очень хочется не столько про детали реализации, сколько про типичные и работоспособные паттерны использования библиотеки. Будет?
Будет, планирую.
Для торопливых :). В целом, паттерн использования структуры данных из libcds таков: объявляете объект и работаете с ним из разных потоков (можно, конечно, и из одного, но тогда вся соль теряется — STL в single thread однозначно будет быстрее). Отличие от STL в том, что не надо вводить никакой синхронизации при обращении к методам контейнера.
Подводные камни: инициализация/терминация библиотеки (считаю, что довольно легкая, пример здесь, секция How to use) и освобождение памяти — вот это очень тонкий момент. Можно сказать, что освобождение основано на событиях: либа сама дернет указанный в template-аргументах контейнера disposer-функтор, когда элемент можно безопасно удалить. Тонкость в том, что вызов диспозера может произойти из другого потока и/или задолго после окончания времени жизни самого контейнера.
Для торопливых :). В целом, паттерн использования структуры данных из libcds таков: объявляете объект и работаете с ним из разных потоков (можно, конечно, и из одного, но тогда вся соль теряется — STL в single thread однозначно будет быстрее). Отличие от STL в том, что не надо вводить никакой синхронизации при обращении к методам контейнера.
Подводные камни: инициализация/терминация библиотеки (считаю, что довольно легкая, пример здесь, секция How to use) и освобождение памяти — вот это очень тонкий момент. Можно сказать, что освобождение основано на событиях: либа сама дернет указанный в template-аргументах контейнера disposer-функтор, когда элемент можно безопасно удалить. Тонкость в том, что вызов диспозера может произойти из другого потока и/или задолго после окончания времени жизни самого контейнера.
как правило пропасть между пониманием атомарных операций и конечной структорой данных — огромна. Надеюсь вы сможете сделать этот переход, а не просто еще раз опишите что такое атомарные операции.
Согласен. Но без азов трудно будет писать далее. Азы эти непростые, атомарность — самое простое из них. Далее следует упорядочение чтения/записи в память…
Спасибо за надежду ;-) В конечном счете, это моя цель — показать, как из этих кирпичиков построить контейнер. Терпения и упорства вам и мне ;-)
Кстати, лучшее описание этого я видел у Вильямса в его C++ Concurrency in Action.
Спасибо за надежду ;-) В конечном счете, это моя цель — показать, как из этих кирпичиков построить контейнер. Терпения и упорства вам и мне ;-)
Кстати, лучшее описание этого я видел у Вильямса в его C++ Concurrency in Action.
Уточнение: освобождение памяти — тонкий момент для intrusive-контейнеров (namespace cds::intrusive). Для обычных контейнеров в стиле STL (namespace cds::container) и при использовании обычного аллокатора std::allocator (а это дефолтный аллокатор в libcds) об освобождении можно не беспокоиться.
То есть подводные камни сводятся только к инициализации либы. Инициализация предполагает выбор способа управления памятью (safe memory reclamation, что можно трактовать как легкий специализированный сборщик мусора). Таких способов либа предоставляет несколько. Обычно в приложении используется только один. Мой совет — Hazard Pointer (
То есть подводные камни сводятся только к инициализации либы. Инициализация предполагает выбор способа управления памятью (safe memory reclamation, что можно трактовать как легкий специализированный сборщик мусора). Таких способов либа предоставляет несколько. Обычно в приложении используется только один. Мой совет — Hazard Pointer (
cds::gc::HP) или буферизованный user-space RCU (cds::urcu::gc< cds::urcu::general_buffered<> >), они наиболее быстрые по тестам; Hazard Pointer — наиболее отлаженный, существует с первых версий libcds.
Очень интересно, пишите еще!
Только пожалуйста, скорее переходите к делу, с таким началом у вас могучая серия получится, которая не понятно еще, когда вся выйдет)
Только пожалуйста, скорее переходите к делу, с таким началом у вас могучая серия получится, которая не понятно еще, когда вся выйдет)
Когда-то давно нужно было написать lock-free очередь на Delphi. Алгоритм родился сам, получился до безобразия простым и работает уже многие годы. Но писался он для двух потоков. Когда понадобилось добавить третий — код заметно вырос. Решить проблему в общем виде пытался, но реализации выходили неэффективные, да и та конкретная задача довольствовалась тремя потоками.
Очень интересно, причём именно теория. Пишите ещё!
Очень интересно, причём именно теория. Пишите ещё!
Привет из 2020.
Мне кажется, или в коде очереди ошибка?
что-то такое должно быть
Мне кажется, или в коде очереди ошибка?
void enqueue(Node * p)
{
if (!m_pTail)
m_pTail->m_pNext = p;
m_pTail = p ;
if (!m_pHead)
m_pHead = p ;
}
что-то такое должно быть
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock-free структуры данных. 1 — Начало