Lock-free структуры данных. Основы: Модель памяти

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

C++ издревле славится своей способностью на высоком уровне выражать низкоуровневые вещи. При разработке модели памяти C++11 стояла задача не нарушить этого свойства, то есть дать программистам максимальную гибкость. Проанализировав существующие на тот момент модели памяти других языков (в основном Java) и типичные примеры внутреннего устройства примитивов синхронизации и lock-free алгоритмов, разработчики стандарта выдвинули не одну, а три модели памяти:

• sequential consistency (последовательная согласованность)
• acquire/release семантика
• relaxed memory ordering (слабый порядок)

Все эти модели памяти определяются в C++ одним перечислением – std::memory_order, имеющим следующие 6 констант:

• memory_order_seq_cst – указывает на для sequential consistent модель
• memory_order_acquire, memory_order_release, memory_order_acq_rel, memory_order_consume – относятся к модели, основанной на acquire/release семантике
• memory_order_relaxed – указывает на relaxed-модель

Прежде чем рассматривать эти модели, следует определиться, как указывать модель памяти в программе. Здесь мы должны снова вернуться к атомарным операциям.
Операции, которые я приводил в статье про атомарность, по большому счету не имеют ничего общего с определенными в C++11, так как в стандарте желаемый memory_order указывается как аргумент атомарной операции. Тому есть две причины:

• Семантическая: по сути, желаемое упорядочение (барьер памяти) относится именно к атомарной операции, которую мы выполняем. Расстановка барьеров в read/write-подходе является шаманством именно потому, что сам барьер вообще никак семантически не связан с тем кодом, в котором он присутствует, — просто инструкция среди равнозначных. Кроме того, расстановка read/write барьеров очень зависит от архитектуры.
• Практическая: Intel Itanium имеет особый, отличный от других архитектур, способ указания упорядочения памяти для инструкций чтения/памяти и RMW-операций. В Itanium тип упорядочения указывается как опциональный флаг самой инструкции: acquire, release или relaxed. Причем отдельных инструкций (барьеров памяти) для указания acquire/release-семантики в архитектуре не предусмотрено, есть только инструкция тяжелого полного барьера памяти

Вот как выглядят операции atomic<T> на самом деле: каждая специализация класса std::atomic<T> должна иметь как минимум следующие методы

void store(T, memory_order = memory_order_seq_cst);
T load(memory_order = memory_order_seq_cst) const;
T exchange(T, memory_order = memory_order_seq_cst);
bool compare_exchange_weak(T&, T, memory_order = memory_order_seq_cst);
bool compare_exchange_strong(T&, T, memory_order = memory_order_seq_cst);

void atomic_thread_fence(memory_order);
void atomic_signal_fence(memory_order);

Как видно, моделью памяти по умолчанию в C++11 является sequential consistency. Её-то мы и рассмотрим первой. Но сначала несколько слов о барьерах компилятора.

Барьеры компилятора

Кто может переупорядочить код, написанный нами? Мы выяснили, что это может делать процессор. Но есть ещё один источник переупорядочения – компилятор.
Многие способы оптимизации (особенно глобальной) и эвристики разрабатывались (и разрабатываются по сей день) в предположении (быть может, неявном) однопоточного выполнения. Компилятору довольно трудно (скорее, даже теоретически невозможно) понять, что ваш код – многопоточный. Поэтому компилятору нужны подсказки – барьеры. Такой барьер говорит компилятору: не смей код перед барьером перемещать (смешивать) в код за барьером, и наоборот. Сам барьер компилятора не генерирует никакого кода.
Для MS Visual С++ барьер компилятора – это псевдофункция _ReadWriteBarrier() (это имя меня всегда ставило в тупик: полная ассоциация с read/write memory barrier – самым тяжелым барьером памяти). Для GCC и Clang – это изящная конструкция

__asm__ __volatile__ ( "" ::: "memory" )

Надо отметить, что ассемблерные вставки __asm__ __volatile__ ( … ) также являются в некотором роде барьером для GCC/Clang: компилятор не имеет права ни выкидывать, ни перемещать их вверх/вниз по коду (об этом говорит модификатор __volatile__).
Константы memory_order воздействуют на компилятор, поддерживающий C++11, в той же мере, как и на процессор, — они являются барьером компилятора, ограничивая возможности компилятора по переупорядочению (то есть оптимизации) нашего кода. Поэтому указание особых барьеров компилятора не требуется, если, конечно, компилятор полностью поддерживает новый стандарт.

Sequential consistency

