Пользователь
0,0
рейтинг
8 октября 2013 в 10:00

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


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

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

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

Атомарные операции делятся на простые — чтение и запись — и операции атомарного изменения (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 успешна, иначе операция неуспешна, значение по адресу pAddr не изменяется.

Примитив CAS можно реализовать с помощью пары LL/SC примерно так:
bool CAS( word * pAddr, word nExpected, word nNew ) {
   if ( LL( pAddr ) == nExpected )
      return SC( pAddr, nNew ) ;
   return false ;
}

Заметим, что, несмотря на многошаговость данного кода, он выполняет атомарный CAS: содержимое целевой ячейки памяти либо не меняется, либо атомарно изменяется. Реализация пары LL/SC на архитектурах, поддерживающих только примитив CAS, возможна, но не столь примитивна; я не буду здесь её рассматривать, интересующихся отсылаю к статье [Mic04].

Современные архитектуры процессоров делятся на два больших лагеря – одни поддерживают в своей системе команд CAS-примитив, другие – пару LL/SC. CAS реализован в архитектурах x86, Intel Itanium, Sparc; впервые примитив появился в архитектуре IBM System 370. Пара LL/SC – это архитектуры PowerPC, MIPS, Alpha, ARM; впервые предложена DEC. Стоит отметить, что примитив LL/SC реализован в современных архитектурах не самым идеальным образом: например, нельзя делать вложенные вызовы LL/SC с разными адресами, возможны ложные сбросы флага linked (так называемый false sharing, см. ниже), нет примитива валидации флага linked внутри пары LL/SC.

С точки зрения C++, стандарт C++11 не рассматривает пару LL/SC, а описывает только атомарный примитив compare_exchange (CAS) и производные от него атомарные примитивы – fetch_add, fetch_sub, exchange и пр. Стандарт подразумевает, что реализовать CAS с помощью LL/SC довольно просто, а вот обратная реализация – LL/SC через CAS – весьма нетривиальна. Поэтому, чтобы не усложнять жизнь разработчикам стандартной библиотеки C++, комитет по стандартизации ввел в C++ только compare_exchange, которого, в принципе, достаточно для реализации lock-free алгоритмов.

False sharing


В современных процессорах длина линии кэша L (cache line) составляет 64 – 128 байт и имеет тенденцию к увеличению в новых моделях. Обмен данными между основной памятью и кэшем осуществляется блоками по L байт (обычно L – степень двойки). При изменении хотя бы одного байта в линии кэша вся линия считается инвалидной и требует синхронизации с основной памятью. Этим управляет протокол поддержки когерентности кэшей в мультипроцессорной/ мультиядерной архитектуре.
Протокол MESI поддержки когерентности кэша
Например ([Cha05]), протокол MESI (Modified — Exclusive — Shared – Invalid) поддержки когерентности кэшей процессоров Intel помечает линию кэша как инвалидную при каждой записи в разделяемую (shared) линию, что приводит к интенсивному обмену с памятью. При первой загрузке данных в линию кэша, MESI помечает эту линию как E (Exclusive), что дает процессору возможность производить неограниченное число чтений/записи данных в линию кэша. Если другой процессор требует доступа к тем же самым данным, которые расположены в кэше этого другого процессора, MESI помечает линию кэша как S (Shared). Теперь любая инструкция записи в такую линию в любом кэше приводит к пометке линии как M (Modified), что, в свою очередь, приводит к отметке этой линии как I (Invalidate) в кэшах других процессоров и, как следствие, загрузке данных из основной памяти. Сейчас я не буду подробно останавливаться на протоколе MESI, так как планирую в одной из следующих заметок привести перевод замечательной статьи, посвященной внутренней организации современных процессоров, где в том числе будет рассмотрен и MESI.


Если разные разделяемые данные попадают в одну линию кэша (то есть расположены в смежных адресах), то изменение одних данных приводит, с точки зрения процессора, к инвалидации других, находящихся в той же линии кэша. Эта ситуация называется false sharing (ложное связывание). Для примитивов LL/SC false sharing губителен, так как реализация этих примитивов выполнена как раз в терминах линий кэша: операция Load-Linked помечает (link) линию кэша, а операция Store-Conditional перед записью проверяет, не сброшен ли флаг link для данной линии; если флаг сброшен, записи не выполняется и SC возвращает false. Так как длина линии L довольно большая, то ложное несрабатывание примитива SC (то есть сброс флага link) случается при любом изменении линии кэша, не связанном с целевыми данными. Как результат – мы можем получить livelock: ситуацию, когда процессоры/ядра заняты на 100%, но никакого прогресса нет.

Борьба с false sharing довольно проста (но расточительна): каждая shared-переменная должна занимать линию кэша целиком; для этого обычно используют заполнение (padding):
struct Foo {
       int volatile nShared1;
       char   _padding1[64];	 // padding for cache line=64 byte
       int volatile nShared2;
       char   _padding2[64];	 // padding for cache line=64 byte
};


Следует отметить, что физическая структура кэша влияет на все операции (в том числе и на CAS), а не только на примитивы LL/SC. В некоторых работах исследуются структуры данных, специальным образом построенные с учетом структуры кэша (в основном, с учетом длины линии кэша); при правильном (“под кэш”) построении структуры данных производительность может увеличиться на порядок.

Разновидности CAS


Кратко остановлюсь ещё на двух полезных атомарных примитивах – CAS двойной ширины (double-word CAS, dwCAS) и двойной CAS (DCAS).

CAS двойной ширины аналогичен обычному CAS, но оперирует с ячейкой памяти удвоенного размера: 64-битовой для 32-битовых архитектур и 128-битовой (точнее, как минимум 96-битовой) для 64-битовых. Для архитектур, предоставляющих пару LL/SC вместо CAS, LL/SC должны оперировать также словами двойной длины. Из знакомых мне архитектур только x86 поддерживает dwCAS. Чем же так полезен этот примитив? Он позволяет организовать одну из первых схем решения ABA-проблемы – tagged pointers. Эта схема была предложена IBM как раз для решения ABA-проблемы и заключается в сопоставлении каждому разделяемому указателю тега – целого числа; tagged pointer может быть описан следующей структурой:
template <typename T>
struct tagged_pointer {
	  T *	ptr ;
	  uintptr_t tag ;

    tagged_pointer()
      : ptr( new T )
      , tag( 1 )
    {}
};

Для обеспечения атомарности, переменные этого типа должны быть выровнены по двойному слову: 8 байт для 32-битовых архитектур и 16 байт для 64-битовых. Тег содержит “номер версии” данных, на которые указывает ptr. Я подробно расскажу о tagged pointers в одной из следующих статей, посвященной безопасному управлению памяти (safe memory reclamation, SMR), здесь же только отмечу тот факт, что tagged pointers подразумевает, что память, однажды выделенная под данные типа T (и соответствующий tagged_pointer) не должна физически удаляться (delete), а должна помещаться во free-list (отдельный для каждого типа T), из которого в дальнейшем данные будут вновь распределяться с инкрементированием тега. Именно это и дает решение ABA-проблемы: фактически, указатель у нас составной и содержит в теге номер версии (порядковый номер распределения); в этом случае dwCAS не будет успешным, если в его аргументах типа tagged_pointer указатели равны, а значения тегов отличаются.

Второй атомарный примитив – двойной CAS (DCAS) – является в настоящий момент чисто гипотетическим и не реализован ни в одной из современных процессорных архитектур. Псевдокод DCAS таков:
bool DCAS( int * pAddr1, int nExpected1, int nNew1,
           int * pAddr2, int nExpected2, int nNew2 )
atomically {
    if ( *pAddr1 == nExpected1 && *pAddr2 == nExpected2 ) {
         *pAddr1 = nNew1 ;
         *pAddr2 = nNew2 ;
         return true ;
    }
    else
         return false
 }

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

Почему данный примитив так интересен? Дело в том, что с его помощью довольно легко можно построить lock-free двусвязный список (deque, double-linked list), а такая структура данных является основой многих интересных алгоритмов. Существует большое число академических работ, посвящённых структурам данных, основанным на DCAS. Хотя этот примитив и не реализован “в железе”, есть работы (например, [Fra03] — наиболее известная из них), описывающие алгоритм построения DCAS (и вообще multi-CAS для сколь угодного числа адресов pAddr1pAddrN) на основе обычного CAS.

Производительность



А как обстоит дело с производительностью атомарных примитивов?
Современные процессоры настолько сложны и непредсказуемы, что изготовители не дают каких-то однозначных гарантий длительности тех или иных инструкций, тем более атомарных, в работе которых задействованы внутренняя синхронизация, сигнализация по шинам процессора и пр. Существует довольно большое число работ, в которых авторы пытаются замерить длительность инструкций процессоров. Я приведу измерения из [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 (а поддерживают его только новейшие версии компиляторов – из доступных мне это 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

Максим Хижинский @khizmax
карма
157,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (34)

  • +1
    Отличная статья!
    А есть ли сейчас смысл писать что-то по 32-битную архитектуру? Подобные алгоритмы используются обычно для серверных приложений, где даже ARM к моменту выхода в широкое применение будет 64-битным.
    • +1
      Совершенно согласен! В своей повседневной профессиональной деятельности я уже лет 5 сижу на 64 битах.
      Но 32 бита ещё довольно распространены, особенно для десктопных и «смартфонных» приложений. К тому же, когда пишешь некую библиотеку с замахом на общность, — 32 бита дисциплинируют. Иногда приходится поломать голову, как засунуть то, что хорошо вписывается в 64-битовую архитектуру, в 32 бита.
    • +1
      Ну станет атомарным чтение не 32 бит, а 64 — суть-то не меняется.
      И да, где в статье привязка именно к 32-битной архитектуре? (а примеры на то и примеры, что показывают конкретные числа)
      • +3
        По сути — да, не меняется.
        Но иногда 32 бита — мало. 32 бита — это выравненность по 4 байтам, то есть 2 младших бита адреса всегда нули. В 64 — имеем нулевыми 3 младших бита. В lock-free алгоритмах часто нужно вместе с некоторым адресом атомарно поменять и некоторые статусы. Для статусов необходимо использовать как раз эти младшие свободные биты в адресе (это так называемый marked pointer), чтобы и адрес, и статусы влезли в CAS. Естественно, в 3 бита влезет больше статусов, чем в 2. Иногда этот лишний бит в 64 бывает очень полезен. А в 32-битовой архитектуре приходится явно указывать выравнивание по 8 байтам, чтобы алгоритм был работоспособным. И тут начинаются танцы с бубном — aligned-распределение памяти (оно зачастую намного медленнее и прожорливей), компиляторно-зависимые конструкции и ограничения и пр.
    • 0
      >А есть ли сейчас смысл писать что-то по 32-битную архитектуру?
      Запустите 64-битную винду. Поставьте туда все популярные браузеры (не из репозиториев, а из первой ссылки в гугле). Запустите. Откройте менеджер процессов и посмотрите на битность запущенных процессов. Все (даже дефолтый IE из 64-битной винды 8.1) будут 32-битные. И это браузеры — передовой, можно сказать, продукт. Хайтек и флаг прогресса. Стоит ли говорить, что основная масса софта ещё долго будет в основном 32-битной.
  • +2
    Про стоимость атомарных операций — порядок-таки изменился: uncontended lock xadd на Sandy Bridge стоит 3ns/op — это где-то десяток «обычных» инструкций.

    Стоимость атомарных операций действительно может скакать на порядки в зависимости от состояния кэша: если нужная строка уже в вашем кэше и в M/E-state — стоимость будет минимальной, иначе придется долго ждать либо загрузки из основной памяти/L2/L3, либо — что еще хуже — арбитрации за владение строкой с другим ядром. Но все то же самое применимо и к обычной, не-атомарной последовательности read-modify-write — любая запись требует строку в L1 в M/E-state, и поэтому бОльшая часть затрат в неудачном варианте уходит именно на то, чтобы ее туда затащить. Разница между атомарными RMW и не-атомарными RMW в основном как раз в барьерах памяти — в неатомарном варианте высокую стоимость записи в неудачном варианте процессор может (если повезет) самортизировать за счет буферизации и спекулятивного исполнения. У атомиков же, как правило, есть семантика барьера, и потому возможности спекуляции сильно ограничены — и потому большую стоимость записи (которая ничем особо не специфична для атомиков — запись сама по себе дорогая) не удается замаскировать. Я недавно писал об этих вещах (и там в комментариях привели ссылку на статью с более детальными и современными бенчмарками инструкций синхронизации)

    • 0
      Спасибо, очень интересный для меня материал, — как ваша заметка, так и ссылки. Радует, что прогресс у hardware-вендоров не стоит на месте и вместо гигагерцев они наконец-то серьезно озаботились внутренней архитектурой и разруливанием узких мест в процессорах.
      • +1
        Это не то чтобы прогресс… закладка в архитектуру была еще лет 10 назад, когда 64-битные процессоры еще были только в проекте. Был вероятно какой-то эксклюзив на котором это все обкатывалось и только потом весь успешный опыт пошел в массовые процессоры. Сложно вообще представить а тем более подсчитать сколько неудачных решений было отсеяно(даже не дошедших до стадии железа).

        Так что верней сказать что это последствия прогресса, а сам прогресс — от там где-то в далеке. Хотя, кому-то ведь везет и он находится на вершине прогресса. Может, где-то в лабораториях уже давным давно обкатывают 128 а может даже и 1024-битные процессоры. Может даже только в симуляторах… поскольку пока процессоры общего назначения большей битности не востребованы, а вот специализированные ядрышки по 1024 бита для видеокарты или биткоин-генератора пришлись бы как раз по месту. Черт побери, а может это уже реальность?
        • –1
          Вся эта «многобитность» чисто логическая, т.е существует только для асм-программиста. Внутри там все равно все АЛУшки 16-битные. Микрокод конвеера процессора разбивает 64-битные операции на набор выполняющихся частично-параллельно 16-битных.
          Там чисто технологические заморочки с нагрузочной способностью транзисторов и синхронизацией. Ну т.е. на практике можно сделать АЛУ хоть на 1024 бита, только работать оно будет медленнее, чем 64 запараллеленых 16-битных + управляющая логика по той же технологии.
          • –1
            Микрокод конвеера процессора разбивает 64-битные операции на набор выполняющихся частично-параллельно 16-битных.

            Где вы такого набрались?
            Ничего разбивать (и тем более неким «микрокодом конвеера») не нужно.
            www.ee.usyd.edu.au/research/allresearch/seminars/01332644-a4GHz300mV.pdf
            • –1
              Вы вообще по своей же ссылке ходили?
              Это 10-летний (!) дискретный (!!) 64-битный АЛУ, состоящий из двух 32-битных секций(!!!).
              • –1
                И? Как будто это что-то меняет? 2 секции там потому что верхняя половина независимо отключается чтобы минимизировать утечки — для 32битных операций она не нужна. Дискретный разумеется — это результат работы R&D отдела Intel для некоего процессора. Стандартный срок проектирования больших CPU — 3-5 лет. Вполне возможно что подобный дизайн использован в Nehalem или около того. У вас есть материалы лучше? В студию!

                FP ALU у какого-нибудь 5+GHz Power имеет ширину 128 бит и более.
                «Микрокод конвеера» это вообще нечто.
                • 0
                  Открою вам страшную тайну — x64 процессоры при выполнении 16- и 32-разрядных операций также не вычисляют «верхние половины», и тоже с целью минимизировать утечки, нагрев и расход энергии. Поэтому физически никаких 64-битных АЛУ (так же как и отдельных блоков MMX/SSE) в современных x86/x64 процессорах просто нет (про другие архитектуры не скажу). Конвеер разбивает 32/64 операции на последовательность 16-разрядных микроинструкций, которые выполняются частично параллельно. Именно благодаря этому факту в те же Атомы так просто и без пафоса была добавлена поддержка 64 бит.

                  Что касается дискретных АЛУ — то это тяжелое наследие той мрачной эпохи на заре компьютеростроения, когда необходимость обрабатывать мощные потоки данных со всяких сенсоров в реальном времени уже была, а адекватных GPU, DSP и ПЛИС ещё не было. Вот и приходилось в приёмных цепях реализовывать вычисление функций типа A*B + C*D схемотехинчески, подключая на входы дискретного сумматора выходы двух дискретных умножителей.
                  • 0
                    Что касается дискретных АЛУ — то это тяжелое наследие той мрачной эпохи на заре компьютеростроения

                    Когда я упоминал Power, я имел в виду вот этот сумматор — так же вариация на тему Kogge-Stone 1973г:
                    citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.2881&rep=rep1&type=pdf
                    Там ещё довольно детальная блок-схема всего ALU показана.
                    Схема огранизации переноса в старшие разряды и «дробление» разрядности ALU это нюансы реализации.

                    Поэтому физически никаких 64-битных АЛУ (так же как и отдельных блоков MMX/SSE) в современных x86/x64 процессорах просто нет

                    Вы хотите сказать что и скалярные и векторные данные обрабатывают одни и те же ALU?
                    Скандалы, интриги, расследования. Что же получается, Интел всем врёт?
                    Как вы обьясните, например, такую блок-схему:
                    www.realworldtech.com/haswell-cpu/4/

                    Конвеер разбивает 32/64 операции на последовательность 16-разрядных микроинструкций,

                    Ага, и имея всего 4 порта запуска EU они, согласно вашим словам, магически комбинируются в 64битные =)
                    Большинство микроопераций на выходе декодера аналогично исходным х86 включая load-op.

                    А вообще вы бы лучше ссылочки на соотвествующие патенты привели. Пожалуйста.

                    Именно благодаря этому факту в те же Атомы так просто и без пафоса была добавлена поддержка 64 бит.

                    А латентность не изменилась. Чудеса.
                    Вообще 64бит там было изначально.
                  • 0
                    x64 процессоры при выполнении 16- и 32-разрядных операций также

                    Почему вы кстати отрицаете связь мною приведённого Интеловского ALU для высокопроизводительных процессоров и х86?
                    IA64 не имеет 32битных операций и не рассчитан на высокую частоту.
  • +2
    Вы как-то так смело утверждаете, что volatile в C++излишне…
    "Таким образом, для C++11-совместимого компилятора указание volatile для атомарной переменной излишне. А вот для старого компилятора бывает необходимо, если вы сами реализуете atomic."
    Да, проблема выравнивание в C++ есть, но по-умолчанию (во всех компиляторах?) работает выравнивание не менее int. А если кто-то изменяет выравнивание, то предполагается, что он знает, что делает.
    Видимо, Вы имеете в виду, что в C++11 нужно пользоваться compare_exchange? Но кроме масса готового кода, библиотек, которые использует volatile есть же множество алгоритмов, на всякого рода флажках, когда не нужно менять состояние, а только определить текущее мгновенное состояние некоторого разделяемого флага или счётчика. Там compare_exchange даже вреден бывает и без volatile не обойтись.
    • 0
      Да, volatile в C++11 излишне. Более того, если строго следовать стандарту, оно приводит к data race (ведь volatile обычно используют для разделяемых данных), что, согласно нового стандарта, есть undefined behaviour. То есть поведение программы никак не гарантируется.
      Data race не будет только на атомарных переменных atomic (это постулируется стандартом). Поэтому в C++11 в качестве флажков нужно использовать atomic.
      Compare_exchange вовсе не обязателен — можно использовать и atomic load/store (разумеется, с правильным memory_order).
      Вообще про volatile в C++ была большая и интересная дискуссия среди авторов нового стандарта. С кучей примеров pro и contra. В конце концов решили, что в C++11 не будут наделять volatile какой-то магической силой, как это сделали в Java или C#.
      Я так подробно расписывал compare_exchange не потому, что только его нужно использовать, а потому, что он самый удобный и распространенный для lock-free алгоритмов. Конечно, есть множество алгоритмов, построенных без compare_exchange.
      • 0
        А как же пресловутая совместимость по исходному коду, из-за которой столько говна в стандарте? Ведь 99% софта использует volatile на С/С++?
      • +2
        И, кстати, а если я пишу на системном уровне и ЗНАЮ, что переменная выравнена и не хочу никакого дополнительного выравнивания и мне нужно получить atomic-чтение?
        Просто пример — поля структур. Вот нужно мне одновременно PACKED и atomic (вполне обычная ситуация, например, при работе с железом) — что делать? В C++11 это фактически взаимоисключающие вещи. А volatile для упакованных структур вполне имеет смысл и полезен, если программист гарантирует выравненность структуры.
        Короче, с ненужностью volatile в C++11 категорически не согласен.
        • +1
          Наверное, я был недостаточно точен.
          Я не говорю про ненужность (и тем более вредность) вообще, я говорю про избыточность для атомарных переменных. Атомарная переменная — это переменная типа atomic<T>. Несмотря на то, что она определена в STL и, вроде бы, независима от самого языка, на самом деле на atomic<T> навешано довольно много семантики, то есть [очень грубо] можно считать, что atomic<T> является ключевым словом. И компиляторы, поддерживающие C++11 atomic, были существенно переработаны внутри, чтобы поддержать требования стандарта, новую модель памяти.
          Были обсуждения при подготовке стандарта, нужно или нет навешивать acquire/release семантику на чтение/записть volatile-переменных, как это сделали в C#. И было принято решение — не нужно. Эту семантику навесили на atomic<T>.
          Кстати, один из аргументов против придания volatile какого-то статуса в C++11 был таким:
          struct VeryLargeStruct {
            // 100500 полей
          };
          
          VeryLargeStruct volatile x;
          

          Эта структура очень большая (по объему) и никак не влезает в atomic. Поэтому и acquire/release семантику на её представителей (x в данном примере) навесить не получится.

          Никто не отменял (или переопределял) значения volatile, как это случилось с auto в C++11. Используйте на здоровье! Просто надо помнить, что для атомарных переменных volatile избыточна.

          Насчет выравнивания. Атомарная переменная должна быть правильно выровнена. Это необходимое условие атомарности. Иначе — UB.
          По поводу packed — это нас x86 избаловала. На другой архитектуре при попытке обращения к невыровненному int мы получим segmentation fault. Это и называется в стандарте «неопределенным поведением» (UB).
        • 0
          >И, кстати, а если я пишу на системном уровне и ЗНАЮ, что переменная выравнена и не хочу никакого дополнительного выравнивания и мне нужно получить atomic-чтение?

          Разве в новом стандарте нет явных барьеров памяти — как раз для тех, кто любит пожесче? По-моему, были.

          А у volatile в С просто недоопределенная семантика. С ним не связано никаких барьеров памяти, это только барьер уровня компилятора. То есть компилятор-то в нужном месте выдаст store/load, а вот процессору ничего не помешает поспекулировать. Поэтому используя volatile вы вынуждены закладываться на детали какой-то конкретной железной (процессорной) модели памяти — например на то, что x86 использует total store order, и не переставляет записи. Гораздо лучше иметь возможность явно сказать «здесь я хочу семантику release», и чтобы компилятор сам в зависимости от target платформы подставил нужное.
  • 0
    С использованием compare_exchange примитив fetch-and-add, показанный выше, может быть написан так:

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

    Если значение по адресу pAddr будет изменено другим потоком в момент после окончания
    int ncur = *pAddr;
    но до начала выполнения
    do {} ...
    то получится бесконечный цикл do {} while.
    Это у вас ошибка, или я недопонял? Если второе, то прокомментируйте подробней пожалуйста.
    • +2
      Здесь используется «специальная» CAS из С++11. Чуть выше по тексту:
      Аргумент nExpected передается по ссылке и на входе содержит ожидаемое значение переменной по адресу pAddr, а на выходе – значение перед изменением. Возвращает же функция признак успеха: true, если по адресу находится значение nExpected (в этом случае оно меняется на nNew), false в случае неудачи (тогда nExpected будет содержать текущее значение переменной по адресу pAddr).

      Поэтому это эвивалентно(вроде бы..) следующему коду с использованием CAS:
      int ncur;
      do { ncur = *pAddr; } while ( !CAS( pAddr, ncur, ncur + nIncr ) );
      return ncur;
      
      • +1
        Совершенно правильно.
        Я намеренно разделил CAS и compare_exchange.
        compare_exchange — это из C++11, аргумент nExpected передается по ссылке и на выходе содержит текущее значение *pAddr. Именно в этом часто бывают ошибки/описки или излишне чтение в CAS-циклах.
  • +3
    Есть ли проблема ABA в языках с GC, например Java? Решим ли мы проблему если никогда не будем освобождать выделенную память?
    • +1
      Мне трудно ответить на этот вопрос, так как я не знаток Java. Поэтому могу только поразмышлять.
      Если мы говорим о физическом удалении, то ABA-проблема возникает при удалении (delete) и тут же включении вновь (allocate) некоего элемента. Удаление в C++ — это физическое удаление. В языках же с GC физического удаления не произойдет, пока кто-то держит ссылку на удаляемый элемент. Такую локальную ссылку какой-то поток держит (тот, который работает с CAS, на котором возникает ABA). Поэтому мой ответ — да, языки с GC свободны от ABA-проблемы.
      Ответ на второй вопрос — решим ли мы проблему если никогда не будем освобождать выделенную память — скорее отрицательный. В общем случае не решим.
      Рассмотрим такой пример, на двух lock-free интрузивных стеках (интрузивный контейнер — хранит не копии данных, а сами данные, — сишный подход, позволяет избавиться от аллокатора в контейнере): поток 1 делает stack1.pop(), доходит до CAS и, к примеру, вытесняется. Поток 2, пока первый вытеснен, успевает сделать:
      T * a = stack1.pop() ;
      T * anext = stack1.pop() ;
      stack1.push( a ) ;
      stack2.push( anext );
      

      Вслед за этим поток 1 выполняет CAS, меняя a на anext, который он запомнил. Но anext теперь включен в stack2! Нарушение stack1: он теперь будет указывать в stack2. ABA-проблема, без освобождения выделенной памяти.
      Кажется, что этот пример входит в противоречие с моим первым утверждением — языки с GC свободны от ABA. На самом деле, противоречия нет. Языки с GC не позволяют работать с сырыми указателями (а если всё же позволяют, то на ваш страх и риск).

      PS: смотрите внимательно, я могу наврать в примерах. ABA — очень тонкая вещь для обнаружения и объяснения, хотя и очень понятная, когда (и если :) разберешься.
      • +1
        Спасибо за развернутый ответ!
        AFAIK в JAVA есть CAS для указателей и кроме того определена memory model довольно тщательно, народ делает lock-free в Java.

        Пример с перетыканием узла из одного списка в другой интересен, мне это не приходило в голову.
        Существуют ли lock-free контейнеры с поддержкой такой операции? Кажется, что в общем случае такое эффективно не сделать (в отличии от отложенного удаления элемента, здесь нам важна задержка до момента, когда на объект больше нет ссылок).

        Я где то видел такой подход по противодействию ABA — внедрение счетчика в неиспользуемые биты указателя. Насколько такое эффективно при «достаточной» разрядности счетчика? Может быть выделять память под lock-free элементы специальным аллокатором, и надеяться, что при 64 битных указателях мы сможем организовать счетчики большой разрядности?
        • +1
          Про Java. Могу сказать, что изобретатели lock-free алгоритмов очень любят Java (вся книга Shavit & Herlihy «The Art of Multiprocessor programming» наполнена примерами только на Java). И это понятно: в Java они избавлены от необходимости следить за указателями, за правильным (в подходящий момент) удалением и пр. — за них все делает GC. Поэтому портировать Java-алгоритмы на C++ бывает довольно сложно.

          Существуют ли lock-free контейнеры с поддержкой такой операции?
          Явных контейнеров с перетаскиванием не встречал. Хотя такая задача иногда возникала на практике. Обходился своими силами — если понимаешь, как контейнер реализован (вернее, когда можно удаленный элемент контейнера 1 поместить в контейнер 2, — это уже из области алгоритмов safe memory reclamation типа Hazard Pointer), это не представляет труда.

          внедрение счетчика в неиспользуемые биты указателя — совершенно верно! Это техника tagged pointers. В статье я утверждаю, что для неё нужен dwCAS, но на самом деле — не всегда. Можно использовать и неиспользуемые биты указателя. В современных 64-битовых платформах на самом деле адресуется, вроде бы, 48 бит (или 42? — не помню). Остальное может быть, в принципе, использовано. Насколько я знаю, boost.lockfree построен на этом.
          Мне такой подход не нравится, — нет никакой уверенности, что в какой-то прекрасный момент производитель не сделает настоящий 64-битный адрес. И всё — наш алгоритм отправится на свалку :-(

          Про достаточную разрядность счетчика — интересный и хороший вопрос! На этот счет были исследования. Насколько я помню (пруф сейчас не готов указать), их результатом было: достаточно 32-битового счетчика. Меньше — можно попасть на переполнение в неподходящий момент (а следствие — ABA). Обоснование: таймслот, выделяемый ОС для потока. Например, где-то в mail-list разработчиков Линукса я встречал такую оценку таймслота: 300 — 500 тысяч «простых» инструкций. После этого поток вытесняется. 300 тысяч не влезут в 16 бит. Это ещё один аргумент против использования 16 бит 64-битового указателя.

          Про специальный аллокатор. Здесь я ничего сказать не могу, — очень большая тема. Я остановился на схемах безопасного освобождения памяти (Hazard Pointer, Pass-the-Buck, RCU), они решают все эти вопросы про ABA и освобождение (конечно, при правильном приготовлении :-) Повесить это на аллокатор… Нужно думать
          • +1
            «Специальный аллокатор» — подразумевалась процедура, которая возвращает указатели с «особыми свойствами». Например, резервирует 4ГБ адресного пространства и выделяет память внутри этих 4 ГБ, в указателях будет задействовано только 32 бита, а все остальное можно использовать под счетчики.
            • 0
              Субаллокатор и offset-указатели… Да, согласен, на этом пути можно добиться многого. Готовых решений, заточенных под lock-free, я не знаю. Быть может, вы будете первым, кто реализует подобное?.. Я серьезно, без всякой иронии. Дерзайте!
              • 0
                Что-то подобное делает JVM автоматически, если размер кучи на 64-битной системе меньше некого предела. До 4Гб большинство указателей будут прозрачно 32-битными указатели, до 32Гб — с offset-ом (где можно, конечно — иногда придется их разворачивать в полные)

                Уходите вы уже с ваших C++ — у нас, на яве, такие печеньки для concurrency… :)
          • 0
            И это понятно: в Java они избавлены от необходимости следить за указателями, за правильным (в подходящий момент) удалением и пр. — за них все делает GC.

            Решит ли ABA проблему в C++ использование объектов со встроенным GC таких как shared_ptr?
            • 0
              В принципе, да, если все аккуратно сделать. У Вильямса в C++ Concurrency in Action приводятся стек и очередь на shared_ptr. Другое дело, что это не всегда будет эффективно.
    • +1
      В языках с GC в первом приближении ABA нет — и это их огромнейшее достоинство в области lock-free.

      Но, конечно, если вы начинаете делать свой собственный memory-management, скажем, заводите пул объектов, чтобы снять нагрузку на GC — вы можете получить ABA назад. Нужно быть очень аккуратным, когда делаете одновременно lock-free и GC-less компоненты.

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