Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).
Можно ли такой подход распространить на lock-free list?.. Посмотрим…
Читать полностью »
Рубрика «lock-free» - 2
Lock-free структуры данных. Iterable list
2016-12-20 в 6:01, admin, рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, ПрограммированиеLock-free структуры данных. Итераторы: multi-level array
2016-12-13 в 6:12, admin, рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, Программирование
В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.
Читать полностью »
Разделяемые указатели и многопоточность. И снова о них, в который раз
2016-11-21 в 23:53, admin, рубрики: c++, lock-free, Алгоритмы, многопоточность, Программирование, умные указатели
Глава из книги "Современное программирование на C++" называется "В сто первый раз об интеллектуальных указателях". Все бы ничего, но книга была издана в 2001 году, так стоит ли в очередной раз возвращаться к этой теме? Мне кажется что как раз сейчас и стоит. За эти пятнадцать лет поменялась сама точка зрения, тот угол под которым мы смотрим на проблему. В те далекие времена только-только вышла первая де-факто стандартная реализация — boost::shared_ptr<>, до этого каждый писал себе реализацию по потребности и как минимум представлял себе детали, сильные и слабые стороны своего кода. Все книги по C++ в то время обязательно описывали одну из вариаций умных указателей в мельчайших деталях.
Сейчас нам дан стандарт, и это хорошо. Но с другой стороны, уже не требуется понимать что там внутри, вместо этого достаточно три раза повторить мантру "используйте умные указатели везде где вы бы использовали обычные указатели", и это уже не так хорошо. Я подозреваю что далеко не все отдают себе отчет что данный стандарт — лишь один из возможных вариантов интерфейса, не говоря уже о разнице между реализациями различных вендоров. При выборе стандарта был сделан выбор между различными возможностями учитывающий разные факторы, но, оптимальный или нет, этот выбор очевидно не единственен.
А еще на stackoverflow например снова и снова задается вопрос — "потокобезопасны ли умные указатели из стандартной библиотеки?". Ответы даются обычно категоричные, но какие-то мало информативные. Если бы я например не знал о чем идет речь, то наверное бы не понял. И кстати, все сравнительно новые книги описывающие новый стандарт C++ этому вопросу тоже уделяют мало внимания.
Так давайте же попробуем сорвать покровы и разберемся с деталями.
Lock-free структуры данных. Concurrent maps: деревья
2015-03-17 в 5:55, admin, рубрики: c++, libcds, lock-free, map, tree, Алгоритмы, параллельное программирование, Программирование 
Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.
Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).
Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.
Читать полностью »
Lock-free структуры данных. Concurrent maps: skip list
2015-03-10 в 6:00, admin, рубрики: c++, libcds, lock-free, map, skip list, Алгоритмы, параллельное программирование, Программирование 
В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..
Читать полностью »
Lock-free структуры данных. Concurrent maps: rehash, no rebuild
2015-03-04 в 6:00, admin, рубрики: c++, libcds, lock-free, map, split-ordered list, Алгоритмы, параллельное программирование, Программирование 
Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?
Читать полностью »
Lock-free структуры данных. Concurrent map: разминка
2015-03-03 в 6:00, admin, рубрики: c++, libcds, lock-free, map, ordered list, Алгоритмы, параллельное программирование, Программирование 
Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.
Читать полностью »
Простейшие Lock-Free объекты для двух потоков
2014-12-15 в 14:11, admin, рубрики: Delphi, lock-free, ПрограммированиеЗдесь было много статей об универсальных Lock-free объектах, однако, для некоторых частных случаев они излишне громоздки. Мой случай как раз таким и являлся: требовалось организовать одностороннюю передачу информации от одного потока другому. Главный поток запускает рабочий, после чего он может только запросить его остановку и никак больше управлять он им не может. В свою очередь рабочий поток может уведомлять главный о своем текущем состоянии (прогрессе выполнения), а также отсылать промежуточные результаты выполнения. Получается, что требуется только передача данных от рабочего к главному потоку.
Разумеется, возможно, я изобрёл велосипед или, хуже того, велосипед с глюками. Поэтому комментарии и критика очень приветствуются!
Читать полностью »
Lock-free структуры данных. Диссекция очереди
2014-12-09 в 7:00, admin, рубрики: c++, lock-free, queue, параллельное программирование, Программирование 
Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.
Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..
Читать полностью »
Lock-free Round Robin
2014-07-04 в 5:43, admin, рубрики: collections, java, lock-free, round-robin, thread-safeВведение
Добрый день, дорогиее.
Давно думал написать статью, но как-то не доходили руки. Да и уже много все написано, причем по несколько раз. Однажды, мне нужно было реализовать распределение нагрузки по пулу.
Алгоритм
Для этого я выбрал алгоритм round robin, как наиболее простой алгоритм подходящий для данной задачи. Для тех кто не знает, что это за алгоритм, цитата из wiki:
Round-robin (от англ. round-robin — циклический) — алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу.
Немного погуглив готовой реализация я не нашел, но наткнулся на статью. Статья отличная, но я решил пойти по другому пути. Написав свою реализацию.
Читать полностью »