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

Lock-free конструкции данных. Следующий трактат

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

Как вы, вероятно, додумались, эта статья посвящена lock-free очередям.

Очереди бывают различные. Они могут различаться по числу писателей (producer) и читателей (consumer) – single/multi producer — single/multi consumer, 4 варианта, — они могут быть ограниченными (bounded, на основе предраспределенного буфера) и неограниченными, на основе списка (unbounded), с помощью приоритетов либо без, lock-free, wait-free либо lock-based, со суровым соблюдением FIFO (fair) и не дюже (unfair) и т.д. Детально типы очередей описаны в этой и этой статьях Дмитрия Вьюкова. Чем больше специализированы требования к очереди, тем, как правило, больше результативным оказывается её алгорифм. В данной статье я разгляжу самый всеобщий вариант очередей — multi-producer/multi-consumer unbounded concurrent queue без поддержки приоритетов.

Очередь является, вероятно, излюбленной конструкцией данных для изыскателей. С одной стороны, она примитивна как полено, с иной, не так примитивна, как стек, — все-таки имеет два конца, а не один; раз имеет два конца, появляются увлекательные задачи, как ими руководить в многопоточной среде. Число публикаций с разными вариациями алгорифма очереди зашкаливает, охватить их все не представляется допустимым. Остановлюсь лаконично на признанных и начну с классической очереди.

Классическая очередь

Классическая очередь — это список (не значимо, односвязный либо двусвязный) с двумя концами — головой Head и хвостом Tail. С головы читаем, в хвост пишем.

Наивная стандартная очередь

Копипаст из первой статьи цикла

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 ;
		}
};

Не ищите, тут нет конкурентности, — это легко иллюстрация, насколько примитивный выбран предмет для разговора. В статье мы увидим, что бывает с примитивными алгорифмами, если их начинают приспосабливать к конкурентной среде.

Типичным (1996 год) алгорифмом lock-free очереди считается алгорифм Michael & Scott.
Как неизменно, простыня код приводится из библиотеки libcds, если в ней есть реализация рассматриваемого алгорифма, в сокращенном (адаптированном) виде. Полный код — см. класс cds::intrusive::MSQueue. Комментарии вставлены по коду, усердствовал, Дабы они не были дюже уж тоскливыми.

bool enqueue( value_type& val )
{
     /* 
        Implementation detail: в моей реализации node_type и value_type - 
        это не одно и то же и требует приведения из одного в другое
        Для простоты дозволено считать, что  node_traits::to_node_ptr - 
        это легко static_cast<node_type *>( &val )
	*/
      node_type * pNew = node_traits::to_node_ptr( val )  ;

      typename gc::Guard guard;	// Защитник, скажем, Hazard Pointer

      // Back-off тактика (template-довод класса)
      back_off bkoff;

      node_type * t;

       // Как неизменно в lock-free, долбимся, пока не сделаем надобное дело...
       while ( true ) {
           /* 
            Охраняем m_pTail, как как мы дальше будем читать его поля
            и не хотим попасть в обстановку чтения из удаленной (delete) 
            памяти
	     */
           t = guard.protect( m_pTail, node_to_value() );

           node_type * pNext = t->m_pNext.load(
                    memory_model::memory_order_acquire);

           /* 
            Увлекательная деталь: алгорифм допускает, 
            что m_pTail может указывать не на хвост,
            и верит, что следующие вызовы настроят 
            хвост верно. Классический пример многопоточной взаимопомощи
	     */
           if ( pNext != nullptr ) {
                // Упс! Требуется зачистить хвост 
                //(в прямом смысле) за иным потоком
                m_pTail.compare_exchange_weak( t, pNext,
                       std::memory_order_release, std::memory_order_relaxed);

/* 
                  Необходимо начинать все вначале, даже если CAS не благополучен
                  CAS неудачен — значит, m_pTail кто-то 
                  поспел поменять позже того, как мы его прочитали.
                */
                continue    ;
           }

          node_type * tmp = nullptr;
          if ( t->m_pNext.compare_exchange_strong( tmp, pNew,
                                std::memory_order_release,
                                std::memory_order_relaxed ))
          {
	    // Удачно добавили новейший элемент в очередь.
                    break    ;
          }

          /* 
            У нас ничего не получилось — CAS не сработал.
            Это значит, что кто-то поспел влезть перед нами.
            Найдена соперничество — чтобы не усугублять её, 
            отступим на дюже короткий момент времени — 
            вызываем функтор back_off
          */
          bkoff();
     }

      /*
       Вообще, счетчик элементов — это по желанию...
       Как видно, данный счетчик не дюже-то и точный — 
       элемент теснее добавлен, а счетчик меняем только теперь. 
       Такой счетчик может говорить лишь о 
       порядке числа элементов, но использовать его 
       как знак пустоты очереди невозможно 
      */
      m_ItemCounter    ;

     /*
	Наконец, пытаемся изменить сам хвост m_pTail.
      Нас тут не волнует, получится у нас либо нет, — если нет, 
      за нами почистят, см. 'Упс!' выше и ниже, в dequeue
     */
     m_pTail.compare_exchange_strong( t, pNew,
               std::memory_order_acq_rel, std::memory_order_relaxed );

     /* 
       Данный алгорифм неизменно возвращает true. 
       Другие, скажем, bounded queue, могут
       воротить и false, когда очередь полна.
       Для единообразия интерфейса enqueue 
       неизменно возвращает знак триумфа
     */
     return true;      
}

