Эта статья послужит вам быстрым, но глубоким введением в низкоуровневую конкурентность.

Механизмы блокировки — важнейшая часть конкурентного программирования. Такие механизмы позволяют множественным потокам одновременно обращаться к разделяемым ресурсам, не мешая друг другу. Одна из самых популярных блокировок – это спинлок (циклическая блокировка), при которой применяется активное ожидание, механизм, позволяющий раз за разом проверять, не освободилась ли блокировка. Правда, при таком подходе будут тратиться драгоценные такты процессора, если блокировка зациклится и станет впустую потреблять ресурсы процессора. Для решения этой проблемы применяется подход под названием экспоненциальная выдержка. При экспоненциальной выдержке применяются постепенно нарастающие периоды ожидания, что позволяет не тратить ресурсы впустую.

В этой статье мы реализуем наш собственный упрощённый спинлок с экспоненциальной выдержкой. Для начала обсудим базовую идею, на которой основан спинлок — проблему активного ожидания. Затем разберём, что представляет собой экспоненциальная выдержка и обсудим, как повысить эффективность спинлоков. Затем поговорим об атомиках и о том, для чего они используются. После этого объясним, что представляют собой барьеры памяти, если они работают в тандеме. Далее рассмотрим образец реализации спинлока с экспоненциальной выдержкой, разберём достоинства и недостатки такого подхода. Наконец, напишем тестовую программу, которая поможет нам убедиться, что всё работает как надо. Начнём!

Спинлок

Спинлок — это тип блокировки, при которой применяется активное ожидание. Это механизм, позволяющий регулярно проверять, не освободилась ли блокировка. В сущности, идея проста: когда поток хочет обратиться к разделяемому ресурсу, он проверяет, доступна ли блокировка. Если блокировка не освободилась, то поток продолжает крутиться в цикле, проверяя доступность блокировки и так до тех пор, пока она не освободится.

Притом, что в некоторых сценариях спинлоки могут быть эффективны, повторюсь, что они могут приводить к неоправданной растрате ресурсов, если блокировка всякий раз удерживается в течение очень недолгого времени. В таком случае поток может израсходовать множество тактов процессора, пока просто крутится в цикле и проверяет доступность блокировки. Из-за этого может ухудшаться производительность и повышаться энергопотребление.

Проблема активного ожидания

Активное ожидание — типичная проблема при конкурентном программировании, когда поток постоянно проверяет условие цикла, тратя на это ресурсы процессора и дожидаясь, пока условие выполнится (станет равно true). В случае со спинлоком активное ожидание происходит, когда поток циклически раз за разом проверяет доступность блокировки.

Активное ожидание может приводить к снижению производительности, высокому энергопотреблению и замедлению реагирования. Для решения этой проблемы применяется метод, называемый экспоненциальной выдержкой.

Экспоненциальная выдержка

Экспоненциальная выдержка применяется в конкурентном программировании, чтобы уменьшить то время, в течение которого поток ожидает, чтобы условие результировало в true. Идея, на которой основана экспоненциальная выдержка — увеличивать время, затрачиваемое потоком на ожидание после каждой неуспешной попытки, а не проверять условие раз за разом в плотном цикле.

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

Атомики

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

В C++11 и более поздних версиях языка предоставляется шаблон std::atomic, упрощающий использование атомиков. Вот как использовать атомарную переменную int:

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter{0};

void increment_counter() {
    counter++;
}

int main() {
    std::thread t1(increment_counter);
    std::thread t2(increment_counter);
    std::thread t3(increment_counter);

    t1.join();
    t2.join();
    t3.join();

    // counter should be equal to 3
    std::cout << "counter value is: " <<  counter.load();
}

В данном примере мы используем атомарную int-переменную counter, при помощи которой отслеживается разделяемый счётчик. После этого определяем функцию increment_counter(), которая увеличивает счётчик на единицу. Мы создаём три потока, каждый из которых вызывает increment_counter(), а затем мы объединяем потоки и выводим на экран значение счётчика.

