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

Разработка → Lock-free структуры данных. 1 — Начало


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



Разговор о lock-free структурах данных бессмыслен без освещения таких тем, как атомарные операции, модель памяти, реализованные в том или ином языке программирования (если, конечно, язык достаточно взрослый, чтобы задуматься о своей модели памяти), безопасное освобождение памяти, компиляторы и используемые ими оптимизации, современные архитектуры процессоров, — все эти темы будут в той или иной степени затронуты в данном цикле. Я беру на себя смелость рассказать обо всех этих вещах, хотя не считаю себя абсолютным экспертом ни в одной из них. С другой стороны, не имея представления о них, я не смог бы написать и развивать библиотеку libcds, — open source C++ библиотеку lock-free контейнеров и алгоритмов безопасного освобождения памяти (safe memory reclamation). Cds – это аббревиатура Concurrent Data Structure, а префикс “lib” – это, как ни странно, “library”.

Начну я с истории появления библиотеки. Дело было в далеком 2006 году.
2006 год


Тогда я работал в довольно крупной компании, пишущей софт для одного телекоммуникационного оператора из Большой Тройки. Мы разрабатывали довольно сложные серверные приложения для зоопарка аппаратных платформ, в которых на первом месте стояла (и всегда будет стоять) проблема производительности. Она решалась, в числе прочего, методом распараллеливания обработки данных. Как водится, распараллеливание приводило к возникновению общих (shared) данных, доступ к которым требовалось синхронизировать. Как-то в одном из обсуждений мой коллега походя спросил: “а ты слышал что-нибудь о lock-free очередях?” В то время я не знал об этом ничего. Но, спросив у гугла, нашел несколько статей, в которых приводился псевдокод lock-free очереди. Прочитав их несколько раз, я ничего не понял. Точнее, я перешел в состояние “ничего не понял” после того, как, засучив рукава и сказав “щас!” всему миру (мол, все вы дураки, один я тут умный), я попытался “упростить” алгоритмы, приведя их в соответствие со здравым смыслом. Спустя месяц борьбы с segmentation fault, мой здравый смысл сдался. Вот тогда я и “ничего не понял”. Я не понял, как ЭТО вообще работает, и даже если ОНО как-то работает, как это можно реализовать на C++. Но ведь как-то оно должно работать, иначе умные люди не писали бы эти статьи, и другие умные люди на них бы не ссылались (статьи были научными, и в конце каждой, как водится в научном сообществе, приводились списки литературы). Следуя этим ссылкам, за год я прочитал несколько десятков мегабайт полезной и не очень информации, начиная от software developer guide по процессорным архитектурам и заканчивая обзорными статьями по общим подходам реализации lock-free алгоритмов. Попутно я что-то пописывал (на C++, разумеется) на эту тему, реализуя те или иные примитивы. Следует отметить, что в это время (год 2006-2007) стандарт C++11 ещё оптимистично назывался C++0x, в STL ещё не было атомарных примитивов, да и интерфейс ещё только намечался, а компиляторы иногда капризничали на моих атомарных примитивах и выдавали нерабочий код на особо критичных участках. К 2008 году у меня начали обрисовываться туманные контуры библиотеки libcds. Первые тесты на разных платформах дали обнадёживающие, иногда ошеломительные (“это стало быстрее в 50 раз!!!”), результаты, и я полностью погрузился в мир lock-free. В 2010 я выложил на SourceForge первую (0.5.0) версию библиотеки. На сегодня свежайшая версия библиотеки – 1.4.0, идет работа над версией 1.5.0.

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


