Стек Трайбера (англ. Treiber Stack) — масштабируеммый стек без блокировок (англ. lock-free). Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber. Алгоритм использует примитив CAS (compare and swap).
Основное отличие стека Трайбера от однопоточного заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Необходимо как-то контролировать процесс взаимодействия потоков. Конечно, это можно было бы сделать, просто блокируя каждую операцию, производимую на стеке. Но такая блокировка уменьшает параллелизм, а значит, уменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потокам работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.
Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с первым аргументом и, в случае успеха, записывающая второй аргумент в память.
Ниже представлен псевдокод операции CAS для целочисленных переменных
fun cas(int* p, int old, int new): bool
if *p != old
return false
*p = new
return true
Запомним, на что указывает голова стека (запишем в локальную переменную head). Значение, которое хранит в себе head, — то, что необходимо будет вернуть. Попробуем переместить голову стеком CASом. Если удалось — вернем head.value. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
Запомним, куда указывает голова стека (запишем в локальную переменную head). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него — head. Попробуем переместить H на новый элемент, при помощи CAS. Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.