В шаблоне std::atomic предоставляются разнообразные методы для доступа к атомарным переменным и их изменения, например, load(), store(), fetch_add() и compare_exchange_strong(). Эти методы гарантируют, что операции над атомарными переменными выполняются атомарно, а когда необходимо — для обеспечения согласованности между потоками применяются барьеры памяти.

Барьеры памяти

Барьер памяти — это своеобразный аппаратный или программный механизм синхронизации, гарантирующий, что все обращения к памяти на конкретном процессоре выполняются в определённом порядке. С их помощью обеспечивается согласованность последовательных операций – эта модель, применяемая в конкурентном программировании, обеспечивает одинаковый порядок операций для всех потоков.

Именно барьеры памяти не позволяют переупорядочивать инструкции доступа к памяти как на уровне процессора, так и на уровне компилятора, что может привести к несогласованному поведению в конкурентных программах. Например, если два потока обращаются к разделяемой переменной, то барьер памяти может согласовать порядок операций чтения и записи в масштабах всех потоков.

Барьеры памяти бывают нескольких типов, и все они обеспечивают разные уровни синхронизации и гарантии упорядочивания. Вот наиболее распространённые типы барьеров памяти:

1. Барьеры компилятора: это инструкции, вставляемые компилятором во избежание переупорядочивания кода. Они гарантируют, что код будет выполняться именно в том порядке, в котором записан — так можно избежать некорректного поведения. Как правило, такие барьеры используются для оптимизации кода и повышения производительности, но в некоторых случаях могут применяться и для устранения проблем с конкурентностью.
2. Барьеры процессора: Барьеры процессора — это процессорные инструкции, гарантирующие, что операции над памятью выполняются в конкретном порядке. Они не позволяют процессору нарушать ход инструкций, и пренебрежение этим правилом в конкурентной программе приведёт к некорректному поведению. Как правило, процессорные барьеры реализуются при помощи специальных инструкций или протоколов когерентности кэша.
3. Барьер сохранения: Барьер сохранения (также называемый барьер записи) — это барьер памяти, гарантирующий, что все операции сохранения в память до достижения барьера будут видимы другим потокам. Барьеры сохранения не позволяют процессору переупорядочивать операции сохранения в память. В противном случае операция записи в одном потоке могла бы сработать до операции чтения в другом потоке.
4. Барьер загрузки: барьер загрузки (также называемый барьер чтения) — это барьер памяти, гарантирующий, что все операции загрузки в память после барьера будут видны актуальному потоку. Барьеры загрузки не позволяют процессору переупорядочивать операции загрузки в память. В противном случае операция чтения могла бы быть выполнена до операции записи в другом потоке.
5. Полный барьер: полный барьер (также именуемый тотальным) — это барьер памяти, гарантирующий, что все операции в памяти до барьера видимы всем потокам, а все операции после барьера видимы только текущему потоку. Полные барьеры обеспечивают наивысший уровень синхронизации и самые сильные гарантии упорядочивания. Обычно они используются, когда требуется максимальная синхронизация.

В C++11 и позже барьеры памяти обеспечиваются при помощи перечисления std::memory_order, применяемого с атомарными операциями и предоставляющего необходимый уровень синхронизации и барьеры памяти. В перечислении std::memory_order предусмотрено несколько вариантов упорядочивания памяти, в том числе, memory_order_relaxed, memory_order_acquire, memory_order_release, memory_order_acq_rel и memory_order_seq_cst.

Вот пример использования барьеров памяти с атомарными операциями:

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<int> counter(0);

void increment_counter() {
    counter.fetch_add(1, std::memory_order_relaxed);
}

int main() {
    std::thread t1(increment_counter);
    std::thread t2(increment_counter);
    std::thread t3(increment_counter);
    std::thread t4(increment_counter);
    std::thread t5(increment_counter);

    t1.join();
    t2.join();
    t3.join();
    t4.join();
    t5.join();


    // counter should be equal to 5
    int expected = 5;
    int got = counter.load(std::memory_order_relaxed);
    if (got != expected) {
        std::cout << "Value not correct! We were expecting: " << expected << " but got: " << got << '\n';
    }

    std::cout << "Value we were expecting is correct: " << got << '\n';
}

