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

Lock-free конструкции данных. Эволюция стека

Anna | 24.06.2014 | нет комментариев
В предыдущих своих заметках я описал основу, на которой строятся lock-free конструкции данных, и базовые алгорифмы управления временем жизни элементов lock-free конструкций данных. Это была прелюдия к изложению собственно lock-free контейнеров. Но дальше я столкнулся с задачей: как возвести последующий рассказ? Легко описывать вестимые мне алгорифмы? Это достаточно тоскливо: много [псевдо-]кода, обилие деталей, значимых, безусловно, но крайне специфических. В конце концов, это есть в опубликованных работах, на которые я даю ссылки, и в значительно больше подробном и суровом изложении. Мне же хотелось рассказать увлекательно об увлекательных вещах, показать пути становления подходов к конструированию конкурентных контейнеров.
Отлично, — подумал я, — тогда способ изложения должен быть такой: берем какой-то тип контейнера — очередь, map, hash map, — и делаем обзор знаменитых на сегодняшний день подлинных алгорифмов для этого типа контейнера. С чего начать? И здесь я припомнил о самой примитивный структуре данных — о стеке.

Казалось бы, ну что дозволено сказать о стеке? Это настоль банальная конструкция данных, что и говорить-то особенно нечего.
Подлинно, работ о реализации конкурентного стека не так уж и много. Но но те, что есть, посвящены в большей степени подходам, нежели собственно стеку. Именно подходы меня и волнуют.

Lock-free стек

Стек — это, вероятно, первая из конструкций данных, для которой был сделан lock-free алгорифм. Считается, что его первым опубликовал Treiber в своей статье 1986 года, правда есть данные, что впервой данный алгорифм был описан в системной документации IBM/360.

Историческое отхождение

Вообще, статья Treiber’а — своего рода Старый Завет, вероятно, первая статья о lock-free структуре данных. Во каждом случае, больше ранних мне не вестимо. Она до сих пор дюже Зачастую упоминается в списках литературы (reference) современных работ, видимо, как подать уважения к основоположнику lock-free подхода.

Алгорифм настоль примитивный, что я приведу его адаптированный код из libcds (кому увлекательно — это интрузивный стек cds::intrusive::TreiberStack):

// m_Top – вершина стека
bool push( value_type& val )
{
    back_off bkoff;

    value_type * t = m_Top.load(std::memory_order_relaxed);
    while ( true ) {
        val.m_pNext.store( t, std::memory_order_relaxed );
        if (m_Top.compare_exchange_weak(t, &val, 
                  std::memory_order_release, std::memory_order_relaxed))       
           return true;
        bkoff();
    }
}
value_type * pop()
{
   back_off bkoff;
   typename gc::Guard guard; // Hazard pointer guard
   while ( true ) {
      value_type * t = guard.protect( m_Top );
      if ( t == nullptr )
         return nullptr ;  // stack is empty

      value_type * pNext = t->m_pNext.load(std::memory_order_relaxed);
      if ( m_Top.compare_exchange_weak( t, pNext, 
                  std::memory_order_acquire, std::memory_order_relaxed ))
           return t;
      bkoff();
   }
}

Данный алгорифм многократно разобран по косточкам (скажем, здесь), так что я повторяться не буду. Короткое изложение алгорифма сводится к тому, что мы долбимся с поддержкой атомарного примитива CAS вm_Top, пока не получим желаемый итог. Легко и достаточно просто.
Подмечу две увлекательных детали:

  • Safe memory reclamation (SMR) нужен только в способе pop, так как только там мы читаем поля m_Top. Вpush никакие поля m_Top не читаются (нет обращения по указателю m_Top), так что и охранять Hazard Pointer’ом ничего не необходимо. Увлекательно это потому, что традиционно SMR требуется во всех способах класса lock-free контейнера
  • Загадочный объект bkoff и его вызов bkoff(), если CAS неуспешен

Вот на этом самом bkoff я хотел бы остановиться подробнее.

Back-off стратегии


