Пользователь
20,9
рейтинг
9 февраля в 03:32

Разработка → Передача сообщений между потоками. Классические блокирующие алгоритмы

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


Так что же разбудило Герцена?

Подтолкнулo меня к действию знакомство с
языком D
не надо продолжать аналогию, я вовсе не хотел сказать что он страшно далек от народа
— чрезвычайно концептуально красивым языком, унаследовавшим и мощно двинувшим вперед идиомы C++ и при этом сохранившим эффективные низкоуровневые инструменты, вплоть до указателей. Возможно из-за этого на мой взгляд в стандартной библиотеке D есть некоторая раздвоенность — большинство функционала можно вызвать или из коробки, простым и легким способом, или через приближенный к нативному интерфейс, зато полностью используя ресурсы и возможности системы. Если C++ перекрывает непрерывным спектром весь диапазон, то в D обычно хорошо заметно такое разделение. Посмотрите сами: нужно измерить интервал времени, есть замечательный модуль std.datetime, однако квант измерения — 100 нс, что мне совершенно недостаточно, пожалуйста — есть не менее замечательный модуль — core.time. Не устраивает облегченный до предела яваподобный std.concurrency.spawn — можете использовать весь букет из core.thread. И так практически везде, за исключением одного, но чрезвычайно важного места — разделения данных между потоками. Да, да, все локальные для данного потока переменные размещаются в thread local storage и никакими силами нельзя заставить другой поток увидеть их адрес. А для обмена данными предусмотрены встроенные очереди, надо признать очень удобные — полиморфные, с возможностью внеочередной посылки важных сообщений и чрезвычайно приятным интерфейсом. Посылать данные через них можно естественно или by value, или неизменяемые (immutable) ссылки. Я, когда об этом прочитал первый раз, просто подпрыгнул от возмущения — «Да как же рука ваша поганая поднялась...» — а потом задумался, припомнил свои проекты за последние годы и признал — да, весь обмен между потоками проходит по такой схеме, а то что не проходит — явная ошибка дизайна.
И тем не менее вопрос повис в воздухе — насколько эффективны очереди в D? Если нет, то это сводит на нет всю прочую эффективность языка, этакое встроенное бутылочное горлышко. Вот так я проснулся и снова взялся за измерения.

Что же конкретно мы будем мерить?

Вопрос на самом деле непростой, я об этом писал и в прошлый раз и пожалуй повторюсь. Обычный «наивный» подход, когда посылают N сообщений, замеряют общее время и делят на N не работает. Давайте разберемся, мы меряем производительность очереди, так? Следовательно можно считать что в процессе измерения скорость генератора сообщений и приемника сообщений стремится к бесконечности, при разумном предположении что внутри очереди данные не копируются, оказывается выгодным поместить как можно больше данных в очередь, потом выполнить однократную передачу некоторого внутреннего указателя и все, данные уже там. При этом среднее время на сообщение будет падать как 1/N (на самом деле ограничено снизу временем вставки/удаления, которое может составлять единицы наносекунд) тогда как время доставки каждого сообщения в теории остается постоянным, и даже растет как O(N) на практике.
Вместо этого я использую противоположный подход — каждое сообщение посылается, замеряется время и только потом посылается следующее (latency). Как следствие, результаты представляются в виде гистограмм, по оси X — время, по оси Y — число пакетов доставленных за это время. Наиболее интересны численно два параметра — медианное среднее время распределения и процент сообщений не уложившихся в некоторый (произвольный) верхний предел.
Строго говоря, такой подход тоже не вполне адекватен, тем не менее он гораздо точнее описывает требования к быстродействию. Я немножко позанимаюсь самокритикой в заключении, пока только скажу что полное описание включало бы генерацию всех возможных видов трафика и анализ его статистическими методами, получилась бы полноценная научная работа из области теории QA, или скорее меня бы настиг очередной приступ прокрастинации.
Еще один момент, упоминаю об этом потому что прошлый раз были долгие дебаты, генератор сообщений может вставлять их в очередь сколь угодно быстро, но при условии что получатель в среднем успевает их извлекать и обрабатывать, иначе все измерение просто лишено смысла. Если ваш принимающий поток не успевает обрабатывать поток данных, надо сделать код быстрее, распараллелить обработку, изменить протокол сообщений, но в любом случае сама очередь здесь не причем. Вроде бы мысль простая, однако прошлый раз пришлось повторять несколько раз в комментариях. Флуктуации скорости, когда вдруг в очереди оказывается много сообщений, вполне возможны и даже неизбежны, это как раз один из факторов который хорошо спроектированный алгоритм должен сглаживать, но это возможно только если максимальная скорость приема больше средней скорости посылки.

