Здравствуйте, 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 просто ошеломило.