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 тысяч одновременно пишущих и
читающих процессоров Неплохо, ИМХО.