Отчего CAS неуспешен? Видимо потому, что между прочтением нынешнего значения m_Top и попыткой применить CAS какой-то иной поток поспел изменить значение m_Top. То есть мы имеем нормальный пример соперничества. В случае мощной нагрузки (high contention), когда N потоков исполняют push/pop, только один из них выиграет, остальные N – 1 будут впустую потреблять процессорное время и мешать друг другу на CAS (припомним протокол MESI кеша).
Как разгрузить процессор при выявлении такой обстановки? Дозволено отступить (back off) от выполнения стержневой задачи и сделать что-либо пригодное либо легко подождать. Именно для этого предуготовлены back-off стратегии.
Безусловно, в всеобщем случае «сделать что-либо пригодное» у нас не получится, так как мы не имеем представления о определенной задаче, так что мы можем только подождать. Как ожидать? Вариант со sleep()отметаем — немногие операционные системы могут обеспечить нам столь малые тайм-ауты ожидания, да и убыточные расходы на переключение контекста слишком крупны — огромнее, чем время выполнения CAS.
В академической среде популярностью пользуется тактика экспоненциального back-off. Идея дюже примитивна:

class exp_backoff {
    int const nInitial;
    int const nStep;
    int const nThreshold;
    int nCurrent;
public:
    exp_backoff( int init=10, int step=2, int threshold=8000 )
         : nInitial(init), nStep(step), nThreshold(threshold), nCurrent(init)
    {}
    void operator()()
    {
          for ( int k = 0; k < nCurrent;   k )
              nop();
          nCurrent *= nStep;
          if ( nCurrent > nThreshold )
               nCurrent = nThreshold;
    }
    void reset() { nCurrent = nInitial; }
};

То есть мы в цикле исполняем nop(), с всяким разом увеличивая длину цикла. Взамен nop() дозволено вызвать что-то больше пригодное, скажем, вычислить bitcoin hint-инструкцию (если таковая имеется), которая говорит процессору «у тебя есть время исполнить свои внутренние дела» (вновь-таки, припомним MESI – таких дел у процессора может быть море).
Задача с экспоненциальным back-off примитивна — сложно подобрать отличные параметры nInitialnStep,nThreshold. Эти константы зависят от архитектуры и от задачи. В коде выше значения для них по умолчанию взяты с потолка.
Следственно на практике достаточно недурным выбором для десктопных процессоров и серверов исходного яруса будет yield() back-off — переключение на иной поток. Тем самым мы отдаем свое время иным, больше везучим потокам, в вере, что они сделают то, что им требуется, и не будут нам мешать (а мы — им).
Стоит ли вообще использовать back-off стратегии? Эксперименты показывают, что стоит: примененная в надобном тесном месте верная back-off тактика может дать выигрыш в продуктивности lock-free контейнера в разы.

Рассмотренные back-off стратегии помогают решить задачу с неудачными CAS, но никак не содействуют выполнению стержневой задачи — операций со стеком. Дозволено ли каким-то образом объединить push/popи back-off, Дабы back-off тактика энергично помогала выполнению операции?

Elimination back-off

Разглядим задачу неудачного CAS в push/pop с иной стороны. Отчего CAS неудачен? Потому что иной поток изменил m_Top. А что делает данный иной поток? Исполняет push() либо pop(). Сейчас подметим, что операции push и pop для стека комплементарны: если один поток исполняет push(), а иной в это же время —pop(), то в тезисе вообще не имеет смысла обращаться к вершине стека m_Top: push-поток мог бы легко передать свои данные pop-потоку, при этом основное качество стека — LIFO – не нарушается. Остается придумать, как свести совместно оба эти потока, минуя вершину стека.


В 2004 году Hendler, Shavit и Yerushalmi предложилимодификацию алгорифма Treiber’а, в котором задача передачи данных между push- и pop-потоками без участия вершины стека решается с поддержкой специальной back-off стратегии, названной имиисключающей back-off стратегией (elimination back-off, я бы перевел ещё как поглощающая back-off тактика).

