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