Введение

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/

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

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