Стек Трайбера — различия между версиями
Kisik (обсуждение | вклад) |
(→Псевдокод) |
||
| Строка 32: | Строка 32: | ||
== Псевдокод == | == Псевдокод == | ||
| − | + | '''fun''' pop(): '''Int''' | |
| − | while (true) | + | '''while''' ('''true''') <font color=green>//Cas loop</font> |
head = H | head = H | ||
| − | if (CAS (&H, head, head.next)) | + | '''if''' (CAS (&H, head, head.next)) |
| − | return head.value | + | '''return''' head.value |
| − | + | ||
| − | + | ||
| − | + | '''fun''' push(x: '''Int''') | |
| − | while (true) | + | '''while''' ('''true''') <font color=green>//Cas loop</font> |
head = H | head = H | ||
| − | if (head == null) | + | '''if''' (head == null) |
| − | throw new EmptyStackException(); | + | '''throw''' new EmptyStackException(); |
newHead = Node {value: x, next: head} | newHead = Node {value: x, next: head} | ||
| − | if (CAS (&H, head, newHead)) | + | '''if''' (CAS (&H, head, newHead)) |
| − | return | + | '''return''' |
| − | + | ||
| − | |||
==Примечания== | ==Примечания== | ||
Версия 10:33, 1 октября 2018
Стек Трайбера (Treiber Stack) — масштабируеммый lock-free стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber[1]. Алгоритм использует примитив (compare and set).
Содержание
Описание
Идея
Основное отличие Treiber stack от однопоточного случая заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Чтобы не получилась каша, хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:
- Добавлять новый элемент только если уверены, что добавляемый элемент — единственный с момента начала операции.
- При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
Lock-freedom алгоритмы и CAS
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Другое важное свойство — неблокируемость. Свойство Lock-freedom гарантирует прогресс в системе. Для его реализации используется операция .
| Определение: |
| Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память. |
Ниже представлен псевдокод операции .
fun cas(p, old, new): bool {
if *p ≠ old {
return false
}
*p ← new
return true
}
используется для реализации таких примитивов синхронизации, как mutex и semaphore. Это своеобразный базовый "кирпичик" для Lock-freedom алгоритмов, ведь если привел к неудачи, то кто-то другой изменил старое значение. Таким образом, прогресс в системе есть. реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и C.
Алгоритм
Структура стека
Как всегда каждый элемент стека содержит информацию о хранимом значении и указатель на следующий элемент. Также имеем указатель на голову стека , который будем изменять при помощи операции . Если , то стек — пуст.
Удаление элементов
Запомним, на что указывает голова стека (запишем в локальную переменную ). Значение, которое хранит в себе , — то, что необходимо будет вернуть. Попробуем переместить голову стеком ом. Если удалось — вернем . Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
Добавление элементов
Запомним, куда указывает голова стека (запишем в локальную переменную ). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него — . Попробуем переместить на новый элемент, при помощи . Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.
Псевдокод
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
