16
правок
Изменения
Нет описания правки
{{В разработке}}
'''Стек Трайбера''' ''(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", 19861968]</ref>. Алгоритм использует примитив <tex>CAS</tex> ''(compare and set)''.
== Описание ==
=== Идея ===
Основное отличие Treiber stack от однопоточного случая, заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы независимо. Поэтому Чтобы не получилась каша, хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:
#Добавлять новый элемент только если уверены, что добавляемый элемент — единственный с момента начала операции.
#При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
}
}
==Примечания==
<references />== Источники информации==
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]
* [https://en.wikipedia.org/wiki/Compare-and-swap Wikipedia {{---}} CAS]
[[Категория: Параллельное программирование]]
