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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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




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

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


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

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

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

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

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

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-е кажется был пример по борьбе с конвоем...

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 — огромная интеллектуальная сложность, причем простейшие решения не годятся как база для более наворочанных.

Здравствуйте, 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 — с каким методом синхронизации кэшей? Метод тут будет очень существенно влиять.