Начнем-с


Это что? А это собственно результат, все мои труды уложились в одну картинку, зато я сейчас буду долго обьяснять что и зачем здесь нарисовано.

Розовый. Стандартный механизм D

5 микросекунд, это много или мало? Практически во всех случаях это мало (то есть это очень хорошо). Для подавляющего большинства реальных проектов это более чем достаточное быстродействие, более того, еще не так давно такое время передачи можно было получить только при помощи специального железа и/или очень специального софта. Здесь же мы имеем инструмент из стандартной библиотеки, со множеством других вкусных плюшек и достаточно быстрый для всех практических нужд. Оценка — отлично. Но однако не великолепно, потому что этой реализации присущи некоторые недостатки не связанные с быстродействием, я расскажу об этом в ругательной части.
Еще раз с удовольствием убеждаемся что главная магия программирования — в отсутствии какой-либо магии. Если залезть под капот (разумеется я не мог не заглянуть), увидим что код совершенно обычный — односвязные списки защищенные мьютексами. Я даже не стану здесь его приводить потому что в смысле реализации очереди он ничего нового нам не скажет. Зато те немногие кому действительно нужны более быстрые алгоритмы, включая неблокирующие, могут легко написать свой собственный вариант убрав все удобные но замедляющие плюшки. Зато свой код я приведу, просто чтобы показать насколько D все таки лаконичный и выразительный язык.
код для иллюстрации
import std.stdio, std.concurrency, std.datetime, core.thread;

void main()
{
	immutable int N=1000000;
	auto tid=spawn(&f, N);
	foreach(i; 0..N) {
		tid.send(thisTid, MonoTime.currTime.ticks);
		// wait for receiver to handle message
		receiveOnly!int();
	}
}

void f(int n)
{
	foreach(i; 0..n) {
		auto m=receiveOnly!(Tid,long)();
		writeln(MonoTime.currTime.ticks-m[1]);
		// ask for the next message
		m[0].send(0);
	}
}



Синий. Лютый и неприкрытый C++.

400 наносекунд! Бинго! Побоку все неблокирующие и прочие хитрые алгоритмы! Или все таки нет?
Нет конечно, это грубая провокация, дело в том что в этом варианте читающий поток никогда не засыпает, продолжает в цикле непрерывно проверять очередь на пришедшие сообщения. Такой вариант работает пока вашим CPU просто нечем больше заняться, как только только появляются конкурирующие процессы, особенно если они так же безалаберно относятся к разделяемым ресурсам, все начинает непредсказуемо проскальзывать. Да, есть вариант с принудительным назначением одного из ядер для обслуживания этого потока, однако архитектурно это очень плохое решение, я вернусь к этому попозже. Есть места где это оправданно или даже необходимо, однако если вы в таком месте работаете, вы наверняка уже все сами знаете, для вас этот пост совершенно лишний.
Однако мы получили важную информацию — на современных системах скорость транзакций определяется вовсе не скоростью мьютексов или копирования данных, главный фактор — wake up time для потока после вынужденной или добровольной паузы. Отсюда мораль — если вы не хотите или не можете себе позволить dedicated CPU для обработки сообщений из очереди, подумайте дважды прежде чем использовать быстрые и сложные но неудобные в использовании решения, потери на подстраивание под них архитектуры приложения почти стопроцентно перевесят тот незначительный выигрыш, который вносит сам алгоритм во время транзакции. И, да, здесь я имею ввиду
boost::lockfree
это образцовый пример реализации неблокирующей очереди, однако тип сообщения обязан иметь тривиальные деструктор и оператор присваивания, условие настолько жестокое для C++ что я собственно так ни разу и не довел код до конечного продукта.