В данном примере мы применили метод fetch_add() к std::memory_order_relaxed, чтобы увеличить значение переменной counter на единицу. Как указывает опция std::memory_order_relaxed, никаких барьеров памяти не требуется, поскольку нам не приходится гарантировать никакой конкретной последовательности операций или синхронизации между потоками.

Реализуем спинлок с экспоненциальной выдержкой

Вот образец реализации спинлока с экспоненциальной выдержкой:

class SpinLock {
public:
    SpinLock() {}

    void lock() {
        retries = 0;
        while (flag.test_and_set(std::memory_order_acquire)) {
            // spin until the lock is released
            backoff();
            retries++;
        }
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }

private:
    void backoff() {
        const int max_retries = 8;
        if (retries < max_retries) {
            std::this_thread::yield();
        } else {
            auto delay = std::chrono::microseconds(1 << (retries - max_retries));
            std::this_thread::sleep_for(delay);
        }
    }

    std::atomic_flag flag = ATOMIC_FLAG_INIT;
    int retries{0};
};

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

Чтобы приобрести блокировку, мы применяем метод test_and_set() к std::memory_order_acquire. Так создаётся барьер памяти, гарантирующий, что все предыдущие операции записи будут видны потоку до тех пор, пока он не приобретёт блокировку. Затем мы применяем метод clear() к std::memory_order_release, чтобы высвободить блокировку, и тем самым выставляем барьер памяти, гарантирующий, что после снятия блокировки все последующие операции записи будут видны другим потокам.

В методе backoff(), который у нас вызывается внутри метода lock() в теле нашего цикла while, мы продолжаем крутиться, пока не достигнем жёстко запрограммированного количества попыток. Далее, израсходовав нашу квоту процессорного времени, мы просто уступаем процессор методом std::this_thread::yield(). После достижения показателя max_retries, мы будем постепенно выжидать всё большие отрезки времени (в микросекундах), а затем выполнять следующую попытку. Учтите: я исхожу из того, что вы не работаете с операционной системой реального времени, поэтому здесь мы работаем с аппроксимацией времени.

Тестируем спинлок

Напишем тестовую программу, в которой создадим 100 потоков и выполним по 10000 операций на поток. При этом мы будем увеличивать counter, а в конце проверим, в самом ли деле значение counter равно произведению количества потоков на количество взаимодействий.

#include <iostream>
#include <thread>
#include "SpinLock.hpp"

SpinLock lock;

void increment_counter(int& counter, int operations) {
    for (int i = 0; i < operations; i++) {
        lock.lock();
        counter++;
        lock.unlock();
    }
}

int main() {
    const int numThreads = 100;
    const int opsPerThread = 10000;

    int counter = 0;

    std::thread threads[numThreads];

    for (int i = 0; i < numThreads; i++) {
        threads[i] = std::thread(increment_counter, std::ref(counter), opsPerThread);
    }

    for (int i = 0; i < numThreads; i++) {
        threads[i].join();
    }

    std::cout << "counter value at the end: " << counter << std::endl;

    if (counter != numThreads * opsPerThread) {
        std::cerr << "Error: Counter value is incorrect!!! Bummer..." << std::endl;
        return 1;
    }

    std::cout << "The counter value is correct! Yay!!" << std::endl;

    return 0;
}

Заключение

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

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

Обращаю ваше внимание на то, что этот код не предназначается для использования в реальной практике и написан только в образовательных целях. Поэтому, как вы догадываетесь, на самом деле тут всё очень сложно. В любом случае, надеюсь, что вы узнали что-то новое, и вам было интересно! Мне – определённо. Удачи в программировании!

Примечание: книга «C++. Практика многопоточного программирования, 2-е издание» Энтони Уильямса отлично подойдёт вам в качестве вводной, если вы хотите понять эту сложную тему и попрактиковаться в ней