lock-free дизайн многопоточных программ

[dimedrol]

День добрый! Вот набрел на такое понятие как lock-free синхронизация. Суть объяснена например здесь: http://developer.amd.com/documentation/articles/pages/125200689.aspx http://www.audiomulch.com/~rossb/code/lockfree/ Меня весьма заинтересовал этот вопрос, поскольку по роду деятельности тоже приходится часто разрабатывать хитрозамученные многопоточные проекты, причем синхронизация и масштабируемость (в случае, если используется целый пул потоков, с числом потоков меняющегося в динамике) доставляет прилично головной боли. В сквязи с этим интересно есть ли у кого опыт использования такого рода синхронизации, а особенно lock-free структур, и каковы результаты.
ЗЫ Интересно, что в ядрах 2.6 линукса используется так называемый RCU механизм, по сути один из приемов lock-free синхронизации

[sss]

dimedrol, нельзя малям по русски объяснить - что за lock-free? Не хочется сильно вкупаться, потому что полезность не ясна.. Кстати вторая ссылка не работает.... И вообще - привет, давно не было...
 

[dimedrol]

Привет, sss, сколько лет сколько зим, действительно давно уже не заходил. Ссылку поправил Пусть у нас есть структура данных, доступ к ней разделяемый между кучей нитей , причем число процессоров в системе может быть произвольным. Расмотрим ситуацию 1.
1) Динамический список элементов, для кореектного удаления или вставки элемента используем синхронизацию через какой-либо примитив синхронизации - чревато дедлоками, если например одна нить захватити синхронизацию и помрет. Однако можно используя функцию атомарного сравнения и замены (на x86 cmpxchg, или InterlockedCompareExchange) потсорить алгоритм работы списка, без стандартных примитивов синхронизации, при этом работа сосписком будет происходить корректно в разделяемой среде, дедлоки ВПРИНЦИПЕ не возможны ни при каких обстоятельствах + фантастически низкие издержки на синхронизацию, которые практически не растут с увеличением числа програмных потоков или физических процессоров на которых они исполняются + можно забыть об инверсии приоритетов и прочие специфические прелести..
2) RCU (Read-Copy-Update) Пусть есть структура критичная по части синхронизации, которую чаще читают чем пишут. Логично использовать какой-либо примитив синхронизации для доступа к ней, но мы поступим хитрее: заведем глобальный указатель на структру данных str *p; Определим операцию чтения структуры, как атомарное присваивание этого указателя переменной b, и дальнейшее его использование в читающей нити. Для записи будет иначе - выделяем память под новый экземпляр структуры str, изменяем его как нам надо и атомарно присваиваем (InterlockedExchange) значению указателя p на нашу новую структуру, при этом все последующие читатели будут работать уже с этой копией. Разумеется необходимо предусмотреть механизм сборки мусора, так как предыдущее значение указателя затирается, а память надо бы освободить. Однако получаем опять-таки все перечисленные в п1 плюсы.

Вот это "вкратце суть". Конечно есть кое-какие фундаментальные проблемки этого подхода, но в целом очень интересно На данный момент я нарыл реализацию lock-free FIFO, FILO, stack, list, и аналоги stl-вского vector-а. Кстати, нашел довольно старую, но интересную статью о разработке игрового движка от valve http://arstechnica.com/gaming/news/2006/11/valve-multicore.ars

[sss]

Нда... Понятно о чем речь. Для полной защиты никогда не использовал одни лишь атомарные операции... Как правило критические секции. Не понимаю, как это поток умер не освободив блокировку? Я в своем коде всегда в местах, где происходит захват, обработку ошибок/исключений прописываю с особой тщательностью... Конечно это приводит к расходам на синхронизацию... Но у меня есть один принцип - поведение кода должно быть предсказуемо. Не предсказуемый  код хуже кода с явными ошибками. Вот, например, сразу тебе коллизия во втором пункте - "все последующие читатели". Получается текущие читатели не узнают об изменении и, самое главное, они становятся возможны...

