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? Немного отстаю от жизни

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