Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 24.06.2014 | нет комментариев

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

В этой статье мы разглядим модель памяти 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_acquirememory_order_releasememory_order_acq_relmemory_order_consume – относятся к модели, основанной на acquire/release семантике
  • memory_order_relaxed – указывает на relaxed-модель

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

  • Семантическая: по сути, желаемое упорядочение (барьер памяти) относится именно к атомарной операции, которую мы исполняем. Расстановка барьеров в read/write-подходе является шаманством именно потому, что сам барьер вообще никак семантически не связан с тем кодом, в котором он присутствует, — легко инструкция среди эквивалентных. Помимо того, расстановка read/write барьеров дюже зависит от архитектуры.
  • Фактическая: Intel Itanium имеет специальный, чудесный от других архитектур, метод указания упорядочения памяти для инструкций чтения/памяти и RMW-операций. В Itanium тип упорядочения указывается как опци_permark! // 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 принимает свой 1-й довод по ссылке и изменяет его, если CAS неудачен, мне дюже мешает! Доводится писать do-while цикл с непустым телом.
    В способе lock овладения блокировкой я использую acquire-семантику, а в способе unlock – release-семантику (кстати, acquire/release семантика повела свою историю как раз из примитивов синхронизации: разработчики эталона наблюдательно проанализировали реализацию разных примитивов синхронизации и вывели паттерн acquire/release.) Как я писал выше, барьеры, проставляемые в этом случае, не разрешают коду, заключенному между lock() и unlock(), просочиться наружу, — то, что нам и необходимо! А атомарность переменной m_spin гарантирует нам, что пока m_spin=1, никто не сумеет овладеть блокировкой, — вновь то, что и требуется!
    В алгорифме мы видим, что я использую compare_exchange_weak. Что это такое?

    Слабый и крепкий CAS

    Как вы помните, зодчество процессоров может относиться к одному из 2-х классов: либо процессор реализует атомарный примитив 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_exchangeexchange,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-семантика

    Наконец, 3-й тип модели атомарных операций – 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 – требует верификации алгорифма.

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

    До недавнего времени мне был вестимо только одно средство верификации — библиотека relacy Дмитрия Вьюкова. К сожалению, это средство требует построения специальной модели. Реально, следует вначале возвести упрощенную модель lock-free алгорифма в терминах библиотеки relacy (отчего упрощенную? – потому что, строя модель, традиционно убираешь любые пригодные фенечки, не относящиеся непринужденно к рассматриваемому алгорифму). Эту модель после этого необходимо отладить, и только потом, когда все отлажено и все атомарные операции снабжены правильными memory_order-доводами, дозволено написать теснее production-версию алгорифма. Такой подход безупречно подходитразработчикам lock-free алгорифмов и конструкций данных, — тем, кто их придумывает. Собственно, для разработчиков на такой модели вmk!li>либо сгенерировать switch/case по каждому допустимым значениям currentOrder. В этом случае взамен одной-2-х ассемблерных инструкций мы получим неэффективный код. Да и задача подходящей для операции семантики не решается, — абсолютно допустимо вызвать 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 конструкции данных и сопутствующие алгорифмы.

 

Источник: programmingmaster.ru

 

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB