Начнем с того, что процессор не будет работать быстрее от того, что у нити повышен приоритет. Не стоит об этом забывать.

Повышение приоритета нити, которая выполняет большую работу процессором, приведет к тому, что UI будет перерисовываться рывками (только по starvation prevention в кернеле). Юзеры за это спасибо не скажут.

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

А вот если вся работа нити состоит в "получить реквест — исполнить его, сделав disk/network IO — ждать следующего" — вот тут повышение приоритета очень полезно.

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

Это приведет к большой задержке между получением и исполнением реквеста.

Если же дать такой нити высокий приоритет — то ее мало кто прервет в самом интересном месте. И негативного эффекта на систему в целом не будет — ей все равно вот-вот блокироваться в вызове, который и есть исполнение реквеста. Заблокируется и отдаст процессор, а реквест тем временем уже бежит — на RPC сервере, на SQL сервере, или же на железке диска.

Это описано еще в классической книге Дейтела про ОС — CPU-bound нитям приоритет пониже, IO-bound — повыше.

Еще надо упомянуть инверсию приоритета. Возникает она при наличии защищенных локом данных, к которым обращаются 2 нити разного приоритета.

Допустим, низкоприоритетная нить A взяла лок, начала трогать данные, и тут ее прервали — например, завершением IO, которое как правило дает priority boost. А там, возможно, еще парочка равных по приоритету нитей побегать успела.

Все это время высокоприоритетная нить B, которая тоже хочет работать с данными, стоит на захваченном локе.

Вот это называется "инверсия приоритета". Тормоза создает — очень даже заметные.

Как избежать: решить для себя, каков наибольший приоритет, с которого будет браться данный лок. И всем остальным нитям поднять приоритет до этой отметки перед взятием лока и на время работы с залоканными данными. Снизить обратно после освобождения лока.

R>>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.
R>>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

I>можно ли где то более подробно посмотреть?

На гугле.

Краткая суть lock-free: активно применяется InterlockedExchangePointer, причем, как я понял, без останова нитей в цикле "крутимся и ждем, пока тут станет не нуль".

Дело в том, что, если позволить такие остановы, то у нас получится spinlock, и, вместо того, чтобы возиться с lock-free, проще будет защитить структуру спинлоком.

Я даже больше скажу: при низком соревновании за лок lock-free не дает никаких преимуществ по сравнению со спинлоком, ибо реализация в основном одна и та же — interlocked exchange.

Да, далеко не любой лок требует обращений к диспетчеру ядра. Например, спинлок не требует вовсе, а самый главный лок в ядре виндов под названием FAST_MUTEX и самый главный лок в Win32 под названием CRITICAL_SECTION вырождаются в спинлок при низком соревновании. Для CRITICAL_SECTION вон даже spin count можно задать.

Так что выигрышей от lock-free — при условии, что используются вот такие умные локи — не так уж и много, разве что при гигантском contention в этом месте, когда умные локи резко тупеют

Недостаток же lock-free — огромная интеллектуальная сложность, причем простейшие решения не годятся как база для более наворочанных.

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Допустим, низкоприоритетная нить A взяла лок, начала трогать данные, и тут ее прервали — например, завершением IO, которое как правило дает priority boost. А там, возможно, еще парочка равных по приоритету нитей побегать успела.
MSS>Все это время высокоприоритетная нить B, которая тоже хочет работать с данными, стоит на захваченном локе.
MSS>Вот это называется "инверсия приоритета". Тормоза создает — очень даже заметные.
MSS>Как избежать: решить для себя, каков наибольший приоритет, с которого будет браться данный лок. И всем остальным нитям поднять приоритет до этой отметки перед взятием лока и на время работы с залоканными данными. Снизить обратно после освобождения лока.

Грамотная ОС должна такие вещи уметь сама.

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Повышение приоритета нити, которая выполняет большую работу процессором, приведет к тому, что UI будет перерисовываться рывками (только по starvation prevention в кернеле). Юзеры за это спасибо не скажут.

MSS>А вот если вся работа нити состоит в "получить реквест — исполнить его, сделав disk/network IO — ждать следующего" — вот тут повышение приоритета очень полезно.

Да, обычно повышают приоритет UI потоков и потоков, забирающих данные с сетевого интерфейса. Первое — для повышения реактивности UI, второе — для предотврашения переполнения буферов на приём.




MSS>Вот это называется "инверсия приоритета". Тормоза создает — очень даже заметные.

Lock-free структуры данных рулят


MSS>Как избежать: решить для себя, каков наибольший приоритет, с которого будет браться данный лок. И всем остальным нитям поднять приоритет до этой отметки перед взятием лока и на время работы с залоканными данными. Снизить обратно после освобождения лока.

По-моему слишком радикально
Получается из 300 тактов (100 — взять лок, 100 — сделать работу, 100 отдать лок) получаем 4300 (+ 2х2000 — вызов ядра). Расчёты очень приблизительные.

R>Да, обычно повышают приоритет UI потоков и потоков, забирающих данные с сетевого интерфейса. Первое — для повышения реактивности UI, второе — для предотврашения переполнения буферов на приём.

Приоритет UI повысит сама ОС что до забора данных с сокета — ага, это все тот же случай IO-bound thread, о котором я писал.

R>Lock-free структуры данных рулят

Пригодны только в простейших случаях, потому не применяются в реальных ОС.

R>По-моему слишком радикально
R>Получается из 300 тактов (100 — взять лок, 100 — сделать работу, 100 отдать лок) получаем 4300 (+ 2х2000 — вызов ядра). Расчёты очень приблизительные.

И пусть. Потери на инверсии приоритета — намного больше. Они там не в трате тактов заключаются, а в том, что, например, значительно позже инициируется disk IO.

В итоге получается, что процесс работает медленно (процентов на 20-30 даже), но да — мало грузит диски и процессор. Потому что он не оптимален.

N>Грамотная ОС должна такие вещи уметь сама.

Ага, должна. Выглядит в теории так — перед тем, как остановить нового контендера в ожидании на локе, приоритет текущего владельца лока вздрючивается до приоритета контендера.

Только вот не на всех реально используемых локах это имплементировано.

Здравствуйте, Maxim S. Shatskih, Вы писали:

R>>Да, обычно повышают приоритет UI потоков и потоков, забирающих данные с сетевого интерфейса. Первое — для повышения реактивности UI, второе — для предотврашения переполнения буферов на приём.

MSS>Приоритет UI повысит сама ОС что до забора данных с сокета — ага, это все тот же случай IO-bound thread, о котором я писал.

R>>Lock-free структуры данных рулят

MSS>Пригодны только в простейших случаях, потому не применяются в реальных ОС.

Это не так.
И применимы в не простейших случаях. И в ОС применяются.
В качестве нагляднейшего и выразительнейшего примера применения в ОС можно глядеть RCU в Linux (часть scalability effort). Так же можно глядеть патчи к tcp подсистеме Linux. И стеки в Win32.
По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.
Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.


R>>По-моему слишком радикально
R>>Получается из 300 тактов (100 — взять лок, 100 — сделать работу, 100 отдать лок) получаем 4300 (+ 2х2000 — вызов ядра). Расчёты очень приблизительные.

MSS>И пусть. Потери на инверсии приоритета — намного больше. Они там не в трате тактов заключаются, а в том, что, например, значительно позже инициируется disk IO.

Я не говорю, что взамен надо допускать инверсии приоритета.
Возможные выходы: опять же Lock-free структуры данных — они не страдают такими болезнями. Либо развязка потоков с разным приоритетом. Либо максимальная минимизация времени под локом и максимальное снижение частоты обращения к нему (возможно кэширование разделяемых данных, либо агрегация запросов к разделяемым данным).

Здравствуйте, remark, Вы писали:

R>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.
R>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

можно ли где то более подробно посмотреть?

Здравствуйте, remark, Вы писали:

R>>>Lock-free структуры данных рулят :super:
MSS>>Пригодны только в простейших случаях, потому не применяются в реальных ОС.
R>Это не так.
R>И применимы в не простейших случаях. И в ОС применяются.
R>В качестве нагляднейшего и выразительнейшего примера применения в ОС можно глядеть RCU в Linux (часть scalability effort). Так же можно глядеть патчи к tcp подсистеме Linux. И стеки в Win32.

RCU — это не lock-free. По крайней мере в обычном понимании большинства тех, кто с этим возится. (Да хотя бы из-за лока писателя — от которого она всё равно не избавляет.) Это совершенно отдельная методика, даже если сделана на схожих принципах.
И у неё есть свои недостатки. Необходимость копирования структуры (по крайней мере в реализации линуксового стиля) на каждый второй мелкий чих — приводит к тому, что эти структуры надо держать мелкими, иначе оверхед на копирование станет заметным.

Под lock-free же обычно понимают ситуации, когда можно изменить обстановку атомарными операциями без захвата какого-то лока. Это реализуемо в ряде случаев, но:

1. Мало где можно ограничиться самым классическим для lock-free случаем оперирования головой односвязного списка, и аналогичными ситуациями, когда меняется или одно поле, или несколько гарантированно идущих подряд в памяти. Уже с двусвязным списком мы пролетаем на большинстве процессоров. В исключения попадают разве что старшие модели семейства PPC, которые умеют держать не один memory guard для LL/SC, а от двух до четырёх. Вот там можно реализовать неблокирующую замену на ходу в обычном двусвязном списке и, может быть, одновременно ещё где-то.

2. Даже при наличии столь продвинутых аппаратных средств часто требуется обеспечить не просто добавление/удаление/замену в списке, а что-то более сложное, при котором постороннее вмешательство посредине полного процесса может быть фатальным. Например, если в процессе одна нить попросила create_thread(), а вторая в это время дёрнула exit(), действия несовместимы.

R>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.

Целиком — 1) не верю. 2) нет смысла. Центральные структуры (например, таблицу маппинга портов в указатели на управляющие структуры соответствующих сокетов, таблицы раутинга, данные iptables) — да, можно и наверняка имеет смысл — если речь про RCU.

R>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

Ну тот же RCU я бы экстремально сложным не назвал. Надо чётко выдерживать методику — это да. Но даже плохо понимая её аккуратно закодировать нужные вызовы — задача для студента.

Здравствуйте, ironwit, Вы писали:

I>Здравствуйте, remark, Вы писали:

R>>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.
R>>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

I>можно ли где то более подробно посмотреть?

http://en.wikipedia.org/wiki/RCU для начала:)

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Вот это называется "инверсия приоритета". Тормоза создает — очень даже заметные.
Хм.. "Инверсией приоритета", помоему называется как раз способ борьбы с этим эффектом. Собственно, потому и инверсия — потоки с более высоким приоритетом скидываются в пользу потока с низким, чтобы эта зараза освободила-таки ресурс.
Ну да ладно.. )

Так же стоит упомянуть про существование в системах с вытесняющей многозадачностью такой штуки как convoy effect.

Простейшее проявление выглядит следующим образом: Если потоку требуется ресурс в монопольное пользование на время превышающее отпущенный ему квант, то менеджер потоков переключит контекст на другой поток раньше, чем владелец ресурса успеет его освободить. И если другим потокам потребуется этот же ресурс, то они проведут отпущенное им время в бесцельном ожидании освобождения ресурса, пока контекст опять не перещелкнется на текущего владельца. Очевидно, очередь за ресурсом будет со временем только расти. Способ борьбы с этим простой — поток обнаружив что ресурс занят, не дожидаясь освобождения ресурса, ставит себя в очередь явно передавая управление дальше по цепочке.
Но самое забавное наступает, когда ресурс может быть несколько раз захвачен и отпущен за квант потока, тут уже стандартный спинлок может не спасти. Если переключение контекста произошло в тот момент, когда ресурс захвачен, другие потоки, бесполезно покрутившись на спинлоке, впадают в спячку, поставив себя в очередь. Если же переключение контекста произошло в тот момент, когда ресурс свободен, то ресурс оказывается немедленно захвачен другим потоком, а первоначальный поток, при попытке опять воспользоваться ресурсом, попадает на ожидание и оказывается в конце очереди. Со временем очередь только растет и конвой не рассасывается до возникновения какой-нибудь нерегулярности. И дальше по кругу — ни один поток не может удержать ресурс дольше небольшой доли кванта (квант / сколько раз за квант ресурс захватывается потоком).
Способ борьбы — отказаться от очереди, и просто явно передавать управление дальше по цепочке. Как только исчезает очередь, конвой рассасывается, будет серия быстрых переключений контекста, но после освобождения ресурса никто его немедленно не захватывает, поэтому текущий поток спокойно может повторно им повладеть.
В MSDN-е кажется был пример по борьбе с конвоем...

Здравствуйте, IB, Вы писали:

IB>Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>>Вот это называется "инверсия приоритета". Тормоза создает — очень даже заметные.
IB>Хм.. "Инверсией приоритета", помоему называется как раз способ борьбы с этим эффектом. Собственно, потому и инверсия — потоки с более высоким приоритетом скидываются в пользу потока с низким, чтобы эта зараза освободила-таки ресурс.
IB>Ну да ладно.. )

IB>Так же стоит упомянуть про существование в системах с вытесняющей многозадачностью такой штуки как convoy effect.

IB>Простейшее проявление выглядит следующим образом: Если потоку требуется ресурс в монопольное пользование на время превышающее отпущенный ему квант, то менеджер потоков переключит контекст на другой поток раньше, чем владелец ресурса успеет его освободить. И если другим потокам потребуется этот же ресурс, то они проведут отпущенное им время в бесцельном ожидании освобождения ресурса, пока контекст опять не перещелкнется на текущего владельца. Очевидно, очередь за ресурсом будет со временем только расти. Способ борьбы с этим простой — поток обнаружив что ресурс занят, не дожидаясь освобождения ресурса, ставит себя в очередь явно передавая управление дальше по цепочке.
IB>Но самое забавное наступает, когда ресурс может быть несколько раз захвачен и отпущен за квант потока, тут уже стандартный спинлок может не спасти. Если переключение контекста произошло в тот момент, когда ресурс захвачен, другие потоки, бесполезно покрутившись на спинлоке, впадают в спячку, поставив себя в очередь. Если же переключение контекста произошло в тот момент, когда ресурс свободен, то ресурс оказывается немедленно захвачен другим потоком, а первоначальный поток, при попытке опять воспользоваться ресурсом, попадает на ожидание и оказывается в конце очереди. Со временем очередь только растет и конвой не рассасывается до возникновения какой-нибудь нерегулярности. И дальше по кругу — ни один поток не может удержать ресурс дольше небольшой доли кванта (квант / сколько раз за квант ресурс захватывается потоком).
IB>Способ борьбы — отказаться от очереди, и просто явно передавать управление дальше по цепочке. Как только исчезает очередь, конвой рассасывается, будет серия быстрых переключений контекста, но после освобождения ресурса никто его немедленно не захватывает, поэтому текущий поток спокойно может повторно им повладеть.
IB>В MSDN-е кажется был пример по борьбе с конвоем...IB>Хм.. "Инверсией приоритета", помоему называется как раз способ борьбы с этим эффектом.

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

IB>Собственно, потому и инверсия

"Инверсия" — потому, что, когда такое случается, высокоприоритетная нить ждет низкоприоритетную.

IB>Простейшее проявление выглядит следующим образом: Если потоку требуется ресурс в монопольное пользование на время превышающее отпущенный ему квант, то менеджер потоков переключит контекст на другой поток раньше, чем владелец ресурса успеет его освободить.

Держать лок целый квант (это очень большое вычислительное время) — ужасно.

Напомню, что кванты времени есть _вспомогательный_ механизм шедулера, а основной — signal/wait. Кванты выходят на сцену только тогда, когда нить бежала целый квант и ни на чем не остановилась в ожидании за это немалое время. Естественно, это 100% загрузки процессора. Вот кванты тут и выходят на сцену, чтобы обеспечить fairness при наличии такой вот нити или нитей.

В VMM старых виндов это вообще 2 слоя архитектуры были — низ шедулера с signal/wait и верх шедулера, который добавлял еще и кванты.

Кстати, один лишь signal/wait без квантов не значит nonpreemptive. Нить все равно может быть вдруг прервана в любом месте — пробуждением другой нити. В nonpreemptive это не так — нить может быть прервана только внутри wait и yield.

IB> И если другим потокам потребуется этот же ресурс, то они проведут отпущенное им время в бесцельном ожидании освобождения ресурса, пока контекст опять не перещелкнется на текущего владельца. Очевидно, очередь за ресурсом будет со временем только расти. Способ борьбы с этим простой — поток обнаружив что ресурс занят, не дожидаясь освобождения ресурса, ставит себя в очередь явно передавая управление дальше по цепочке.

Ага, картина действительно похожа на priority inversion. Так что, чем короче залоканные куски кода — тем лучше.

IB>Но самое забавное наступает, когда ресурс может быть несколько раз захвачен и отпущен за квант потока, тут уже стандартный спинлок может не спасти. Если переключение контекста произошло в тот момент, когда ресурс захвачен, другие потоки, бесполезно покрутившись на спинлоке, впадают в спячку, поставив себя в очередь.

Ну это тогда не спинлок, а что-то вроде FAST_MUTEX. Спинлок вообще не связан с шедулером, ожидание на нем — это вечный цикл. Спинлок, который заставляет контендера обратиться к шедулеру и поставить себя в очередь после какого-то количества оборотов цикла — это вот скорее FAST_MUTEX или CRITICAL_SECTION.

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

Голодание. Классическое. Потому придумываются виды локов, гарантирующие fairness в виде first in — first out, например, есть такой queued spinlock.

В MSDNе — есть, и там convoy effect — это ожидание доступности ресурса под названием thread. Сейчас еще в Википедии гляну.

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

IB>Хм.. "Инверсией приоритета", помоему называется как раз способ борьбы с этим эффектом.

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

IB>Собственно, потому и инверсия

"Инверсия" — потому, что, когда такое случается, высокоприоритетная нить ждет низкоприоритетную.

IB>Простейшее проявление выглядит следующим образом: Если потоку требуется ресурс в монопольное пользование на время превышающее отпущенный ему квант, то менеджер потоков переключит контекст на другой поток раньше, чем владелец ресурса успеет его освободить.

Держать лок целый квант (это очень большое вычислительное время) — ужасно.

Напомню, что кванты времени есть _вспомогательный_ механизм шедулера, а основной — signal/wait. Кванты выходят на сцену только тогда, когда нить бежала целый квант и ни на чем не остановилась в ожидании за это немалое время. Естественно, это 100% загрузки процессора. Вот кванты тут и выходят на сцену, чтобы обеспечить fairness при наличии такой вот нити или нитей.

В VMM старых виндов это вообще 2 слоя архитектуры были — низ шедулера с signal/wait и верх шедулера, который добавлял еще и кванты.

Кстати, один лишь signal/wait без квантов не значит nonpreemptive. Нить все равно может быть вдруг прервана в любом месте — пробуждением другой нити. В nonpreemptive это не так — нить может быть прервана только внутри wait и yield.

IB> И если другим потокам потребуется этот же ресурс, то они проведут отпущенное им время в бесцельном ожидании освобождения ресурса, пока контекст опять не перещелкнется на текущего владельца. Очевидно, очередь за ресурсом будет со временем только расти. Способ борьбы с этим простой — поток обнаружив что ресурс занят, не дожидаясь освобождения ресурса, ставит себя в очередь явно передавая управление дальше по цепочке.

Ага, картина действительно похожа на priority inversion. Так что, чем короче залоканные куски кода — тем лучше.

IB>Но самое забавное наступает, когда ресурс может быть несколько раз захвачен и отпущен за квант потока, тут уже стандартный спинлок может не спасти. Если переключение контекста произошло в тот момент, когда ресурс захвачен, другие потоки, бесполезно покрутившись на спинлоке, впадают в спячку, поставив себя в очередь.

Ну это тогда не спинлок, а что-то вроде FAST_MUTEX. Спинлок вообще не связан с шедулером, ожидание на нем — это вечный цикл. Спинлок, который заставляет контендера обратиться к шедулеру и поставить себя в очередь после какого-то количества оборотов цикла — это вот скорее FAST_MUTEX или CRITICAL_SECTION.

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

Голодание. Классическое. Потому придумываются виды локов, гарантирующие fairness в виде first in — first out, например, есть такой queued spinlock.

В MSDNе — есть, и там convoy effect — это ожидание доступности ресурса под названием thread. Сейчас еще в Википедии гляну.

MSS>Краткая суть lock-free: активно применяется InterlockedExchangePointer, причем, как я понял, без останова нитей в цикле "крутимся и ждем, пока тут станет не нуль".

иесть ещё пара способов из опыта функциональных языков. первый — это использование иммутабельных структур данных. вместо изменения существующих просто конструируются новые структуры, ес-но это требует GC для сколь-либо удобной работы

второй — STM, транзакционный подход к обновлению структур данных: http://research.microsoft.com/%7Esimonpj/papers/stm/

я точно помню, что STM переносилось на какие-то С-подобные языки, поищи сам

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Краткая суть lock-free: активно применяется InterlockedExchangePointer, причем, как я понял, без останова нитей в цикле "крутимся и ждем, пока тут станет не нуль".
MSS>Дело в том, что, если позволить такие остановы, то у нас получится spinlock, и, вместо того, чтобы возиться с lock-free, проще будет защитить структуру спинлоком.
MSS>Я даже больше скажу: при низком соревновании за лок lock-free не дает никаких преимуществ по сравнению со спинлоком, ибо реализация в основном одна и та же — interlocked exchange.
MSS>Так что выигрышей от lock-free — при условии, что используются вот такие умные локи — не так уж и много, разве что при гигантском contention в этом месте, когда умные локи резко тупеют
Нет. В lock-free у нас столкновение на локах — исключительно редкое событие. А еще есть и wait-free алгоритмы, в которых мы гарантировано никогда не будем ждать. Кстати, доказано, что любой параллельный алгоритм можно сделать wait-free. Правда, для многих алгоритмов такая реализация потребует слишком больших расходов памяти.

Ну и самое главное преимущество по сравнению со спинлоками — атомарность. В случае со спинлокам нас могут за-preemt'ить пока мы его держим, тогда остальные потоки будут курить бамбук в течение долгого времени.

MSS>Недостаток же lock-free — огромная интеллектуальная сложность, причем простейшие решения не годятся как база для более наворочанных.
Можно использовать множество готовых решений. Меня вот недавано вот это: http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf просто ошеломило.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, Maxim S. Shatskih, Вы писали:

C>Нет. В lock-free у нас столкновение на локах — исключительно редкое событие.

Редкое или нет, а отрабатывать надо. Возьмём классический учебный пример про односвязный список. Запоминаем в своей структуре указатель на первый элемент (1) и подменяем голову списка (2). Может кто-то влезть между этими действиями? Да, может. Что делать? Перезапускать по новой. Детали реализации будут в точности соответствовать циклу вокруг CMPXCHG в x86, CASXA в Sparc, и LL/SC (независимо от имени) в Alpha/PPC/MIPS/etc., и оно рано или поздно выполнится успешно (кроме случая, когда конкурентов за этот ресурс слишком много).

C> А еще есть и wait-free алгоритмы, в которых мы гарантировано никогда не будем ждать. Кстати, доказано, что любой параллельный алгоритм можно сделать wait-free. Правда, для многих алгоритмов такая реализация потребует слишком больших расходов памяти.

URL? А то что-то по словам "wait-free algorithms" находится только общая вода.

C>Ну и самое главное преимущество по сравнению со спинлоками — атомарность. В случае со спинлокам нас могут за-preemt'ить пока мы его держим, тогда остальные потоки будут курить бамбук в течение долгого времени.

Я не вижу принципиальной разницы с другой ситуацией, когда, например, для некоего ресурса есть менеджер, который обеспечивает изоляцию операций и транзакции, и работает с сообщениями, но у него заполнился буфер незавершенных транзакций. Точно так же все остальные будут стоять и курить бамбук.

MSS>>Недостаток же lock-free — огромная интеллектуальная сложность, причем простейшие решения не годятся как база для более наворочанных.
C>Можно использовать множество готовых решений. Меня вот недавано вот это: http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf просто ошеломило.

