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

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

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

Построение lock-free конструкций данных зиждется на 2-х китах – атомарных операциях и методах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый приемНачал! Вижу, что тема lock-free увлекательна програсообществу, это меня радует. Я планировал возвести цикл по академическому тезису, плавно переходя от основ к алгорифмам, заодно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особенно не рассусоливая. Я согласен, в этом есть свой резон. В финальном счете, и мне не так увлекательно, что там внутри boost, — опишите, как его использовать! Следственно свой эпический цикл я поделю на три части:ОсновыВнутри и Извне. Всякая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплотную до строения современных процессоров; это часть для почемучек как бы меня. Внутри будет освещать увлекательные алгорифмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free конструкцию данных, libcds будет неиссякаемым источником C кода. В Извне будут статьи о практике использования libcds, — программные решения, советы и FAQ. Извне будет кормиться вашими вопросами/замечаниями/предложениями, дорогие програжители.

А пока я судорожно готовлю предисловие Извне, — первая часть Основ. Статья во многом не о C (правда и о нем тоже) и даже не о lock-free (правда без atomic lock-free алгорифмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых задачах, возникающих при применении таких примитивов.
Атомарность — это 1-й круг ада низкий ярус из 2-х.

Атомарные операции делятся на примитивные — чтение и запись — и операции атомарного метаморфозы (read-modify-write, RMW). Атомарную операцию дозволено определить как неделимую операцию: она либо теснее случилась, либо ещё нет; мы не можем увидеть никаких промежуточных стадий её выполнения, никаких частичных результатов. В этом смысле даже примитивные операции чтения/записи, в тезисе, могут быть не атомарными; скажем, чтение невыравненных данных является неатомарным: в архитектуре x86 такое чтение приведет к внутреннему исключению, принуждающему процессор читать данные частями, в других архитектурах (Sparc, Intel Itanium) – к неизбежной ошибке (segmentation fault), которую, в тезисе, дозволено перехватить и обработать, но об атомарности речи тут быть теснее не может. В современных процессорах гарантируется атомарность чтения/записи только выравненных примитивных (integral) типов – целых чисел и указателей. Теперешний компилятор гарантирует положительное выравнивание переменных базовых типов, правда написать пример невыравненного обращения, скажем, к целому, не составляет труда. Если же вы хотите атомарно трудиться со конструкцией (по размеру влезающей в 4 – 8 байт), то следует самим позаботиться о положительном выравнивании с поддержкой директив (признаков) компилятора (всякий компилятор поддерживает свой неповторимый метод указания выравнивания данных/типов). Кстати, библиотека libcds содержит комплект вспомогательных типов и макросов, скрывающих компиляторно-зависимую часть при объявлении выравненных данных.

Compare-and-swap

Придумать алгорифм lock-free контейнера, использующего только чтение/запись, достаточно трудно, если вообще допустимо (мне такие конструкции данных для произвольного числа потоков не вестимы). Следственно разработчики процессорных архитектур внедрили RMW-операции, способные атомарно исполнить чтение выравненной ячейки памяти и запись в неё: compare-and-swap (CAS), fetch-and-add (FAA), test-and-set (TAS) и пр. В академической среде операция compare-and-swap (CAS) рассматривается как базовая; её псевдокод примитивен:

bool CAS( int * pAddr, int nExpected, int nNew )
atomically {
    if ( *pAddr == nExpected ) {
         *pAddr = nNew ;
         return true ;
    }
    else
        return false ;
 }

Словами: если нынешнее значение переменной по адресу pAddr равно ожидаемому nExpected, то присвоить переменной значение nNew и возвратить true, напротив возвратить false, значение переменной не изменяется. Всё это выполняется атомарно, то есть неделимо и без видимых частичных результатов. Через CAS дозволено выразить все остальные RMW-операции, скажем, fetch-and-add будет выглядеть так:

int FAA( int * pAddr, int nIncr )
{
     int ncur ;
     do {
          ncur = *pAddr ;
     } while ( !CAS( pAddr, ncur, ncur   nIncr ) ;
     return ncur ;
}

“Академический” вариант операции CAS не неизменно комфортен на практике, чай нередко при неудаче CAS нам увлекательно, что же за значение содержится теперь в ячейке. Следственно Зачастую рассматривают такой вариант CAS (так называемый valued CAS, также выполняется атомарно):

int CAS( int * pAddr, int nExpected, int nNew )
atomically {
      if ( *pAddr == nExpected ) {
           *pAddr = nNew ;
           return nExpected ;
       }
       else
            return *pAddr
 }

В C 11 функция compare_exchange (сурово говоря, в C 11 нет такой функции, есть её разновидностиcompare_exchange_strong и compare_exchange_weak, но об них я расскажу позднее) покрывает оба эти варианта:

bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew );

Довод nExpected передается по ссылке и на входе содержит ожидаемое значение переменной по адресуpAddr, а на выходе – значение перед изменением. Возвращает же функция знак триумфа: true, если по адресу находится значение nExpected (в этом случае оно меняется на nNew), false в случае неудачи (тогдаnExpected будет содержать нынешнее значение переменной по адресу pAddr). Такое универсальное построение операции CAS покрывает оба варианта “академического” определения CAS, но на практике использование compare_exchange чревато ошибками, так как нужно помнить, что довод nExpected передается по ссылке и может быть изменен, что не неизменно терпимо.
С применением compare_exchange примитив fetch-and-add, показанный выше, может быть написан так:

int FAA( int * pAddr, int nIncr )
{
     int ncur = *pAddr;
     do {} while ( !compare_exchange( pAddr, ncur, ncur   nIncr ) ;
     return ncur ;
}

ABA-задача

Примитив CAS каждому классен, но при его использовании допустима серьезная задача, получившая наименование ABA-задачи. Для её изложения следует разглядеть классический паттерн применения операции CAS:

int nCur = *pAddr ;
while (true) {
    int nNew = вычисляем новое значение
    if ( compare_exchange( pAddr, nCur, nNew ))
        break;
}

Реально, мы “долбимся” в цикле до тех пор, пока CAS не сработает; цикл нужен, так как между чтением нынешнего значения переменной по адресу pAddr и вычислением нового значения nNew переменная по адресуpAddr может быть изменена иным потоком.


ABA-задача описывается дальнейшим образом: возможен, поток X читает значение A из некоторой разделяемой ячейки, содержащий указатель на некоторые данные. После этого иной поток, Y, изменяет значение этой ячейки на B и вновь на A, но сейчас указатель A указывает на другие данные. Когда поток X с поддержкой примитива CAS пытается поменять значение ячейки, сопоставление указателя с предыдущим (прочтенным) значением A удачно, и итог CAS удачен, но A сейчас указывает на абсолютно другие данные! В итоге поток может нарушить внутренние связи объекта (что, в свою очередь, может привести к краху).

Вот реализация lock-free стека, подверженного ABA-задаче [Mic04]:

// Shared variables
static NodeType * Top = NULL; // Initially null

Push(NodeType * node) { 
            do { 
/*Push1*/ 	   NodeType * t = Top;
/*Push2*/	   node->Next = t;
/*Push3*/   } while ( !CAS(&Top,t,node) );
}

NodeType * Pop() { 
          Node * next ;
          do { 
/*Pop1*/        NodeType * t = Top;
/*Pop2*/        if ( t == null )
/*Pop3*/             return null;
/*Pop4*/        next = t->Next;
/*Pop5*/   } while ( !CAS(&Top,t,next) );
/*Pop6*/   return t;
}

Дальнейшая последовательность действий приводит к нарушению конструкции стека (подметим, что эта последовательность не исключительная, иллюстрирующая ABA-загвоздку):

Thread X Thread Y
Вызывает Pop().
Исполнена строка Pop4,
значения переменных: t == A
next == A->next
NodeType * pTop = Pop()
pTop == вершине стека, то есть A
Pop()
Push( pTop )
Сейчас вершина стека – вновь A
Подметим, что A->next изменилось
Выполняется строка Pop5.
CAS удачен, но полю Top->next
присваивается значение,
несуществующее в стеке,
так как поток Y вытолкнул
из стека A и A->next,
а локальная переменная next
хранит ветхое значение A->next

ABA-задача – это бич всех lock-free контейнеров, основанных на примитиве CAS. Она может появиться только в многопоточном коде в итоге удаления элемента A из контейнера и замены его на иной (B), а после этого вновь на A (отсель и наименование “ABA-задача”), в то время как иной поток держит указатель на удаляемый элемент. Даже если поток физически удалит A (delete A), а после этого вызовет new для создания нового элемента, нет никаких гарантий, что аллокатор не возвратит адрес A (отличные аллокаторы именно так и сделают). Зачастую она проявляется больше ухищренным образом, чем описано выше, затрагивает не два, а больше потоков (в этом смысле дозволено говорить о ABCBA-загвоздке, ABABA-задаче и т.д., насколько хватит фантазии), и её распознавание неизменно является нетривиальной задачей. Средство борьбы с ABA-задачей – отложенное физическое удаление (deferred deallocation, либо safe memory reclamation) элемента в момент, когда есть полная ручательство, что никто (ни один из конкурирующих потоков) не имеет ни локальных, ни глобальных ссылок на удаляемый элемент.
Таким образом, удаление элемента из lock-free конструкции является двухфазным:

  • Первая фаза – исключение элемента из lock-free контейнера;
  • Вторая фаза (отложенная) – физическое удаление элемента, когда нет никаких ссылок на него.

Я детально остановлюсь на разных схемах отложенного удаления в одной из следующих статей.

Load-Linked / Store-Conditional

Вероятно, присутствие ABA-задачи при применении CAS подтолкнуло проектировщиков процессоров к поиску других RMW-операций, не подверженных ABA-загвоздке. И такие операции были обнаружены – пара load-linked/store-conditional (LL/SC). Эти операции дюже примитивны – вот их псевдокод:

word LL( word * pAddr ) {
      return *pAddr ;
}

bool SC( word * pAddr, word New ) {
      if ( данные в pAddr не изменились с момента вызова LL) {
           *pAddr = New ;
           return true ;
      }
      else
         return false ;
}

Пара LL/SC работает как операторные скобки. Операция load-linked (LL) легко возвращает нынешнее значение переменной по адресу pAddr. Операция store-conditional (SC) исполняет сохранение в ранее прочитанный операцией LL адрес pAddr только в том случае, если данные в pAddr не изменились с момента чтения. При этом под изменением воспринимается любая модификация кеш-линии, к которой относится адрес pAddr. Для реализации пары LL/SC разработчикам процессоров пришлось изменить конструкцию кеша: дерзко говоря, всякая кеш-линия должна иметь добавочный бит ранга. При чтении операцией LL данный бит устанавливается (link), при всякий записи в кеш-линию (либо её вытеснении из кеша) бит сбрасывается, а операция SC перед сохранением проверяет, выставлен ли данный бит у кеш-линии: если бит = 1, то есть никто не изменил кеш-линию, значение по адресу pAddr меняется на новое и операция SC усп[McKen05]. В этой работе авторы, помимо прочего, сопоставляют продолжительность атомарного инкремента и примитива CAS с продолжительностью операции nop (no-operation). Выходит, для Intel Xeon 3.06 ГГц (примера 2005 года) атомарный инкремент имеет продолжительность 400 nop, CAS – 850 – 1000 nop. Процессор IBM Power4 1.45 ГГц: 180 nop для атомарного инкремента и 250 nop для CAS. Измерения достаточно ветхие (2005 год), за прошедшее время зодчество процессоров сделала ещё несколько шагов вперед, но порядок цифр, я думаю, остался бывшим.

Как видите, атомарные примитивы достаточно массивны. Следственно использовать их повсюду достаточно убыточно: скажем, если алгорифм поиска по бинарному дереву использует CAS для чтения нынешнего узла дерева, ничего классного я от такого алгорифма не ожидаю (а такие алгорифмы я видел). честности ради стоит подметить, что, по моим ощущениям, с всяким новым поколением архитектуры Intel Core примитив CAS становится всё стремительней, видимо, инженеры Intel много сил вкладывают в улучшение микроархитектуры.

Volatile и атомарность

В C есть таинственное ключевое слово volatile. Изредка volatile объединяют с атомарностью и упорядочением — это ненормально, но имеет под собой некоторые исторические основания.
По сути, volatile гарантирует только, что компилятор не будет кэшировать значение в регистре (оптимизирующие компиляторы дюже любят это делать: чем огромнее регистров — тем огромнее кэшируют). То есть чтение volatile-переменной неизменно обозначает чтение из памяти, запись volatile-перемнной —неизменно запись в память. Следственно если кто-то параллельно будет изменять volatile-данные, мы это сразу увидим.
На самом деле, не увидим. По причине как раз отсутствия барьеров памяти. В некоторых языках (Java, C#)volatile присвоен волшебный ранг, обеспечивающий упорядочение, но не в C 11. И никакого специального выравнивания volatile не гарантирует, а мы сейчас знаем, что нужным условием атомарности является как раз верное выравнивание данных.
Таким образом, для C 11-совместимого компилятора указание volatile для атомарной переменной излишне. А вот для ветхого компилятора бывает нужно, если вы сами реализуете atomic. В таком объявлении:

class atomic_int {
	int	m_nAtomic;
  //….
};

компилятор имеет полное право «оптимизировать» обращения к m_nAtomic (невзирая на то, что обращение идет неявно, через this). Следственно нелишним будет указать тут int volatile m_nAtomic.

volatile-способы в C

Исследуя интерфейс atomic, вы наверно обратите внимание, что многие его способы имеют спецификаторvolatile:

void store( T val ) volatile ;

Что это? Указатель this является volatile (то есть, имеет тип T * volatile)? Вообще, это немыслимо, —this Зачастую передается в регистре, и это специфицировано в некоторых ABI. На самом деле, это тип T volatile * .
По аналогии с const-способами, данный спецификатор говорит, что this указывает на volatile-данные, то есть все данные-члены объекта являются volatile в таком способе. Что, в свою очередь, воспрещает компилятору оптимизировать обращения к данным-членам. В тезисе, то же самое, как если бы мы объявили эти данные как volatile.
Ну и напомню, что спецификаторы const и volatile — это не противоположности, они могут существовать совместно. Вот объявление способа чтения в atomic<T>:

T load() const volatile ;

Это дозволено трактовать так:

  • const — способ сам не изменяет данные-члены объекта
  • volatile — но данные-члены могут быть параллельно изменены кем-то иным, следственно не следует их кешировать

libcds

В завершение – что мы имеем в библиотеке libcds? А имеем мы следующий велосипед реализацию атомарных примитивов в духе C 11 для архитектур x86/amd64, Intel Itanium и Sparc. Если компилятор не поддерживает C 11 <atomic> (а поддерживают его только новейшие версии компиляторов – из доступных мне это GCC 4.7 , MS Visual C 2012, Clang 3.0 ), то libcds использует свою реализацию атомарных примитивов. При этом основным атомарным примитивом при построении lock-free конструкций данных, помимо обыкновенных атомарных чтения/записи, является CAS, дюже редко где применяется CAS над двойным словом (dwCAS). Реализации DCAS (и вообще multi-CAS) в libcds [пока] нет, но абсолютно допустимо, что появится в грядущем, – уж дюже увлекательные конструкции данных дозволено на нем возвести. Останавливает только то, что, согласно многим изысканиям, реализация DCAS по алгорифму [Fra03] достаточно неэффективна. Но чай я теснее подмечал, что критерий результативности – вещь сугубо индивидуальная в мире lock-free: то, что неэффективно теперь и на этом железе и для этой задачи, может оказаться весьма результативным потом либо на ином железе либо для иной задачи!

В дальнейшей статье Основ речь пойдет об упорядочении обращения к памяти (memory ordering) – о барьерах памяти (memory fence, memory barrier).

Cсылки:

[Cha05] Dean Chandler Reduce False Sharing in .NET, 2005, Intel Corporation

[Fra03] Keir Fraser Practical Lock Freedom, 2004; technical report is based on a dissertation submitted September 2003 by K.Fraser for the degree of Doctor of Philosophy to the University of Cambridge, King’s College

[McKen05] Paul McKenney, Thomas Hart, Jonathan Walpole Practical Concerns for Scalable Synchronization

[Mic04] Maged Michael ABA Prevention using single-word instruction, IBM Research Report, 2004

Lock-free конструкции данных

 

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

 

Оставить комментарий

Ваш email не будет опубликован. Обязательные поля помечены (обязательно)

Вы можете использовать это HTMLтеги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

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