Что такое Resizable Concurrent Map

Автор: admin от 17-03-2017, 19:45, посмотрело: 303

В одном из прежних постов я рассказывал, как реализовать «простейшую в мире lock-free хеш-таблицу» на C++. Она была настолько проста, что было невозможно удалять из нее записи или менять ее размерность. С тех пор прошло несколько лет, и не так давно я написал несколько многопоточных ассоциативных массивов без таких ограничений. Их можно найти в моем проекте Junction на GitHub.

Junction содержит несколько многопоточных реализаций интерфейса map – даже «самая простая в мире» среди них, под названием ConcurrentMap_Crude. Для краткости будем называть ее Crude map. В этом посте я объясню разницу между Crude map и Linear map из библиотеки Junction. Linear — самый простой map в Junction, поддерживающий и изменение размера, и удаление.

Можете ознакомиться с объяснением того, как работает Crude map, в первоначальном посте. Если коротко, то она основана на открытой адресации и линейном пробировании. Это значит, что она по сути является большим массивом ключей и значений, использующим линейный поиск. Во время добавления или поиска заданного ключа мы вычисляем хеш от ключа, чтобы определить, с какого места начать поиск. Добавление и поиск данных возможны в многопоточном режиме.

Что такое Resizable Concurrent Map

Категория: Программирование

 

Самая простая в мире lock-free хеш-таблица

Автор: admin от 28-02-2017, 17:35, посмотрело: 567

Самая простая в мире lock-free хеш-таблица

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

Категория: Программирование

 

Введение в lock-free программирование

Автор: admin от 20-02-2017, 18:20, посмотрело: 460

Введение в lock-free программирование

В этом посте мы хотели бы еще раз поднять тему программирования без блокировок, сперва дав ему определение, а затем выделить из всего многообразия информации несколько ключевых положений. Мы покажем, как эти положения соотносятся между собой, с помощью блок-схем, а потом мы немного коснемся деталей. Минимальное требование к разработчику, постигающему lock-free, — умение писать правильный многопоточный код, используя мьютексы или другие высокоуровневые объекты синхронизации, например, семафоры или события.

Категория: Программирование

 

Lock-free структуры данных. Iterable list

Автор: admin от 20-12-2016, 11:05, посмотрело: 279

Lock-free структуры данных. Iterable list 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 структуры данных. Итераторы: multi-level array

Автор: admin от 13-12-2016, 09:35, посмотрело: 268

Lock-free структуры данных. Итераторы: multi-level array
В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.

Категория: Программирование

 

Блокировка дубликатов Symfony Сommand

Автор: admin от 12-12-2016, 11:00, посмотрело: 286

Блокировка дубликатов Symfony Сommand

Сегодня хочу предложить вашему вниманию частный случай для решения «неудобств», связанных с периодичным запуском процессов в том случае, если предыдущий еще не завершился. Иначе говоря — блокировка запущенных процессов в symfony/console. Но все было бы слишком банально, если бы не необходимость блокировки среди группы серверов, а не на отдельно взятом.

Дано: Один и тот же процесс, который запускается на N серверов.
Задача: Сделать так, чтобы в единицу времени был запущен только один.

Категория: Программирование / Веб-разработка

 

Разделяемые указатели и многопоточность. И снова о них, в который раз

Автор: admin от 22-11-2016, 07:55, посмотрело: 369

Разделяемые указатели и многопоточность. И снова о них, в который раз

Глава из книги "Современное программирование на C++" называется "В сто первый раз об интеллектуальных указателях". Все бы ничего, но книга была издана в 2001 году, так стоит ли в очередной раз возвращаться к этой теме? Мне кажется что как раз сейчас и стоит. За эти пятнадцать лет поменялась сама точка зрения, тот угол под которым мы смотрим на проблему. В те далекие времена только-только вышла первая де-факто стандартная реализация — boost::shared_ptr<>, до этого каждый писал себе реализацию по потребности и как минимум представлял себе детали, сильные и слабые стороны своего кода. Все книги по C++ в то время обязательно описывали одну из вариаций умных указателей в мельчайших деталях.
Сейчас нам дан стандарт, и это хорошо. Но с другой стороны, уже не требуется понимать что там внутри, вместо этого достаточно три раза повторить мантру "используйте умные указатели везде где вы бы использовали обычные указатели", и это уже не так хорошо. Я подозреваю что далеко не все отдают себе отчет что данный стандарт — лишь один из возможных вариантов интерфейса, не говоря уже о разнице между реализациями различных вендоров. При выборе стандарта был сделан выбор между различными возможностями учитывающий разные факторы, но, оптимальный или нет, этот выбор очевидно не единственен.
А еще на stackoverflow например снова и снова задается вопрос — "потокобезопасны ли умные указатели из стандартной библиотеки?". Ответы даются обычно категоричные, но какие-то мало информативные. Если бы я например не знал о чем идет речь, то наверное бы не понял. И кстати, все сравнительно новые книги описывающие новый стандарт C++ этому вопросу тоже уделяют мало внимания.
Так давайте же попробуем сорвать покровы и разберемся с деталями.

Категория: Программирование

 

Блокировки работают не так уж медленно

Автор: admin от 27-09-2016, 14:05, посмотрело: 376

Блокировки в общем и мьютексы, как их частная реализация, имеют давнюю историю неправильной оценки скорости их работы. Ещё в 1986-ом году в одной из Usenet-конференций Matthew Dillon написал: «Большинство людей ошибочно уяснили себе, что блокировки работают медленно». Сегодня, спустя многие годы, можно констатировать, что ничего не изменилось.

Действительно, блокировки могут работать медленно на некоторых платформах, или в сверх-конкурентном коде. И, если вы разрабатываете многопоточное приложение, то вполне возможно, что рано или поздно натолкнётесь на ситуацию, когда какая-нибудь одна блокировка будет съедать очень много ресурсов (скорее всего из-за ошибки в коде, приводящей к слишком частому её вызову). Но всё это частные случаи, не имеющие в общем случае отношения к утверждению «блокировки работают медленно». Как мы увидим ниже, код с блокировками может работать весьма производительно.

Одна из причин заблуждений о скорости работы блокировок состоит в том, что многие программисты не отличают понятия «легковесный мьютекс» и «мьютекс, как объект ядра ОС». Всегда используйте легковесные мьютексы. К примеру, если вы программируете на С++ под Windows, то ваш выбор это критические секции.

Блокировки работают не так уж медленноВторой причиной заблуждений могут служить, как это ни парадоксально, бенчмарки. К примеру, далее в этой статье мы будем измерять производительность блокировок под высокой нагрузкой: каждый поток будет требовать блокировку для выполнения любого действия, а сами блокировки будут очень короткими (и, в результате, очень частыми). Это нормально для эксперимента, но такой способ написания кода — это не то, что вам нужно в реальном приложении.

Категория: Программирование / Системное администрирование / Веб-разработка / Windows

 

Атомарная обработка блоков данных без блокировки

Автор: admin от 24-11-2015, 15:47, посмотрело: 766

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

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

Категория: Программирование

 

Lock-free алгоритмы и реализация стэка

Автор: admin от 24-11-2015, 11:38, посмотрело: 393

В данной статье хочу поднять несколько холиварную тему — тему безлоковых алгоритмов, а в частности реализации безлокового стека. Точнее, стек этот условно безлоковый, почему — будет ясно далее. Хочу сразу предупредить, что все примеры будут даны на языке C.

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

Категория: Программирование

 
Назад Вперед