Для начала, для тех кто не очень в теме, хочу вкратце рассказать, что такое безлоковые алгоритмы, и зачем они нужны. Зачастую в многопоточных приложениях используется доступ к одним и тем же данным из нескольких потоков, как пример могу привести очередь обработки. Для того чтобы эти данные оставались консистентными (целостными) необходимы методы их защиты от одновременных несогласованных изменений. Обычно такими методами являются всевозможные локи, (спинлоки, мьютексы), которые полностью предотвращают одновременный доступ к данным, закрываясь перед доступом к данным на чтение или запись, и открываясь после того, как необходимая операция завершилась.
Не вдаваясь в различия между спинлоками и мьютексами хочу сказать, что принцип этот остаётся неизменным, какие бы локи вы не использовали.
В свою очередь lock-free алгоритмы используют атомарные операции типа CAS (compare and swap) для согласования одновременного доступа, чтобы данные сохраняли целостность. Как итог, lock-free алгоритмы как правило имеют значительно лучшее быстродействие. Всё бы хорошо, если бы не высокая сложность их реализации, начиная от набившей всем оскомину проблемы ABA, заканчивая опасностью доступа к удалённым сегментам памяти, и как следствие падению программы. И именно из-за их высокой сложности lock-free алгоритмы до сих пор очень мало используемы.
Но это всё лирика, а теперь давайте перейдём к сути. Немало я встречал безлоковых реализаций стека: некоторые безусловно нерабочие, некоторые — «naive», т.е. не учитывают проблему ABA, многие и рабочие. К примеру один из таких стеков с очень хорошим описанием проблем которые могут встретиться при реализации lock-free стека я нашёл вот тут: blog.memsql.com/common-pitfalls-in-writing-lock-free-algorithms.
Для желающих разобраться это довольно неплохая статья, которая показывает проблемы lock-free алгоритмов и методы их решений.
Одной из проблем lock-free стека является динамическое управление памятью: ноды стека должны выделяться и (если мы не хотим утечек памяти) удаляться. При этом проблема возникает именно с удалением. Возьмём «наивную» реализацию стека:
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);
if(node) {
result = node->data;
free(node);
}
return result;
}
Данная реализация именуется «наивной» потому что она считает, что если CAS удался, значит у нас оказались именно те данные, которые мы имели ввиду. На деле же существует множество сценариев, в которых head может оказаться тем же что и в начале итерации, но означать он будет совершенно другое.
К примеру, предположим ситуацию, в которой один из читающих потоков успел сохранить head в node, и взять node->next, но compare_and_swap вызваться ещё не успел. Затем поток прерывается, и отдаёт управление другим потокам, один из которых полностью успевает снять и удалить head, другой — снять и удалить head->next, а третий поместить элемент на стек, причём память для этого элемента выделилась с того же адреса по которому находился старый head. Затем управление возвращается к первому потоку.
В данном случае node совпадёт с head, но тот node->next который мы успели взять будет не только неактуальным, но и указывать на удалённый участок памяти.
Эта проблема во многих источниках именуется проблемой ABA', или ABA' problem. Она является истинным бичом начинающих энтузиастов, занимающихся lock-free алгоритмами. Решается она чаще всего введением в дополнение к указателям счётчиков-тэгов, которые изменяются при каждом помещении на стек, так что даже при одинаковом значении указателя пара тэг-указатель будет отличаться.
Вторая проблема с которой столкнется данная реализация — освобождение памяти. Для демонстрации этой проблемы давайте предположим ситуацию, в которой один из читающих потоков сохранил head в node и передал управление другим потокам. Другой же читающий поток успел провести всю процедуру извлечения из стека и удаления памяти. Когда управление вернется первому потоку попытка взять node->next будет ссылаться на освобожденный участок памяти, что, конечно же, не очень хорошо, и даже вполне может привести к падению программы. Данную проблему решают по разному. В указанной мной статье используются так называемые hazard pointers: список указателей, которые нельзя удалять. Перед тем как удалить участок памяти поток сверяется с этим списком. Есть и другие способы: например временное замещение головы стека условным значением, предотвращающим его удаление в другом потоке. Реализация, которую я хочу предложить, основывается на одном простом факте: доступ к стеку осуществляется через единственный элемент: голову списка, который всё равно невозможно изменять одновременно, поэтому по сравнению с другими контейнерами, такими как например очередь, где идёт чтение из головы и запись в хвост, выигрыш от lock-free подхода довольно невысок.
Поэтому я хочу предложить комбинированный подход к стеку. В данном алгоритме запись выполняется в режиме lock-free, т.е. CAS-ом, чтение же, кроме CAS-а использует ещё и spinlock для того чтобы избежать одновременного чтения в нескольких потоках. Из-за того что чтение будет осуществляется лишь в одном потоке у нас сразу исчезает проблема доступа к освобожденной памяти. Более того, т.к. в течение операции чтения невозможен вариант с удалением и последующей вставкой (можно только вставлять), то и проблема ABA исчезает сама собой. Иными словами, я предлагаю алгоритм, использующий локи только в одной из частей, которая может вызвать наибольшие проблемы.
В моём случае реализация будет выглядеть следующим образом:
void thread_buffer_push(struct thread_buffer_s *head, void *data) {
struct thread_buffer_s *tb, *oldhead;
tb = malloc(sizeof(struct thread_buffer_s));
tb->data = data;
oldhead = head->next;
tb->next = oldhead;
while(!__sync_bool_compare_and_swap(&head->next, oldhead, tb)) {
usleep(1);
oldhead = head->next;
tb->next = oldhead;
}
}
void* thread_buffer_pop(struct thread_buffer_s *head)
{
struct thread_buffer_s *current;
void *result = NULL;
// Spinlock acquire
while(!__sync_bool_compare_and_swap(&head->list_mutex, 0, 1)) {
usleep(1);
}
current = head->next;
// NOONE can pop and delete the same element, since it's read-locked
// But it can change since the stack can be pushed without locking
while(current && !__sync_bool_compare_and_swap(&head->next, current, current->next)) {
usleep(1);
current = head->next;
}
if(current) {
result = current->data;
free(current);
}
// Spinlock release
while(!__sync_bool_compare_and_swap(&head->list_mutex, 1, 0)) {
usleep(1);
}
return result;
}
Данная реализация была протестирована на быстродействие наряду с lock-free алгоритмом учитывающим вышеназванные ошибки, а также алгоритмами использующими spinlock и mutex (pthread_mutex). Usleep(1) был добавлен после экспериментов в соответствии с рекомендациями, данными в статье по указанной мной ссылке.
Оценочное время выполнения каждого из этих алгоритмов следующее (в течение всех тестов оно менялось лишь незначительно):
mutex:
real 0m1.336s
user 0m1.173s
sys 0m3.628s
lock-free:
real 0m0.533s
user 0m0.792s
sys 0m0.046s
spinlock:
real 0m0.520s
user 0m0.630s
sys 0m0.018s
semi-locked:
real 0m0.353s
user 0m0.360s
sys 0m0.075s
Незначительные отличия lock-free и spinlock алгоритма объясняются тем, что как я писал выше, у стека существует лишь одна точка общего доступа (head). То, что эти отличия не в пользу lock-free алгоритма является побочными явлениями добавления защиты от доступа к удалённым указателям.
Выводы хотелось бы сделать следующие: перед тем как реализовывать lock-free алгоритм необходим анализ используемых структур данных на предмет возможности параллельного доступа нескольких потоков одновременно. Вполне возможно, что именно в вашем случае (как, например, в случае со стеком) lock-free подход лишь добавит вам геморроя, не улучшая значительно быстродействия. Данная статья также демонстрирует возможность комбинированных подходов к реализации параллельных алгоритмов.
Комментарии (18)
vintage
24.11.2015 13:30+2Немного расмышлений на тему:
1. Чтобы два потока могли одновременно работать с одной структурой без всяких локов cas-ов и прочего непотребства, то вносимые ими изменения не должны пересекаться вообще. Грубо говоря, у структуры должно быть по отдельной точке редактирования на каждый поток.
2. Простейшая структура имеющая 2 независимые точки изменения — очередь. Один поток пишет данные в хвост, второй срезает их с макушки. Единственное условие их непересечения — в очереди всегда должен быть как минимум один элемент — этого легко добиться.
3. Стек имеет лишь одну точку редактирования — вершину стека. Соответственно с ним может беспроблемно работать лишь один поток. Поэтому назначаем один поток арбитром, который единолично управляет стеком, а общение с остальными потоками организуем через очереди (2).
4. Очередь со множеством писателей реализуется, через множество очередей с одни писателем в каждой. Читатель при этом по разным стратегиям может выбирать сообщения из этих очередей.
5. Очередь со множеством читателей организуется аналогично стеку (3) через отдельный поток-балансировщик — он срезает сообщение с макушки общей очереди и добавляет в хвост очереди подходящего читателя.
Какие тут могут быть подводные камни? Есть некоторое пенальти на перекладывание между очередями, но оно хорошо масштабируется, в отличие от крутящихся в бесконечном цикле CAS или попыток взять блокировку.
vladvic
24.11.2015 14:15+2А вы, батенька, оптимист =)
В любой структуре данных, даже в очереди, бывают следующие случаи:
1) несколько потоков пишут или читают в/из очереди одновременно (это уже не входит в вашу концепцию)
2) очередь содержит 0 или 1 элемент, в данном случае при чтении/записи доступ идёт к одному и тому же элементу: head == tail
все эти случаи тоже нуждаются в грамотной обработке. Это возможно только с помощью локов, или тех же самых атомарных доступов.
Ну и плюс ваш подход съедает нехилое количество инструкций только на арбитраж.
wheercool
24.11.2015 14:22Читайте внимательнее
1) Очередь изначально поддерживает только 2 потока: 1 читатель и 1 писатель. Как сделать много писателей автор описал в п.4
2) Обеспечить наличие фейкового элемента в очереди думаю не очень сложно
Насчет технических деталей не знаю не реализовывал, но концепция выглядит довольно стройной.vladvic
24.11.2015 14:31Прошу прощения, действительно проблема 1 неактуальна. Но остаётся всё же 2 и 3. Оверхед на поддержку очередей с лихвой перекроет любой возможный прирост быстродействия. Не представляю, как вы собираетесь решать проблему пустой очереди с помощью фейкового элемента.
vintage
24.11.2015 16:25Очень просто, пишущий поток завершает серию сообщений пустым сообщением, а читающий игнорирует пустые сообщения и никогда не удаляет последнее. Пример кода: https://gist.github.com/nin-jin/111f32935da5c758a1c8 правда тут используется сборщик мусора и передаются только строки.
Насчёт быстродействия надо тестировать, но реализация, как можно заметить довольно тривиальная.
DrLivesey
24.11.2015 13:42-5Очень прошу прощения, но «безлоковый» сначала прочитал как «бестолковый». Прочитав «Холивар на тему бестолковых алгоритмов», понял что что-то пошло не так…
HaronK
25.11.2015 15:07Когда-то также интересовался этой темой. Даже написал свою реализацию lock-free очереди (GitHub, StackExchange).
Идея там простая: есть 2 потока, один пишет в очередь, другой из нее читает. Внутри очереди есть 2 подочереди — одна для писателя, другая для читателя. Когда читатель вычитывает свою подочередь, он забирает подочередь писателя, а писатель начинает новую.
В базовам варианте (один читатель, один писатель) для синхронизации используется единственная atomic переменная.
Для продакшина нужна будет дополнительная обработка, но идея, я думаю, должна быть работоспособной.
chabapok
26.11.2015 15:32malloc/free должно быть тоже lock-free. Но стандартные malloc/free такими не являются. Более того, такой вызов — это же уход в kernel space, и он не может быть быстрым. То есть, кардинально повысить производительность не выйдет, потому что значительную часть сьест malloc. Но выход есть. Тут должен быть специальный lock-free malloc.
Конечно, это все на уровне догадок. Реально чтоб сравнить, надо мерять как оно будет в конкретных числах.vladvic
26.11.2015 18:07Реальные конкретные числа, замеры, указаны в конце статьи =)
Озвученный в статье подход даёт почти 30% прироста в сравнении с чистым lock-free или чистым спинлоком.chabapok
26.11.2015 19:27Ну это понятно. Тут интересней, сколько процентов времени сжирается внутри malloc.
chabapok
26.11.2015 22:26Я тут еще подумал. Ведь стек — достаточно специфичная штука для многопоточной работы. Если у нас есть схема, когда в одном потоке в стек что-то кладется, а в другом снимается — фактически порядок съема обратным не будет, из за того что push и pop в разных потоках чередуются по-разному. И если в стек будет ложиться и приниматься по 1 записи — оно будет работать как очередь. Если же у нас в потоке-потребителе получится reverse ordered, это будет означать, что у нас на самом деле было не многопоточное выполнение, а последовательное выполнение двух задач в разных потоках. Реально же, на таком длительном тесте, стек будет работать почти как unordered collection.
Но. Если нас устраивает последовательное выполнение, то эффективней выполнить задачи в одном потоке — это более cache-frendly. А если нас устраивает unordered, то может лучше не стек? Если потоки действительно одновременно пишут и читают вершину, там же на вершине на этой будет false sharing (в данном случае наверное даже true sharing). Время будет съедаться на миграцию кэшлайна между ядрами, можно словить 1000 кратную просадку производительности.
Вобщем, достаточно искуственный пример. И тесты, (предположу, что в них скорей всего нет оценки степени «разупорядоченности») неясно что меряют. Набор различных эффектов, проявивших себя в различной мере, и наложенных друг на друга случайным образом.
Можете добавить в тесты следующую фишку: Через стек передаем последовательный набор чисел: 1,2,3,4,5,6..., Снимаются эти числа (когда снимаем в том же потоке) в обратной последовательности. На снимающей стороне мы смотрим, действительно ли последовательность съема обратная. Если происходит скачок по отношению к предыдущему снятому значению в сторону увеличения — значит потоком-производителем была засунута новая порция данных. Мы заводим счетчик таких событий.
И дальше мы говорим, мол всего элементов было столько-то, а конкуррентных вставок было столько-то, и отношение этих величин такое-то.
И когда мы сравниваем реализацию с мутексами с реализацией на cas-ах и спинлоках, то сравнивать имеет смысл прогоны теста, с оглядкой на отношение этих величин. Потому, что ОС, когда она обрабатывает мутексы, то может будить потоки по-разному.
И потом еще надо прогнать сначала push а потом pop этих элементов в одном потоке. Причем, прогнать в двух вариантах:
1 — сначала push всех, потом pop всех. (элементов должны быть сотни мб)
2 — push и pop порциями размером не более 64 байт (чтоб гарантированно работать в одном кэшлайне), вершина стека должна быть выровненной по 64 байтам.
И тут сравнивать время обработки с многопоточным временем обработки. Неисключено, что по варианту 2 будет выигрыш.
а потом прогоните через разные многопоточные очереди такой же обьем данных. И сравние. Это крректно потому, что мы выше решили, что стек может дать как ordered так и unordered данные на принимающей стороне. Нормальная очередь будет более cache-frendly, по идее должно получится существенно быстрей.
evnuh
Ваша статья — это перевод или пересказ той статьи, на которую вы дали ссылку?
Более того, парни из memsql сами же её и перевели и писали на хабр: habrahabr.ru/post/174369 Ваша статья абсолютно идентична по смыслу с ней.
В третьих, в коде у парней я нашёл минимум одну ошибку в реализации lock-free (указатель на next_node зачем-то атомарный) и ещё пару непоняток в коде. Ещё после той статьи им отписал, не знаю, исправили или нет.
vladvic
Я надеюсь вы до конца прочитали? Нет, это не перевод и не пересказ. Более того, в конце статьи делаются выводы о нецелесообразности использования чистого лок-фри подхода в применении к стеку.