Dr. Cliff Click: Towards a Scalable Non-Blocking Coding Style

Rapporteur at JavaOne 2008 from Dr. Cliff Click from Azul Systems one of the Best in the world specialist in Super-Scalable(768 and Up cores) Non-Blocking structures for Java.

Author of high-scale-lib (free lib at SourceForge) (lib has BitVector, HashTable and (FIFO-Queue in progress now)).

Dr. Cliff Click talk how by using FSM(Finite State Machine) and atomic-CAS create scalable non-locking structures.

"Classic reader/writer lock chokes w/ >100 CPUs

• Contention on single reader-count word limits scaling"

"• Lock-Free: Each CAS makes progress

• CAS success is local progress

• CAS failure means another CAS succeeded(global progress, local starvation)"

"JDK API mistake: witness turned into a boolean

• Hence failure-for-cause can not be distinguished from spurious-failure"

"Highly scalable (proven scalable to ~1000 CPUs)"

P.S. FSM model for verification maybe interesting for you, Igor?

Материалы по lock-free

Тут в Вики статья "Non-blocking synchronization". Обратите внимание на различия в Wait-freedom, Lock-freedom и Obstruction-freedom.
Тут в Вики часть статьи "Lock" с подзаголовком "The problems with locks".
Тут на русском, тут на английском статья "Введение в неблокирующие алгоритмы". Рассматриваются:
- Неблокирующий счетчик
- Неблокирующий стек Трайбера (Treiber)
- Неблокирующая очередь Майкла-Скотта (Michael-Scott)

P.S. Именно очередь Майкла-Скотта использована в java.util.concurrent.ConcurrentLinkedQueue. Там в javadoc так и написано "This implementation employs an efficient "wait-free" algorithm based on one described in Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.".

Lock-free BlockingStack

Дмитрий Вьюков в комментах спрашивает "А слабо к этому стеку прикрутить блокирующую семантику, что бы pop() на пустом стеке блокировался до появления элемента, и так что бы стек оставался lock-free пока есть элементы?". Отвечаю - не слабо: