Рубрика «lock-free»

в 15:42, , рубрики: atomic swap, lock-free, атомики, классификатор, конкурентность, Параллелизм, параллельное программирование, Программирование, Угадай писал человек или LLM

Mutex, CAS, акторы, STM, CRDT, иммутабельность, MVCC, Disruptor…

Когда читаешь про многопоточность, кажется, что способов — десятки, и каждый требует отдельного изучения.

На самом деле их ровно три. Всё остальное — реализации и комбинации.

Эта статья — попытка навести порядок в голове. После неё вы сможете:

  • за 5 секунд классифицировать любой подход к конкурентности;

  • понимать, почему Erlang выбрал акторы, а Java предлагает synchronized;

  • не изобретать велосипеды и не зацикливаться на «единственно правильном» решении;

  • проектировать многопоточный код, держа в голове простую модель.

    Читать полностью »

в 11:15, , рубрики: atomic, atomicity, c++, lock-free, Атомик, атомики

Мотивация

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

Причины существования атомиков

  • data race (гонка данных) — ситуация, когда два или более потоков одновременно обращаются к одной области памяти, причём хотя бы один выполняет запись, и при этом хотя бы один поток не синхронизирован.

Рассмотрим следующий код.
Ссылка на код: https://godbolt.org/z/qWzGreMac.

Читать полностью »

в 15:16, , рубрики: atomic, c++, concurrency, lock-free, multithreading programming

Многопоточное программирование в C++ традиционно ассоциируется с мьютексами, condition variables и потенциальными проблемами вроде deadlocks и race conditions. Однако современные стандарты C++ (начиная с C++11 и далее) предоставляют инструменты для написания высокопроизводительного многопоточного кода без классических блокировок. В этой статье рассмотрим продвинутые техники: lock-free программирование, атомарные операции и различные модели упорядочивания памяти.

Зачем нужен lock-free код?

Lock-free структуры данных позволяют нескольким потокам работать с общими данными без использования мьютексов. Основные преимущества:

в 7:05, , рубрики: c++, c++11, lock-free, Блог компании Яндекс, Программирование, Процессоры

ARM и программирование без блокировок - 1

Выпуск ARM-процессора Apple M1 вдохновил меня на то, чтобы написать в Твиттер про опасности программирования без блокировок (lock-free). Этот твит вызвал бурную дискуссию. Обсуждение прошло довольно неплохо, учитывая то, что попытки втиснуть в рамки Твиттера обсуждениие такой сложной темы, как модели памяти центрального процессора, — в принципе бессмысленны. Но у меня осталось желание немного раскрыть тему.

Этот пост задуман не только как обычная вводная статья про опасности программирования без блокировок (о которых я в последний раз писал около 15 лет назад), но и как объяснение, почему слабая модель памяти ARM ломает некоторый код, и почему этот код, вероятно, не работал изначально. Я также хочу объяснить, почему стандарт C++11 значительно улучшил ситуацию в программировании без блокировок (несмотря на возражения против противоположной точки зрения).
Читать полностью »

в 21:44, , рубрики: c++, c++11, C++14, high performance, lock, lock-free, locks, low-latency, высокая производительность, параллельное программирование, Программирование

Примеры использования и тестирование потоко-безопасного указателя и contention-free shared-mutex

В этой статье мы покажем: дополнительные оптимизации, примеры использования и тестирование разработанного нами потоко-безопасного указателя с оптимизированным разделяемым мьютексом contfree_safe_ptr<T> – это эквивалентно safe_ptr<T, contention_free_shared_mutex<>>
В конце покажем сравнительные графики тестов нашего thread-safe указателя и одних из лучших lock-free алгоритмов из libCDS на процессорах Intel Core i5/i7, Xeon, 2 x Xeon.
Читать полностью »

в 13:22, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

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

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

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

Что такое Resizable Concurrent Map - 1
Читать полностью »

в 15:07, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

image

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

в 13:02, , рубрики: algorithms, lock-free, multithreading, parallel programming, wunderfund, Алгоритмы, Блог компании Wunder Fund, параллельное программирование, Программирование

image

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

в 6:01, , рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, Программирование

Lock-free структуры данных. Iterable list - 1 Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).
Можно ли такой подход распространить на lock-free list?.. Посмотрим…
Читать полностью »

в 6:12, , рубрики: c++, iterator, libcds, lock-free, map, Алгоритмы, параллельное программирование, Программирование

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

123...4
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js