Предположим, мы реализовали lock-free стек (это самая простейшая из lock-free структура данных), скомпилировали его и тестируем. И получаем корку (core file). В чем дело? Мы станем искать ошибку, прогоняя в уме (никакой дебаггер нам здесь не поможет) строку за строкой реализацию нашего lock-free стека, пытаясь сэмулировать многопоточность и ответить на вопрос, какое фатальное сочетание выполнения строки K потока 1 и одновременно строки N потока 2 привело к краху. Быть может, мы найдем и исправим какие-то ошибки, но все равно – наш lock-free стек будет падать. Почему?
Оказывается, то, что мы делаем, пытаясь найти ошибку и сопоставляя в уме строки программы для выполняющихся одновременно потоков, называется гарантией sequential consistency. Это строгая модель памяти, которая предполагает, что процессор делает все именно в том порядке, как написано в программе. Например, для такого кода:

// Thread 1
atomic<int> a, b ;
a.store( 5 );
int vb = b.load();

// Thread 2
atomic<int> x,y ;
int vx = x.load() ;
y.store( 42 ) ;

допустимыми для sequential consistency являются любые сценарии выполнения, кроме тех, которые меняют местами a.store / b.load и x.load / y.store. Заметим, что в этом коде я не указываю явно memory_order-аргумент в load/store, — я полагаюсь на значение аргумента по умолчанию.
Точно такая же гарантия распространяется и на компилятор: компилятору запрещено переупорядочивать наш код таким образом, что операции после memory_order_seq_cst были бы перемещены выше этого барьера, и наоборот, — операции перед seq_cst-барьером не могут быть опущены ниже барьера.
Модель sequential consistency интуитивно близка человеку, но имеет очень существенный недостаток: она слишком строга для современных процессоров. Она приводит к самым тяжелым барьерам памяти, не позволяя процессору применить в полной мере спекулятивное выполнение. Поэтому новый стандарт C++ принял такой компромисс:

• Модель sequential consistency принять как модель по умолчанию для атомарных операций за её строгость и понятность
• Ввести в C++ другие, более слабые модели памяти, позволяющие реализовать потенциал современных архитектур

В качестве дополнения к sequential consistency была предложена модель, основанная на acquire/release семантике.

Acquire/release семантика

Из названия acquire-release семантики можно сделать вывод, что эта семантика как-то связана с захватом (acquire) и освобождением (release) ресурсов. Действительно, это так. Захват ресурса – это его чтение из памяти в регистр, освобождение – запись из регистра в память:

load memory, register ;
membar #LoadLoad | #LoadStore ; // acquire-барьер

// Операции внутри acquire/release-секции
...

membar #LoadStore | #StoreStore ; // release-барьер
store regiser, memory ;

Как видно, в этом коде мы обошлись без применения тяжелого барьера #StoreLoad. Также можно заметить, что как acquire-барьер, так и release-барьер представляют собой полубарьеры: acquire не упорядочивает предыдущие store-операции с последующими load/store, а release не упорядочивает предыдущие load с последующими, равно как и предыдущие store с последующими load. Это относится как к процессору, так и к компилятору.
Acquire/release являются барьерами для всего кода, который заключен между acquire/release. Некоторые операции перед acquire-барьером могут просочиться (могут быть переупорядочены процессором или компилятором) внутрь acquire/release-секции, также как и некоторые операции после release-барьера могут быть перенесены вверх (опять-таки, процессором или компилятором), внутрь acquire/release-секции. Но операции, заключенные внутри acquire-release, не выйдут за её пределы.

Наверно, самый простой пример применения acquire/release-семантики – это spin-lock.

Вот как выглядит простейший spin-lock на acquire/release (знатоки C++ укажут, что для реализации spin-lock надо бы использовать специальный тип atomic_flag, но я построю spin-lock на атомарной переменной (даже не булевой) – так наглядней с точки зрения этой статьи):

class spin_lock 
{
    atomic<unsigned int> m_spin ;
public:
    spin_lock(): m_spin(0) {}
    ~spin_lock() { assert( m_spin.load(memory_order_relaxed) == 0);}

    void lock()
    {
        unsigned int nCur;
        do { nCur = 0; }
        while ( !m_spin.compare_exchange_weak( nCur, 1, memory_order_acquire ));
    }
    void unlock()
    {
        m_spin.store( 0, memory_order_release );
    }
};

