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

Lock-free конструкции данных. Внутри. RCU

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

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

Речь пойдет об ещё одной технике безвредного освобождения памяти для lock-free контйнеров — RCU. Эта техника значительно отличается от рассмотренных ранее алгорифмов a la Hazard Pointer.

Read – Copy Update (RCU) – техника синхронизации, предуготовленная для «примерно read-only», то есть редко изменяемых, конструкций данных. Нормальными примерами такой конструкции являются map и set – в них множество операций является поиском, то есть чтением данных. Считается, что для нормального map’а больше 90% вызываемых операций — это поиск по ключу, следственно значимо, Дабы операция поиска была особенно стремительной; синхронизация поиска в тезисе не необходима — читатели при отсутствии писателей могут трудиться параллельно. RCU обеспечивает наименьшие убыточные расходы как раз для read-операций.

Откуда взялось наименование Read – Copy Update? Изначально идея была дюже примитивна: есть некоторая редко изменяемая конструкция данных. Если нам требуется изменить её, то мы делаем её копию и изготавливаем метаморфоза — добавление либо удаление данных — именно в копии. При этом параллельные читатели работают с изначальной, не измененной конструкцией. В определенный безвредный момент времени, когда нет читателей, мы можем подменить конструкцию данных на измененную копию. В итоге все дальнейшие читатели будут видеть метаморфозы, произведенные писателем.


Создателем и энергичным популяризатором техники RCU является Paul McKenney. Он возглавляет целую школу «любителей RCU», из которой вышло много знаменитых ученых в области lock-free и нетрадиционных схем синхронизации, а также он является «основным по RCU» в ядре Linux (Linux-kernel RCU maintainer) и авторомряда работ по RCU.


RCU была внедрена в ядро Linux в 2002 году и с тех пор все больше и больше врастает в код ядра, см. рисунок справа. Длинное время она позиционировалась как техника синхронизации именно для ядра операционной системы. Так как ядро имеет полный контроль над всеми потоками, — как пользовательскими, так и системными, — то в ядре достаточно легко определить тот безвредный момент времени подмены данных на измененную копию. Но нас волнует прикладное использование RCU, допустимо ли оно? Раньше чем ответить на данный вопрос, разглядим подробнее теорию RCU и применяемую в ней терминологию.

Всеобщее изложение RCU

Приведенное выше изложение идеи RCU дюже упрощенно. Как мы знаем, имея атомарные операции, мы можем не делать копию данных, а изменять конструкцию данных «на лету» параллельно с её чтением. Тогда «читателем» становится поток, исполняющий всякую операцию, помимо удаления элемента из конструкции данных. Писателем будем называть поток, удаляющий что-либо из конструкции. Удаление должно производиться в момент времени, когда никто не «наступил» на удаляемые данные, напротив мы получим букет сложно обнаружимых задач — от ABA-задачи до memory corruption. RCU решает все эти задачи, причем способом, хорошим от рассмотренной ранее схемы Hazard Pointers.

Читатели в технике RCU выполняются в скептической сегменты чтения (read-side critical section). При входе в такую скептическую секцию читатель вызывает функцию rcu_read_lock(), при выходе —rcu_read_unlock(). Это дюже легкие функции, фактически не влияющие на продуктивность; в ядре Linux они не весят вообще ничего (zero-overhead).
Если поток находится не в скептической сегменты чтения, то говорят, что поток в мирном состоянии(quiescent state, quiescent-состояние). Всякий период времени, в котором всякий поток правда бы однажды находился в quiescent-состоянии, называют grace period. Всякая скептическая сегмент чтения, которая началась перед grace period, должна закончиться раньше, чем закончится grace period. Всякий grace period гарантированно финален, так как любая скептическая сегмент чтения финальна (подразумевается, что число потоков безусловно, а также что мы отличные программисты и чураемся безграничных циклов, равно как и гибели потока).