Видя слово "reprobing loop" можно дальше не читать.:) То есть, может, какое-то ускорение там есть. Но от принципиальной проблемы, что пока твоя нить думает, что делать с данными, другая в них вмешивается — ты таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и вылезти боком — если у тебя работа более сложная, чем установка лока.

C>>Можно использовать множество готовых решений. Меня вот недавано вот это: http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdf просто ошеломило.

N>Видя слово "reprobing loop" можно дальше не читать. То есть, может, какое-то ускорение там есть. Но от принципиальной проблемы, что пока твоя нить думает, что делать с данными, другая в них вмешивается — ты таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и вылезти боком — если у тебя работа более сложная, чем установка лока.

ты в курсе, что основные задежрки в современных cpu идёт при кеш-промахах? обращение в память стоит порядка 50-100 тактов. типичная операция над хешем — это где-то пара обращений к памяти мимо кеша, не меньше. если залочить отдельноо каждую ячейку (или блок ячеек) хеша и его заголовок, то блокировка на ячейке станет очень маловероятна, а блокировка на заголовке будет идти считанные такты поскольку сам он находится в кеше cpu. я думаю, соотношение времени блокировки может быть порядка 200 тактов на обычном хеше к 10 на необычном

при этом вероятность попасть на блокировку одновременно с другим тредом ждолжна снизиться имхо даже больше чем в 20 раз, но тут моя мысль останавливается а в той статье разве нет никакого анализа?

netch80 wrote:
> C> А еще есть и wait-free алгоритмы, в которых мы гарантировано никогда
> не будем ждать. Кстати, доказано, что *любой* параллельный алгоритм
> можно сделать wait-free. Правда, для многих алгоритмов такая реализация
> потребует слишком больших расходов памяти.
> URL? А то что-то по словам "wait-free algorithms" находится только общая
> вода.
Нашел вот тут:
http://en.wikipedia.org/wiki/Non-blocking_synchronization#Wait-freedom

> C>Ну и самое главное преимущество по сравнению со спинлоками —
> атомарность. В случае со спинлокам нас могут за-preemt'ить пока мы его
> держим, тогда остальные потоки будут курить бамбук в течение долгого
> времени.
> Я не вижу принципиальной разницы с другой ситуацией, когда, например,
> для некоего ресурса есть менеджер, который обеспечивает изоляцию
> операций и транзакции, и работает с сообщениями, но у него заполнился
> буфер незавершенных транзакций. Точно так же все остальные будут стоять
> и курить бамбук.
А как мы в его буффер будем писать? Под блокировкой?

Проблема в том, что если тебя за-preemt'ят пока ты держишь спинлок — то
остальные потоки будут активно продолжать его крутить (офигительные
потери производительности на SMP).

> Видя слово "reprobing loop" можно дальше не читать. То есть, может,
> какое-то ускорение там есть. Но от принципиальной проблемы, что пока
> твоя нить думает, что делать с данными, другая в них вмешивается — ты
> таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и
> вылезти боком — если у тебя работа более сложная, чем установка лока.
Нет, нет и еще раз нет. Пока ты думаешь что делать с данными — ты НЕ
держишь блокировок в lock-free. Другие потоки могут спокойно в него
продолжать писать. То что твоя очередь за время думанья может стать
длиннее экватора Юпитера — это уже другая проблема.

Собственно, та hash map масштабируется до 4 тысяч одновременно пишущих и
читающих процессоров Неплохо, ИМХО.

Здравствуйте, Cyberax, Вы писали:

>> C>Ну и самое главное преимущество по сравнению со спинлоками —
>> атомарность. В случае со спинлокам нас могут за-preemt'ить пока мы его
>> держим, тогда остальные потоки будут курить бамбук в течение долгого
>> времени.
>> Я не вижу принципиальной разницы с другой ситуацией, когда, например,
>> для некоего ресурса есть менеджер, который обеспечивает изоляцию
>> операций и транзакции, и работает с сообщениями, но у него заполнился
>> буфер незавершенных транзакций. Точно так же все остальные будут стоять
>> и курить бамбук.
C>А как мы в его буффер будем писать? Под блокировкой? :)

C>Проблема в том, что если тебя за-preemt'ят пока ты держишь спинлок — то
C>остальные потоки будут активно продолжать его крутить (офигительные
C>потери производительности на SMP).

Блин. Так потому спинлоки в их стандартном виде и не могут использоваться в среде с насильным preemption в принципе! Причём случай пришедшего "сбоку" процесса ещё как-то реален (хоть и с сильной потерей производительности), а если например обработчик прерывания придёт допущенный — всё, система умер). Если может быть вытеснение текущего процесса — используется какой-нибудь вариант с очередями ожидания на объекте исключения.

И какое отношение это имеет к Вашему тезису — не понимаю. Разве что в том, что я не обратил внимания на "крючок" в Вашем тексте про вытеснение процесса со спинлоком и стал возражать тезису целиком, а не на этот крючок. Согласен, не заметил. Но я и не предполагаю столь намеренно диверсионного дизайна.

C>netch80 wrote:
>> C> А еще есть и wait-free алгоритмы, в которых мы гарантировано никогда
>> не будем ждать. Кстати, доказано, что *любой* параллельный алгоритм
>> можно сделать wait-free. Правда, для многих алгоритмов такая реализация
>> потребует слишком больших расходов памяти.
>> URL? А то что-то по словам "wait-free algorithms" находится только общая
>> вода.
C>Нашел вот тут:
C>http://en.wikipedia.org/wiki/Non-blocking_synchronization#Wait-freedom

Ага. Так там есть замечательная цитата по поводу:

However, the resulting performance does not in general match even naive blocking designs. It has also been shown[3] that the widely-available atomic conditional primitives, compare-and-swap and LL/SC, cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads. Wait-free algorithms are therefore rare, both in research and in practice.

То есть перейти на них, конечно, можно, но результат будет ужасен (см. первое предложение). А по дальнейшему — так как вместо CAS и LL/SC ничего пока не придумали — то вообще думать в эту сторону смысла нет.

>> Видя слово "reprobing loop" можно дальше не читать.:) То есть, может,
>> какое-то ускорение там есть. Но от принципиальной проблемы, что пока
>> твоя нить думает, что делать с данными, другая в них вмешивается — ты
>> таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и
>> вылезти боком — если у тебя работа более сложная, чем установка лока.
C>Нет, нет и еще раз нет. Пока ты думаешь что делать с данными — ты НЕ
C>держишь блокировок в lock-free. Другие потоки могут спокойно в него
C>продолжать писать.

А я, по-Вашему, о чём говорю?;)) Да, не держишь блокировок. Именно поэтому, когда ты уже пошёл менять данные так, как тебе нужно — будь готов, что данные к этому времени изменились и замена может обломиться. А тогда — начинать всё сначала — тот самый reprobing loop. Да, и цитата из того же:

Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion.

C> То что твоя очередь за время думанья может стать
C>длиннее экватора Юпитера — это уже другая проблема.

Нет, это не проблема как таковая. Проблема в том, что в случае lock-free получается та же блокировка, но вид сбоку. Потребителю результата (например, автору кода который использует malloc()) обычно совершенно по барабану, как там сделано — мьютекс или lock-free. При одновременном входе с двух процессоров в случае мьютекса один процессор успеет быстрее другого сделать CAS на объект мьютекса, а в случае lock-free — на общие данные, а второй будет или сонно, или решительно, но курить бамбук и уходить на следующий круг. Решительно не вижу, чем второй вариант выгоднее первого для всех случаев. При редких столкновениях за доступ — да, он выгоднее. При частых — скорее наоборот.

C>Собственно, та hash map масштабируется до 4 тысяч одновременно пишущих и
C>читающих процессоров :) Неплохо, ИМХО.

Не сказано, как меряли, в плане разнообразия данных. Если там в качестве ключей брались все строки разные — охотно верю. Если бы было много одинаковых — тормозило бы почище чем на локах.

В остальном — да, симпатичная работа.:)

Здравствуйте, BulatZiganshin, Вы писали:

