Lock-free структуры
Last updated
Last updated
Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором принят отказ от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки.
Преимущество неблокирующих алгоритмов — в лучшей масштабируемости по количеству процессоров. К тому же, если ОС прервёт один из потоков фоновой задачей, остальные, как минимум, выполнят свою работу, не простаивая. По максимуму — возьмут невыполненную работу на себя.
В Библиотеки Gee присутствуют неблокирующие структуры:
Односвязный список. Эта реализация основана на статье Михаила Фомичева и Эрика Рупперта.
Список с пропусками (Skip list). Эта реализация основана на магистерской диссертации Михаила Фомичева.