Пccess_unlock() { thread_record * pRec = get_thread_record(); assert( pRec != nullptr ); pRec->nThreadCtl.fetch_sub( 1, std::memory_order_release ); }
При входе в скептическую секцию URCU проверяется, вложенный это вызов либо нет. Если вызов вложенный (то есть счетчик в младших 31 бите не нуль), счетчик вложенности легко инкрементируется. Если же вызов не вложенный, переменнойnThreadCtl нынешнего потока присваивается значение всеобщей переменной g_nGlobalCtl; тем самым помечается, что вход в скептическую секцию был произведен в определенный grace-период (старший бит g_nGlobalCtl), а единица в младших битахg_nGlobalCtl инициализирует счетчик вложенности нынешнего потока. При первом, самом внешнем входе в скептическую секцию используется acquire-барьер памяти. Он гарантирует, что дальнейший код не будет перенесен («оптимизирован») вверх за барьер ни процессором, ни компилятором. Тем самым обеспечивается видимость нынешнего grace-периода потока каждому процессорам, — если нарушить данный порядок, алгорифм URCU рассыплется. При входе во вложенную скептическую секцию барьера не требуется, так как нынешний grace-период (старший бит) не изменяется.
При выходе из скептической сегменты (access_unlock) легко декрементируется счетчик вложенности вnThreadCtl нынешнего потока. Используется release-семантика атомарной операции; на самом деле, release-барьер нужен тут только при выходе из самой верхней скептической сегменты (при переходе от 1 к 0 счетчика вложенности), при выходе из вложенной скептической сегменты довольно relaxed-семантики. Release-барьер при обнулении счетчика требуется потому, что при переходе счетчика вложенности от 1 к 0 реально происходит объявление «поток больше не использует RCU», то есть выход из grace-периода, что является скептическим для алгорифма URCU, — нарушение порядка компилятором либо процессором приведет к неработоспособности алгорифма. Распознание обстановок «0 — не 0» в коде затребует условного перехода, что вряд ли добавит продуктивности функции access_unlock, да и стержневой паттерн применения скептических сегментов URCU – без вложенности, следственно release-семантика используется тут неизменно.

Как видно, код со стороны читателей достаточно легкий. Применяются атомарные чтение-запись и thread-local данные. Безусловно, это не zero-overhead, но все же гораздо отменнее, чем мьютекс либо CAS.

Поток-писатель перед тем, как физически удалить элемент, должен удостовериться, что grace-период закончен. Данные окончания grace-периода — одно из 2-х:

  • Младшие биты (счетчик вложенности) nThreadCtl всякого потока равны нулю, что обозначает, что поток не находится в скептической сегменты URCU
  • Старший бит nThreadCtl не совпадает с со старшим битом g_nGlobalCtl, что обозначает, что читатель вошел в скептическую секцию позже начала grace-периода

Эти данные проверяются дальнейшей функцией:

bool check_grace_period( thread_record * pRec )
{
   uint32_t const v = pRec->nThreadCtl.load( std::memory_order_relaxed );
   return (v & general_purpose_rcu::c_nNestMask)
      && ((( v ^ g_nGlobalCtl.load( std::memory_order_relaxed )) & ~c_nNestedMask ));       }

Писатель перед физическим удалением вызывает функцию synchronize, которая ждет окончания нынешнего grace-периода:

std::mutex  g_Mutex ;
void synchronize()
{
   std::atomic_thread_fence( std::memory_order_acquire );
   {
      cds::lock::scoped_lock<std::mutex> sl( g_Mutex );
      flip_and_wait();
      flip_and_wait();
   }
   std::atomic_thread_fence( std::memory_order_release );
}

Тут g_Mutex — всеобщий для алгорифма URCU мьютекс (да-да! URCU все же техника синхронизации, так что без мьютекса никуда). Таким образом, только один поток-писатель может войти в synchronize. Не забываем, что RCU позиционируется для «примерно read-only» данных, так что специальной толкотни на этом мьютексе не ожидается.
Писатель ждет окончания grace-периода, вызывая функцию flip_and_wait:

void flip_and_wait()
{
   g_nGlobalCtl.fetch_xor( c_nControlBit, std::memory_order_seq_cst );
   for (thread_record* pRec = g_ThreadList.head(std::memory_order_acquire);
         pRec!= nullptr; 
         pRec = pRec->m_pNext ) 
   {
     while ( check_grace_period( pRec )) 
     {
        sleep( 10 ); // ожидаем 10 миллисекунд
        CDS_COMPILER_RW_BARRIER ;
     }
   }
}

Эта функция меняет идентификатор grace-периода, что обозначает предисловие нового grace-периода, с поддержкой атомарного fetch_xor и ожидает (вызовом check_grace_period), пока все потоки-читатели не завершат данный новейший grace-период. В псевдокоде ожидание происходит простым sleep на 10 миллисекунд, в настоящем коде libcds применяется template-параметр, задающий back-off-тактику.