N>>Видя слово "reprobing loop" можно дальше не читать.:) То есть, может, какое-то ускорение там есть. Но от принципиальной проблемы, что пока твоя нить думает, что делать с данными, другая в них вмешивается — ты таким образом не уйдёшь, а замена лока на операции типа CASA может ещё и вылезти боком — если у тебя работа более сложная, чем установка лока.
BZ>ты в курсе, что основные задежрки в современных cpu идёт при кеш-промахах? обращение в память стоит порядка 50-100 тактов. типичная операция над хешем — это где-то пара обращений к памяти мимо кеша, не меньше. если залочить отдельноо каждую ячейку (или блок ячеек) хеша и его заголовок, то блокировка на ячейке станет очень маловероятна, а блокировка на заголовке будет идти считанные такты поскольку сам он находится в кеше cpu. я думаю, соотношение времени блокировки может быть порядка 200 тактов на обычном хеше к 10 на необычном :)

Блокировка на заголовке — в многопроцессорной системе — не будет "идти считанные такты", потому что требует обязательной записи в память. Write-back поведение кэша здесь недопустимо в принципе. В реализацию общей шины по типу "мы тут сначала кидаем нотификацию, что по адресу XXX чего-то записали, сбросьте его из кэша; а потом уже реально запишем" я слабо верю (хотя сейчас могут и такие появляться... чем чёрт не шутит). А теперь сравним. Считаем по 100 тактов на запись в память, и в сумме 30 тактов на все остальные действия, и что данные уже в кэше (то есть читать обходится очень дёшево). Тогда:
— с мьютексом при удачном занятии с первого раза: 430, ибо 4 записи в память (мьютекс занять, локальные данные записать, центральные данные записать, мьютекс отпустить)
— с мьютексом при задержке от ожидания освобождения другим процессором: 430 + неизвестно_сколько
— lock-free с первой удачной попытки: 230 (локальные данные записать просто так, центральные данные записать через CAS)
— lock-free со второй удачной попытки: 360 (ибо весь алгоритм надо повторить => прибавляем цену всего кроме несостоявшейся записи, ибо CAS обнаружил подмену данных)
— lock-free с третьей удачной попытки: 490
.....
А теперь хохма — вспоминаем мануал по x86 и исправляем, ибо там CAS (в виде CMPXCHG, XADD) не умеет обойтись без записи:
— lock-free на x86 со второй удачной попытки: 460 (просто умножаем на 2)
— lock-free на x86 с третьей удачной попытки: 690
.....

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

BZ>при этом вероятность попасть на блокировку одновременно с другим тредом ждолжна снизиться имхо даже больше чем в 20 раз, но тут моя мысль останавливается :) а в той статье разве нет никакого анализа?

Вероятность попасть и на блокировку, и на перезапуск действия считается примерно одинаково — плотность действий (в герцах;)) умножаем на оценочную длительность действия, а затем полученную "плотность конкуренции" переводим методами теории вероятностей в собственно вероятность (плотность растёт вверх => вероятность асимптотически стремится к 1). В нашем примере lock-free исполняется где-то в два раза быстрее, значит, и вероятность соответственно меньше. Но если внутренняя работа сложнее — они уже могут сравняться.

В случае обсуждаемого хэша именно вероятность попасть в одно действие одновременно с другой нитью, как я понял, очень мала. И всё равно — как видно, среднее улучшение — всё те же два раза. Кстати, при 32 процессорах улучшение там вообще ничтожно.

Для правильной оценки работы ещё надо понять, что это за системы на 384 и 768 процессоров.
UMA? (ой;)) NUMA — с каким методом синхронизации кэшей? Метод тут будет очень существенно влиять.

BZ>>ты в курсе, что основные задежрки в современных cpu идёт при кеш-промахах? обращение в память стоит порядка 50-100 тактов.

N>Блокировка на заголовке — в многопроцессорной системе — не будет "идти считанные такты", потому что требует обязательной записи в память.

оп-па. мы даже о разных системах говорим. я об ~односокетных, ты — о больших. и расчёты в заивсимости от этого маленького обстоятельства оказываются совершенно разными

Здравствуйте, BulatZiganshin, Вы писали:

BZ>>>ты в курсе, что основные задежрки в современных cpu идёт при кеш-промахах? обращение в память стоит порядка 50-100 тактов.

N>>Блокировка на заголовке — в многопроцессорной системе — не будет "идти считанные такты", потому что требует обязательной записи в память.

BZ>оп-па. мы даже о разных системах говорим. я об ~односокетных, ты — о больших. и расчёты в заивсимости от этого маленького обстоятельства оказываются совершенно разными :)

Насколько я понимаю, время записи в память от количества сокетов не зависит. Или имеются в виду процессорные сокеты? Тогда тоже не всё однозначно; да, часто можно включить write-back, но для многоядерных систем с раздельными кэшами это тоже не сработает.

Ну а рассчитывать на однопроцессорные одноядерные системы как на основной вариант сейчас совсем нельзя.

netch80 wrote:
> C>Проблема в том, что если тебя за-preemt'ят пока ты держишь спинлок — то
> C>остальные потоки будут активно продолжать его крутить (офигительные
> C>потери производительности на SMP).
> Блин. Так потому спинлоки в их стандартном виде и не могут
> использоваться в среде с насильным preemption в принципе!
Так ведь используются (см. EnterCriticalSection) В user mode,
например, так вообще нельзя никак запретить preemption твоего потока.

> C>Нашел вот тут:
> C>http://en.wikipedia.org/wiki/Non-blocking_synchronization#Wait-freedom
> Ага. Так там есть замечательная цитата по поводу:
[skip]
> То есть перейти на них, конечно, можно, но результат будет ужасен (см.
> первое предложение). А по дальнейшему — так как вместо CAS и LL/SC
> ничего пока не придумали — то вообще думать в эту сторону смысла нет.
Ну да, в общем случае они действительно не подходят. А в
отдельных частных случаях зато дают огромные преимущества.

> C>Нет, нет и еще раз нет. Пока ты думаешь что делать с данными — ты НЕ
> C>держишь блокировок в lock-free. Другие потоки могут спокойно в него
> C>продолжать писать.
> А я, по-Вашему, о чём говорю?) Да, не держишь блокировок. Именно
> поэтому, когда ты уже пошёл менять данные так, как тебе нужно — будь
> готов, что данные к этому времени изменились и замена может обломиться.
Ээээ... Ты, видимо, не понимаешь сути lock-free. Данные обычно не меняют
(это тупо), обычно меняют контейнеры.

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

> При одновременном входе с двух процессоров в случае мьютекса один
> процессор успеет быстрее другого сделать CAS на объект мьютекса
> а в случае lock-free — на общие
> данные, а второй будет или сонно, или решительно, но курить бамбук и
> уходить на следующий круг.
Проблема в том, что со спинлоком он будет курить бамбук все время,
пока ты делаешь работу. В случае с lock-free он будет курить бамбук
ровно 1 лишний цикл (если другой претендент ровно в этот же момент не
сделает операцию — но это очень маловероятно).

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

> C>Собственно, та hash map масштабируется до 4 тысяч одновременно пишущих и
> C>читающих процессоров Неплохо, ИМХО.
> Не сказано, как меряли, в плане разнообразия данных. Если там в качестве
> ключей брались все строки разные — охотно верю. Если бы было много
> одинаковых — тормозило бы почище чем на локах.
Не тормозило бы

Здравствуйте, Cyberax, Вы писали:

>> Блин. Так потому спинлоки в их стандартном виде и не могут
>> использоваться в среде с насильным preemption в принципе!
C>Так ведь используются (см. EnterCriticalSection) :)

Это не стандартный вид, в котором просто цикл попыток захвата (с модификацией на оптимизацию кэша). Для CRITICAL_SECTION, невозможность получить лок сразу — приводит к вызову уже ядерного ожидания на семафоре CriticalSection->LockSemaphore вызовом NtWaitForSingleObject(). Причём изначально — даже без цикла попыток захвата (может, сейчас оптимизировали? исходники позже NT4 не держал в руках, а лезть отладчиком облом). В терминологии, например, Sun такой объект зовётся "adaptive mutex", и уж никак не "spinlock".

C> В user mode,
C>например, так вообще нельзя никак запретить preemption твоего потока.