Заметим, что в этом коде то, что compare_exchange принимает свой первый аргумент по ссылке и изменяет его, если CAS неудачен, мне очень мешает! Приходится писать do-while цикл с непустым телом.
В методе lock овладения блокировкой я использую acquire-семантику, а в методе unlock – release-семантику (кстати, acquire/release семантика повела свою историю как раз из примитивов синхронизации: разработчики стандарта внимательно проанализировали реализацию различных примитивов синхронизации и вывели паттерн acquire/release.) Как я писал выше, барьеры, проставляемые в этом случае, не позволяют коду, заключенному между lock() и unlock(), просочиться наружу, — то, что нам и нужно! А атомарность переменной m_spin гарантирует нам, что пока m_spin=1, никто не сможет овладеть блокировкой, — опять то, что и требуется!
В алгоритме мы видим, что я использую compare_exchange_weak. Что это такое?

Слабый и сильный CAS

Как вы помните, архитектура процессоров может относиться к одному из двух классов: либо процессор реализует атомарный примитив CAS (compare-and-swap), либо пару LL/SC (load-linked/store-conditional). Пара LL/SC позволяет реализовать атомарный CAS, но сама по себе не является атомарной в силу многих причин. Одна из этих причин – код, выполняющийся внутри LL/SC, может быть прерван операционной системой; например, именно в этот момент ОС принимает решение вытеснить текущий поток. Соответственно, store-conditional потом, после возобновления, не сработает. То есть наш CAS возвратит false, хотя на самом деле причина этого false может быть не в данных, а в стороннем событии – прерывании потока.
Именно это соображение подвигло разработчиков стандарта ввести два примитива compare_exchange – слабый (weak) и сильный (strong). Называются эти примитивы соответственно compare_exchange_weak и compare_exchange_strong. Слабая версия может быть неудачной, то есть возвратить false, даже в том случае, если текущее значение переменной равно ожидаемому. То есть слабый CAS может нарушить семантику CAS и возвратить false, когда на самом деле надо возвращать true (но не наоборот!) Сильный CAS этого сделать не может: он строго следует семантике CAS. Конечно, это может чего-то стоить.
Когда следует применять слабый, а когда – сильный CAS? Я для себя вывел такое правило: если CAS используется в цикле (а это основной паттерн использования CAS) и в цикле нет наворота операций (то есть тело цикло – легкое), то я использую compare_exchange_weak – слабый CAS. В противном случае – сильный compare_exchange_strong.

Memory order для acquire/release семантики

Как я отмечал выше, для acquire/release семантики определены следующие значения memory_order:

• memory_order_acquire
• memory_order_consume
• memory_order_release
• memory_order_acq_rel

Для чтения (load) допустимыми являются значения memory_order_acquire и memory_order_consume.
Для записи (store) – только memory_order_release.
Memory_order_acq_rel является допустимым только для RMW-операций – compare_exchange, exchange, fetch_xxx. Вообще, атомарный RMW-примитив может обладать acquire-семантикой memory_order_acquire, release-семантикой memory_order_release или той и другой вместе — memory_order_acq_rel. Для RMW-операций эти константы определяют именно семантику, так как read-modify-write примитив одновременно выполняет атомарные чтение и запись. Семантически RMW-операция может рассматриваться либо как acquire-чтение, либо как release-запись, либо как то и другое.
Определить семантику RMW-операции можно только в алгоритме, где она применяется. Часто в lock-free алгоритмах можно выделить части, чем-то похожие spin-lock: в начале мы получаем (acquire) некий ресурс, что-то делаем (обычно вычисляем новое значение) и в конце мы устанавливаем (release) новое значение ресурса. Если получение ресурса выполняется RMW-операцией (обычно это CAS), то такая операция вполне вероятно имеет acquire-семантику. Если установка нового значения выполняется RMW-примитивом (CAS или exchange), то он вполне вероятно имеет release-семантику. “Вполне вероятно” вставлено неспроста: требуется детальный анализ алгоритма, прежде чем можно будет понять, какая семантика подходит для RMW-операции.
Если же RMW-примитив выполняется отдельно (невозможно выделить паттерн acquire/release), то возможны 3 варианта для семантики:

• memory_order_seq_cst – RMW-операция является ключевым звеном алгоритма, переупорядочение кода, перенос чтения и записи вверх-вниз может привести к ошибке
• memory_order_acq_rel – чем-то аналогично memory_order_seq_cst, но RMW-операция находится внутри acquire/release-секции
• memory_order_relaxed – перенос RMW-операции (её load и store-частей) вверх-вниз по коду (например, в пределах acquire/release секции, если операция находится внутри такой секции) не приводит к ошибкам

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

Consume-семантика

Существует отдельная, более слабая, разновидность acquire-семантики – consume-семантика чтения. Эта семантика была введена как «дань памяти» процессору DEC Alpha.
Архитектура Alpha имеет существенное отличие от других современных архитектур: она могла нарушать зависимость по данным. В таком примере кода:

