Treiber stack — различия между версиями

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

Текущая версия на 19:15, 4 сентября 2022