В user mode — да. Но тут такими глупостями мало кто занимается. А вот в ядре — сколько угодно. Например, в Linux (образца района 2.4) — spinlock + запрет прерываний (если какой-то обработчик прерывания может лезть к тем же данным) — и достаточно.

А вот для сравнения — FreeBSD SMPng'шная (5-7) — спинлоки использует только для шедулера плюс "нижней" части обработчиков прерываний, только машинно-зависимых действий. Дальнейшая обработка идёт в swi-нитях ядра, у которых задран приоритет, а больше они ничем не отличаются от обычных. И синхронизация там — почти классические мьютексы и местами rwlocks.

C>Ну да, в общем случае они действительно не подходят. А в
C>отдельных частных случаях зато дают огромные преимущества.

Ага. Просто этих отдельных случаев ой как мало...

C>Ээээ... Ты, видимо, не понимаешь сути lock-free.

Зуб даю, начальник, понимаю:)

C> Данные обычно не меняют
C>(это тупо), обычно меняют контейнеры.

Я данными тут называю и всякие указатели в контейнерах. Но ограничиваться контейнерами — таки да, смысла не очень много.

>> При одновременном входе с двух процессоров в случае мьютекса один
>> процессор успеет быстрее другого сделать CAS на объект мьютекса
>> а в случае lock-free — на общие
>> данные, а второй будет или сонно, или решительно, но курить бамбук и
>> уходить на следующий круг.
C>Проблема в том, что со спинлоком он будет курить бамбук все время,
C>пока ты делаешь работу. В случае с lock-free он будет курить бамбук
C>ровно 1 лишний цикл (если другой претендент ровно в этот же момент не
C>сделает операцию — но это очень маловероятно).

C>Поэтому вместо спинлока в highly contended коде нужно ставить мьютексы,
C>которые будут останавливать поток, а не увеличивать энтропию Вселенной зря.

Стоп-стоп. Spinlock vs. mutex — это вопрос не совсем этого самого contented, а скорее вопрос среды, в которой это всё исполняется. На межпроцессорной синхронизации тебе никто мьютекс не даст (слишком дорого делать в железе), там тебе ничего кроме спинлоков не остаётся. Но на такой синхронизации никто и не будет насильно вытеснять (а кто допустил вытеснение — тот просто дурак). А вот спустившись на уровень пользовательских процессов, или даже ядерных процессов, но уже с разрешением вытеснения — наоборот, спинлок становится реальным, но крайне неэффективным. Появляются мьютексы (или в тупой реализации, или поумнее, как с adaptive вариантом), но в любом случае там очередь ожидания и посылание шедулеру сигнала "я сплю, разбуди когда нужно" через соответствующий ядерный запрос.

А lock-free или не lock-free — вопрос именно уровня соревновательности. Если много желающих сделать операцию пришло одновременно — результат получит только один, остальные пойдут на следующий круг. Там тоже один получит результат, остальные будут курить. И так далее... От чрезмерной драки это спасает обычно только недостаточное количество процессоров:) или же максимальное разнесение структур. Если же дофига процессоров и все лезут к одному ресурсу — это получится хуже спинлока.

Кстати, я не понимаю, как обошлись в твоём примере супер-хэша без RCU по отношению к общим структурам хэша.

>> C>Собственно, та hash map масштабируется до 4 тысяч одновременно пишущих и
>> C>читающих процессоров :) Неплохо, ИМХО.
>> Не сказано, как меряли, в плане разнообразия данных. Если там в качестве
>> ключей брались все строки разные — охотно верю. Если бы было много
>> одинаковых — тормозило бы почище чем на локах.
C>Не тормозило бы :)

Уверен? А почему?

Здравствуйте, netch80, Вы писали:

N>Кстати, я не понимаю, как обошлись в твоём примере супер-хэша без RCU по отношению к общим структурам хэша.

Это ж ява! У них же там мусорщик есть!

Здравствуйте, ironwit, Вы писали:

I>Здравствуйте, remark, Вы писали:

R>>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.
R>>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

I>можно ли где то более подробно посмотреть?

http://www.rsdn.ru/Forum/?mid=2414109

Автор: remark
Дата: 21.03.07

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>(сорри за неудачный дубликат, прошу модератора удалить второе такое же сообщение со случайно возникшим огромным оверквотингом, сделал бы сам, да, похоже, тут нет редактирования своих сообщений)
Редактирования нет, а удаление есть — выбери пункт в модерилке "удалить как ошибочное", пока ни одного ответа нет — грохнется.

MSS>Держать лок целый квант (это очень большое вычислительное время) — ужасно.
Это уже другой вопрос..

