Изменения
запятые и другие незначительные правки
{{В разработке}}
'''Стек Трайбера''' (англ. ''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'').
== Описание ==
=== Требования к алгоритму ===
Основное отличие стека Трайбера от однопоточного заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Необходимо как-то контролировать процесс взаимодействия потоков. Конечно, это можно было бы сделать , просто блокируя каждую операцию, производимую на стеке. Но такая блокировка не есть хорошо, ведь тем самым мы уменьшаем уменьшает параллелизм, а значит, уменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потокам работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.
=== Lock-free алгоритмы и CAS ===
Свойство неблокируемости (англ. ''Lock-freedom'') гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.
{{Определение
|definition=
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с первым аргументоми, и в случае успеха , записывающая второй аргумент в память.
}}
Ниже представлен псевдокод операции <tex>CAS</tex> для целочисленных переменных.
'''return''' '''true'''
<tex>CAS</tex> используется для реализации таких примитивов синхронизации, как ''mutex'' и ''semaphore''. Это своеобразный базовый "кирпичик" для ''Lock-freedomfree'' алгоритмов, ведь если <tex>CAS</tex> привел к неудачинеудаче, то кто-то другой поток изменил старое значение. Таким образом, прогресс в системе есть. <tex>CAS</tex> реализован на уровне атомарных переменных во многих языках программирования.
== Алгоритм ==
=== Идеи ===
Переходя от требований к конкретной реализации, введем следующие условия:
#Добавлять новый элемент только убедившись, что на момент окончания операции, указатель на голову стека остался тот же. Другими словами, элемент, выбранный нами в качестве <tex>next</tex>, на момент окончания операции все еще актуален.
#При удалении элемента, перед его возвратом, нужно быть уверенным, что мы действительно удаляем текущую голову стека и в качестве новой головы предъявляем <tex>H.next</tex>.
=== Структура стека ===
Как всегда , каждый элемент стека содержит информацию о хранимом значении (<tex>value</tex>) и указатель на следующий элемент (<tex>next</tex>). Также имеем указатель на голову стека <tex>H</tex>, который будем изменять при помощи операции <tex>CAS</tex>. Если при этом голова указывает на <tex>null</tex>, то стек — пуст.
=== Удаление элементов ===
