Стек Трайбера
Стек Трайбера (англ. Treiber Stack) — масштабируеммый стек без блокировок (англ. lock-free). Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber[1]. Алгоритм использует примитив (compare and set).
Описание
Требования к алгоритму
Основное отличие стека Трайбера от однопоточного заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Необходимо как-то контролировать процесс взаимодействия потоков. Конечно, это можно было бы сделать, просто блокируя каждую операцию, производимую на стеке. Но такая блокировка уменьшает параллелизм, а значит, уменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потокам работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.
Lock-free алгоритмы и CAS
Свойство неблокируемости (англ. Lock-freedom) гарантирует прогресс в системе. Для его реализации используется операция .
| Определение: |
| Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с первым аргументом и, в случае успеха, записывающая второй аргумент в память. |
Ниже представлен псевдокод операции для целочисленных переменных.
fun cas(int* p, int old, int new): bool
if *p != old
return false
*p = new
return true
используется для реализации таких примитивов синхронизации, как mutex и semaphore. Это своеобразный базовый "кирпичик" для Lock-free алгоритмов, ведь если привел к неудаче, то другой поток изменил старое значение. реализован на уровне атомарных переменных во многих языках программирования.
Алгоритм
Идеи
Переходя от требований к конкретной реализации, введем следующие условия:
- Добавлять новый элемент только убедившись, что на момент окончания операции, указатель на голову стека остался тот же. Другими словами, элемент, выбранный нами в качестве , на момент окончания операции все еще актуален.
- При удалении элемента, перед его возвратом, нужно быть уверенным, что мы действительно удаляем текущую голову стека и в качестве новой головы предъявляем .
Структура стека
Как всегда, каждый элемент стека содержит информацию о хранимом значении () и указатель на следующий элемент (). Также имеем указатель на голову стека , который будем изменять при помощи операции . Если при этом голова указывает на , то стек — пуст.
Удаление элементов
Запомним, на что указывает голова стека (запишем в локальную переменную ). Значение, которое хранит в себе , — то, что необходимо будет вернуть. Попробуем переместить голову стеком ом. Если удалось — вернем . Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
Добавление элементов
Запомним, куда указывает голова стека (запишем в локальную переменную ). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него — . Попробуем переместить на новый элемент, при помощи . Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.
Псевдокод
fun pop(): Int
while (true) //Cas loop
head = H
if (CAS (&H, head, head.next))
return head.value
fun push(x: Int)
while (true) //Cas loop
head = H
if (head == null)
throw new EmptyStackException();
newHead = Node {value: x, next: head}
if (CAS (&H, head, newHead))
return