value_type * dequeue()
{
     node_type * pNext;
     back_off bkoff;

    // Для dequeue нам необходимо 2 Hazard Pointer'а
     typename gc::template GuardArray<2>  guards;

      node_type * h;

      // Долбимся, пока не сумеем исполнить...
      while ( true ) {
           // Читаем и охраняем голову m_pHead
           h = guards.protect( 0, m_pHead, node_to_value() );
           // и следуюий за головой элемент
           pNext = guards.protect( 1, h->m_pNext, node_to_value() );

           // Проверяем: то, что мы только что прочли, 
           // осталось связанным?..
           if ( m_pHead.load(std::memory_order_relaxed) != h ) {
                // нет, - кто-то поспел нам все испортить... 
                // Начинаем вначале
                continue;
           }

           /* 
             Знак пустоты очереди. 
             Подметим, что в различие от хвоста голова неизменно 
             находится на верном месте
           */
           if ( pNext == nullptr )
                 return nullptr;    // очередь пуста

           /* 
             Тут мы читаем хвост, но охранять его 
             Hazard Pointer'ом не необходимо — нас не волнует содержимое, 
             на которое он указывает (поля конструкции)
           */
           node_type * t = m_pTail.load(std::memory_order_acquire);
           if ( h == t ) {
                /* 
                  Упс! Хвост не на месте: есть голова, 
                  есть дальнейший за головой элемент,
                  а хвост указывает на голову.
                  Требуется подмогнуть нерадивым товарищам...
		    */
               m_pTail.compare_exchange_strong( t, pNext,
                        std::memory_order_release, std::memory_order_relaxed);
               // Позже помощи все доводится начинать снова - 
               // следственно нам не значим итог CAS
               continue;
           }

           // Самый значимый момент — линкуем новую голову
           // То есть продвигаемся по списку ниже
           if ( m_pHead.compare_exchange_strong( h, pNext, 
                     std::memory_order_release, std::memory_order_relaxed ))
           {
                    // Удалось — завершаем наш безмерный цикл
                    break;
           }
           /* 
            Не удалось... Значит, кто-то нам помешал. 
            Дабы не мешать иным, отвлечемся на миг
           */
           bkoff()    ;
     }

    // Изменяем не дюже-то и пригодный счетчик элементов, 
    // см. коммент в enqueue
     --m_ItemCounter;

     // Это вызов функтора 'удаление элемента h'
     dispose_node( h );

     /* 
	!!! А вот это увлекательный момент!
      Мы возвращаем элемент, дальнейший за [бывшей] головой
      Подметим, что pNext все еще в очереди — 
      это наша новая голова!
     */
     return pNext;
}

