Викиконспекты - Вклад участника [ru]

Стек Трайбера

2018-10-01T07:44:56Z

217.66.156.58: /* Lock-freedom алгоритмы и CAS */

{{В разработке}}
'''Стек Трайбера''' ''(Treiber Stack)'' — масштабируеммый ''lock-free'' стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber<ref>[http://domino.research.ibm.com/library/cyberdig.nsf/0/58319a2ed2b1078985257003004617ef?OpenDocument R. Kent Treiber {{---}} Systems Programming: Coping with Parallelism, 1968]</ref>. Алгоритм использует примитив <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('''int*''' p, '''int''' old, '''int''' 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>. Попробуем переместить <tex>H</tex> на новый элемент, при помощи <tex>CAS</tex>. Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.

== Псевдокод ==
'''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'''

==Примечания==

<references />
== Источники информации==
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]
* [https://en.wikipedia.org/wiki/Compare-and-swap Wikipedia {{---}} CAS]

[[Категория: Параллельное программирование]]

Стек Трайбера

2018-10-01T07:33:01Z

217.66.156.58: /* Псевдокод */

{{В разработке}}
'''Стек Трайбера''' ''(Treiber Stack)'' — масштабируеммый ''lock-free'' стек. Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber<ref>[http://domino.research.ibm.com/library/cyberdig.nsf/0/58319a2ed2b1078985257003004617ef?OpenDocument R. Kent Treiber {{---}} Systems Programming: Coping with Parallelism, 1968]</ref>. Алгоритм использует примитив <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>. Попробуем переместить <tex>H</tex> на новый элемент, при помощи <tex>CAS</tex>. Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.

== Псевдокод ==
'''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'''

==Примечания==

<references />
== Источники информации==
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]
* [https://en.wikipedia.org/wiki/Compare-and-swap Wikipedia {{---}} CAS]

[[Категория: Параллельное программирование]]