16
правок
Изменения
Нет описания правки
{{В разработке}}
Treiber Stack - масштабируеммый lock-free стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber в статье "Systems Programming: Coping with Parallelism", 1986. Алгоритм использует примитив <tex>CAS </tex> ''(compare and set)''.
== Описание ==
=== Идея ===
Основное отличие Treiber stack от однопоточного случая, заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы независимо. Поэтому хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:
=== Lock-freedom алгоритмы и CAS ===
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Важное свойство - неблокируемость. Свойство Lock-freedom гарантирует прогресс в системе. Для его реализации используется операция CAS.