[sss]

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

 CLockCS l ( &m_csState) -  умная крит. секция....  Подсмотрено в DirectShow.

Код:

void CMessenger::ExecuteHandlers( PMesssage pMesssage)
{
  size_t       stCount;
  PPtrNode     pCurr;
  bool         bHandled      = false;
  size_t       stIdx         = 0;
  PMsgFuncNode *StepHandlers = NULL;
  try
  {
    //Создаем список обработчиков текущей петли и закрепляем их
    {
      CLockCS l ( &m_csState);
      stCount = m_Handlers.Count;
      if ( stCount)
      {
        StepHandlers = (PMsgFuncNode*) MemAlloc( stCount * sizeof( PMsgFuncNode));
        pCurr = m_Handlers.First;
        while ( pCurr)
        {
          StepHandlers[stIdx] = (PMsgFuncNode) pCurr->Data;
          StepHandlers[stIdx]->AddRef();
          stIdx++;
          pCurr = pCurr->Next;
        }
      }
    }
    //Выполняем обработчики        
    for ( size_t i = 0; i < stCount; i++)
    {
      //Любой из них мог вызвать Terminate!!!
      if ( m_State == State_Running && bHandled == false && StepHandlers[i]->Enabled)
      {
        {
          // Закрепляем, что бы связанный с контекстом HandlerContext
          // обломался со своим удалением до выполнения обработчика
          CLockCS l( &StepHandlers[i]->m_csState);
          if ( StepHandlers[i]->Enabled)
          {
            bHandled = StepHandlers[i]->HandleMessage( pMesssage);
          }
        }
      }
      StepHandlers[i]->Release();
    }
    if ( StepHandlers) MemFree( StepHandlers);
  }
  catch( EExcept* e)
  {
    if ( StepHandlers) MemFree( StepHandlers);
    e->Release();
  }
}

[Антон (LogRus)]

dimedrol, я уже несколько раз давал ссылки из тех что я использую (читаю)
http://groups.google.com/group/lock-free
http://herbsutter.wordpress.com
http://highscalability.com/
http://software.intel.com/ru-ru/parallel/
http://www.threadingbuildingblocks.org/

ссылки конечно здорово, но

.............используем синхронизацию через какой-либо примитив синхронизации - чревато дедлоками..........

имхо, кривые руки

.........дедлоки ВПРИНЦИПЕ не возможны ни при каких обстоятельствах..............

собственно не избавляет от кривых рук

...........заведем глобальный указатель на структру данных str *p; .................

какая гадость

кроме-то того, lock-free требуют очень аккуратного проектирования и очень тщательного тестирования
http://software.intel.com/ru-ru/articles/interview-with-dmitriy-vyukov-the-author-of-relacy-race-detector-rrd/

sss, lock-free это всякие алгоритмы и приёмы разработки многопоточных приложений не использующие примитивов синхронизации

[dimedrol]

Насчет предсказуемости кода - согласен абсолютно. Насчет текущих читаетелей - они будут работать посути со своей локальной копией данных, пока не перечитают измененный вариант, такой механизм успешно работает, как пример - RCU в линуксовом ядре: выдержка из книги Бовет Д.Чезати М. Ядро Линукс

Поскольку читающий тракт почти ничего не делает для предотвращения
конфликтов одновременного обращения, мы вправе ожидать, что вся работа
перекладывается на пишущий тракт. Действительно, когда пишущему тракту
нужно обновить структуру, он разыменовывает указатель и делает копию
всей структуры. Затем он обновляет копию. Закончив эту операцию, пишу-
щий тракт изменяет указатель на структуру так, чтобы он ссылался на обнов-
ленную копию. Поскольку изменение значения указателя является атомар-
ным действием, любой читающий или пишущий тракт видит либо старый
экземпляр структуры, либо новый, и никакая порча данных невозможна. Од-
нако при таком подходе необходим барьер памяти для гарантии того, что об-
новленный указатель будет виден на других процессорах только после моди-
фикации структуры данных. Такой барьер памяти неявно устанавливается,
если в комбинации с обновлением копии используется спин-блокировка,
предотвращающая параллельное выполнение пишущих трактов.
Реальная проблема с техникой обновления копии для чтения заключается в
том, что старая копия не может быть освобождена сразу после того, как пи-
шущий тракт изменит указатель. На практике читающие тракты, работавшие
со структурой, когда пишущий тракт начал процедуру обновления, могут все
еще читать старую копию.