В 80-х годах прошлого века было популярно так называемое структурное программирование, позиционировавшееся как метод написания хороших программ. Апологетом структурного программирования был Николас Вирт, автор язык Pascal, написавший бестселлер “Алгоритмы + структуры данных = программы”. Интересно, что эта старая формула указывает на слабое место современных API типа pthreads, Win32 API, предлагаемых операционными системами: API дают средство построения параллельных программ (это средство – потоки, threads), но не дают средств построения параллельных структур данных, обеспечивающих совместный доступ. Вместо этого API предоставляют средства ограничения доступа к данным в виде примитивов синхронизации. Однако синхронизация – это узкое место параллельных программ. По своей сути синхронизация – это антипод параллельности: распараллеливая алгоритмы, мы работаем с последовательными структурами данных, обеспечивая их работу примитивами синхронизации – критическими секциями, мьютексами (mutex), условными переменными (condvar); в результате мы выстраиваем все наши потоки в очередь на доступ к структуре данных, тем самым убивая параллельность. Примитивы синхронизации иногда являются объектами ядра ОС, поэтому обращение к такому объекту может быть очень дорогим: может потребоваться переключение контекста, переход на уровень ядра ОС, поддержка очередей ожидания доступа к защищаемым примитивом синхронизации данным и пр. И все это, быть может, только для того, чтобы поменять в данных значение одного единственного указателя, то есть выполнить одну-две ассемблерных инструкции. Накладные расходы могут быть (по факту и есть) очень велики. Кроме того, не стоит забывать, что объект ядра ОС – это ограниченный по количеству ресурс.

Ещё одним недостатком синхронизации является слабая масштабируемость. При возрастании числа потоков синхронизированный доступ к данным становится узким местом программы; зачастую при увеличении степени параллельности вместо пропорционального увеличения производительности мы получаем её ухудшение в условиях большой нагрузки (high contention).

Руководствуясь формулой Вирта “Алгоритмы + структуры данных = программы”, в своей работе над libcds я сосредоточился только на структурах данных: в библиотеке вы не найдете алгоритмов параллельной сортировки или параллельного for-each. Библиотека содержит только конкурентные структуры данных – очередь, список, map, set и т.п, — и необходимые алгоритмы поддержки lock-free данных, в первую очередь это алгоритмы безопасного освобождения памяти (safe memory reclamation). Зачастую та или иная структура данных представлена несколькими реализациями. Так задумывалось изначально: как правило, существует несколько интересных алгоритмов, реализующих очередь или map, и я не знаю в общем случае, какой из них “лучше”: во-первых, понятие “лучше” или “хуже” относительно и зависит от конкретного железа и конкретной задачи, во-вторых, пока не реализуешь алгоритм и не сравнишь его с другими, не поймешь, лучше он или нет. Ну а если алгоритм реализован и отлажен, то почему бы ему не занять своё место в библиотеке (и предоставить нелегкий выбор пользователю)?..
Лирическое отступление
Кстати, в этом плане у меня претензия к STL: почему, например, map во всех известных мне реализациях STL сделан как red-black tree? Есть много других структур данных, подходящих для реализации map, например, AVL tree, которое является таким же бинарным деревом, но с более сильным критерием сбалансированности (к тому же – наша разработка). Видимо, не только меня мучают такие вопросы: я встречал статьи, в которых сравнивались реализации red-black tree и AVL tree, и выводы в этих статьях были не однозначно в пользу red-black tree: во многих задачах (и на многих архитектурах) AVL tree оказывалось быстрее.



В академической среде изучение способов реализации конкурентных структур данных, обеспечивающих одновременный доступ к разделяемым данным, привело к созданию нескольких основных направлений:
  • Lock-free структуры данных;
  • Fine-grained algorithms;
  • Транзакционная память (transactional memory)


В libcds нет реализаций, основанных на транзакционной памяти. Транзакционная память – это обширная область исследований, нацеленная в основном на будущее. Алгоритмы, основанные на транзакционной памяти, подразумевают, грубо говоря, что память поддерживает атомарные транзакции, которые можно атомарно принять (commit) или отклонить (rollback). Очевидно, что такая память должна быть реализована в железе; существующие софтверные реализации, по признанию самих исследователей, не обладают достаточной производительностью. Ради справедливости стоит отметить, что процессоры Intel архитектуры Haswell уже имеют поддержку транзакционности в своей системе команд, так что стоит ожидать, что расцвет алгоритмов, построенных на принципах транзакционной памяти, не за горами.