Как видим, очередь представлена односвязным списком от головы к хвосту.
Какой в этом алгорифме значимый момент? Значимый момент — исхитриться руководить двумя указателями — на хвост и на голову — с поддержкой обыкновенного (не двойного!) CAS. Это достигается за счет, во-первых, того, что очередь никогда не пуста, — посмотрите наблюдательно на код, есть там где-нибудь проверки головы/хвоста на nullptr?.. Не обнаружите. Для обеспечения физической (но не логической) непустоты в конструкторе очерели потом найдем рассогласование прямого и обратного списка — что ж, придется потратить время на согласование (запуск fix_list).
Выходит, что в сухом остатке? И enqueue, и dequeue у нас сейчас имеют ровно по одному CAS. Цена — запускfix_list при выявлении нарушения списка. Огромная это цена либо крошечная — скажет эксперимент.
Рабочий код дозволено обнаружить в файле cds/intrusive.optimistic_queue.h, классcds::intrusive::OptimisticQueue библиотеки libcds.

Wait-free queue

Для заключения разговора о классической очереди стоит упомянуть об алгорифме wait-free очереди.
Wait-free – самое суровое требование среди прочих. Говорит оно о том, что время выполнения алгорифма должно быть безусловно и предсказуемо. На практике wait-free алгорифмы Зачастую приметно (сюрприз!)уступают по продуктивности своим менее суровым собратьям — lock-free и obstruction-free, — превосходя их по числу и трудности кода.
Строение многих wait-free алгорифмов достаточно стандартно: взамен того, Дабы исполнять операцию (в нашем случае enqueue/dequeue) они вначале объявляют её, — сберегают дескриптор операции совместно с доводами в некотором общедоступном разделяемом хранилище, — а после этого начинают помогать конкурирующим потокам: просматривают дескрипторы в хранилище и пытаются исполнить то, что в них (дескрипторах) записано. В итоге при огромный нагрузке несколько потоков исполняют одну и ту же работу, и только один из них будет победителем.
Трудность реализации таких алгорифмов на C в основном в том, как реализовать это хранилище и как избавиться от аллокации памяти под дескрипторы.
Библиотека libcds не имеет реализации wait-free очереди. Потому как сами авторы приводят в своем изыскании неутешительные данные о её продуктивности.

Итоги тестирования

В этой статье я решил изменить своей нелюбви к сравнительным тестам и привести итоги тестирования приведенных выше алгорифмов.
Тесты — синтетические, тестовая машина — двухпроцессорный Debian Linux, Intel Dual Xeon X5670 2.93 GHz, 6 ядер на процессор hyperthreading, итого 24 логических процессора. На момент проведения тестов машина была фактически свободной — idle на ярусе 90%.
Компилятор — GCC 4.8.2, оптимизация -O3 -march=native -mtune=native.
Тестируемые очереди — из пространства имен cds::container, то есть не интрузивные. Это значит, что для всякого элемента производится аллокация памяти. Сопоставлять будем со стандартными реализациямиstd::queue<T, std::deque<T>> и std::queue<T, std::list<T>> с синхронизацией мьютексом. Тип T – конструкция из 2-х целых. Все lock-free очереди основаны на Hazard Pointer.

Тест на выносливость

Достаточно особенный тест. Каждого 10 млн enqueue/dequeue пар операций. В первой части тест исполняет 10 млн enqueue, при этом 75% операций — это enqueue, 25% — dequeue (то есть в первой части 10 млн enqueueи 2.5 млн — dequeue). Вторая часть — только dequeue 7.5 млн раз, пока очередь не станет пустой.
Задумка при конструировании этого теста была такой: минимизировать воздействие кеша аллокатора, если, безусловно, у аллокатора есть кеш.
Безусловные данные — время выполнения теста:

