Здравствуйте, 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>Не тормозило бы :)