Fine-grained алгоритмы – это изощренные методы синхронизации, как правило, построенные не на применении примитивов синхронизации, предоставляемых OC, а на применении “легких” атомарных примитивов, например, на spin-lock. На основе таких примитивов строятся структуры данных, допускающие параллельное чтение или даже параллельную запись, в которых синхронизация производится на уровне узла (node) или страницы (page, bucket) структуры данных и встроена в сами алгоритмы операций над этой структурой. Часто fine-grained контейнеры показывают производительность, сравнимую с производительностью lock-free контейнеров при относительно небольшой нагрузке. Библиотека libcds не брезгует такими структурами данных.

Lock-free структурами данных я буду называть структуры данных, не требующие внешней синхронизации доступа. Это неформальное, чисто техническое определение, отражающее внутреннее строение контейнера и операций над ним. Слово “внешней” здесь выделено намеренно: надо понимать, что вовсе без применения специальной поддержки со стороны процессора lock-free структуры данных построить, скорее всего, не удастся. Но поддержка такого рода в lock-free контейнерах обеспечивается не синхронизацией доступа к последовательным методам контейнера, а механизмом атомарной модификации, зашитым внутрь методов контейнера, либо внутренней синхронизацией на уровне составных частей контейнера (узлов, buckets, страниц).

Формальное определение lock-free объекта звучит так [Her91]: разделяемый объект называется lock-free объектом (неблокируемым, non-blocking объектом), если он гарантирует, что некоторый поток закончит выполнение операции над объектом за конечное число шагов вне зависимости от результата работы других потоков (даже если эти другие потоки завершились крахом). Более строгое понятие wait-free объекта гласит: объект является wait-free, если каждый поток завершит операцию над объектом за конечное число шагов. Условие lock-free гарантирует продвижение как минимум какого-то одного потока, тогда как более сильное условие wait-free гарантирует успешное выполнение для всех потоков. В теории конкурентных структур данных существует также понятие linearizability [Her90], играющее важную роль в формальных доказательствах корректности lock-free алгоритмов. Грубо говоря, алгоритм является линеаризуемым (linearizable), если результат его работы виден по окончании алгоритма. Например, результат вставки в список виден по окончании функции вставки. Звучит по-идиотски, но возможно придумать алгоритм, который делает вставку в список и не является линеаризуемым. Например, всякого рода буферизация может привести к нарушению этого свойства: вместо вставки мы можем поместить новый элемент в некий буфер, дать команду другому потоку “вставь элемент из буфера в список” и не ждать, когда элемент будет вставлен; или же мы будем вставлять только тогда, когда в буфере накопится достаточное число элементов. Тогда по окончании функции вставки в список мы не можем гарантировать, что элемент находится в списке; всё, что мы можем гарантировать, это что элемент непременно будет (будущее время!) вставлен в список сейчас или позже.

Эти понятия широко используются в научно-исследовательских работах; моя статья не претендует на звание научно-исследовательской, поэтому я буду применять термин lock-free в “обывательском” смысле для обозначения класса конкурентных контейнеров, построенных без применения традиционных шаблонов синхронизации, либо не требующих внешней синхронизации.