MSS>В MSDNе — есть, и там convoy effect — это ожидание доступности ресурса под названием thread. Сейчас еще в Википедии гляну.
Была древняя статья Грея на эту тему — "The Convoy Phenomenon", кажется, к сожалению за бабло.. (

Здравствуйте, Maxim S. Shatskih, Вы писали:

MSS>Краткая суть lock-free: активно применяется InterlockedExchangePointer, причем, как я понял, без останова нитей в цикле "крутимся и ждем, пока тут станет не нуль".

Ну почему же так узко! Часть алгоритмов, например, построено исключительно на атомарных сохранениях и загрузках их памяти. Такие алгоритмы исключительно smp/multicore friendly, т.к. по минимум нагружают межпроцессорные соединения и протокол когерентности кэшей. Никакие спин-локи и рядом не стояли.

MSS>Дело в том, что, если позволить такие остановы, то у нас получится spinlock, и, вместо того, чтобы возиться с lock-free, проще будет защитить структуру спинлоком.

Несомненно проще!


MSS>Я даже больше скажу: при низком соревновании за лок lock-free не дает никаких преимуществ по сравнению со спинлоком, ибо реализация в основном одна и та же — interlocked exchange.

MSS>Да, далеко не любой лок требует обращений к диспетчеру ядра. Например, спинлок не требует вовсе, а самый главный лок в ядре виндов под названием FAST_MUTEX и самый главный лок в Win32 под названием CRITICAL_SECTION вырождаются в спинлок при низком соревновании. Для CRITICAL_SECTION вон даже spin count можно задать.

MSS>Так что выигрышей от lock-free — при условии, что используются вот такие умные локи — не так уж и много, разве что при гигантском contention в этом месте, когда умные локи резко тупеют

lock-free алгоритмы гораздо разнообразнее. Они на порядок разнообразнее lock-based алгоритмов. Это часто забывают. Когда ты используешь lock-based подход ты думаешь так: вот есть однопоточная структура, защитим её мьютексом и получим многопоточную. Когда ты используешь lock-free подход ты думаешь так: так, вот эта операция выполняется на порядок чаще остальных, значит я попробую "сместить акцент" на эту операцию и сделаю её без атомарных read-modify-write операций, либо дорогих барьеров памяти, а остальные операции взамен будут выполняться чуть дольше, но это окупиться.
Практически неограниченный простор для вариаций.


MSS>Недостаток же lock-free — огромная интеллектуальная сложность, причем простейшие решения не годятся как база для более наворочанных.

Фактически приходится думать не "Посмотрим, что надо сделать и подберём соотв. средства", а "Посмотрим, какие у нас есть средства, и посмотрим, что мы можем с ними сделать"

Для меня хуже даже не столько сложность, а что некоторых решений вообще НЕТ.

Здравствуйте, BulatZiganshin, Вы писали:

MSS>>Краткая суть lock-free: активно применяется InterlockedExchangePointer, причем, как я понял, без останова нитей в цикле "крутимся и ждем, пока тут станет не нуль".

BZ>иесть ещё пара способов из опыта функциональных языков. первый — это использование иммутабельных структур данных. вместо изменения существующих просто конструируются новые структуры, ес-но это требует GC для сколь-либо удобной работы

Имеется достаточно методик для решения этой проблемы и без сборщика мусора: RCU, SMR, ROP, DRC, VZOOM.



BZ>второй — STM, транзакционный подход к обновлению структур данных: http://research.microsoft.com/%7Esimonpj/papers/stm/

BZ>я точно помню, что STM переносилось на какие-то С-подобные языки, поищи сам

Сейчас нет ни одной пригодной для реального использования реализации STM.
Есть либо научные разработки, либо пыль в глаза от крупных компаний. Больше второе.
Могу огорчить — и ещё долго не будет.

Здравствуйте, netch80, Вы писали:

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

Когда нет подходящего и хорошего Lock-free решения, действительно проще просто взять Lock-based решение.
А как тебе такой вариант. Lock-free алгоритм при выполнении операций вообще не модифицирует разделяемую память. Точнее скажем так — никакие два потока не конкурируют за запись а одну ячейку памяти (кэш-линию), и никакой поток непосредственно сразу не читает данные записанные другим потоком.
Похоже на сказку, да? А такой алгоритм есть. Каждая операция выполняется десяток таков.
Что это за структура данных можете угадать.

Здравствуйте, netch80, Вы писали:

C>>Так ведь используются (см. EnterCriticalSection)
N>Это не стандартный вид, в котором просто цикл попыток захвата (с модификацией на оптимизацию кэша).
Это как раз стандартный спинлок + мьютекс.

В Линуксе есть аналог — http://en.wikipedia.org/wiki/Futex

N>Для CRITICAL_SECTION, невозможность получить лок сразу — приводит к вызову уже ядерного ожидания на семафоре CriticalSection->LockSemaphore вызовом NtWaitForSingleObject(). Причём изначально — даже без цикла попыток захвата (может, сейчас оптимизировали? исходники позже NT4 не держал в руках, а лезть отладчиком облом). В терминологии, например, Sun такой объект зовётся "adaptive mutex", и уж никак не "spinlock".
Нет. Просто мы некоторое время крутим spinlock, а только потом блокируемся на мьютексе. Называется, biased mutex — нам не нужно вызовов в ядро, если лок свободен, но в случае, если он занят — крутим лок.

C>> В user mode,
C>>например, так вообще нельзя никак запретить preemption твоего потока.
N>В user mode — да. Но тут такими глупостями мало кто занимается. А вот в ядре — сколько угодно. Например, в Linux (образца района 2.4) — spinlock + запрет прерываний (если какой-то обработчик прерывания может лезть к тем же данным) — и достаточно.
Ну так в ядре — понятно. Там мы можем preemption легко запретить.

C>>Ну да, в общем случае они действительно не подходят. А в
C>>отдельных частных случаях зато дают огромные преимущества.
N>Ага. Просто этих отдельных случаев ой как мало...
Вполне достаточно, как выясняется. Тут ведь как с компиляторами — реализация очень сложная, но для прикладного программиста эта сложность спрятана.

C>>Ээээ... Ты, видимо, не понимаешь сути lock-free.
N>Зуб даю, начальник, понимаю
Где там мои щипцы...

C>> Данные обычно не меняют (это тупо), обычно меняют контейнеры.
N>Я данными тут называю и всякие указатели в контейнерах. Но ограничиваться контейнерами — таки да, смысла не очень много.
Ну поменяют указатель в контейнере — какие проблемы? Твою копию указателя же никто не собирается менять.

C>>Поэтому вместо спинлока в highly contended коде нужно ставить мьютексы,
C>>которые будут останавливать поток, а не увеличивать энтропию Вселенной зря.
N>Стоп-стоп. Spinlock vs. mutex — это вопрос не совсем этого самого contented, а скорее вопрос среды, в которой это всё исполняется. На межпроцессорной синхронизации тебе никто мьютекс не даст (слишком дорого делать в железе), там тебе ничего кроме спинлоков не остаётся.
N>Но на такой синхронизации никто и не будет насильно вытеснять (а кто допустил вытеснение — тот просто дурак). А вот спустившись на уровень пользовательских процессов, или даже ядерных процессов, но уже с разрешением вытеснения — наоборот, спинлок становится реальным, но крайне неэффективным. Появляются мьютексы (или в тупой реализации, или поумнее, как с adaptive вариантом), но в любом случае там очередь ожидания и посылание шедулеру сигнала "я сплю, разбуди когда нужно" через соответствующий ядерный запрос.
Ну вот, ты сам сказал — основное отличие мьютекса в том, что он является системным объектом, о нем знает ядро и учитывает его состояние при планировании процессов. Спинлок же абсолютно не зависит от ядра.

Естественно, на никзком уровне мьютекс тоже может использовать спинлок.

N>А lock-free или не lock-free — вопрос именно уровня соревновательности. Если много желающих сделать операцию пришло одновременно — результат получит только один, остальные пойдут на следующий круг. Там тоже один получит результат, остальные будут курить. И так далее... От чрезмерной драки это спасает обычно только недостаточное количество процессоров или же максимальное разнесение структур. Если же дофига процессоров и все лезут к одному ресурсу — это получится хуже спинлока.
Нет, нет и нет. В lock-free окно для contention'а — гарантировано только одна атомарная non-preemptible CAS-команда. Это такая его особенность.

Поэтому получить contention на нормальных lock-free-структурах почти нереально — даже в случае с сотней процессоров она пренебрежимо мала.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, netch80, Вы писали:
C>>>Так ведь используются (см. EnterCriticalSection) :)
N>>Это не стандартный вид, в котором просто цикл попыток захвата (с модификацией на оптимизацию кэша).
C>Это как раз стандартный спинлок + мьютекс.

Вот именно, что "+ мьютекс". А не "крутимся до посинения".

N>>Для CRITICAL_SECTION, невозможность получить лок сразу — приводит к вызову уже ядерного ожидания на семафоре CriticalSection->LockSemaphore вызовом NtWaitForSingleObject(). Причём изначально — даже без цикла попыток захвата (может, сейчас оптимизировали? исходники позже NT4 не держал в руках, а лезть отладчиком облом). В терминологии, например, Sun такой объект зовётся "adaptive mutex", и уж никак не "spinlock".
C>Нет. Просто мы некоторое время крутим spinlock, а только потом блокируемся на мьютексе.

1. К чему это "нет"? Я ж сказал — "если невозможно получить лок сразу".
2. Какое "некоторое время"?

Lock1:
   lock inc     dword ptr CsLockCount[edx]  ; ... CriticalSection->LockCount
        jnz     @F
[... скипнул расстановку своих данных в структуру и выход]
@@:
        cmp     CsOwningThread[edx],eax
        jne     @F
        inc     dword ptr CsRecursionCount[edx]
if DBG
        mov     eax,CsDebugInfo[edx]
        inc     dword ptr CsEntryCount[eax]
endif ; DBG
        xor     eax,eax
        stdRET  _RtlEnterCriticalSection

@@:
        stdCall _RtlpWaitForCriticalSection, <edx>

Вижу только одну попытку. Не получилось — "jne @F" и уходим на RtlpWaitForCriticalSection(), которая уже безоговорочно лезет к ядерному локу.

C>Ну вот, ты сам сказал — основное отличие мьютекса в том, что он является системным объектом, о нем знает ядро и учитывает его состояние при планировании процессов. Спинлок же абсолютно не зависит от ядра.
C>Естественно, на никзком уровне мьютекс тоже может использовать спинлок.

И скорее всего использует. Но мы не об этом отличии говорим.

N>>А lock-free или не lock-free — вопрос именно уровня соревновательности. Если много желающих сделать операцию пришло одновременно — результат получит только один, остальные пойдут на следующий круг. Там тоже один получит результат, остальные будут курить. И так далее... От чрезмерной драки это спасает обычно только недостаточное количество процессоров:) или же максимальное разнесение структур. Если же дофига процессоров и все лезут к одному ресурсу — это получится хуже спинлока.
C>Нет, нет и нет. В lock-free окно для contention'а — гарантировано только одна атомарная non-preemptible CAS-команда. Это такая его особенность.

Гонишь, по-моему.
Вот классический учебный пример с добавлением в вершину стека, сделанного на односвязном списке:

void
lf_stack_insert(LIST **headp, LIST *newelem)
{
  LIST *curhead;
  do {
    curhead = *headp; // (1)
    newelem->next = curhead; // (2)
  } while (!atomic_smpset_ptr(headp, curhead, newelem)); // (3)
}

"Окно для contention" здесь — весь цикл. Фактически — от (1) до (3) включительно. Потому что в (1) берётся текущее значение, и именно от этой операции начинается тот участок, на котором постороннее вклинивание приводит к тому, что всю операцию надо перезапускать, начиная от (1), потому что голова списка поменялась — надо и новое значение запомнить для сравнения, и в свой новый элемент его записать.