Так что же можно сделать оставаясь в рамках разумного?

Красный. Разумный и взвешенный C++.

Если кому-то пришел на ум usleep() и ему подобные — забудьте, вы гарантированно увеличиваете время отклика до минимум 40 микросекунд, это лучшее что современное ядро может гарантировать. Немногим лучше yield(), он, хотя и неплохо работает на малых загрузках, имеет тенденцию делиться процессорным временем с кем попало.
Это все из-за котиков разумеется
Опыт показывает, что на каждом сервере имеется хотя бы один процесс отрисовывающий в данный момент котиков, и он не отдаст CPU никому пока все котики в инете не будут тщательно отрисованы и залайканы
Выход один и он очевиден — использовать std::condition_variable, благо что мьютексы для синхронизации у нас уже используются и изменения в коде будут минимальными. В таком варианте получатель засыпает на переменной если очередь пуста, а генератор сообщений посылает сигнал если подозревает что партнер может спать. В этом случае ядро имеет все возможности для оптимизации и мы получаем результат, 3 микросекунды. Это уже можно сказать что ого, мы наступаем буквально на пятки всяким хитрым реализациям, при этом базовый код крайне прост и его можно адаптировать под все случаи жизни. Никакой полиморфизм здесь конечно и не ночевал как в D, зато и получилось почти в два раза быстрее. Без шуток, это вполне реальный конкурент неблокирующим алгоритмам.

Зеленый. Мастштабируемость, масштабируемость.

А это архитектурное решение которое я долго искал и вынашивал, хотя результат выглядит крайне просто. Часто спрашивают, сколько максимально сообщений в секунду можно передать через очередь и тому подобные вещи, забывая что противоположная ситуация случается не менее часто — пусть у нас имеется некоторое количество потоков, которые занимаются своим делом и время от времени должны посылать сообщения, не слишком часто, но важных. Мы не хотим на каждый такой поток вешать отдельного слушателя, который все равно будет по большей части спать, значит придется создать один общий центр обработки, который будет опрашивать все очереди и обслуживать сообщения по мере поступления. Но поскольку у нас сегодня не вечер длинного кода, а вечер коротких концептуальных фрагментов, я предлагаю использовать boost::asio, в качестве огромного бонуса этот же поток может обслуживать еще и сокеты и таймеры. Здесь, кстати, можно было бы легко обойтись вообще без очереди, захватывая данные прямо в передаваемой функции, очередь служит скорее как агрегатор и буфер для данных, ну и для смысловой связки с предыдущими примерами.
И что же мы получаем? 4.3 микросекунды на процессе из только одного генератора, совсем даже неплохо. Надо учитывать что результат неизбежно ухудшится в системе где много потоков одновременно пишут сообщения, однако масштабируемость практически ничем неограничена и это многого стоит.
Еще раз хочу подчеркнуть в чем философский смысл этого фрагмента — мы пересылаем в другой поток не просто данные, а данные плюс функтор, который сам знает как с ними работать, что-то вроде межпоточной виртуальности. Это настолько общая концепция, что могла бы наверное претендовать на звание отдельного design pattern.


На этом экспериментальная часть заканчивается, если нужен код всех тестов то вот он. Осторожно, это не готовая библиотека, так что бездумно копировать не советую, однако может служить вполне годным тьюториалом для разработки своего кода. Дополнения и улучшения приветствуются.

Разные рассуждения, по делу и не очень.

Зачем вообще нужны очереди сообщений? Как нас учит пример D, это самый кошерный паттерн для проектирования многопоточных систем, за которыми будущее, значит будущее и за очередями тоже. Но все ли очереди одинаковы? Какие есть варианты и в чем различия? Вот об этом и поговорим.
Во первых нужно различать потоки данных и потоки сообщений. С потоками данных все сравнительно просто, каждый переданный фрагмент не несет смысловой нагрузки и границы между фрагментами достаточно произвольны. Расходы на копирование сравнимы или превосходят ресурсы потребляемые собственно очередью и рецепт в этом случае крайне простой — увеличивайте внутренний буфер насколько можно, получите просто невероятную скорость. Квант данных, большой файл например, можно считать одним сообщением, настолько большим что оно чисто технически не может быть передано за один раз. Ну и все, больше об этом сказать наверное и нечего. А вот в потоке сообщений каждый следующий фрагмент несет законченную порцию информации и должен вызвать немедленную реакцию, о них-то мы сегодня и говорим.
Еще бывает полезно проанализировать архитектуру с точки зрения связности, что с чем соединяется. Простейший тип -«труба», соединяет два потока, писателя и читателя, его главное назначение — обеспечить развязку входного и выходного потоков, в идеале ни один из них не должен знать о проблемах другого. Второй атомарный тип очереди — «воронка», куда произвольное количество потоков могут писать, но только один читает. Это наверное наиболее востребованный случай, простейший пример — логгер. И вообще-то это все, обратный случай, когда один поток пишет и несколько читают, реализуется с помощью пучка «труб» и поэтому не является атомарным, а если вам вдруг понадобилась очередь куда кто угодно может писать и кто угодно из нее читать то я очень посоветовал бы пересмотреть свое отношение к жизни вообще и к проектирования многопоточных систем в частности.
Возвращаясь к развязке входного и выходного потоков, отсюда неизбежно следует вывод что идеальная очередь должна быть безразмерной, то есть при необходимости вмещать в себя бесконечно много сообщений. Простой пример: пусть крайне важный и ответственный поток хочет записать коротенькое сообщение в лог и вернуться к своим крайне важным делам. Однако лог у нас построен на основе очереди с буфером фиксированного размера, и вот только что кто-то скинул туда «Войну и мир» в полном объеме. Что делать? Блокировать вызывающий поток такая низкоприоритетная задача как логгер не должна, возвращать ошибку или исключение — крайне нежелательно с архитектурной точки зрения (мы перекладываем ответственность на вызывающую функцию, мы обязуем ее отслеживать все возможные исходы, мы крайне усложняем вызывающий код и вероятность ошибки, а взамен не получаем ничего — что делать-то все равно не ясно). И вообще, к чему были все эти разговоры о неблокирующих очередях, если оно вот прямо тут на наших глазах заблокированное лежит?. Именно поэтому я уже упоминал что стандартные очереди D не являются универсальным решением для межпоточного взаимодействия, более того, неблокирующий boost::lockfree::queue в одном из вариантов тоже использует фиксированный буфер и не является на самом деле неблокирующей очередью, хотя и использует неблокирующий алгоритм.
К счастью, оперативная память нынче — один из самых дешевых ресурсов, поэтому видимо самой оптимальной среди универсальных будет адаптивная стратегия — память при необходимости выделяется из кучи (большими кусками чтоб два раза не бегать) и никогда не освобождается, таким образом размер очереди подстраивается под всплески трафика и, при нормальной статистике, обращение к аллокатору происходит все реже. Опыт показывает что даже на серверах средней руки такой подход легко дает несколько часов форы, за которые можно успеть что-нибудь починить, дотянуть до плановой остановки, или хотя бы подыскать другую работу.
Ну и последнее — статистическая природа трафика. Про отличие передачи данных и передачи сообщений я уже говорил, но сообщения тоже могут иметь разное по времени распределение. Как ни странно, наиболее легкий случай если данные приходят максимально быстро (но не быстрее чем мы их успеваем из очереди вынимать), но при этом равномерно. При этом максимально эффективно работают различные ускорители, от спинлоков до встроенных в систему средств. Сложнее случай когда в потоке сообщений происходят мощные всплески, которые гарантированно превосходят скорость обработки. В этом режиме очередь должна эффективно накапливать приходящие сообщения, выделяя при необходимости память и не допуская при этом значительного замедления.
Именно тут я смухлевал
в тестах, сообщения посылаются строго по одному и я никак не исследовал ни поведение очередей D при блокировке на записи, ни поведение C очередей при необходимости аллоцировать память. Еще я никак не исследовал взаимное влияние и борьбу за ресурсы нескольких потоков, особенно когда их становится больше чем физических CPU. По обьему это легко тянет на отдельный пост.
Однако самый возможно тяжелый режим — когда сообщения приходят очень редко, но требуют немедленной реакции. За такое время может произойти что угодно, включая выпадение в своп. Если при нормальном распределении интервалов такие события случаются редко и попадают в те доли процента которые мы отбросили в тестах, то в этом случае эффективность может упасть на порядки.