Имеется массив elimination array размером N (N — малое число). Данный массив является членом класса стека. При неуспехе CAS, уходя в back-off, поток создает дескриптор своей операции (push либо pop) и случайным образом выбирает произвольную ячейку этого массива. Если ячейка пуста, он записывает в неё указатель на свой дескриптор и исполняет обыкновенный back-off, скажем, экспоненциальный. В этом случае поток дозволено назвать пассивным.
Если же выбранная ячейка теснее содержит указатель на дескриптор P операции какого-то иного (пассивного) потока, то поток (назовем его энергичным) проверяет, что это за операция. Если операции комплементарны — push и pop, — то они взаимно поглощаются:

  • если энергичный поток исполняет push, то он записывает в дескриптор P свой довод, передавая таким образом его в операцию pop пассивного потока;
  • если энергичный поток исполняет pop, то он читает из дескриптора P довод комплементарной операцииpush.


После этого энергичный поток помечает запись в ячейке elimination array как обработанную, Дабы пассивный поток при выходе из back-off увидел, что кто-то волшебным образом исполнил его работу. В итоге энергичный и пассивный потоки исполнят свои операции без обращения к вершине стека.
Если же в выбранной ячейке elimination array операция та же самая (обстановка push-push либо pop-pop), — не повезло. В этом случае энергичный поток исполняет обыкновенный back-off и дальше пытается исполнить свой push/pop как традиционно, — CAS вершины стека.
Пассивный же поток, окончив back-off, проверяет свой дескриптор в elimination array. Если дескриптор имеет отметку, что операция исполнена, то есть нашелся иной поток с комплементарной операцией, то пассивный поток удачно завершает свой push/pop.
Все вышеописанные действия выполняются в lock-free повадке, без каких-либо блокировок, следственно настоящий алгорифм труднее описанного, но толк от этого не меняется.
Дескриптор содержит код операции — push либо pop, — и довод операции: в случае push — указатель на добавляемый элемент, в случае pop поле указателя остается пустым (nullptr), в случае триумфа elimination в него записывается указатель на элемент поглощающей операции push.
Elimination back-off разрешает гораздо разгрузить стек при высокой нагрузке, а при малой, когда CAS вершины стека примерно неизменно удачен, такая схема не привносит вообще никакого оверхеда. Алгорифм требует тонкой настройки, заключающейся в выборе оптимального размера elimination array, что зависит от задачи и реальной нагрузки. Дозволено также предложить адаптивный вариант алгорифма, когда размер elimination array изменяется в маленьких пределах в процессе работы, подстраиваясь под нагрузку.
В случае разбалансированности, когда операции push и pop идут пачками — много push без pop, после этого много pop без push, — алгорифм не даст какого-либо ощутимого выигрыша, правда и специального проигрыша в продуктивности быть не должно по сопоставлению с типичным алгорифмом Treiber’а.

Flat combining

До сих пор мы говорили о lock-free стеке. Разглядим сейчас обыкновенный lock-based стек:

template <class T> class LockStack {
    std::stack<T *> m_Stack;
    std::mutex      m_Mutex; 
public:
    void push( T& v ) {
        m_Mutex.lock();
        m_Stack.push( &v );
        m_Mutex.unlock();
    }
    T * pop() {
        m_Mutex.lock();
        T * pv = m_Stack.top();
        m_Stack.pop()
        m_Mutex.unlock();
        return pv;
    }
};

Видимо, что при соперником выполнении продуктивность его будет крайне низка — все обращения к стеку сериализуются на мьютексе, всё выполняется сурово ступенчато. Дозволено ли как-нибудь повысить performance?
Если N потоков единовременно обращаются к стеку, только один из них захватит мьютекс, остальные и, в меньшей степени, для очереди.
Получивший становление в последние годы flat combining является специальным трендом при построении конкурентных контейнеров — как lock-free, так и fine grained lock-based.
Верю, мы ещё встретимся с этими техниками в последующем.

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

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