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

Lock-free конструкции данных. Извне: вступление в libcds

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

В этой статье я даю короткий обзор того, как использовать библиотеку lock-free конструкций данных libcds. В реализацию я углубляться тут не буду, — это легко взор извне, взор со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие знаменитые конструкции данных. Отчасти это объясняется целевой областью – lock-free конструкции данных достаточно минималистичны по комплекту предоставляемых способов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому увлекательно – благо пожаловать под кат

Libcds является C библиотекой lock-free конструкций данных и способов неопасного освобождения памяти (safe memory reclamation, SMR) для lock-free конструкций. Она примерно header-only – все конструкции данных определены в .h-файлах заголовков и только реализация ядра алгорифмов SMR вынесена в небольшую динамическую библиотеку.

Короткий обзор SMR

Вероятно, самый тонкий момент при разработке lock-free конструкции данных – определить, в какой момент времени дозволено неопасно физически удалить элемент контейнера. Удаление элемента — неизменно двухфазная операция: вначале мы исключаем элемент из контейнера, после этого удаляем (deallocate) память, выделенную под элемент. При lock-free подходе вторая фаза – физическое удаление – требует, Дабы была полная убежденность, что никто (ни один из параллельных потоков) не имеет ссылки, всеобщей либо локальной, на удаляемый элемент.
За неопасное удаление отвечают алгорифмы SMR, которые дозволено рассматривать как специализированные сборщики мусора (garbage collectors, GC). В данной статье я не буду останавливаться на внутренних деталях реализации того либо другого алгорифма SMR, дам лишь всеобщее изложение, довольное для начала работы с libcds. Верю детально обсудить все алгорифмы в грядущих статьях.

