Изменения

'''Стек Трайбера''' (англ. ''(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 free алгоритмы и CAS ===Для многопоточного алгоритма недостаточно требовать лишь взаимное исключениеСвойство неблокируемости (англ. Другое важное свойство — неблокируемость. Свойство ''Lock-freedom'' ) гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.

'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументовпервым аргументом и, и в случае успеха , записывающая второй аргумент в память.

Ниже представлен псевдокод операции <tex>CAS</tex>для целочисленных переменных.  '''fun ''' cas('''int*''' p, '''int''' old, '''int''' new): '''bool {''' '''if ''' *p ≠ != old { '''return ''' '''false }''' *p ← = new '''return ''' '''true''' }<tex>CAS</tex> используется для реализации таких примитивов синхронизации, как ''mutex'' и ''semaphore''. Это своеобразный базовый "кирпичик" для ''Lock-freedomfree'' алгоритмов, ведь если <tex>CAS</tex> привел к неудачинеудаче, то кто-то другой поток изменил старое значение. Таким образом, прогресс в системе есть. <tex>CAS</tex> реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и Cпрограммирования.

Как всегда , каждый элемент стека содержит информацию о хранимом значении (<tex>value</tex>) и указатель на следующий элемент(<tex>next</tex>). Также имеем указатель на голову стека <tex>H</tex>, который будем изменять при помощи операции <tex>CAS</tex>. Если при этом голова указывает на <tex>H==null</tex>, то стек — пуст.