Неполный список граблей в ассортименте.

  • Соблюдайте баланс записи и чтения: если читающий поток не справляется, никакой алгоритм вас не спасет. Делайте что хотите чтобы его ускорить, только очередь в этом не вините.
  • Кумулятивное замедление: бывает что для некоторых реализаций скорость очереди зависит от числа сообщений в ней, тогда случайный всплеск активности может замедлить очередь настолько, что она не освободится до следующего всплеска, примерно как затор на дороге. Такую неустойчивость довольно сложно смоделировать при тестировании.
  • Синдром ночного сторожа: иногда сообщения приходят очень редко, раз в час или даже раз в день, с точки зрения ОС это все равно вечность. Если сторож на посту сидит и ждет сигнала тревоги, а сигнала ни разу не было за всю его жизнь, чем он будет занят в критический момент? С таким спонтанным засыпанием трудно бороться.
  • Учитывайте хвост распределения: в приведенных тестах 2-3 сообщения на 1000 обрабатывались аномально долго, это общая черта для всех ОС общего назначения. Если вам вдруг надо еще понизить это число, придется крепко потрудиться.
  • Не рассчитывайте на выделенные CPU: это мощный ускоряющий фактор, но абсолютно не масштабируемый. В отличие от памяти, CPU — дорогой ресурс. Даже если в вашей системе 100500 ядер, обязательно найдется 100500+1 разработчиков желающих себе одно
    в личное пользование.
    Тот самый ПМ который год назад сам предлагал зарезервировать ядро на ускорение очередей теперь заглянет в душу честными голубыми глазами и скажет — «Ко мне тут ребята из фронтенда приходили, у них на главной странице логотип компании некрасивыми рывками перерисовывается. Просят выделить им одно из ядер, ты же понимаешь — это серьезно и всем видно, даже заказчик на днях внимание обратил. А твой сервер и так вроде работает, да и все равно его никто не видит». Если такое случится, рекомендую глубоко вдохнуть и медленно досчитать до десяти, иначе разрушения и жертвы неизбежны.
  • есть много чего еще: но я забыл что именно



