Просто о RCU (Read–Copy-Update)

Введение

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://liburcu.org/

https://lwn.net/Articles/262464/

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