Как стать автором
Обновить

Комментарии 39

С нетерпением жду продолжения, потому что lock-free структуры для меня — все еще темный лес.
Тема очень важная. Спасибо за статью и особенно за ссылки.
Весьма полезный цикл намечается, хотя пока не совсем понятно, что есть gc::Guard::protect() и что за дополнительные аргументы у функций вроде compare_exchange_strong.
К сожалению, в рамках одной-двух статей всего не опишешь. Поэтому я вовсе не стал давать комментариев по коду, только вкратце намекнул на техники, которые применены. В следующих статьях надеюсь все эти вопросы — начиная от compare_exchange и до gc::Guard::Protect() — осветить подробно.
Получается, это и есть параллельные алгоритмы… Очень интересно.
Картинка намекает на то, что 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 или нет.
Спасибо за ответ. Ждем статью).
В .NET, например, 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
В Win32 есть функция InitializeCriticalSectionAndSpinCount. Она посредством объекта CriticalSection использует для ожидания сначала спинлок, и только если после заданного числа итераций объект не освободился — то используется «тяжелый» семафор.
правило такое — если вы защищаете спинлоком код, который выполняется дольше чем два переключения контекста (плюс наполнение кэша и TLB) — вам нужно использовать мютекс. В противном случае спинлок будет эффективен. НО:
есть проблема масштабирования. куча статей на эту тему гласит — на малом кол-ве ядер/процессоров спинлок хорош. где-то после 5 и далее хорош только mutex.
Спасибо очень интересно
Будет обо что почесать руки )
Будущее здесь. Спасибо ;)
Спасибо! Очень интересно! Поддержка ARM'ов в вашей библиотеке планируется?
Да, планируется. В принципе, если компилятор поддерживает C++11 (конкретно — <atomic>), то структуры данных из libcds уже сейчас поддерживают ARM. Осталось избавиться от жесткой привязке к архитектуре/ОС в либе. Ну и потестить. Надеюсь к новому году (как у меня принято :) выпустить новую версию без такой привязки.
О, черт, а я и не знал! Было бы интересно послушать одного из пионеров lock-free, теоретика и практика. Как правило, такие люди мыслят довольно нестандартно, есть чему поучиться…
Спасибо!
Продолжайте, очень интересно как без блокировок организован доступ к данным. И, если можно про паттерны, когда потоки помогают друг другу можно что-нибудь отдельное рассказать.
Продолжайте, и интересно, и полезно! Думаю, для многих это полностью новый взгляд на вещи!
По 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-функтор, когда элемент можно безопасно удалить. Тонкость в том, что вызов диспозера может произойти из другого потока и/или задолго после окончания времени жизни самого контейнера.
Кстати, а на всяких GPU-ных архитектурах оно работает?
Я не работал с GPU, так что не могу даже оценить, работает ли хоть теоретически.
как правило пропасть между пониманием атомарных операций и конечной структорой данных — огромна. Надеюсь вы сможете сделать этот переход, а не просто еще раз опишите что такое атомарные операции.
Согласен. Но без азов трудно будет писать далее. Азы эти непростые, атомарность — самое простое из них. Далее следует упорядочение чтения/записи в память…
Спасибо за надежду ;-) В конечном счете, это моя цель — показать, как из этих кирпичиков построить контейнер. Терпения и упорства вам и мне ;-)
Кстати, лучшее описание этого я видел у Вильямса в его C++ Concurrency in Action.
Уточнение: освобождение памяти — тонкий момент для intrusive-контейнеров (namespace cds::intrusive). Для обычных контейнеров в стиле STL (namespace cds::container) и при использовании обычного аллокатора std::allocator (а это дефолтный аллокатор в libcds) об освобождении можно не беспокоиться.
То есть подводные камни сводятся только к инициализации либы. Инициализация предполагает выбор способа управления памятью (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 ;
}


что-то такое должно быть
в первой строке тела конечно должно быть (кнопки редактирования комментария не нашёл)
if (m_pTail)

Эмм… Мне помнится, эта ошибка уже была давно исправлена в статье, сейчас не вижу этого кода.
Вы точно уверены, что это привет из 2020 года, а не из 2013?.. ;-)

Ну я вроде не слепой) в вашей реализации очереди под картинкой «ближе к жизни...» не список получился, а стек. В своём комментарии я просто привёл пример того, как оно должно бы быть, и сам ещё ошибку сделал, которую в сабкомментарии исправил

Да, согласен, — поправил, спасибо!

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Истории