Заканчивать принято на оптимистичной ноте: за многопоточностью не то чтобы будущее, скорее настоящее. А за мощными, гибкими и универсальными механизмами обмена сообщениями — будущее, но они еще толком не написаны, видимо нас ждут.
Всем успехов.
Сергей Дегтярев @degs
карма
94,5
рейтинг 20,9
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (37)

  • 0
    А где собственно lock-free очередь? Без неё пост явно не полный, и не даёт ответа на воспрос — на сколько lock-free очередь быстрее обычной (не lock free).
    • 0
      Так про них был первый пост, в самом начале на него ссылка.
      (ниже веткой ошибся)
      • 0
        В таком случае — правильно ли я понимаю что разницы практически нет (и там и там около 400нс если слушать в бесконечном цикле без слипов)?
        • +2
          Да, именно так и получается, можно сказать основной вывод в этом и состоит.
    • 0
      А почему вы думаете, что lock-free очередь должна быть быстрее? Есть ситуации когда lock-free алгоритмы могут себя вести куда менее эффективно. Синтетика тут может показать совершенно иные результаты, нежели будет в реальной жизни.
      • 0
        Обычно lock-free алгоритмы используют с целью улучшения производительности. Или же есть какой-то другой смысл в их использовании?
        • 0
          Используются для борьбы с dead lock'ом и подобными плохими ситуациями, которые трудно предсказать при наличии сложной логики поведения.
          • +1
            Нет, что вы, не-lock-free вовсе не означает deadlock. В общем случае термин lock-free означает что вставка/удаление из очереди происходят без использования мьютексов или других средств синхронизации. В идеале, wait-free algorithms, происходят за конечное число инструкций.
            Всем рекомендую почитать вот эту блестящую серию постов.
            • 0
              Может тогда приведете пример не-lock-free алгоритма который был бы свободен от lock'ов?
              • 0
                пожалуйста, вот псевдокод (я игнорирую для наглядности инициализацию и случаи пустой очереди, кроме того он страдает известной ABA проблемой):
                struct node { node* next; };
                
                struct queue
                {
                    node *head, *tail;
                
                // это пример wait-free алгоритма, операция завершается 
                //    за известное заранее число инструкций
                    void put(node* n) {
                        n->next=0;
                        atomic_swap(tail, n);
                        if(n) n->next=tail;
                    }
                
                // это lock-free, но не wait-free алгоритм,
                //   мы крутимся в цикле пока операция не пройдет успешно
                    node* get() {
                        for(;;) {
                            node *n=head;
                            if(atomic_compare_and_swap(head, n, n->next))
                                return n;
                        }
                    }
                };
                

                В общем случае используются атомарные операции, конкретно atomic_swap(a,b) — атомарно обменивает местами значения аргументов, и atomic_compare_and_swap(target, compare, new_value) — атомарно проверяет что target == compare и, если да, присваивает target=new_value, возвращает bool = успех операции.
                • 0
                  Вообще-то wait-free это и есть частный случай lock-free. Т.е. любой wait-free алгоритм удовлетворяет условиям lock-free.
                  Т.е. это как целые и натуральные числа, не все целые натуральные, но все натуральные — целые.

                  Вот хорошая обзорная статья с классификацией:

                  concurrencyfreaks.blogspot.ru/2013/05/lock-free-and-wait-free-definition-and.html

              • 0
                Я извиняюсь, не понял сразу вопроса.
                Не-lock-free алгоритм по определению использует блокирующие операции, но не входит в состояние deadlock, не путайте lock и deadlock.
                • 0
                  Как раз-таки существуют примеры non-blocking алгоритмов не обеспечивающие lock-free.
                  Spin-locks are an example of non-blocking synchronization: if one thread has a lock then waiting threads are not suspended, but must instead loop until the thread that holds the lock has released it. Spin locks and other algorithms with busy-wait loops are not lock-free, because if one thread (the one holding the lock) is suspended then no thread can make progress.


                  www.justsoftwaresolutions.co.uk/threading/non_blocking_lock_free_and_wait_free.html
                  • 0
                    я рассматриваю spinlock просто как один из вариантов блокировки, вы же сами написали:
                    Spin locks and other algorithms with busy-wait loops are not lock-free
                    • –1
                      Блокирующие алгоритмы это когда thread обратившийся к объекту засыпает в случае, если объект занят, до тех пор пока объект не освободится. Не блокирующие алгоритмы возвращают thread'у управление в любому случае.

                      Spin-lock является неблокирующим алгоритмом.
                      • 0
                        wiki
                        Без блокировок (англ. lock-free)
                        Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
                        • 0
                          to lock — запирать, замыкать
                          to block — блокировать, преграждать
          • 0
            Как вы себе это представляете? dead-lock-и возникают в именно что сложных ситуациях — нельзя просто так взять и заменить mutex-ы в существующих сложных объектах на некий lock-free алгоритм. lock-free структуры поставляются именно в виде готовых к употреблению структур. Это то-же самое, что и отказаться от mutex-ов в пользу оберток над структурами, защищающими все операции над этими структурами mutex-ом — но в таких случаях логика простая, и dead-lock-ов не возникает.
            • 0
              Давайте все-таки уточним: deadlock не возникает сам по себе, его создаем мы сами тем что криво пишем алгоритм.
              Правильно написанный алгоритм никогда не испытывает deadlock, и симметрично, lock-free алгоритм не является средством deadlock избежать.
            • 0
              Да есть ситуация когда mutex или что-то аналогичное используется что бы разделить доступ к объекту, которые по своей семантике не может быть использован разными процессами одновременно в принципе, тогда да — mutex'у нет замены.

              Но есть существуют и другие ситуации, когда, например, mutex создается на каждое обращение к non-thread safe коду, когда подразумевается доступ из разных thread'ов. Если такого кода очень много, то в итоге это может привести к непонятной логике и куче плохих ситуаций. Такие mutex'ы как правило легко заменять на lock-free алгоритмы.
              image

              Диаграмка отсюда preshing.com/20120612/an-introduction-to-lock-free-programming
              • +1
                Если код разросся до такого состояния, что существует куча логики с использованием блокировок в непонятных ситуациях, тогда lock-free алгоритмы точно не помогут такому коду, т.к. эти алгоритмы в разы сложнее алгоритмов с блокировками.
                Я бы рекомендовал придерживаться нескольких правил, чтобы избежать взаимных блокировок:
                1) мьютекс должен блокировать доступ к данным, а не код (если это возможно)
                2) никогда не вызывайте внешний код из под блокировки (коллбеки и т.п.)
                3) в идеале lock/unlock должны происходить в одной функции (RAII)
        • 0
          Да, обычно, но дело в том, что сами по себе lock-free алгоритмы при слишком высокой нагрузке могут стать менее эффективны. Из-за слишком частых холостых проходов. И если в синтетике нагрузить с большой кучи физических ядер, то просесть может очень сильно. В итоге смотреть есть смысл только уже в конкретных решениях.
          • +1
            Из-за слишком частых холостых проходов.
            Это не особо актуально для очередей с одним входом и одним выходом.
  • 0
    Так про них был первый пост, в самом начале на него ссылка.
  • 0
    Да, да, все локальные для данного потока переменные размещаются в thread local storage и никакими силами нельзя заставить другой поток увидеть их адрес.

    Для этого используются ключевые слова shared (разрешён только синхронный совместный доступ) и __gshared (как в C++, делай что хочешь).

    Если залезть под капот (разумеется я не мог не заглянуть), увидим что код совершенно обычный — односвязные списки защищенные мьютексами.
    Там ещё и сообщения полиморфные, то есть можно послать что угодно кому угодно, а тому придётся разгребать. Лучше всего для обмена сообщениями между потоками подходят каналы, как в go. Вот моя реализация неблокирующих каналов на D. Там, правда, используется экспоненциальное засыпание, а не блокирующая переменная, и не хватает мультиплексирования волокон, которые позволяют вместо засыпания, заняться потоку чем-то полезным.
    • 0
      Все правильно, только пост все таки не о коде, а о сравнении быстродействия стандартных механизмов, в том числе в D.
      • 0
        Ну так сравните в том числе и с неблокирующей реализацией на D:

        import std.stdio, std.datetime, jin.go;
        
        struct Tick { long start; }
        struct Ask {}
        
        enum N = 1000000;
        
        void main() {
        
        	auto ticks = new Queue!Tick;
        	auto asks = new Queue!Ask;
        
        	start!f( ticks , asks );
        
        	foreach( i ; 0 .. N ) {
        		ticks.push!Tick( MonoTime.currTime.ticks );
        		asks.take;
        	}
        }
        
        void f( Queue!Tick ticks , Queue!Ask asks ) {
        	foreach( i ; 0 .. N ) {
        		auto m  = ticks.take.start;
        		writeln( MonoTime.currTime.ticks - m );
        		asks.push!Ask();
        	}
        }
        


        Кроме того, на сколько я понял, вы собирали дебажные версии, а не релизные, что даёт свой вклад.
        • 0

          сравнил)
          У вас похоже где-то засыпание происходит, если вы не против, я в коде поковыряюсь немного.
          • 0
            Ну да, я же написал, что экспоненциальное засыпание :-) Думаю если добавиь перед засыпанием спинлок, то это сильно ускорит в этом тесте. А реализация на файберах (в один поток) думаю вообще всех уделает. Буду рад, если покопаетесь :-)
  • +3
    И вообщем-то мы приходим к тому, что lock-free имеет смысл только во всяких системах с какими-то нереально-огромными потоками данных, ну типа магистральных роутеров или чего-то такого. В обычной программе, обрабатывающей какие-то смешные миллиарды сообщений в день — эти изыски не будут иметь особого влияния в виду экономии пары секунд процессорного времени за сутки.
  • 0
    Можно узнать ваше мнение о nanomsg? Он решает схожие задачи и насколько успешно?
    • 0
      Честно скажу, про nanomsg от вас услышал, но я тут почитал немножко.
      Вообще говоря, это библиотека другого уровня и главная ее цель — общий интерфейс для семейства различных протоколов. А насчет быстродействия, интуиция мне подсказывает что должно быть порядка 100 мкс, по крайней мере это та цель к которой я бы стремился. Я кстати когда-то мерил ZeroMQ, давно уже, цифр не помню, но помню что подтормаживало сильно, был разочарован.
  • 0
    А как достигается разрешение радикально выше 100 нс при измерении? ЕМНИП, HPET работает на 14 или 18 МГц и разрешения выше 55нс получить проблематично без использования левых таймеров. Мне, например, на .NET/Win32 интервал менее 300нс стандартными средствами не удалось замерять.
    • 0
      на моей машине:

      iBolit# cat /sys/devices/system/clocksource/clocksource0/available_clocksource 
      tsc hpet acpi_pm 
      iBolit# cat /sys/devices/system/clocksource/clocksource0/current_clocksource
      tsc

      и разрешение TSC у меня как раз равно 1нс, TSC как правило сильно выигрывает у HPET. Конечно остается проблема точности вызова самой функции, но я это тоже мерил (в статью не вошло за недостатком места) и оцениваю точность измерения в 20 нс.
      • 0
        Ну я последовал рекомендации на MSDN: "We strongly discourage using the RDTSC or RDTSCP processor instruction to directly query the TSC because you won't get reliable results on some versions of Windows, across live migrations of virtual machines, and on hardware systems without invariant or tightly synchronized TSCs."
        И кстати на Linux машинах тоже не использовал его, т.к. при graceful синхронизации по ntp только hpet нормальные timestamp давал в момент "движения" времени.
        • 0
          Ну у меня же измеряются короткие интервалы для которых дрейф TSC несущественен, а абсолютное время и ntp вообще не нужны.
          • 0
            Ну у меня интервалы не более 60 микросекунд в общем, просто метка путешествует через 3 процесса. Вобщем как я и думал, в D вопрос кросс-процессорного профилирования тоже нормально не решен. Ну как и нигде вобщем.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.