Вполне рабочий подход, если вдуматься - как правило, то что читатель будет некоторое время работать со старой копией данных, никак не будет отражаться на работу системы.
В двнном случае больше интересен новый принцип синхронизации, который, кстати судя по гуглу уже находит применение в системах реального времени и высокопроизводительных системах (особенно многопроцессорных).
Вообще, погуглив lock-free я удивился числу научных статей на тему подобных алгоритмов, общие выводы сводятся к перспективности таких методов, особенно для многопроцессорных систем. Причем поддержку воплощают и в железе, вот подтверждение моих слов http://www.amd64.org/fileadmin/user_upload/pub/epham08-asf-eval.pdf
ИМХО за этим подходом будущее, число ядер и степень параллельности вычислений растут, неизбежен момент, когда издержки на привычные способы синхронизации станут неприемлемы.. возможно будущие виды микропроцессорных систем уже будут включать аппаратную поддержку атомарного доступа к тем или иным блокам памяти.. впринципе она уже есть на х86 инструкции cmpxchg cmpxchg8b и аналогичные, только большей разрядности, для 64бит систем, на других процессорах аналогичные вариации.

[dimedrol]

LogRus спасибо за ссылки! да, дедлоки - это как правило кривые руки И все-таки мне интересно, кто-нибудь применял это в реальных проектах? Как ощущения? Каковы результаты?

[sss]

dimedrol, ну не знаю... Вон LogRus правильно сказал ( хотя и жестко): берешься писать многопоточный код - тупик это признак тупика в логике программы.... А вот скорость синхронизации - не поспоришь. Но ничто не бывает бесплатно. Для меня неприемлимо возникновение читателя с устаревшими данными... Кстати проблема освобождения буфера читателя легко решается  "управлением с помощью атомарных операций счетчиком ссылок".

[RXL]

Literature up to the turn of the 21st century used "non-blocking" synonymously with lock-free.

Очередная подмена терминов для большей запутанности?

http://en.wikipedia.org/wiki/Read-copy-update

[Антон (LogRus)]

что касается практики, то практически не применял, просто следую правилу: не надо исправлять проблему которой нет обычно, достаточно spin_mutex и коротких блокировок, что бы всё работало достаточно быстро.
ну и конечно изолирование задач для разных потоков, а синхронизация только при постановке и удалении задачи, задачи достаточно длинные, поэтому блокировки не являются камнем преткновения

[sss]

LogRus, поддерживаю. Блокировки, как правило, не то место, которое требует пристального внимания из-за производительности. У меня как правило, если тормозит в кодах синхронизации это тупо написанный код.

[dimedrol]

Мне тоже как-то не подворачивается проект на котором бы пришлось опробовать новенькое, , хотя в перспективе кое-что вырисовывается поэтому и спрашиваю,а еще интерес взял по этой теме  Лично сам, стараюсь  минимизировать объем разделяемых данных, чтобы побольше пользоваться Interlocked функциями для доступа к ним - но это в критических случаях, обычно и стандартные примитивы синхронизации устраивают.

[Антон (LogRus)]

в одной из статей Саттер (а может и не он ) выдвинул такую мысль, что однопоточность в многопоточном приложении, то именно, то что нужно, т.е. чем длиннее и не изолированней команды исполняемые потоками, тем лучше.

[Dimka]

