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 – степень двойки). При изменении хотя бы одного байта в линии кэша вся линия считается инвалидной и требует синхронизации с основной памятью. Этим управляет протокол поддержки когерентности кэшей в мультипроцессорной/ мультиядерной архитектуре.


Если разные разделяемые данные попадают в одну линию кэша (то есть расположены в смежных адресах), то изменение одних данных приводит, с точки зрения процессора, к инвалидации других, находящихся в той же линии кэша. Эта ситуация называется 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 для сколь угодного числа адресов pAddr1 … pAddrN) на основе обычного 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.

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