В libcds реализованы следующие алгорифмы SMR:

  • Hazard Pointer – вероятно, 1-й и самый знаменитый из алгорифмов SMR. Изобретен Майклом (это фамилия) в 2002 году [Mic02, Mic03, Mic04]. Отличается относительной простотой и отличным быстродействием, предуготовлен для «охраны» локальных ссылок на элементы контейнера. Недочет – требует указания максимального числа единовременно работающих потоков. Заголовочный файл<cds/gc/hp.h>, класс cds::gc::HP
  • Pass-the-Buck — концептуально схож на Hazard Pointer, но не зависит от числа потоков. Предложен в 2002 году Herlihy, V. Luchangco и M. Moir [Her02, Her05]. Из-за автономности от числа потоков немножко тяжелее, чем Hazard Pointer. Заголовочный файл <cds/gc/ptb.h>, класс cds::gc::PTB
  • Hazard Pointer with Reference Counting — разновидность алгорифма Hazard Pointer, предложенная представителями шведской школы во главе с Hя потока (per-thread data), следственно обязаны находиться в thread local storage (TLS). Для обеспечения этого некоторые реализации диктуют свою политику управления потоками либо свою иерархию классов для потоков. Это, безусловно, комфортно для разработчика библиотеки, но абсолютно неудобно для пользователя. Следственно я при проектировании libcds пошел иным путем: библиотека не зависит от выбранной вами модели (либо иерархии классов) потоков, но должна быть очевидным образом подключена (attach) к потоку.Всякий поток (thread), работающий с контейнером из libcds, должен быть инициализирован дальнейшим образом:
    // cds::threading::Manager
    #include <cds/threading/model.h>
    
    int myThreadEntryPoint(void *)
    {
        // Подключение потока к инфраструктуре libcds
        cds::threading::Manager::attachThread() ;
    
        // Сейчас в данном потоке мы можем применять 
        // lock-free контейнеры libcds
        ...
    
       // Отключение потока от libcds
       cds::threading::Manager::detachThread() ;
    
       return 0;
    }
    

    Класс cds::threading::Manager является классом-переходником для внутренней инфраструктуры управления потоками. Он вам может потребоваться только для подключения/отключения потока к инфраструктуре libcds.
    Вышеприведенный код инициализации потока не неопасен с точки зрения исключений. Больше верный подход – применять объект, конструктор которого подключает поток к инфраструктуре libcds, а деструктор – отключает. Для этого всякий класс GC имеет внутренний класс thread_gc. С ним инициализация потока выглядит так:

    #include <cds/gc/hp.h>
    
    int myThreadEntryPoint(void *)
    {
        // Подключение потока к инфраструктуре libcds
        cds::gc::HP::thread_gc  threadGC ;
    
        // Сейчас в данном потоке мы можем применять 
        // lock-free контейнеры libcds
        ...
    
       return 0;
    }
    

    Как быть, если поток сделан не нами?

    Бывают обстановки, когда требуется подключить к libcds поток, тот, что сделан не нами, и мы никак не можем повлиять на инициализацию этого потока. Скажем, наше приложение является плагином к веб-серверу. Веб-сервер создает пул потоков (thread pool) и вызывает обработчики, реализованные в плагинах, в контексте этих потоков. В таком случае мы не можем ни сделать GC-объект, ни инициализировать поток объявлением объекта типа GC::thread_gc. Что делать?

    Придется применять внутренние механизмы инициализации libcds: сделать класс-инициализатор библиотеки и объявить статический объект этого класса:

    #include <cds/gc/hp.h>
    
    class LibcdsInit {
    public:
        LibcdsInit()
        {
           // Инициализируем libcds
           cds::Initialize();
           // Инициализируем Hazard Pointer singleton
           cds::gc::hzp::GarbageCollector::Construct() ;
        }
        ~LibcdsInit()
        {
           // Терминация Hazard Pointer singleton
           // довод true – следует отключить 
           // от Hazard Pointer все потоки
           cds::gc::hzp::GarbageCollector::Destruct(true) ;
    
           // Терминация libcds
           cds::Terminate();
        };
    };
    // Объявляем статический инициализатор
    static LibcdsInit libcdsInitializator ;
    

    Взамен класса-инициализатора LibcdsInit соответствующие вызовы дозволено разместить в DllMain(для Windows) либо в функции-конструкторы/деструкторы (__attribute__((constructor)) для GCC).

    Инициализация потока заключается в подключении его “навсегда” вызовомcds::threading::Manager::attachThread():

    // cds::threading::Manager
    #include <cds/threading/model.h>
    
    void callback() 
    {
        Cds::threading::Manager::attachThread();
    
        // сейчас дозволено применять в потоке lock-free
        // контейнеры libcds
    }
    

    Отключение потока мы не вызываем.

    Контейнеры

    Позже инициализации библиотеки дозволено применять lock-free конструкции данных. В libcds контейнеры делятся на два крупных класса – обыкновенные и странные интрузивные.
    Обыкновенные – это контейнеры в жанре STL, они хранят копию данных. Все такие контейнеры объявлены в пространстве имен cds::container.
    Интрузивные контейнеры хранят собственно данные, а не их копии. Идея взята из boost::intrusive. Превосходство интрузивных контейнеров в том, что не нужно вызывать аллокатор для создания копии данных. Считается, и не без оснований, что использование стандартного аллокатора сводит на нет идею lock-free, так как сам аллокатор содержит внутри себя примитивы синхронизации. В всеобщем случае это верно, но современные продвинутые аллокаторы могут оптимизировать разделение памяти, исключая внутреннюю синхронизацию за счет, скажем, наличия пула памяти для всякого потока.
    Я не буду в этой статье детально останавливаться на интрузивных контейнерах — они требуют специальных приемов для освобождения памяти при исключении элемента из контейнера, это тема отдельного разговора. Тут лишь подмечу, что множество классов обыкновенных контейнеров основываются на интрузивных, то есть, как правило, каждый увлекательный lock-free код находится в классе интрузивного контейнера. Интрузивные контейнеры объявлены в пространстве именcds::intrusive.

    Все конструкции данных в libcds являются шаблонными классами с единообразным template-интерфейсом. Дозволено выделить два типа template-интерфейсов:

    • учрежденный на variadic template
    • учрежденный на traits

    Объявления, основанные на variadic template, применяются для примитивных контейнеров – стеков и очередей. Всеобщий паттерн таков:

    template <typename GC, typename T, typename… Options>
    class queue { … };
    

    Для компиляторов, не поддерживающих variadic template, применяется эмуляция.
    Внутри класса контейнера Options упаковываются в конструкцию Traits.

    Variadic template-подход оказался не дюже комфортным для трудного наследования, следственно для классов больше трудных контейнеров типа setmap и пр. применяются traits-объявления:

    template <typename GC, typename T, typename Traits>
    class set { … };
    

    Для всякого такого класса существует метафункция make_traits, преобразующая variadic template в traits:

    template <typename… Options>
    struct make_traits {
       typedef typename pack<Options…>::type type ;
    };
    

    С поддержкой make_traits объявление объекта контейнера принимает вид:

    struct Foo { … };
    cds::container::SkipListSet< cds::gc::HP, Foo, 
        typename cds::container::skip_list::make_traits<
          Opt1, 
          Opt2, 
          Opt3
        >::type
    > theSkipListSet ;
    

    Такое объявление, безусловно, выглядит резко, но может сделать задачи при отладке, – имя класса может занимать несколько десятков строк. Traits-объявления больше суперкомпактны для отладки:

    struct Foo { … };
    
    struct skipListSetTraits: 
        public cds::container::skip_list::make_traits<
          Opt1, 
          Opt2, 
          Opt3
        >::type
    {};
    
    cds::container::SkipListSet< cds::gc::HP, Foo, 
        skipListSetTraits
    > theSkipListSet ;
    

    Template-доводами класса конструкции данных являются:

    • GC — применяемый алгорифм SMR
    • T — тип данных, хранимых в контейнере
    • Options… либо Traits — опции (policy, стратегии) контейнера

    На опциях следует остановиться отдельно.

    Опции

    Всякий класс контейнера, помимо типа данных и алгорифма SMR, может иметь многообразное число дополнительных настроек, задающих то либо иное поведение. Скажем, для упорядоченных контейнеров (map, set) нужно указать бинарный предикат сопоставления элементовstd::less<T>. Либо задать ту либо другую тактику действий при выявлении параллельной работы (back-off тактика). Либо установить аллокатор, применяемый для создания элементов контейнера.
    Всякий класс контейнера имеет несколько (до десятка) таких, как правило, необязательных настроек, которые я называю опциями. Подход, применяемый в STL, когда всякая настройка является template-доводом образца класса, мне не дюже нравится: такие позиционно-зависимые доводы с default-значениями усложняют использование класса. Если класс имmk!/code>.

    Библиотека значительно полагается на два свойства аллокаторов:

    • всякий аллокатор имеет метафункцию template <typename Other> struct rebind, которая разрешает перестроить аллокатор под иной тип Other. Как я теснее сказал, аллокатором по умолчанию является std::allocator<int>, — контейнер посредством метафункции rebind меняет тип int на требуемый
    • аллокатор — всеобщий объект. Это требование вытекает из того факта, что физическое удаление элемента lock-free контейнера является отложенным и может случиться позже уничтожения самого объекта контейнера. Следственно, в различие от STL, контейнеры libcds никогда не хранят ссылок на объект аллокатора и не имеют способов задания объекта-аллокатора. Если необходимо распределить память внутри способа контейнера, аллокатор вызывается через непостоянный объект: allocator_type().allocate( 1 ). Верно так же, освобождение памяти происходит вызовом allocator_type().deallocate( p ). Стоит ещё раз подметить, что освобождение является отложенным и может случиться теснее тогда, когда самого объекта контейнера теснее нет, да и вызывается оно из алгорифма SMR

    Короткие технические колляции

    Поддерживаемые компиляторы:

    • GCC 4.3 и выше
    • MS Visual C 2008 и выше
    • Clang 3.0 и выше (со стандартной библиотекой GCC libstdc )

    Поддерживаемые операционные системы и архитектуры процессоров:

    • Windows x86, amd64
    • Linux x86, amd64, Intel Itanium, Sparc
    • Solaris Sparc
    • HP-UX Intel Itanium

    Помощь других ОС либо архитектур процессоров является делом допустимым, но нетривиальным, исключительно если целевой компилятор не поддерживает C 11 atomic.

    Завершение

    Верю, позже прочтения данной статьи будет ясно, как применять библиотеку libcds. Помимо того, я попытался пояснить основные тезисы, руководствуясь которыми я реализую в библиотеке конструкции данных.

    Я абсолютно не касаюсь вопросов продуктивности. Как я ранее теснее подмечал, о продуктивности дозволено говорить только применительно к определенной задаче и определенному железу. Нынешнее сталь дюже по-различному относится к lock-free алгорифмам: одно благосклонно к ним, другое бывает необходимым длинно уговаривать, подбирая те либо иные опции класса контейнера для достижения приемлемой продуктивности. Lock-free конструкции данных достаточно трудны по сопоставлению со своими обыкновенными собратьями, следственно начинает играть фактор «кто стремительней»: либо примитив синхронизации обыкновенный контейнер, либо трудный lock-free контейнер без внешней синхронизации.

    Если вы хотите получить добродушный совет, то вот он: усердствуйте совсем не применять разделяемых (shared) данных. Америку таким советом я не открыл, но следовать ему в повседневной жизни бывает трудно.

    Ссылки

    [Des09] M.Desnoyers Low-Impact Operating System Tracing PhD Thesis,Chapter 6 «User-Level Implementations of Read-Copy Update»

    [Des11] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole User-Level Implementations of Read-Copy Update

    [Gid05] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas Practical and Efficient Lock-Free Garbage Collection Based on Reference Counting

    [Gid06] A.Gidenstam Algorithms for synchronization and consistency in concurrent system services, Chapter 5 «Lock-Free Memory Reclamation» Thesis for the degree of Doctor of Philosophy

    [Her02] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting dynamic-sized lockfree data structures Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002

    [Her05] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support for Dynamic_Sized Data Structures ACM Transactions on Computer Systems, Vol.23, No.2, May 2005

    [Mic02] Maged M.Michael Safe memory reclamation for dynamic lock-free objects using atomic reads and writes

    [Mic03] Maged M.Michael Hazard Pointers: Safe memory reclamation for lock-free objects

    [Mic04] Andrei Alexandrescy, Maged Michael Lock-free Data Structures with Hazard Pointers

 

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

 

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