Что-то я не уловил, чем описанное RCU выгоднее сложной блокировки типа "много читателей - один писатель". Тем, что читатели не блокируются, пока писатель пишет? А как эта RCU обрабатывает ситуацию с многими писателиями? Ведь, пока один работает с одной копией, другой уже может успеть заменить исходные данные на собственные. Из приведённого отрывка книги я вижу, что это вопрос неоднозначный и "проблемный".

Но главное, чего я не уловил: где выгода? В избавлении от 1-й машинной инструкции типа cmpxchg? И каков прирост производительности?

[dimedrol]

Ну, если требуется очень частый доступ к разделяемым данным в ядре - стандартная синхронизация будет вносить большие издержки видимо. А выгода в том, что одной стандартной инструкцией cmpxchg мы можем максимум 4 или 8 байтами оперировать по сути, а RCU опрериует целыми структурами, вроде есть даже такое понятие Lock-free структуры. Заодно вот еще отрывок из той же книжки:

Обновление копии для чтения (Read-copy update, RCU) является еще одним
приемом синхронизации, разработанным для защиты структур, к которым
несколько процессоров обращается, в основном, для чтения. RCU позволяет
нескольким пишущим и читающим трактам работать одновременно (это шаг
вперед, по сравнению с seqlock-блокировками, позволяющими работать толь-
ко одному пишущему тракту). Более того, техника обновления копии для
чтения свободна от блокировок, т. е. в ней нет блокировки или счетчика, ко-
торые бы совместно использовались всеми процессорами. Это огромное пре-
имущество перед спин-блокировками чтения/записи и seqlock-блокировками,
которые требуют больших накладных расходов из-за снупинга и порчи строк
кэша.
Каким образом применение техники RCU позволяет достичь удивительных
результатов при синхронизации нескольких процессов без совместно исполь-
зуемых структур данных? Основная идея состоит в ограничении области дей-
ствия RCU:
□ С помощью RCU можно защищать только динамически выделенные дан-
ные, доступные через указатели.
□ Никакой управляющий тракт ядра не может "спать" внутри критической
области, защищенной с помощью RCU.

Обновление копии для чтения является нововведением в Linux 2.6; оно ис-
пользуется в сетевом слое и в виртуальной файловой системе.

Впринципе, кому интересно, можно и поглядеть в самих исходниках ядра лично у меня пока руки не доходят никак.

[Антон (LogRus)]

вот кое-что интересное
http://groups.google.com/group/lock-free/browse_thread/thread/c8e3201da4a6a300

[Dimka]

Каким образом применение техники RCU позволяет достичь удивительных
результатов при синхронизации нескольких процессов без совместно исполь-
зуемых структур данных? Основная идея состоит в ограничении области дей-
ствия RCU

Т.е., развивая мысль, идеально быстрая синхронизация наблюдается там, где не нужна никакая синхронизация

Не, я согласен, что обмен значениями 2-х переменных в 1 инструкцию на 1 CPU выглядит проще, чем блокировка в начале критической секции. Но как это работает на многих параллельных CPU? Как не разрушить логику, когда много писателей изменяют данные на основе старой исходной копии и не знают друг о друге - самый медленный писатель благополучно потеряет результаты всех более быстрых, параллельно с ним работающих. Каждый раз заводить очередь? Но даже очередь может рассыпаться, если 2 писателя получат общую голову списка и добавят к ней 2 новых, нарушив последовательность, что затем приведёт к потере 1 элемента.

[dimedrol]

LogRus, классная ссылка интересный принцип кстати в форуме там еще одна ссылка на статьи http://research.sun.com/scalable/pubs/index.html
Dimka, разумеется надо вдумчиво планировать синхронизацию, даже если она допускает столько свободы, сколько обещает lock-free.

[sss]

dimedrol, а ты понял смысл? Просвяти пожалуйста...

Код:

while (n->next_ == 0)
                            SwitchToThread(); 

Мне это напомнило мои коды из детства, когда я пытался синхронизироваться вокруг глобального флага....

[sss]

Кстати, вот пример... Сто потоков прошли условие n->next_ == 0 одновременно... И чё? Извиняюсь, не прошли...
Вообще мне все это представляется попытками написать свои объекты диспетчеризации. Флаг в руки....

