В данной статье хочу поднять несколько холиварную тему — тему безлоковых алгоритмов, а в частности реализации безлокового стека. Точнее, стек этот условно безлоковый, почему — будет ясно далее. Хочу сразу предупредить, что все примеры будут даны на языке C.
Для начала, для тех кто не очень в теме, хочу вкратце рассказать, что такое безлоковые алгоритмы, и зачем они нужны. Зачастую в многопоточных приложениях используется доступ к одним и тем же данным из нескольких потоков, как пример могу привести очередь обработки. Для того чтобы эти данные оставались консистентными (целостными) необходимы методы их защиты от одновременных несогласованных изменений. Обычно такими методами являются всевозможные локи, (спинлоки, мьютексы), которые полностью предотвращают одновременный доступ к данным, закрываясь перед доступом к данным на чтение или запись, и открываясь после того, как необходимая операция завершилась.
Не вдаваясь в различия между спинлоками и мьютексами хочу сказать, что принцип этот остаётся неизменным, какие бы локи вы не использовали.
В свою очередь 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 стека является динамическое управление памятью: ноды стека должны выделяться и (если мы не хотим утечек памяти) удаляться. При этом проблема возникает именно с удалением. Возьмём «наивную» реализацию стека:
Данная реализация именуется «наивной» потому что она считает, что если 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 исчезает сама собой. Иными словами, я предлагаю алгоритм, использующий локи только в одной из частей, которая может вызвать наибольшие проблемы.
В моём случае реализация будет выглядеть следующим образом:
Данная реализация была протестирована на быстродействие наряду с 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 подход лишь добавит вам геморроя, не улучшая значительно быстродействия. Данная статья также демонстрирует возможность комбинированных подходов к реализации параллельных алгоритмов.
Для начала, для тех кто не очень в теме, хочу вкратце рассказать, что такое безлоковые алгоритмы, и зачем они нужны. Зачастую в многопоточных приложениях используется доступ к одним и тем же данным из нескольких потоков, как пример могу привести очередь обработки. Для того чтобы эти данные оставались консистентными (целостными) необходимы методы их защиты от одновременных несогласованных изменений. Обычно такими методами являются всевозможные локи, (спинлоки, мьютексы), которые полностью предотвращают одновременный доступ к данным, закрываясь перед доступом к данным на чтение или запись, и открываясь после того, как необходимая операция завершилась.
Не вдаваясь в различия между спинлоками и мьютексами хочу сказать, что принцип этот остаётся неизменным, какие бы локи вы не использовали.
В свою очередь 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 подход лишь добавит вам геморроя, не улучшая значительно быстродействия. Данная статья также демонстрирует возможность комбинированных подходов к реализации параллельных алгоритмов.
