В этой статье я хочу поднять несколько холиварную тему — тему lockless-алгоритмов и в частности реализации lockless-стека.
Точнее, этот стек условно безблоковый; почему, станет ясно позже.
Сразу хочу предупредить, что все примеры будут даны на языке C. Для начала, для тех, кто не очень знаком с темой, хочу вкратце рассказать, что такое lockless-алгоритмы и зачем они нужны.
Зачастую многопоточные приложения используют доступ к одним и тем же данным из нескольких потоков, в качестве примера могу привести очередь обработки.
Чтобы эти данные оставались согласованными (целостностью), необходимы методы защиты их от одновременных несогласованных изменений.
Обычно такими методами являются всевозможные блокировки (спин-блокировки, мьютексы), полностью предотвращающие одновременный доступ к данным, закрывающиеся перед доступом к данным на чтение или запись и открывающиеся после завершения необходимой операции.
Не вдаваясь в различия между спин-блокировками и мьютексами, хочу сказать, что этот принцип остается неизменным, какие бы блокировки вы ни использовали.
В свою очередь, алгоритмы без блокировки используют атомарные операции, такие как CAS (сравнение и замена), для согласования одновременного доступа, чтобы данные сохраняли целостность.
В результате алгоритмы без блокировок обычно имеют значительно лучшую производительность.
Все бы ничего, если бы не высокая сложность их реализации, начиная от набившей всем оскомину проблемы ABA, заканчивая опасностью доступа к удаленным сегментам памяти и, как следствие, крахом программы.
.
И именно из-за своей высокой сложности lock-free-алгоритмы до сих пор используются очень мало.
Но это все лирика, а теперь перейдем к делу.
Я встречал довольно много реализаций lockless-стека: некоторые точно не работают, некоторые «наивны», т.е.
многие рабочие не учитывают проблему ABA. Например, я нашел один из таких стеков с очень хорошим описанием проблем, которые могут возникнуть при реализации стека без блокировок: blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms .
Для тех, кто хочет в этом разобраться, это довольно хорошая статья, показывающая проблемы lock-free алгоритмов и методы их решения.
Одной из проблем стека без блокировок является динамическое управление памятью: узлы стека необходимо выделить и (если мы не хотим утечек памяти) удалить.
В этом случае проблема возникает именно с удалением.
Возьмем «наивную» реализацию стека:
Теги: #lock-free #stack #C++ #C++ #многопоточность #C++ #C++ #Параллельное программированиеvoid push(void *data) { struct stack_node_s *node = malloc(sizeof(struct stack_node_s)); node->data = data; do { node->next = head; } while(!compare_and_swap(&head, node->next, node); } void *pop() { struct stack_node_s *node; void *result = NULL; do { node = head; } while(node && !compare_and_swap(&head, node, node->next);
-
Внешнее Резервное Копирование Данных
19 Oct, 24 -
Баннерная Реклама Все Еще Царит
19 Oct, 24 -
Хостинг S3 Вырос До 5 Миллиардов Файлов
19 Oct, 24 -
Отправка Почты В Codeigniter
19 Oct, 24 -
Инструменты Для Форматирования Css-Кода
19 Oct, 24 -
Ловкость = 4 + 12
19 Oct, 24