Лирическое отступление 2 - О времени
Следует отметить, что понятие времени (причинно-следственных связей) как-то размыто в lock-free структурах данных. При традиционном подходе мы действуем так: блокируем доступ к контейнеру, что-то с ним делаем (например, добавляем элемент), разблокируем. В момент разблокировки мы знаем, что вставленный элемент находится в контейнере. В lock-free контейнере всё не так. Нам не нужно блокировать доступ, мы просто вызываем метод добавления. Если он возвратил true, значит, вставка прошла успешно. Но это не значит, что элемент находится в контейнере, — он уже может быть удален конкурирующим потоком. Это демонстрирует важное отличие lock-free контейнеров от традиционных a la STL, — мы не можем вытаскивать внутренности реализации контейнера наружу; например, концепция итераторов, широко используемая в STL, не применима к конкурентным структурам данных. Я надеюсь подробно обсудить построение интерфейсов классов конкурентных контейнеров в одной из следующих статей.



Чем же характеризуются lock-free алгоритмы? Пожалуй, первое, что бросается в глаза – это их сложность. Вы представляете, что из себя представляет обычная очередь, реализованная на односвязном списке? Очень простой код:
Показать очень простой код
struct Node {
		Node * m_pNext ;
};
class queue {
		Node * m_pHead ;
		Node * m_pTail ;
public:
		queue(): m_pHead( NULL ), m_pTail( NULL ) {}
		void enqueue( Node * p )
		{
			p->m_pNext = m_pTail ;
			m_pTail = p ;
			if ( !m_pHead )
				m_pHead = p ;
		}
		Node * dequeue()
		{
			if ( !m_pHead ) return NULL ;
			Node * p = m_pHead ;
			m_pHead = p->m_pNext ;
			if ( !m_pHead )
				m_pTail = NULL ;
			return p ;
		}
};


Можно написать и ещё короче. А вот как выглядят методы enqueue/dequeue (синонимы push/pop) реализации классического алгоритма lock-free очереди Майкла & Скотта ([Mic96], код взят с минимальными сокращениями из класса cds::intrusive::MSQueue библиотеки libcds):
Показать то же самое, но написанное очень громоздко
bool enqueue( value_type& val )
{
      node_type * pNew = node_traits::to_node_ptr( val )  ;

      typename gc::Guard guard    ;
      back_off bkoff  ;

      node_type * t    ;
       while ( true ) {
           t = guard.protect( m_pTail, node_to_value() )  ;

           node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire)  ;
           if ( pNext != null_ptr<node_type *>() ) {
                // Tail is misplaced, advance it
                m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, 
                                                                                 CDS_ATOMIC::memory_order_relaxed ) ;
                continue    ;
           }

          node_type * tmp = null_ptr<node_type *>() ;
          if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, 
                   CDS_ATOMIC::memory_order_relaxed ))
          {
                    break    ;
          }
          bkoff()    ;
     }
    ++m_ItemCounter    ;

     m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_acq_rel, 
                                                                        CDS_ATOMIC::memory_order_relaxed );

     return true ;      
}

value_type * dequeue()
{
     node_type * pNext   ;
     back_off bkoff      ;
     typename gc::template GuardArray<2>  guards  ;

      node_type * h       ;
      while ( true ) {
           h = guards.protect( 0, m_pHead, node_to_value() )           ;
           pNext = guards.protect( 1, h->m_pNext, node_to_value() )    ;
           if ( m_pHead.load(memory_model::memory_order_relaxed) != h )
                continue    ;

           if ( pNext == null_ptr<node_type *>() )
                 return NULL  ;    // empty queue

           node_type * t = m_pTail.load(memory_model::memory_order_acquire);
           if ( h == t ) {
                // It is needed to help enqueue
               m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, 
                                                                                  CDS_ATOMIC::memory_order_relaxed ) ;
               continue    ;
           }

           if ( m_pHead.compare_exchange_strong( h, pNext, 
                     memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed ))
           {
                    break    ;
           }
           bkoff()    ;
     }

     --m_ItemCounter          ;

     dispose_node( h )   ;
     return pNext ;
}