А если задача посложнее — то и длительность критического участка наверняка будет больше.

Здравствуйте, netch80, Вы писали:

N>>>Для CRITICAL_SECTION, невозможность получить лок сразу — приводит к вызову уже ядерного ожидания на семафоре CriticalSection->LockSemaphore вызовом NtWaitForSingleObject(). Причём изначально — даже без цикла попыток захвата (может, сейчас оптимизировали? исходники позже NT4 не держал в руках, а лезть отладчиком облом). В терминологии, например, Sun такой объект зовётся "adaptive mutex", и уж никак не "spinlock".
C>>Нет. Просто мы некоторое время крутим spinlock, а только потом блокируемся на мьютексе.
N>1. К чему это "нет"? Я ж сказал — "если невозможно получить лок сразу".
N>2. Какое "некоторое время"?
http://msdn2.microsoft.com/en-us/library/ms683476.aspx

N>>>А lock-free или не lock-free — вопрос именно уровня соревновательности. Если много желающих сделать операцию пришло одновременно — результат получит только один, остальные пойдут на следующий круг. Там тоже один получит результат, остальные будут курить. И так далее... От чрезмерной драки это спасает обычно только недостаточное количество процессоров или же максимальное разнесение структур. Если же дофига процессоров и все лезут к одному ресурсу — это получится хуже спинлока.
C>>Нет, нет и нет. В lock-free окно для contention'а — гарантировано только одна атомарная non-preemptible CAS-команда. Это такая его особенность.
N>Гонишь, по-моему.
N>Вот классический учебный пример с добавлением в вершину стека, сделанного на односвязном списке:
Это плохой пример Смотри здесь, например: http://www.cs.bgu.ac.il/~hendlerd/papers/p206-hendler.pdf — почти константная скорость операций, без зависимости от числа потоков.

Здравствуйте, netch80, Вы писали:

N>RCU — это не lock-free. По крайней мере в обычном понимании большинства тех, кто с этим возится. (Да хотя бы из-за лока писателя — от которого она всё равно не избавляет.) Это совершенно отдельная методика, даже если сделана на схожих принципах.

Спорное утверждение.


N>И у неё есть свои недостатки. Необходимость копирования структуры (по крайней мере в реализации линуксового стиля) на каждый второй мелкий чих — приводит к тому, что эти структуры надо держать мелкими, иначе оверхед на копирование станет заметным.

RCU — это методика для read-mostly структур. В жизни это очень большой процент. И тут она рвёт всех.


N>Под lock-free же обычно понимают ситуации, когда можно изменить обстановку атомарными операциями без захвата какого-то лока. Это реализуемо в ряде случаев, но:

N>1. Мало где можно ограничиться самым классическим для lock-free случаем оперирования головой односвязного списка, и аналогичными ситуациями, когда меняется или одно поле, или несколько гарантированно идущих подряд в памяти. Уже с двусвязным списком мы пролетаем на большинстве процессоров. В исключения попадают разве что старшие модели семейства PPC, которые умеют держать не один memory guard для LL/SC, а от двух до четырёх. Вот там можно реализовать неблокирующую замену на ходу в обычном двусвязном списке и, может быть, одновременно ещё где-то.

http://www.cs.chalmers.se/~dcs/ConcurrentDataStructures/phd_chap7.pdf


N>2. Даже при наличии столь продвинутых аппаратных средств часто требуется обеспечить не просто добавление/удаление/замену в списке, а что-то более сложное, при котором постороннее вмешательство посредине полного процесса может быть фатальным. Например, если в процессе одна нить попросила create_thread(), а вторая в это время дёрнула exit(), действия несовместимы.

Не понял.


R>>По поводу простейших случаев. Я уверен, что можно целиком реализовать, например, стек tcp/ip на lock-free структурах.

N>Целиком — 1) не верю. 2) нет смысла. Центральные структуры (например, таблицу маппинга портов в указатели на управляющие структуры соответствующих сокетов, таблицы раутинга, данные iptables) — да, можно и наверняка имеет смысл — если речь про RCU.

Почему нет смысла?
В таких вещах традиционно серьёзное внимание уделяют производительности.



R>>Фактически, единственный недостаток Lock-free — это экстремальная сложность. В остальном это — superior подход.

N>Ну тот же RCU я бы экстремально сложным не назвал. Надо чётко выдерживать методику — это да. Но даже плохо понимая её аккуратно закодировать нужные вызовы — задача для студента.

LOL

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, netch80, Вы писали:

N>>1. К чему это "нет"? Я ж сказал — "если невозможно получить лок сразу".
N>>2. Какое "некоторое время"?
C>http://msdn2.microsoft.com/en-us/library/ms683476.aspx

Значит, по первому пункту возражений нет. Что и требовалось доказать.

C>Это плохой пример :) Смотри здесь, например: http://www.cs.bgu.ac.il/~hendlerd/papers/p206-hendler.pdf — почти константная скорость операций, без зависимости от числа потоков.

Ну, это метода известная. Вот на таких подходах память и жрётся.

Здравствуйте, netch80, Вы писали:

N>>>1. К чему это "нет"? Я ж сказал — "если невозможно получить лок сразу".
N>>>2. Какое "некоторое время"?
C>>http://msdn2.microsoft.com/en-us/library/ms683476.aspx
N>Значит, по первому пункту возражений нет. Что и требовалось доказать.
Да, я редко с крит.секциями работаю

C>>Это плохой пример Смотри здесь, например: http://www.cs.bgu.ac.il/~hendlerd/papers/p206-hendler.pdf — почти константная скорость операций, без зависимости от числа потоков.
N>Ну, это метода известная. Вот на таких подходах память и жрётся.
Совсем не сильно. Причем выигрыш в константной скорости, скорее всего, будет стоить этого.

Здравствуйте, remark, Вы писали:

N>>Ну тот же RCU я бы экстремально сложным не назвал. Надо чётко выдерживать методику — это да. Но даже плохо понимая её аккуратно закодировать нужные вызовы — задача для студента.
R>LOL :)))

Возражения? ;) Если указали место и сказали "копать здесь"?

R>http://www.cs.chalmers.se/~dcs/ConcurrentDataStructures/phd_chap7.pdf

Ух ты. 2004-2005? Немного отстаю от жизни:)

Здравствуйте, netch80, Вы писали:

C>>Это плохой пример Смотри здесь, например: http://www.cs.bgu.ac.il/~hendlerd/papers/p206-hendler.pdf — почти константная скорость операций, без зависимости от числа потоков.

N>Ну, это метода известная. Вот на таких подходах память и жрётся.

Где ж там память жрётся?

Здравствуйте, netch80, Вы писали:

N>Здравствуйте, remark, Вы писали:

N>>>Ну тот же RCU я бы экстремально сложным не назвал. Надо чётко выдерживать методику — это да. Но даже плохо понимая её аккуратно закодировать нужные вызовы — задача для студента.
R>>LOL

N>Возражения? Если указали место и сказали "копать здесь"?

А так же сказали, что здесь же где-то идёт газопровод, захоронение радиоактивных отходов и могильник с сибирской язвой
Это если продолжить аналогию.

А если серьёзно, то этому "студенту" придётся как минимум досконально разбираться в тематике барьеров памяти на всех поддерживаемых архитектурах (если не ошибаюсь, то в списке есть и Alpha). Не хочу никого обидеть, но думаю, что на rsdn таких людей можно пересчитать по пальцам одной руки...

Не могу найти, в сорцах линукса где-то был такой документ типа "Список вопросов, на которые Вы должны свободно отвечать, если пытаетесь делать патч к RCU". Вопросы там такие нормальные были. Представляю студента, отвечающего перед McKenney.

R>>http://www.cs.chalmers.se/~dcs/ConcurrentDataStructures/phd_chap7.pdf

N>Ух ты. 2004-2005? Немного отстаю от жизни

Списки есть, двусвязные списки есть, массивы есть, очереди есть, стеки есть, хэш-спики/отображения есть. По-моему, вообще всё для жизни есть! Чего ещё желать-то?
А некоторые всё говорят о каких-то примитивных случаях.