Отчего писатель вызывает flip_and_wait двукратно? Для пояснения разглядим такую последовательность действий с двумя потоками A и B. Представим, что вызов flip_and_wait в synchronize только один:

  • Поток A вызывает access_lock. В теле этой функции определяется, что вызов не вложенный, читается всеобщий g_nGlobalCtl, но пока не присваивается переменной nThreadCtl потока (все выполняется параллельно, так что такая обстановка абсолютно возможна)
  • Поток B вызывает synchronize. Вызывается 1-й flip_and_wait, тот, что изменяет бит-идентификатор grace-периода в g_nGlobalCtl. Нынешним идентификатором grace-периода становится 1
  • Так как в скептической сегменты URCU никого нет (припомним, что поток A ещё не поспел присвоить значение своей переменной nThreadCtl), поток B завершает synchronize
  • Поток A исполняет присваивание своей переменной nThreadCtl. Припомним, что поток прочитал ветхое значение grace-периода, равное 0
  • Поток A завершает access_lock и продолжает выполнение в скептической сегменты
  • Поток B вызывает synchronize ещё раз (видимо, вновь хочет что-то удалить). Вновь происходит обращение нынешнего grace-периода в g_nGlobalCtl, так что его идентификатор сейчас 0.

Но поток A в скептической сегменты, которая началась ранее, чем B изменил grace-период! Нарушение семантики URCU, которое приведет со временем ко каждому букету — от ABA до memory corruption. Припомним: synchronize вызывается писателем перед тем, как физически удалить память под элемент

Вызывая flip_and_wait двукратно, то есть двукратно ждя окончания grace-периода, мы решаем вышеописанную задачу, повод которой — конкурентное выполнение потоков.

Другое решение

Дозволено, безусловно, решить эту задачу и по-иному, если применять взамен бита-идентификатора grace-периода некоторый счетчик. Но здесь появляется задача, которую мы теснее видели в статье про алгорифм tagged pointer, — счетчик подвержен переполнению! Для безопасности счетчик должен быть 32-битным, тогда переполнение нам не ужасно. Но такой счетчик приводит к необходимости иметь 64-битный атомарный тип на 32-битовых платформах. Такого типа либо нет, либо он достаточно неэффективен. Либо нам придется отказаться от вложенности скептических сегментов URCU, что тоже не дюже комфортно.
Следственно остановимся на всеобщем решении с битом в качестве идентификатора grace-периода и вызовом 2-х flip_and_wait

Реализация URCU в libcds


Вышеописанный алгорифм URCU классен каждому, помимо того, что перед всяким удалением требуется вызывать достаточно весомый synchronize. Дозволено ли как-то это усовершенствовать?
Да, дозволено, причем таким же способом, как и в алгорифме Hazard Pointer, — применить отложенное удаление. Будем взамен удаления помещать элементы в определенный буфер. Функцию synchronize будем вызывать только когда буфер заполнится. В различие от Hazard Pointer, в URCU буфер будет всеобщим для всех потоков (вообще, дозволено сделать и per-thread буферы, ничто этому не мешает).
Больше того, Дабы не тормозить писателя, на долю которого вывалилась доля чистить буфер при его переполнении, функционал чистки буфера, то есть действительного удаления, дозволено возложить отдельному потоку.

Библиотека libcds имеет пять реализаций URCU, все они живут в пространстве имен cds::urcu:

  • general_instant — реализация, верно дальнейшая описанному алгорифму URCU: всякое удаление вызывает synchronize, никакой буферизации. Если удаление у нас достаточно частая операция, то есть стрываем gc::access_lock(), при выходе — gc::access_unlock() (тут gc — это одна из реализаций URCU; для безопасности исключений отменнее применять технику scoped lock взамен вызова функций). Исключительный тонкий момент — удаление элемента: способ удаления также должен входить в скептическую секцию чтения, но физическое удаление элемента, осуществляемое вызовомgc::retire_ptr, должно производиться вне скептической сегменты, напротив допустим deadlock: способgc::retire_ptr внутри может вызвать synchronize.Libcds определяет URCU-специализации для всех классов set и map. URCU-специализации для контейнеров типа «очередь» и «стек» не определено, — это не «примерно read-only» контейнеры, так что URCU не для них.

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

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