Изменения
Нет описания правки
'''Стек Трайбера''' ''(Treiber Stack)'' — масштабируеммый ''lock-free'' стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber<ref>[http://domino.research.ibm.com/library/cyberdig.nsf/0/58319a2ed2b1078985257003004617ef?OpenDocument R. Kent Treiber {{---}} Systems Programming: Coping with Parallelism, 1968]</ref>. Алгоритм использует примитив <tex>CAS</tex> ''(compare and set)''.
== Описание ==
=== Идея Требования к алгоритму ===Основное отличие Treiber stack от однопоточного случая заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Чтобы не получилась каша, хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:#Добавлять новый элемент только если увереныКонечно, это можно было бы сделать просто блокируя каждую операцию, что добавляемый элемент — единственный с момента начала операциипроизводимую на стеке.#При удалении элементаНо такая блокировка не есть хорошо, перед его возвратомведь тем самым мы уменьшаем параллелизм, нужно быть уверенныма значит,что никакой другой поток не добавил новый элемент в стек с начала операцииуменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потоком работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.
=== Lock-freedom алгоритмы и CAS ===
{{Определение
|definition=
== Алгоритм ==
=== Идеи ===
Переходя от требований к конкретной реализации, введем следующие условия:
#Добавлять новый элемент только если уверены, что добавляемый элемент — единственный с момента начала операции.
#При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
=== Структура стека ===
Как всегда каждый элемент стека содержит информацию о хранимом значении и указатель на следующий элемент. Также имеем указатель на голову стека <tex>H</tex>, который будем изменять при помощи операции <tex>CAS</tex>. Если при этом голова указывает на <tex>null</tex>, то стек — пуст.
<references />
==См. также==
* [[Алгоритмы_взаимного_исключения]]
== Источники информации==
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]