struct foo {
	int x;
	int y;
} ;
atomic<foo *> pFoo ;

foo * p = pFoo.load( memory_order_relaxed );
int x = p->x;

Она могла переупорядочить чтение p->x и собственно получение p (не спрашивайте меня, как такое возможно, — это свойство Alpha; с Alpha мне не приходилось работать, так что ни подтвердить, ни опровергнуть это я не могу).
Для предотвращения такого переупорядочения была введена consume-семантика. Она применима для атомарного чтения указателя на структуру, после чего следует чтение полей структуры. В данном примере указатель pFoo следует читать так:

foo * p = pFoo.load( memory_order_consume );
int x = p->x;

Consume семантика стоит где-то посередине между relaxed- и acquire-семантикой чтения. На многих современных архитектурах она отображается на relaxed-чтение.

И ещё раз о CAS

Выше я привел интерфейс atomic<T> с двумя CAS – weak и strong. На самом деле, существует ещё два варианта CAS – с дополнительным аргументом memory_order:

bool compare_exchange_weak(T&, T, memory_order successOrder, memory_order failedOrder );
bool compare_exchange_strong(T&, T, memory_order successOrder, memory_order failedOrder );

Что это за аргумент – failedOrder?
Вспомним, что CAS – это read-modify-write примитив. Даже в случае неудачи он выполняет атомарное чтение. Аргумент failedOrder как раз и определяет семантику этого чтения в случае неудачи CAS. Поддерживаются те же значения, что для обычного чтения.
На практике указание «семантики при неудаче» требуется довольно редко. Конечно, всё зависит от алгоритма!

Relaxed-семантика

Наконец, третий тип модели атомарных операций – relaxed-семантика, которая применима ко всем атомарным примитивам – load, store, всем RMW, — и которая не накладывает почти никаких ограничений и поэтому позволяет процессору переупорядочивать почти в полной мере, демонстрируя свою полную мощь. Почему почти?
Во-первых, требование стандарта – соблюдать атомарность relaxed-операций. То есть даже relaxed-операция должна быть неделимой, без частичных эффектов.
Во-вторых, для атомарной relaxed-записи стандартом запрещена спекулятивная запись.
Эти требования могут налагать ограничения на реализацию атомарных relaxed-операций в некоторых weakly ordered архитектурах. Например, relaxed load атомарной переменной на Intel Itanium реализуется как load.acq (acquire-чтение, не путать Itanium acquire с C++ acquire).

Happens-before, synchronized-with и прочие отношения

Тот, кто знаком со стандартом C++11, спросят: «А где же отношения, определяющие семантику атомарных операций, — happened before, synchronized-with и прочие?»
Я отвечу – в стандарте.
Хорошее рассмотрение именно в терминах стандарта дано в книге Энтони Вильямса C++ Concurrency in Action (есть русский перевод), пятая глава. Там есть много детально разобранных в терминах отношений примеров.
Разработчики стандарта сделали важную работу – они вывели правила (отношения) для модели памяти C++, причем эти правила описывали не расстановку барьеров памяти, а гарантии взаимодействия потоков. В результате получилось компактное аксиоматическое описание модели памяти C++.
К сожалению, применять эти отношения на практике чрезвычайно сложно по причине огромного количества вариантов, которые требуется рассмотреть для доказательства корректности указания memory_order в более-менее сложном lock-free алгоритме. Именно поэтому моделью по умолчанию является sequential consistency – эта модель вовсе не требует указывать какие-то специальные memory_order-аргументы для атомарных операций. Как отмечалось, эта модель является и самой тормозной.
Применение более слабых моделей – acquire/release или relaxed – требует верификации алгоритма.

Верификация lock-free алгоритмов