Что дозволено сказать? Первое, что кидается в глаза — самой стремительной оказалась блокируемаяstd::queue<T, std::deque<T>>. Отчего? Думаю, все дело в работе с памятью: std::deque распределяет память блоками по N элементов, а не под всякий элемент. Это наводит на мысль, что в тестах нужно подчистую исключить воздействие аллокатора, так как он вносит довольно крупные задержки, да к тому же, как правило, имеет внутри себя мьютекс[ы]. Что ж, в libcds есть интрузивные версии всех контейнеров, которые не распределяют память под свои элементы, нужно испробовать тест с ними.
Что касается наших lock-free очередей, видно, что все те оптимизации, которые мы рассматривали применительно к MSQueue, дали свои плоды, правда и не такие уж крупные.

Prodcer/consumer test

Абсолютно себе жизненный тест. Есть N писателей и N читателей очереди. Каждого выполняется 10 млн операций записи, соответственно, и 10 млн операций чтения. На графиках число потоков — это сумма числа потоков читателей и писателей.
Безусловные данные — время выполнения теста:

Тут lock-free очереди ведут себя больше хорошо. Победителем оказалась OpimisticQueue, — значит, все те допущения, которые были заложены в её конструкцию, себя оправдали.
Данный тест больше приближен к действительности, — тут нет массового накопления элементов в очереди, следственно в игру вступают внутренние оптимизации аллокатора (я так думаю). Что ж, все верно, — чай, в конце концов, очередь предуготовлена не для безрассудного накопления, а для буферизации всплесков активности, и типичное состояние очереди — это неимение в ней элементов.

Бонус — к вопросу о стеке

Раз уж разговор зашел о тестах…
В перерыве между этой и предыдущей статьей о lock-free стеках я реализовал в libcds elimination back-off для стека Treiber’а. Сама реализация, точнее, путь от изложения подхода/псевдокода к завершенному продукту на C заслуживает отдельной статьи (которая, скорее каждого, никогда не будет написана, — слишком много кода пришлось бы в неё вставлять). В итоге получилось по сути то, что написано у авторов elimination back-off, но если посмотреть на код — абсолютно другое. Пока что доступно только в репозитории libcds.
Тут же хочу похвастаться привести итоги синтетических тестов. Тестовая машина — та же самая.
Тест — producer/consumer: одни потоки пишут в стек (push), другие — читают (pop). Читателей и писателей — равное число, всеобщее их число — это число потоков. Всеобщее число элементов — 10 млн (то есть 10 млнpush и 10 млн pop). Для стандартных стеков синхронизация осуществляется мьютексом.
Безусловное время выполнения теста:

Думаю, график говорит сам за себя.
Увлекательно, за счет чего достигнут столь высокий рост продуктивности elimination back-off? Казалось бы, за счет того, что push/pop аннигилируют друг с ином. Но если мы посмотрим на внутреннюю статистику (все классы контейнеров в libcds имеют свою внутреннюю статистику, по умолчанию отключенную), то увидим, что из 10 млн push/pop аннигилировали только 10 – 15 тысяч (в тесте с 64 потоками), то есть около 0.1%, при всеобщем числе попыток (то есть числе входа в elimination back-off) около 35 тысяч! Выходит, что основное превосходство elimination back-off в том, что при выявлении слишком огромный нагрузки некоторые потоки выводятся в спячку (в приведенных итогах сон пассивного потока в elimination back-off длится 5 миллисекунд), тем самым механически сокращая всеобщую нагрузку на стек.

Итоги

Выходит, мы разглядели классическую lock-free очередь, представленную как список элементов. Такая очередь характеризуется наличием 2-х точек соперничества — головы и хвоста. Мы разглядели типичный алгорифм Майкла и Скотта, а также несколько его совершенствований. Верю, что рассмотренные приемы оптимизации были увлекательны и могут сгодиться в повседневной жизни.

По итогам тестов дозволено сделать итог, что, хоть очереди и lock-free, волшебный CAS не дал какого-то возвышенного выигрыша в продуктивности. Следственно, нужно искать какие-то другие подходы, разрешающие отказаться от тесных мест (головы и хвоста), каким-то образом распараллелить работу с очередью.
Этим мы и займемся в дальнейшем «очередном трактате».

Продолжение следует…

 

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

 

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