В java.util.concurrent.atomic.AtomicXXX есть волшебный метод weakCompareAndSet, который отличается от оригинального
compareAndSet двумя моментами:
1) может
spuriously fail "The weak version may be more efficient in the normal case, but differs in that any given invocation of weakCompareAndSetmethod may fail, even spuriously (that is, for no apparent reason)."
2) не устанавливает happend-before отношение "weakCompareAndSet atomically reads and conditionally writes a variable, is ordered with respect to other memory operations on that variable, but otherwise acts as an ordinary non-volatile memory operation."
---
Для такого поведения (второй пункт) найдено пока два Use Case:
A) счетчики
B) Michael-Scott queues (надо попробовать реализовать)
P.S. Как понимаю, j.u.c.ConcurrentLinkedQueue реализовано на основе Michael-Scott queue, но использует "strong" CAS.
В алгоритме Майкла-Скотта CAS используется в различных местах. Например, СAS tail после добавления элемента (строка 226 здесь: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/ConcurrentLinkedQueue.java#226) используется только для оптимизации (не является точкой линеаризации алгоритма, не влияет на корректность алгоритма) и там можно было бы действительно использовать слабую версию. Другое дело, что на платформе x86 просто нет универсальных операций, позволяющих реализовать weakCAS, так чтобы он не был сильным. Там он реализовал просто как обычный "сильный" СMPXCHG.
ОтветитьУдалитьНа практике, weakCAS можно реализовать эффективней чем CAS только на платформах где есть примитив LL/SC: http://en.wikipedia.org/wiki/Load-link/store-conditional
Даст ли это заметный прирост производительность -- надо замерять.
Первый пункт довольно интерестный. Fail подразумевает что метод вернет false, но последующие вызовы eventually вернут true?
ОтветитьУдалить>> последующие вызовы eventually вернут true?
ОтветитьУдалитьМатематически, я полагаю, eventually == для каждого запуска программы можно указать такой промежуток времени, что после него все "произойдет". Т.е. время "события" неограниченно сверху для всех возможных запусков, но конечно в каждом конкретном запуске. Т.е. свойство wait-free - "guaranteed per-thread progress". Все же атомарные операции предполагают wait-free - "guaranteed system-wide progress". Т.е. какой-то другой поток может неограниченное количество раз "выигрывать" у моего потока (не знаю, происходит ли такое на реальных процессорах).
В принципе, как я понял, на некоторых процах weakCAS может fail, если кто-то писал в ту же кэш-линию (а в нашу переменную не писал). Т.е. из-за "false sharing" не гарантирует даже lock-free.
P.S. В целом я с Вашим утверждение согласен, но, по моим представлениям, eventualy надо заменить на что-то более слабое, именно "may spuriously fail" без всяких гарантий на будущее.