До недавнего времени мне был известно только одно средство верификации — библиотека relacy Дмитрия Вьюкова. К сожалению, это средство требует построения особой модели. Фактически, следует сначала построить упрощенную модель lock-free алгоритма в терминах библиотеки relacy (почему упрощенную? – потому что, строя модель, обычно убираешь всякие полезные фенечки, не относящиеся непосредственно к рассматриваемому алгоритму). Эту модель затем нужно отладить, и только потом, когда все отлажено и все атомарные операции снабжены корректными memory_order-аргументами, можно написать уже production-версию алгоритма. Такой подход идеально подходит разработчикам lock-free алгоритмов и структур данных, — тем, кто их придумывает. Собственно, для разработчиков на такой модели всё и заканчивается. Но имплементаторам (мне нравится русский термин «воплотитель» – он подчеркивает, что субъект ничего сам не придумывает, а только творчески воплощает в жизнь чью-то мысль) такой двухступенчатый подход зачастую не подходит (вследствие природной лени), — им нужно всё здесь и сейчас, и желательно побыстрее.
Видимо, сам автор relacy, Дмитрий Вьюков, понимал этот недостаток своего детища (никакой иронии – relacy действительно прорывной проект в своей области), и однажды в интервью на форуме Intel высказал мысль – сделать так, чтобы средство верификации (relacy или что-то подобное) было внедрено внутрь стандартной библиотеки. Тогда никакой дополнительной модели делать уже не придется. Чем-то это напоминает концепцию safe iterators в дебажной STL.
Недавно Дмитрий вместе со своими соратниками из Google представили новый инструмент ThreadSanitizer. Этот инструмент позволяет проверить наличие data race (гонки по данным) в программе, то есть, фактически, правильное применение упорядочения в атомарных операциях. Более того, этот инструмент внедрен даже не в STL, а ещё глубже — в компилятор (Clang 3.2, а затем в GCC 4.8).
Применение ThreadSanitizer довольно простое – достаточно скомпилировать программу с определенными ключами, сделать тестовый прогон — и наслаждаться изучением обширных логов. Я в своей библиотеке libcds планирую в ближайшее время применить данный инструмент, дабы убедиться, какой я олух что в libcds всё в порядке.

«Я не понимаю...» — Критика стандарта

Да, я беру на себя смелость критиковать стандарт C++11! Я не понимаю, почему в стандарте был выбран подход, когда семантика указывается аргументом атомарной операции. Куда логичнее было бы воспользоваться шаблонами и определить что-то такое:

template <typename T>
class atomic {
    template <memory_order Order = memory_order_seq_cst>
    T load() const ;

    template <memory_order Order = memory_order_seq_cst>
    void store( T val ) ;

    template <memory_order SuccessOrder = memory_order_seq_cst>
    bool compare_exchange_weak( T& expected, T desired ) ;

   // и так далее
};

Поясню, почему я считаю, что такое определение более корректно.
Как уже неоднократно указывалось, семантика атомарных операций влияет не только на процессор, но и на компилятор. Для компилятора семантика выступает в роли [полу]барьеров оптимизации. Кроме того, компилятор должен следить за тем, чтобы атомарной операции была назначена допустимая семантика (вспомните, что, например, release-семантика неприменима к чтению). Поэтому семантика должна быть определена на этапе компиляции. Я не представляю, что будет делать компилятор в таком коде:

extern std::memory_order currentOrder ;
std::Atomic<unsigned int> atomicInt ;
atomicInt.store( 42, currentOrder ) ;

Этот код формально не противоречит стандарту C++11. Тем не менее, все, что может здесь сделать компилятор, это:

• либо выдать ошибку, — тогда зачем вообще допускается такой интерфейс атомарных операций, который может привести к ошибке?
• либо применить семантику sequential consistent – из соображений «не было бы хуже». Но тогда переменная currentOrder просто игнорируется, а наша программа получает тормоза, которых мы хотели избежать
• либо сгенерировать switch/case по всем возможным значениям currentOrder. В этом случае вместо одной-двух ассемблерных инструкций мы получим неэффективный код. Да и проблема подходящей для операции семантики не решается, — вполне возможно вызвать release-чтение или acquire-запись

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

std::Atomic<int> atomicInt ;
atomicInt.store<std::memory_order_release>( 42 ) ;
// или даже так:
atomicInt.template store<std::memory_order_release>( 42 ) ;

Но, по моему мнению, такая «угловатость» компенсируется преимуществами шаблонного подхода, — однозначностью указания семантики операции во время компиляции.
Единственное объяснение C++11 подхода, которое приходит мне на ум, — пресловутая совместимость с C. Ведь помимо класса std::atomic стандарт C++11 вводит свободные C-шные атомарные функции atomic_load, atomic_store и пр.
Отмечу, что в libcds во времена, когда C++11 ещё был только в проекте, я реализовал атомарные примитивы именно в терминах шаблонов. Потом пришел к мнению, что надо все-таки следовать стандарту, и перелопатил очередную версию libcds под интерфейс атомарных операций C++11.

Конец Основ

Эта статья – заключение Основ.

Конец основ по мнению Гугла

Именно эту картинку выдал мне Гугл первой по запросу «конец Основ». А что, какая-то логика в этом есть…

Далее обязуюсь рассказывать уже “по теме” – lock-free структуры данных и сопутствующие алгоритмы.

Автор: khizmax

Источник