[RXL]

Dimka,

1. На SMP работает нормально: как только выполняется запись, она распространяется в кеш L0 и L1 процессора, а остальные ядра/процессоры перед чтением данной ячейки памяти должны провести валидацию с чужими кешами - тут то и найдется изменение.

2. Согласен, что это разрушительно. Но для чего в SQL существует READ COMMITED? — Ведь оно тоже не поддерживает целостность данных на изменение. Выходит, что для производительности! Значит, есть задачи, для которых старые данные не важны.

Для поддержания целостности с сохранением достоинств RCU можно скомбинировать:

struct
{
  mutex mtx;
  unsigned int version;
  data_t *data;
}

1. Копирование.
1.1. Блокируем.
1.2. Копируем указатель данных.
1.3. Копируем версию.
1.4. Снимаем блокировку.
1.5. Копируем данные.
2. Обработка.
3. Обновление.
3.1. Блокируем.
3.2. Сверяем версию:
  не равно - возвращаемся к п.1.2.
  равно - увеличиваем номер версии.
3.3. Подменяем указатель на данные.
3.4. Снимаем блокировку.

Это как раз эквивалент REPEATABLE READ.

[Dimka]

RXL, с этим я тоже согласен, если процесс вычисления новых данных по старым достаточно длинен. Правда, такая схема с возвратом и повторным чтением-попыткой обновления, подозреваю, в ряде случаев выглядит ещё хуже, чем классическая блокировка. Вместо спящих конкурирующих потоков мы получаем активные конкурирующие потоки без полезного результата в части производительности, так как лишь 1 делает полезную работу, а остальные в это же время делают лишнюю работу, вместо того, чтобы спать.

[sss]

Dimka, ок. Попытки синхронизации без использования блокировок потока неизбежно приведут к гонкам. Мне не нужен код, обладающий повышенной производительностью на 10% и загружающий ядро на 100%. Более перспективным считаю направление, в котором параллельные задачи выполняются одним потоком последовательно...

[RXL]

Думаю, что каждой задаче - свой алгоритм.

[Dimka]

Более перспективным считаю направление, в котором параллельные задачи выполняются одним потоком последовательно...

Кстати, хотелось бы поподробнее.

В таком контексте упоминают мультиплексирование, реализованное, например, в nginx. Образно оно показывается в виде жонглёра, подбрасывающего шарики. Пока 1 шарик перекладывается из руки в руку (обрабатывается), другие летят в воздухе (выполняются какие-то медленные операции типа ввода-вывода). Поток исполнения один, много мелких задачек в очереди.

Кто про это может рассказать кратко, но по существу? Лучше с небольшим примерчиком кода.

[sss]

Dimka, да это мне просто в голову приходит все чаще и чаще... Не знаю, интуитивно что ли.... Я смотрю на то, как отмёрли шлейфы IDE и прижились 3 провода SATA... Как пакетный принцип передачи в телефонии вытесняет канальный и т.д. и т.п...

[RXL]

sss, параллельные физические интерфейсы с точки зрения протоколов все равно последовательные. Т.е. разница только в модуляции. Одну дифференциальную пару проще использовать, чем согласовывать N пар (или N проводов), и, как следствие, повышать скорость передачи.

Телефонию вообще странно тут приводить - она не коррелирует.  Ее изменение целиком объясняются переходом на цифровой способ доставки сигналов и информации.

В условиях многопроцессорности/многопоточности выгоднее как раз многозадачность. И чем реже происходит синхронизация (читай - блокировка), тем выгоднее.

[Антон (LogRus)]

В условиях многопроцессорности/многопоточности выгоднее как раз многозадачность. И чем реже происходит синхронизация (читай - блокировка), тем выгоднее.

не явную синхронизацию кэшей тоже считаем

[RXL]

LogRus, ну, это уже не наш уровень - над этим пусть производители процессоров думают, как этого избежать.