Алгоритм сложный. Тот же односвязный список, но даже простое визуальное сравнение обычной и lock-free очереди уже кое о чём говорит. В lock-free очереди мы видим:
  • бесконечный цикл – мы пытаемся выполнить операцию, пока не получится. Это типичный паттерн применения атомарной операции compare_exchange;
  • защиту локальных переменных (guards) с помощью одного из методов безопасной работы с памятью (указателями) в lock-free алгоритмах, в данном случае – это метод Hazard Pointers;
  • применение атомарных примитивов C++11 – load, compare_exchange, барьеров памяти memory_order_xxx;
  • helping — очень распространенный прием в lock-free алгоритмах, когда один поток помогает другому сделать его работу;
  • применение back-off стратегий (функтор bkoff), которые не являются обязательными, но позволяют в некоторых случаях существенно разгрузить процессор в условиях сильной нагрузки, когда много потоков обращаются к очереди одновременно


Сейчас я не буду ничего объяснять, так как все эти вещи весьма обширные и требуют отдельного разговора. Пусть сохранится интрига. Я надеюсь осветить эти темы в будущих статьях.

Следующая статья будет посвящена краеугольному понятию, на котором основаны все lock-free структуры данных, — атомарности и атомарным примитивам.


И напоследок – полезные книги (не статьи), в которых, с моей точки зрения, наиболее полно освещены вопросы конкурентного программирования.
На сегодняшний момент мне известны две хорошие работы:

1. Nir Shavit, Maurice Herlihy The Art of Multiprocessor programming. Перевода на русский язык, насколько я знаю, нет. Книга очень известных в мире lock-free авторов описывает множество параллельных алгоритмов и способов их построения. Все примеры на Java, поэтому авторам не пришлось заботиться об освобождении памяти, модели памяти C++ (в Java модель памяти более строгая) и прочих вещах, которые в Java внедрены в сам язык, а в C++ всё это приходится писать самому. Несмотря на это, книга очень полезная.

2. Anthony Williams C++ Concurrency in Action (есть русский перевод). Книга известного в мире C++ автора посвящена вопросам multithread programming именно в C++, доступно описывает новый стандарт C++11 и новые возможности, предоставляемые стандартом для реализации параллельных алгоритмов. Настоятельно рекомендуется к прочтению.

Ссылки:

[Her90] M. Herlihy, J. M. Wing Linearizability: A Correctness Condition for Concurrent Objects, ACM Transactions on Programming Languages and Systems, 1990

[Her91] M. Herlihy A Methodology for Implementing Highly Concurrent Data Object, 1991

[Mic96] M.Michael, M.Scott Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

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

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

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

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

  • +8
    С нетерпением жду продолжения, потому что lock-free структуры для меня — все еще темный лес.
  • +2
    Тема очень важная. Спасибо за статью и особенно за ссылки.
  • +1
    Весьма полезный цикл намечается, хотя пока не совсем понятно, что есть gc::Guard::protect() и что за дополнительные аргументы у функций вроде compare_exchange_strong.
    • +2
      К сожалению, в рамках одной-двух статей всего не опишешь. Поэтому я вовсе не стал давать комментариев по коду, только вкратце намекнул на техники, которые применены. В следующих статьях надеюсь все эти вопросы — начиная от compare_exchange и до gc::Guard::Protect() — осветить подробно.
      • 0
        Получается, это и есть параллельные алгоритмы… Очень интересно.
  • +5
    Картинка намекает на то, что lock-free структуры на самом деле не существуют и ломают мозг? :)
    • +4
      Да, Вы верно угадали посыл картинки ;) Но Вы правы только во втором — действительно, ломают мозг. Насчет первого — существуют, так же как и невозможные фигуры
  • +1
    В похожей статье: habrahabr.ru/post/174369/ в комментариях предложили использовать SpinLock вместо Mutex-а. По графикам это получается какая-то панацея? Нет?
    • +3
      Действительно, во многих случаях spin-lock может дать значительный выигрыш. Но ничего бесплатного не бывает. Я планирую подробно остановиться на spin-lock'ах в одной из следующих статей, так как это хороший и простой пример, сейчас же отмечу: spin-lock хорош, когда он защищает очень короткую часть кода, — буквально несколько ассемблерных инструкций (где-то на форумах Intel проскальзывала оценка в 1 — 8 asm insn). Если же spin-lock защищает нечто бОльшее по размеру — велика вероятность «верчения» при высокой загрузке (high contention): процессоры/ядра будут заняты на 100%, но никакой полезной работы делать не будут, будут вертеться на spin-lock'е.
      В общем, вывод таков: только вы сами, для своей конкретной задачи и железа, можете сказать, подойдет ли вам spin-lock или нет.
      • +1
        Спасибо за ответ. Ждем статью).
      • +1
        В .NET, например, SpinWait.SpinOnce после определённого количества вызовов усыпляет поток — вроде довольно полезно.
        • +2
          Заставляете меня забегать вперед ;-)
          Согласен, не только полезно, но и нужно! Не безусловно усыплять конечно же, а проводить какие-то действия. Это называется back-off стратегией, — что делать, когда не получается захватить ресурс. Одна из стратегий — переключение на другой поток (sched_yield, Sleep(0)), — на практике показывает себя с довольно хорошей стороны, хотя не очень популярна в академическом мире, где властвует экспоненциальный back-off (это, грубо говоря — попытка захвата ресурса с экспоненциально увеличивающимся интервалом ожидания). SpinWait/SpinOnce, думаю, гибрид этих двух методик.
      • +1
        > велика вероятность «верчения» при высокой загрузке (high contention)

        тут очень много зависит от реализации spin-lock. Ticket based spin lock (используется в linux kernel) страдает этой проблемой, да.

        Тут немного по этой тематике pdos.csail.mit.edu/papers/linux:lock.pdf
    • +1
      В Win32 есть функция InitializeCriticalSectionAndSpinCount. Она посредством объекта CriticalSection использует для ожидания сначала спинлок, и только если после заданного числа итераций объект не освободился — то используется «тяжелый» семафор.
    • 0
      правило такое — если вы защищаете спинлоком код, который выполняется дольше чем два переключения контекста (плюс наполнение кэша и TLB) — вам нужно использовать мютекс. В противном случае спинлок будет эффективен. НО:
      есть проблема масштабирования. куча статей на эту тему гласит — на малом кол-ве ядер/процессоров спинлок хорош. где-то после 5 и далее хорош только mutex.
  • +1
    Спасибо очень интересно
    Будет обо что почесать руки )
  • 0
    Будущее здесь. Спасибо ;)
  • +2
    Спасибо! Очень интересно! Поддержка ARM'ов в вашей библиотеке планируется?
    • +3
      Да, планируется. В принципе, если компилятор поддерживает C++11 (конкретно — <atomic>), то структуры данных из libcds уже сейчас поддерживают ARM. Осталось избавиться от жесткой привязке к архитектуре/ОС в либе. Ну и потестить. Надеюсь к новому году (как у меня принято :) выпустить новую версию без такой привязки.
  • +6
    На летней школе Microsoft Research в 2012 в Питере был Maurice Herlihy и как раз рассказывал про lock-free.
    Вот презентации: раз, два, три.
    • +2
      О, черт, а я и не знал! Было бы интересно послушать одного из пионеров lock-free, теоретика и практика. Как правило, такие люди мыслят довольно нестандартно, есть чему поучиться…
      Спасибо!
  • 0
    Продолжайте, очень интересно как без блокировок организован доступ к данным. И, если можно про паттерны, когда потоки помогают друг другу можно что-нибудь отдельное рассказать.
  • 0
    Продолжайте, и интересно, и полезно! Думаю, для многих это полностью новый взгляд на вещи!
  • +2
    По Lock-Free (и далее Wait-Free) синхронизации могу порекомендовать книгу Concurrent and Distributed Computing in Java (Vijay K. Garg), в частности, главу 5 — Wait-Free Synchronization. Несмотря на наличие Java в названии, книга в основном посвящена теории, алгоритмам и их анализу.

    Эта книга была настольной при подготовке к экзамену по параллельному программированию. Не уверен, есть ли более полезная книга по обозначенной теме.
  • 0
    Слушайте, очень-очень-очень хочется не столько про детали реализации, сколько про типичные и работоспособные паттерны использования библиотеки. Будет?
    • 0
      Будет, планирую.
      Для торопливых :). В целом, паттерн использования структуры данных из libcds таков: объявляете объект и работаете с ним из разных потоков (можно, конечно, и из одного, но тогда вся соль теряется — STL в single thread однозначно будет быстрее). Отличие от STL в том, что не надо вводить никакой синхронизации при обращении к методам контейнера.
      Подводные камни: инициализация/терминация библиотеки (считаю, что довольно легкая, пример здесь, секция How to use) и освобождение памяти — вот это очень тонкий момент. Можно сказать, что освобождение основано на событиях: либа сама дернет указанный в template-аргументах контейнера disposer-функтор, когда элемент можно безопасно удалить. Тонкость в том, что вызов диспозера может произойти из другого потока и/или задолго после окончания времени жизни самого контейнера.
      • 0
        Кстати, а на всяких GPU-ных архитектурах оно работает?
        • 0
          Я не работал с GPU, так что не могу даже оценить, работает ли хоть теоретически.
  • +2
    как правило пропасть между пониманием атомарных операций и конечной структорой данных — огромна. Надеюсь вы сможете сделать этот переход, а не просто еще раз опишите что такое атомарные операции.
    • +1
      Согласен. Но без азов трудно будет писать далее. Азы эти непростые, атомарность — самое простое из них. Далее следует упорядочение чтения/записи в память…
      Спасибо за надежду ;-) В конечном счете, это моя цель — показать, как из этих кирпичиков построить контейнер. Терпения и упорства вам и мне ;-)
      Кстати, лучшее описание этого я видел у Вильямса в его C++ Concurrency in Action.
  • 0
    Уточнение: освобождение памяти — тонкий момент для intrusive-контейнеров (namespace cds::intrusive). Для обычных контейнеров в стиле STL (namespace cds::container) и при использовании обычного аллокатора std::allocator (а это дефолтный аллокатор в libcds) об освобождении можно не беспокоиться.
    То есть подводные камни сводятся только к инициализации либы. Инициализация предполагает выбор способа управления памятью (safe memory reclamation, что можно трактовать как легкий специализированный сборщик мусора). Таких способов либа предоставляет несколько. Обычно в приложении используется только один. Мой совет — Hazard Pointer (cds::gc::HP) или буферизованный user-space RCU (cds::urcu::gc< cds::urcu::general_buffered<> >), они наиболее быстрые по тестам; Hazard Pointer — наиболее отлаженный, существует с первых версий libcds.
  • +2
    Очень интересно, пишите еще!
    Только пожалуйста, скорее переходите к делу, с таким началом у вас могучая серия получится, которая не понятно еще, когда вся выйдет)
  • 0
    Есть ещё интересный бложек preshing.com в том числе про тему lock-free, модели памяти и всякие всячести и красивые картинки. Так же там автор описывает свой mintomic.github.io. Может кому-нибудь будет интересно.

    UPD: Да, забыл — за статью спасибо. :)
  • 0
    Когда-то давно нужно было написать lock-free очередь на Delphi. Алгоритм родился сам, получился до безобразия простым и работает уже многие годы. Но писался он для двух потоков. Когда понадобилось добавить третий — код заметно вырос. Решить проблему в общем виде пытался, но реализации выходили неэффективные, да и та конкретная задача довольствовалась тремя потоками.

    Очень интересно, причём именно теория. Пишите ещё!

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