16
правок
Изменения
Создание статьи Treiber stack
{{В разработке}}
Treiber Stack - масштабируеммый lock-free стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber в статье "Systems Programming: Coping with Parallelism", 1986. Алгоритм использует примитив CAS (compare and set).
== Описание ==
=== Идея ===
Основное отличие Treiber stack от однопоточного случая, заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы независимо. Поэтому хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:
1. Добавлять новый элемент только если уверены, что добавляемый элемент - единственный с момента начала операции.
2. При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
=== Lock-freedom алгоритмы и CAS ===
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Важное свойство - неблокируемость. Свойство Lock-freedom гарантирует прогресс в системе. Для его реализации используется операция CAS.
{{Определение
|definition=
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память.
}}
Ниже представлен псевдокод операции CAS.
fun cas(p, old, new): bool {
if *p ≠ old {
return false
}
*p ← new
return true
}
CAS операция используется для реализации таких примитивов синхронизации, как mutex и semaphore. Это своебразный базовый кирпичик для Lock-freedom алгоритмов, ведь если CAS привел к неудачи, то кто-то другой изменил старое значение. Таким образом, прогресс в системе есть. CAS реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и C.
== Алгоритм ==
=== Структура стека ===
Как всегда каждый элемент стека содержит информацию о хранимом значении и указатель на следующий элемент. Также имеем указатель на голову стека H, который будем изменять при помощи операции CAS. Если H==NULL, то стек - пуст.
=== Удаление элементов ===
Запомним, на что указывает голова стека (head). Значение, которое хранит в себе head - то, что необходимо будет вернуть. Попробуем переместить голову стеком CASом. Если удалось - вернем head.value. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
=== Добавление элементов ===
Запомним, куда указывает голова стека (head). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него - head. Попробуем переместить H на новый элемент, при помощи CAS. Если это удалось - добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.
== Псевдокод ==
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
newHead = Node {value: x, next: head}
if (CAS (&H, head, newHead))
return
}
}
== Источники ==
* [https://en.wikipedia.org/wiki/Treiber_Stack Treiber Stack]
* [https://en.wikipedia.org/wiki/Compare-and-swap CAS]
[[Категория: Параллельное программирование]]
Treiber Stack - масштабируеммый lock-free стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber в статье "Systems Programming: Coping with Parallelism", 1986. Алгоритм использует примитив CAS (compare and set).
== Описание ==
=== Идея ===
Основное отличие Treiber stack от однопоточного случая, заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы независимо. Поэтому хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:
1. Добавлять новый элемент только если уверены, что добавляемый элемент - единственный с момента начала операции.
2. При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
=== Lock-freedom алгоритмы и CAS ===
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Важное свойство - неблокируемость. Свойство Lock-freedom гарантирует прогресс в системе. Для его реализации используется операция CAS.
{{Определение
|definition=
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память.
}}
Ниже представлен псевдокод операции CAS.
fun cas(p, old, new): bool {
if *p ≠ old {
return false
}
*p ← new
return true
}
CAS операция используется для реализации таких примитивов синхронизации, как mutex и semaphore. Это своебразный базовый кирпичик для Lock-freedom алгоритмов, ведь если CAS привел к неудачи, то кто-то другой изменил старое значение. Таким образом, прогресс в системе есть. CAS реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и C.
== Алгоритм ==
=== Структура стека ===
Как всегда каждый элемент стека содержит информацию о хранимом значении и указатель на следующий элемент. Также имеем указатель на голову стека H, который будем изменять при помощи операции CAS. Если H==NULL, то стек - пуст.
=== Удаление элементов ===
Запомним, на что указывает голова стека (head). Значение, которое хранит в себе head - то, что необходимо будет вернуть. Попробуем переместить голову стеком CASом. Если удалось - вернем head.value. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
=== Добавление элементов ===
Запомним, куда указывает голова стека (head). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него - head. Попробуем переместить H на новый элемент, при помощи CAS. Если это удалось - добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.
== Псевдокод ==
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
newHead = Node {value: x, next: head}
if (CAS (&H, head, newHead))
return
}
}
== Источники ==
* [https://en.wikipedia.org/wiki/Treiber_Stack Treiber Stack]
* [https://en.wikipedia.org/wiki/Compare-and-swap CAS]
[[Категория: Параллельное программирование]]
