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


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

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

    Исторический миниобзор
    Поначалу производители не публиковали открытую спецификацию модели памяти процессора, то есть набор правил, по которым weakly-ordered процессор работает с памятью, тем самым надеясь, я думаю, выгадать себе пространство для маневра в будущем (действительно, зачем ограничивать себя в развитии архитектуры, беря какие-то обязательства?) Но затем производители выпустили джинна из бутылки, — гигагерцы уперлись в потолок, и производители начали повсеместно внедрять многоядерность. В результате реальная мультипоточность пошла в массы. Первыми забили тревогу разработчики операционных систем: им надо поддерживать многоядерность в ядре, а спецификаций weakly ordered архитектуры нет. Затем подтянулись органы стандартизации языков: программы становятся всё более распараллеленными, пора стандартизировать модель памяти языка, дать какие-то гарантии при конкурентном многопоточном выполнении, а спецификаций модели памяти процессоров нет. В результате на сегодняшний день практически у всех современных архитектур процессоров есть открытые спецификации модели памяти, и немалую роль в появлении таких спецификаций сыграла работа над стандартами модели памяти Java, .NET, C++.

    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);
    

    Отдельные барьеры памяти
    Конечно, С++11 имеет и отдельные свободные функции барьера памяти:
    void atomic_thread_fence(memory_order);
    void atomic_signal_fence(memory_order);
    

    atomic_thread_fence позволяет, фактически, использовать подход отдельных read/write-барьеров, признанный устаревшим. Хотя сами способы упорядочения memory_order не предоставляют способа указать read-барьер (Load/Load) или write-барьер (Store/Store).
    atomic_signal_fence предназначена для использования в обработчиках сигналов. Как правило, эта функция не генерирует никакого кода, но является барьером компилятора.

    Как видно, моделью памяти по умолчанию в 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.
    Lock-free и spin-lock
    Может показаться странным, что в статье цикла о lock-free алгоритмах я привожу пример алгоритма блокировки. Требуется объясниться.
    Я не ярый поклонник чистого lock-free, ни в коем случае. Да, чистый lock-free (а тем паче wait-free) алгоритм меня радует, и радует вдвойне, если получается его реализовать (не всегда такое происходит). Я являюсь сторонником прагматического подхода: всё, что эффективно, то хорошо. Поэтому я не брезгую применять блокировки там, где они могут дать выгоду. Spin-lock может дать значительную выгоду по сравнению с обычными мьютексами, если он «охраняет» очень маленький кусочек кода – несколько ассемблерных инструкций. К тому же 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).
    Реквием по Итаниуму
    В своих статьях я часто упоминаю Intel Itanium. Может возникнуть впечатление, что я фанат архитектуры Itanium, которая, похоже, медленно умирает. Нет, я не фанат, но…
    VLIW-архитектура Itanium в чем-то отличается от других по принципу построения системы команд. Memory ordering указывается как суффикс load/store/RMW-инструкций, — такого нет в других современных архитектурах. Даже используемые термины – acquire, release, — наводят мысль, не списан ли C++11 с Итаниума.
    Если мы вспомним историю, Itanium – это та архитектура (или ее потомок), на которой мы все сейчас бы сидели, если бы в свое время AMD не подсуетилась и не выпустила AMD64 – 64-битное расширение x86. Intel же в это время неспешно разрабатывала новую архитектуру под 64-битные вычисления. И туманно намекала об этой новой архитектуре. Из намеков можно было понять, что нас ждет Итаниум на десктопе. Кстати, майкросовтовские порт Windows и компилятора Visual C++ под Itanium также косвенно свидетельствуют об этом (кто-нибудь видел работающие винды на итаниуме?) Но шустрая AMD разрушила планы Intel, и последней пришлось срочно догонять, внедряя 64 бита в x86. Итаниум так и остался в серверном сегменте, где потихоньку умирал, не получая должных ресурсов на развитие.
    Между тем, Итаниум со своим “пучком” инструкций в “очень длинном слове” (VLIW – very long instruction word) является до сих пор интересным и прорывным процессором. То, что современные процессоры делают сами, — загружают свои исполнительные блоки, переупорядочивая операции, — в Итаниуме было доверено компилятору. Но компиляторы не справились с такой задачей и генерировали (и до сих пор генерируют) не слишком оптимальный код. В результате производительность Итаниума проседала в несколько раз – и только за счет нерационального (с точки зрения Итаниума) распределения инструкций по “пучкам” VLIW (не помню, как это называется в Итаниуме, но перевод – “пучок” – запомнился), что приводило к нерациональной загрузке его исполнительных блоков.
    Так что Itanium – это наше нереализованное будущее.
    Хотя, кто знает, быть может, ещё рано писать реквием?..


    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 – требует верификации алгоритма.

    UPD: Хабражитель cheremin справедливо указал на неточность последнего утверждения. Действительно, сама по себе sequential consistency не гарантирует ничего, — можно написать чушь и с её использованием. Поэтому уточняю: верификация lock-free алгоритма требуется всегда, для любой модели памяти, а в случае слабых моделей — требуется особо.


    Верификация 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 всё в порядке.
    Важность верификации для архитектуры x86
    Архитектура x86, пожалуй, является менее всего расслабленной (weakly-ordered) среди всех расслабленных. Это её достоинство, но в этом же кроется и главная опасность для lock-free алгоритмов: то, что будет надежно работать в x86, может быть совершенно неработоспособным на процессорах других архитектур.
    А дело все в том, что многие из memory_order-значений отображаются в коде в null (даже не в nop!), — x86 просто не требует этих барьеров. Например, release-семантика записи – это обычный атомарный mov из регистра в память, такой же mov применяется для relaxed-записи.
    Поэтому отлаживать lock-free алгоритмы, претендующие на общеупотребительность для любой архитектуры, на x86-платформе необходимо только с каким-либо средством верификации или эмулятором более расслабленной модели памяти.


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


    Да, я беру на себя смелость критиковать стандарт 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 структуры данных и сопутствующие алгоритмы.

    • +66
    • 63,5k
    • 8
    Поделиться публикацией

    Комментарии 8

      +2
      >Применение более слабых моделей – acquire/release или relaxed – требует верификации алгоритма.

      Тут очень двусмысленно звучит — как будто, если вы используете SC-модель доступа к атомикам, то верификация вообще не нужна. Даже если мы говорим только про отсутствие data race (а не про race conditions) — SC-семантика гарантирует вам data race free только и именно для тех переменных, к которым вы обращаетесь через SC-примитивы. Для всех остальных переменных ничего априори не гарантируется, все гарантии необходимо выводить через те самые happens-before, за которыми вы послали так далеко :). А ведь ни одна разумная программа не состоит только из атомиков, так что даже используя только SC-атомики можно легко и непринужденно получить код с гонками за счет «обычных» переменных, которые не несут явной спецификации memory-order. Мне кажется, это ваше утверждение стоит уточнить, во избежание
        0
        Согласен, во фразе, наверное, не хватает "особо требует верификации".
        Про data race — тоже согласен. По сути, обращение к атомарной переменной — это всегда data race; можно сказать, что это легализованный стандартом data race, все остальные — UB.
        Про отношения happend-before и пр. Подготавливая эту заметку, я метался между подходом C++11 (отношениями) и тем, из чего вырос этот подход — барьерами. Не умаляя достоинств отношений и аксиоматики, хочу сказать, что всё же более приземленный подход, основанный на постановке барьеров, мне импонирует больше, он для меня более понятен и более применим. Барьер я могу пощупать, он материален, он воплощается в инструкции процессора. Об отношениях пусть говорят люди более сведущие, например, А.Вильямс.
        Я не видел работ, объясняющих расстановку memory ordering с точки зрения happens-before и прочих в чем-то более сложном, чем стек или самая простая очередь. Да, существует ряд исследований, посвященных попыткам автоматизации расстановки memory ordering в алгоритмах (насколько помню, Dechev и другие), но серьезных успехов к настоящему времени не достигнуто, насколько я знаю.
        Мне кажется, что для модели памяти C++11 не хватает типичных паттернов применения. По моим наблюдениям, такие паттерны все-таки существуют, по крайней мере в алгоритмах lock-free структур данных, но пока не нашлась пресловутая «банда четырех» для их обнаружения и «легализации».
          +1
          >По сути, обращение к атомарной переменной — это всегда data race; можно сказать, что это легализованный стандартом data race, все остальные — UB

          На мой взгляд, data race — это само по себе и есть соглашение. Соглашение о том, какие конкурирующие инструкции работы с памятью мы считаем легальными, а какие ведут к потенциально нехорошему поведению. Т.е. data race — это и есть название для тех паттернов конкурирующего доступа к памяти, которые порождают что-то нехорошее. А обычное определение «запись и чтение/запись из разных потоков, не упорядоченное SA» — просто показывает, какие конфликты можно разрулить на уровне процессора/контролера памяти/компилятора, а какие конфликты требуют участия программиста, потому что эффективно их разрулить автоматически пока невозможно.

          >Барьер я могу пощупать, он материален, он воплощается в инструкции процессора. Об отношениях пусть говорят люди более сведущие, например, А.Вильямс.

          Я думаю, это просто С-шный бэкграунд сказывается. В яве к happens-before уже привыкли. И это большой вопрос, на самом деле, что первично — нотация happens-before восходит еще к статье Лампорта из 70-х, когда еще писали в терминах явных сообщений между узлами, а не в терминах shared memory.

          Если честно, мне как раз не очень понятно, как вы целостно рассуждаете о корректности алгоритма в терминах барьеров? Да еще и кроссплатформенно — т.е. когда вы не можете явно описать, как именно реализован этот барьер на этой архитектуре, что за конкретные действия за ним стоят. На мой взгляд, нотация относительного порядка (aka happens-before) единственный достаточно универсальный способ рассуждать о взаимодействии потоков, это как раз семантика барьеров должна описываться в терминах happens-before. Правда, я не вдавался особо в глубины C++ MM, но я помню дискуссии в concurrency-interest, где Ханс Боэм писал, что явные барьеры в C-MM оставлены в основном для обратной совместимости, чтобы не нужно было переписывать уже существующие алгоритмы с 0. Но вообще, как я понял, он считает их рудиментом, и довольно опасным рудиментом — с той точки зрения, что с ними сложнее писать корректный кроссплатформенный код.
            0
            Да, вы правы, наверное, сказывается C-шный подход. Я не знаток модели памяти явы, слышал только, что в ней применяется модель sequential consistency, и существует довольно обширное её описание. Собственно, при проектировании модели памяти C++ решали две задачи: добиться более компактного описания (за это ратовал, вроде бы, тот же H.Boehm) + большей свободы выбора (= большей эффективности кода, где это можно).

            Как я рассуждаю в терминах барьеров — хороший вопрос. На самом деле, все довольно просто: я рассуждаю в терминах абстрактных memory ordering, заданных стандартом, при этом имея в виду, что за ними кроется, — в основном это переупорядочение компилятором (acquire/release-полубарьеры), и только во вторую очередь — процессором. При этом как реализован тот или иной memory ordering на конкретной архитектуре, мне не важно, — я надеюсь на реализацию atomic в STL. К сожалению, мне пришлось спускаться ниже и делать свой atomic-велосипед. Тому было (частично и есть) две причины:
            • во времена моих первых шагов не было C++11
            • разработчики компиляторов до сих пор, похоже, не сошлись во мнении, как должна быть реализована C++11 MM. На это намекает недавно обнаруженный баг в libcds с использованием Clang + libc++ (родная реализация STL для Clang). Опыт учит — ищи ошибку прежде всего у себя, но странное поведение, — крах в однопоточном коде, где всё должно работать и на relaxed atomic, — наводит на мысль, что дело все-таки в компиляторе

            Мыслить в терминах отношений happens-before и пр. у меня как-то не особо получается. Когда вижу чью-либо статью, основанную на отношениях, — кажется, всё понимаю, а вот сам применить на практике — увы… Судя по обилию блогов/заметок о C++11 atomic, такой мозговой клинч наблюдается не только у меня, — многие в разговоре об atomic переходят к рассуждениям о барьерах. Быть может, просто не хватает практики — «об этом надо говорить (и спорить)».
            Я согласен, что отношения — более правильный подход. Вот только он слишком абстрактен, приводит к огромным по размеру выкладкам в случае более-менее сложного алгоритма, в котором взаимодействуют более двух atomic, и пока ещё нет инструментов (точнее, только-только появляются первые) по проверке его применения на практике (инструментов верификации).
            Проблема чем-то напоминает понятия формальной системы и её интерпретации: можно построить очень интересную формальную теорию, но найти ей интерпретацию, то есть её воплощение в реальном мире, бывает просто невозможно. Путь познания, как правило, другой: от интерпретации (наблюдаемого в жизни) — к формальному описанию. В нашем частном случае формальная модель — это happeds-before, synchronized-with и пр. отношения, а интерпретация — в конечном счете, банальные барьеры.

            Вообще, все сказанное мной в статьях и комментариях, — это мое ИМХО, кое в чем я до конца не уверен. Например, в том, правильно ли я проставляю memory ordering в libcds ;-)
              +1
              >Я не знаток модели памяти явы, слышал только, что в ней применяется модель sequential consistency, и существует довольно обширное её описание.

              Да, канонически в яве все synchronization actions действительно имеют SC-семантику. Модель сама по себе не такая уж обширная. Обширное описание, скорее, есть у причин почему она такая, какая есть, и как к этому пришли — с этой точки зрения, уверен, описание модели C++ будет только еще более обширным. Но есть такая тонкость, что в яве нет undefined behavior по изначальному дизайну языка. Потому примерно половина объема (и 3/4 сложности) модели памяти в яве это именно попытка задать, пусть очень сложную, но все-таки определенную семантику даже коду с гонками. Попытка эта, в общем-то, провалилась — через пару лет после публикации и реализации в этой части были обнаружены баги, которые не позволяли реализовывать важные оптимизации, поэтому существующие реализации JVM фактически нарушают спецификацию где-то в темных углах кода с data race. Есть несколько предложений, как исправить ошибки, но все они не совместимы с текущей версией JMM, поэтому пока все просто закрывают на это глаза. Как я понимаю, этот фэйл является одной из причин почему сейчас гуру concurrency (Ханс Боэм, Даг Ли, и прочие) в один голос повторяют «data race is evil».
              Если не брать эту темную сторону, то оригинальная JMM ни разу не сложнее CMM, даже проще — потому что есть только два варианта memory_ordering: relaxed/SC, причем используемый вариант привязан к типу переменной изначально, а не к конкретной операции доступа: есть volatile переменные, все операции с которыми всегда SC, и есть обычные переменные, которые всегда relaxed. Это, собственно, второй ее недостаток — очевидно, что SC несовместимо со scalability, без введения чего-то типа acquire/release/consume нереально линейно масштабироваться дальше пары десятков процессоров. Фактически же, аналоги acquire/release/consume операций уже некоторое время имеются в яве, но это полулегальные операции, потому что официального апдейта JMM с их формализацией нет и не предвидится.

              >Мыслить в терминах отношений happens-before и пр. у меня как-то не особо получается.

              Ну, среди явистов тоже очень многие рассуждают в терминах барьеров. Как эвристические рассуждения это неплохо, но суть в том, что если вы попытаетесь сделать рассуждения про барьеры и возможные перестановки более строгим — вы, собственно, и получите happens-before notation. Так что лучше уж, как мне кажется, идти сюда сразу же, как вы поймали общую идею алгоритма, и начинаете думать про реализацию.

              > В нашем частном случае формальная модель — это happeds-before, synchronized-with и пр. отношения, а интерпретация — в конечном счете, банальные барьеры.

              Я думаю, что здесь вы как раз ошибаетесь. Процессоры не господом богом с неба спущены — они разрабатываются инженерами под нужды разработчиков. Я где-то читал, что при разработке JMM были случаи, когда разработчики Intel подправляли спецификацию своих процессоров по итогам обсуждения — и это вполне логично, ибо кому нужны процессоры с набором команд, с которыми неудобно и ненадежно программировать? Судьба пресловутой Alpha очень наглядна в этом смысле. Разумеется, это двусторонний диалог, но это именно диалог — в отличие от законов природы, с которыми особо-то не подискутируешь.

              Например, абсолютное большинство современных general purposes процессоров создает иллюзию SC в однопоточном случае — хотя реально они все суперскалярные и используют внеочередное исполнение команд — то есть поддержание иллюзии SC-исполнения на самом деле стоит немалого гемороя их инженерам. Зачем они идут на этот геморой? — Потому что у процессора с менее тривиальной моделью исполнения будут большие проблемы с продажами. Наглядный пример того, как именно процессоры делаются под концепцию, а не наоборот.

              … Вообще, у меня есть мнение, что дело здесь не в сложности именно HB, а в том, что программисты сейчас вообще отвыкли серьезно относиться к надежности своего кода. К тому, что корректность алгоритма нужно доказывать, а не «жопой чуять». Если вы когда-нибудь пробовали доказывать корректность однопоточных алгоритмов, вы должны бы заметить, что разница в сложности не такая уж большая. Но для однопоточного кода отладка и тестирование довольно дешевы, дешевле, чем формальное доказательство — уже целое поколение (я в их числе) выросло на идеологии «достаточное количество юнит-тестов является доказательством корректности программы». И когда оказывается, что для многопоточного случая все это на порядки менее эффективно, и мы снова сталкиваемся с необходимостью формального доказательства — вот тут-то и возникает ощущение огромной сложности.

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

        А как-же _mm_stream_ps и иже с ними :)
          +1
          Нетрадиционные костыли, призванные «более улучшить» традиционные костыли (в виде кэша) не рассматриваем, — для них требуются специальные костыли методы применения, о которых, как правило, подробно написано в разных местах мануалов.
          0
          Большое спасибо за эту серию постов! Очень мало информации по этой теме на русском языке, тем более с попыткой объяснить на нескольких уровнях абстракций (от нутрей ЦПУ до C++) более-менее доступным языком. Надо отметить, что Ваш цикл не (с)только про lock-free, а, скорее, широко охватывает окружающий эту тему контекст.

          по “пучкам” VLIW (не помню, как это называется в Итаниуме, но перевод – “пучок” – запомнился)

          В IA-64 это зовётся «bundle».

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

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

          Так что Itanium – это наше нереализованное будущее.

          Как говорится, история в сослагательном наклонении не существует. Кто знает, чем будущее обернётся? Вот, например, российский «Эльбрус» — тоже VLIW.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое