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

Lock-free конструкции данных. 1 — Предисловие

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

Я верю, что эта статья станет началом цикла заметок о 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), которые не являются непременными, но разрешают в некоторых случаях значительно разгрузить процессор в условиях мощной нагрузки, когда много пото

 

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

 

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