Lock-free структуры

Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором принят отказ от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки.

Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные, как минимум, выполнят свою работу, не простаивая. По максимуму — возьмут невыполненную работу на себя.

В Библиотеки Gee присутствуют неблокирующие структуры:

ConcurrentList

Односвязный список. Эта реализация основана на статье Михаила Фомичева и Эрика Рупперта.

ConcurrentSet

Список с пропусками (Skip list). Эта реализация основана на магистерской диссертации Михаила Фомичева.