Введение
Lock-free структуры данных в общем и целом неплохо описаны в различной литературе, но на мой взгляд порог вхождения в эту тему высок. Приведу простой кейс использования одной из разновидностей данной технологии под названием RCU (Read–Copy-Update). В двух словах, это механизм неблокирующего обновления структуры данных у которой много читателей и всего один писатель. Wikipedia.
Тестовый пример
В нашем тесте используем библиотеку liburcu, которая наличествует в штатном репозитории Ubuntu.
Код проекта https://github.com/vic-35/test_liburcu , проект создан в QT creator для облегчения отладки и запуска.
Основная идея - создать минимальное приложение, которое покажет смысл применения RCU и наглядную разницу в производительности.
Для инициализации RCU в каждой нити вызывается rcu_register_thread() и по завершении rcu_unregister_thread().
Приложение состоит из двух одинаковых алгоритмов , выполненных с использованием SpinLock и RCU. Запускаем несколько нитей , одна выполняет изменение указателя и его значения , остальные считывают значения по указателю и проверяют не считалось ли некорректное значение. Родительский поток ждет 10 секунд и освобождает мьютекс остановки нитей. В итоговом окне видим номер нити и количество считанных значений.
SpinLock версия выполняет чтение-модификацию, захватив SpinLock, в одну единицу времени только один поток имеет доступ к переменной result.
while (pthread_mutex_trylock(&m1) == EBUSY) {
pthread_spin_lock(&s1);
usleep(1);
if (i == 0) {
unsigned int rez = *result;
*result = 0x0;
free(result);
result = malloc(sizeof(unsigned int));
if (rez == REZ1) {
*result = REZ2;
count++;
} else {
*result = REZ1;
count1++;
}
} else {
unsigned int rez = *result;
if (rez != REZ1 && rez != REZ2) {
printf("Fatal error :%lld :%lld :%lld\n", i, count, count1);
exit(-1);
}
if (rez == REZ1) {
count++;
} else {
count1++;
}
}
pthread_spin_unlock(&s1);
}
RCU версия также очень проста. Перед выполнением чтения синхронизируемых данных выполняется вызов rcu_read_lock(), по завершению rcu_read_unlock(). Между вызовами гарантируется работа с валидными данными. Необходимо понимать что каждая из нитей может работать со своим указателем на переменную *result , но у каждой гарантированно будет выделена память и валидное значение переменной.
Замена указателя производится вызовом rcu_xchg_pointer(&result, new_result), а ожидание обновления переменной у всех нитей, находящихся в rcu_read_lock секции , функция synchronize_rcu().
while (pthread_mutex_trylock(&m1) == EBUSY) {
rcu_read_lock();
usleep(1);
if (i == 0) {
unsigned int rez = *result;
unsigned int *new_result = malloc(sizeof(unsigned int));
if (rez == REZ1) {
*new_result = REZ2;
count++;
} else {
*new_result = REZ1;
count1++;
}
rcu_read_unlock();
unsigned int *old_result = rcu_xchg_pointer(&result, new_result);
synchronize_rcu();
if (old_result)
*old_result = 0;
free(old_result);
} else {
unsigned int rez = *result;
if (rez != REZ1 && rez != REZ2) {
printf("Fatal error :%lld :%lld :%lld\n", i, count, count1);
exit(-1);
}
if (rez == REZ1) {
count++;
} else {
count1++;
}
rcu_read_unlock();
}
}
Тестирование
Сначала выполняется SpinLock затем RCU.
Проверяем с запуском одной нити , есть ли разница в алгоритмах. Алгоритм на SpinLock в большинстве случаев выполняет больше циклов чтения - изменения переменной.
start :0
end :0 :86325 :86324
start :0
end :0 :84708 :84708
Проверяем с запуском нескольких нитей. Алгоритм на SpinLock резко сдает позиции, фактически нити постоянно ждут очереди на доступ к ресурсу.
start :0
start :1
start :5
start :4
start :2
start :3
end :2 :17574 :24472
end :4 :1773 :2824
end :0 :3639 :3638
end :1 :16770 :16452
end :5 :21121 :32123
end :3 :18075 :22640
start :0
start :3
start :2
start :5
start :4
start :1
end :5 :85755 :85766
end :3 :86214 :86157
end :2 :86143 :86066
end :4 :85594 :85790
end :0 :41820 :41820
end :1 :85583 :85670
Проверяем необходимость синхронизации в принципе. Комментируем вызовы pthread_spin_lock(&s1) и pthread_spin_unlock(&s1). При выполнении программы происходит чтение не инициализированного участка памяти, ошибка сравнения и прерывание выполнения.
start :0
start :1
start :2
start :4
start :5
start :3
Fatal error :4 :18 :18
Вывод
Пример является наглядной демонстрацией возможностей Lock-free структур. Тест несомненно синтетический, в реальном приложении нити не стоят в бесконечной очереди к одному ресурсу и факторов быстродействия очень много. Обратите внимание что synchronize_rcu не может находится внутри rcu_read_lock секции. Для выполнения обновления внутри rcu_read_lock секции есть механизм отложенного удаления ресурсов, он чуть более сложен и не описан в рамках данного кейса.
Подробно о библиотеке liburcu.
https://lwn.net/Articles/262464/
Надеюсь что данный пример поможет кому то ускорить его многопоточное приложение.
