Concurrency in C++: Spinlock

10.03.2018

Спинлок(англ. spinlock) — примитив синхронизации применяемый для реализации поведения взаимного исключения и аналогичен мьютексу(англ. mutex). Обычно спинлок имеет тот же интерфейс, что и мьютекс, что обеспечивает их взаимозаменяемость в коде.

Сейчас в Дзене чуть более, чем полностью отсутствует хоть какая-нибудь возможность форматировать сниппеты с кодом: ни моноширинных шрифтов, ни подключаемых GitHub Gist'ов — ничего. Поэтому далее будут скриншоты vim'а с кодом.

Реализация

Интерфейс объекта, реализующего взаимную блокировку должен содержать два метода lock()/unlock() для взятия блокировки и её освобождения. Обычно эти методы являются noexcept, просто потому что негде бросить исключения: все операции простые, а сами методы зачастую просто подставляются вместо вызовов. Сам объект инициализируется так, чтобы после конструирования объект мог быть захвачен. Обратите внимание, что копирующий конструктор и копирующий оператор присваивания удалены. Дело в том, что семантика таких операций совершенно не ясна и зависит от контекста.

Интерфейс объекта, реализующего взаимную блокировку.
Интерфейс объекта, реализующего взаимную блокировку.

Как реализован мьютекс можно посмотреть, например, в glibc или в libcxx. Вообще говоря, мьютекс выполняет довольно сложные операции и должен следовать всем ограничениям стандарта, поэтому операции над ним довольно тяжёлые. В противовес ему спинлок не определяется в стандарте, не выполняет походы в ядро и может быть полностью реализован на атомарных операциях в пользовательском пространстве, что даёт на порядок больший выигрыш в некоторых ситуациях.

Реализация спинлока существенным образом опирается на понятия атомарной операции и модели памяти. Операция называется атомарной, если операция выполнена целиком, либо не выполнена полностью. Другими словами, мы не можем наблюдать промежуточного состояние операции. Например, простой инкремент в C++ не является атомарной операцией несмотря на возможность существования подходящей ассемблерной инструкции, поскольку для процессора она состоит из трёх операций загрузки значения из памяти, увеличения его на единицу и записи обратно в память. Неатомарные операции в многопроцессорных системах приводят к гонками за данными(англ. data race). Переменные, над которыми выполняются атомарные операции, называются атомарными переменными или атомиками. Здесь нас будет интересовать std::atomic_flag, которым мы будем помечать взятие спинлока и его освобождение. Это простейший атомик с самым бедным функционалом.

С простыми операциями вроде сложения или умножения на два всё понятно, но как быть условными? Как реализовать условие взятия спинлока, если тот свободен? Ведь между проверкой условия и изменения атомарной переменной проходит довольно значительное время. Да и вообще проверка условия тоже не атомарная операция. К счастью, существует так называемая CAS-операция(англ. copy-and-swap), которая позволяет проверить условие и записать новое значение атомарно. В точности CAS делает следующее: сравнивает значение атомарной переменной с тем значением, которое мы ожидаем, а в случае равенства обоих значений записывает желаемое значение в атомарную переменную. Если запись удалась, то операция считается успешной и возвращается true, иначе false. Чаще всего CAS-операции применяются в CAS-циклах — обычный цикл, где условием выхода считается успешность CAS-операции.

Для std::atomic_flag метод-член test_and_set() как раз и есть CAS-операция, где ожидаемое значение - свободный спинлок(false), а желаемое значение - взятый спинлок(true). Чтобы отпустить спинлок, достаточно сбросить флаг с помощью атомарной операции clear().

Реализация спинлока на атомарных переменных.
Реализация спинлока на атомарных переменных.

Приведённая выше реализация имеет несколько более тонких деталей. Первая и самая простая для понимания связана с вызовом std::this_thread::yield(), который используется для передачи управления другому потоку в случае, если не получилось захватить лок.

Вторая и менее тривиальная деталь связана с заданием упорядочивания доступа к памяти. Если не вдаваться в детали, то memory_order_release и memory_order_acquire создают отношение синхронизирован-с между операциями в разных потоках. Причём результаты всех операций в данной нити до вызова unlock() видны всем операциям, расположенным после вызова lock() в других потоках. Другими словами, между такими операциями существует отношение выполняется-прежде, что гарантирует корректность доступа к памяти из разных потоков. Замечу, что на x86-64 и других процессорах с сильной моделью памяти использование ослабленных условий упорядочивания доступа отличных от memory_order_seq_cst не даёт большого выигрыша по сравнению с архитектурами ARM.

В реализации спинлока используется CAS-цикл, в котором крутится поток и постоянно пытается взять лок. Вот поэтому спинлок и получил такое название.

Тест производительности

Будем тестировать производительность нашего спинлока по сравнению с мьютексом на простых операциях, например, инкремент счётчика. Возьмём за основу Google Benchmark и две функции, которые измеряют время взятия лока, инкремента счётчика и освобождения лока. Один подобный тест не является корректным основанием для сравнения, тем не менее, даёт некоторую интуицию о временных масштабах.

В benchmark.cc сравниваются скорость инкремента счётчика, помещённого в критическую секцию, которую защищает std::mutex или SpinLock.
В benchmark.cc сравниваются скорость инкремента счётчика, помещённого в критическую секцию, которую защищает std::mutex или SpinLock.

Компилируем, собираем и запускаем для одного, двух, четырёх и восьми потоков. На моей тачке результаты имеют следующий вид. При любом числе потоков спинлок оказывается быстрее почти на порядок, чем std::mutex. В тесте измеряем реальное время выполнения.

Результаты сравнительного тестирования std::mutex и SpinLock.
Результаты сравнительного тестирования std::mutex и SpinLock.

Кодогенерация

Интересно взглянуть, какой код генерирует компилятор для нашего спинлока в бенчмарке выше. Достаточно добавить `-S -fverbose-asm`, чтобы получить на выходе ассемблерный исходник benchmark.s. Самый интересный его кусочек приведён ниже.

Ассемблерный листинг критической секции, ограниченной SpinLock, в benchmark.cc.
Ассемблерный листинг критической секции, ограниченной SpinLock, в benchmark.cc.

Этот код соответствует строкам 27-31, где многократно в критической секции, ограниченной спинлоком, инкрементируется счётчик. Видно, что компилятор подставил код lock() в строчки 676-685 ассемблерного листинга. Здесь и инструкция xchgb, и testb, и jne, которые все вместе реализуют CAS-цикл захвата блокировки. Чуть ниже в строке 691 блокировка снимается простой пересылкой нуля в нужное слово. Замечу, что компиляторы gcc и clang имеют встроенные функции __atomic_*, которые эквивалентны необходимым атомарным операциям.

Заключение

Здесь мы реализовали простейший вариант спинлока, который подойдёт для защиты лёгких операций в пространстве пользователя, провели тесты производительности и взглянули на результат кодогенерации. Кроме спинлока остаётся ещё много других полезных примитивов, реализация rw spinlock, использование futex'а, очереди и каналы, а также lock-free и wait-free структуры данных.