Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 37
А где собственно lock-free очередь? Без неё пост явно не полный, и не даёт ответа на воспрос — на сколько lock-free очередь быстрее обычной (не lock free).
Так про них был первый пост, в самом начале на него ссылка.
(ниже веткой ошибся)
(ниже веткой ошибся)
А почему вы думаете, что lock-free очередь должна быть быстрее? Есть ситуации когда lock-free алгоритмы могут себя вести куда менее эффективно. Синтетика тут может показать совершенно иные результаты, нежели будет в реальной жизни.
Обычно lock-free алгоритмы используют с целью улучшения производительности. Или же есть какой-то другой смысл в их использовании?
Нет, что вы, не-lock-free вовсе не означает deadlock. В общем случае термин lock-free означает что вставка/удаление из очереди происходят без использования мьютексов или других средств синхронизации. В идеале, wait-free algorithms, происходят за конечное число инструкций.
Всем рекомендую почитать вот эту блестящую серию постов.
Всем рекомендую почитать вот эту блестящую серию постов.
пожалуйста, вот псевдокод (я игнорирую для наглядности инициализацию и случаи пустой очереди, кроме того он страдает известной ABA проблемой):
В общем случае используются атомарные операции, конкретно atomic_swap(a,b) — атомарно обменивает местами значения аргументов, и atomic_compare_and_swap(target, compare, new_value) — атомарно проверяет что target == compare и, если да, присваивает target=new_value, возвращает bool = успех операции.
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 = успех операции.
Я извиняюсь, не понял сразу вопроса.
Не-lock-free алгоритм по определению использует блокирующие операции, но не входит в состояние deadlock, не путайте lock и deadlock.
Не-lock-free алгоритм по определению использует блокирующие операции, но не входит в состояние deadlock, не путайте lock и deadlock.
я рассматриваю spinlock просто как один из вариантов блокировки, вы же сами написали:
Spin locks and other algorithms with busy-wait loops are not lock-free
wiki
Без блокировок (англ. lock-free)
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
Без блокировок (англ. lock-free)
Для алгоритмов без блокировок гарантируется системный прогресс по крайней мере одного потока. Например, поток, выполняющий операцию «сравнение с обменом» в цикле, теоретически может выполняться бесконечно, но каждая его итерация означает, что какой-то другой поток совершил прогресс, то есть система в целом совершает прогресс.
Как вы себе это представляете? dead-lock-и возникают в именно что сложных ситуациях — нельзя просто так взять и заменить mutex-ы в существующих сложных объектах на некий lock-free алгоритм. lock-free структуры поставляются именно в виде готовых к употреблению структур. Это то-же самое, что и отказаться от mutex-ов в пользу оберток над структурами, защищающими все операции над этими структурами mutex-ом — но в таких случаях логика простая, и dead-lock-ов не возникает.
Давайте все-таки уточним: deadlock не возникает сам по себе, его создаем мы сами тем что криво пишем алгоритм.
Правильно написанный алгоритм никогда не испытывает deadlock, и симметрично, lock-free алгоритм не является средством deadlock избежать.
Правильно написанный алгоритм никогда не испытывает deadlock, и симметрично, lock-free алгоритм не является средством deadlock избежать.
Если код разросся до такого состояния, что существует куча логики с использованием блокировок в непонятных ситуациях, тогда lock-free алгоритмы точно не помогут такому коду, т.к. эти алгоритмы в разы сложнее алгоритмов с блокировками.
Я бы рекомендовал придерживаться нескольких правил, чтобы избежать взаимных блокировок:
1) мьютекс должен блокировать доступ к данным, а не код (если это возможно)
2) никогда не вызывайте внешний код из под блокировки (коллбеки и т.п.)
3) в идеале lock/unlock должны происходить в одной функции (RAII)
Я бы рекомендовал придерживаться нескольких правил, чтобы избежать взаимных блокировок:
1) мьютекс должен блокировать доступ к данным, а не код (если это возможно)
2) никогда не вызывайте внешний код из под блокировки (коллбеки и т.п.)
3) в идеале lock/unlock должны происходить в одной функции (RAII)
Да, обычно, но дело в том, что сами по себе lock-free алгоритмы при слишком высокой нагрузке могут стать менее эффективны. Из-за слишком частых холостых проходов. И если в синтетике нагрузить с большой кучи физических ядер, то просесть может очень сильно. В итоге смотреть есть смысл только уже в конкретных решениях.
Так про них был первый пост, в самом начале на него ссылка.
Да, да, все локальные для данного потока переменные размещаются в thread local storage и никакими силами нельзя заставить другой поток увидеть их адрес.
Для этого используются ключевые слова shared (разрешён только синхронный совместный доступ) и __gshared (как в C++, делай что хочешь).
Если залезть под капот (разумеется я не мог не заглянуть), увидим что код совершенно обычный — односвязные списки защищенные мьютексами.Там ещё и сообщения полиморфные, то есть можно послать что угодно кому угодно, а тому придётся разгребать. Лучше всего для обмена сообщениями между потоками подходят каналы, как в go. Вот моя реализация неблокирующих каналов на D. Там, правда, используется экспоненциальное засыпание, а не блокирующая переменная, и не хватает мультиплексирования волокон, которые позволяют вместо засыпания, заняться потоку чем-то полезным.
Все правильно, только пост все таки не о коде, а о сравнении быстродействия стандартных механизмов, в том числе в D.
Ну так сравните в том числе и с неблокирующей реализацией на 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();
}
}
Кроме того, на сколько я понял, вы собирали дебажные версии, а не релизные, что даёт свой вклад.
И вообщем-то мы приходим к тому, что lock-free имеет смысл только во всяких системах с какими-то нереально-огромными потоками данных, ну типа магистральных роутеров или чего-то такого. В обычной программе, обрабатывающей какие-то смешные миллиарды сообщений в день — эти изыски не будут иметь особого влияния в виду экономии пары секунд процессорного времени за сутки.
Честно скажу, про nanomsg от вас услышал, но я тут почитал немножко.
Вообще говоря, это библиотека другого уровня и главная ее цель — общий интерфейс для семейства различных протоколов. А насчет быстродействия, интуиция мне подсказывает что должно быть порядка 100 мкс, по крайней мере это та цель к которой я бы стремился. Я кстати когда-то мерил ZeroMQ, давно уже, цифр не помню, но помню что подтормаживало сильно, был разочарован.
Вообще говоря, это библиотека другого уровня и главная ее цель — общий интерфейс для семейства различных протоколов. А насчет быстродействия, интуиция мне подсказывает что должно быть порядка 100 мкс, по крайней мере это та цель к которой я бы стремился. Я кстати когда-то мерил ZeroMQ, давно уже, цифр не помню, но помню что подтормаживало сильно, был разочарован.
А как достигается разрешение радикально выше 100 нс при измерении? ЕМНИП, HPET работает на 14 или 18 МГц и разрешения выше 55нс получить проблематично без использования левых таймеров. Мне, например, на .NET/Win32 интервал менее 300нс стандартными средствами не удалось замерять.
на моей машине:
и разрешение TSC у меня как раз равно 1нс, TSC как правило сильно выигрывает у HPET. Конечно остается проблема точности вызова самой функции, но я это тоже мерил (в статью не вошло за недостатком места) и оцениваю точность измерения в 20 нс.
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 нс.
Ну я последовал рекомендации на 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 давал в момент "движения" времени.
И кстати на Linux машинах тоже не использовал его, т.к. при graceful синхронизации по ntp только hpet нормальные timestamp давал в момент "движения" времени.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Передача сообщений между потоками. Классические блокирующие алгоритмы