Стек Трайбера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 6 участников)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
'''Стек Трайбера''' ''(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-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-free алгоритмы и CAS ===
#При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.
+
Свойство неблокируемости (англ. ''Lock-freedom'') гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.
=== Lock-freedom алгоритмы и CAS ===
 
Для многопоточного алгоритма недостаточно требовать лишь взаимное исключение. Другое важное свойство — неблокируемость. Свойство ''Lock-freedom'' гарантирует прогресс в системе. Для его реализации используется операция <tex>CAS</tex>.
 
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с одним из аргументов, и в случае успеха записывающая второй аргумент в память.
+
'''Сравнение с обменом''' (англ. ''compare and set, compare and swap, CAS'') — атомарная инструкция, сравнивающая значение в памяти с первым аргументом и, в случае успеха, записывающая второй аргумент в память.
 
}}
 
}}
Ниже представлен псевдокод операции <tex>CAS</tex>.
+
Ниже представлен псевдокод операции <tex>CAS</tex> для целочисленных переменных.
  fun cas(p, old, new): bool {
+
 
     if *p old {
+
  '''fun''' cas('''int*''' p, '''int''' old, '''int''' new): '''bool'''
         return false
+
     '''if''' *p != old  
    }
+
         '''return''' '''false'''
     *p new
+
     *p = new
     return true
+
     '''return''' '''true'''
}
+
 
<tex>CAS</tex>  используется для реализации таких примитивов синхронизации, как ''mutex'' и ''semaphore''. Это своеобразный базовый "кирпичик" для ''Lock-freedom'' алгоритмов, ведь если <tex>CAS</tex> привел к неудачи, то кто-то другой изменил старое значение. Таким образом, прогресс в системе есть. <tex>CAS</tex> реализован на уровне атомарных переменных во многих языках программирование, в том числе Java и C.
+
<tex>CAS</tex>  используется для реализации таких примитивов синхронизации, как ''mutex'' и ''semaphore''. Это своеобразный базовый "кирпичик" для ''Lock-free'' алгоритмов, ведь если <tex>CAS</tex> привел к неудаче, то другой поток изменил старое значение. <tex>CAS</tex> реализован на уровне атомарных переменных во многих языках программирования.
  
 
== Алгоритм ==  
 
== Алгоритм ==  
 +
 +
=== Идеи ===
 +
Переходя от требований к конкретной реализации, введем следующие условия:
 +
#Добавлять новый элемент только убедившись, что на момент окончания операции, указатель на голову стека остался тот же. Другими словами, элемент, выбранный нами в качестве <tex>next</tex>, на момент окончания операции все еще актуален.
 +
#При удалении элемента, перед его возвратом, нужно быть уверенным, что мы действительно удаляем текущую голову стека и в качестве новой головы предъявляем <tex>H.next</tex>.
 +
 
=== Структура стека ===
 
=== Структура стека ===
Как всегда каждый элемент стека содержит информацию о хранимом значении и указатель на следующий элемент. Также имеем указатель на голову стека <tex>H</tex>, который будем изменять при помощи операции <tex>CAS</tex>. Если <tex>H==null</tex>, то стек — пуст.
+
Как всегда, каждый элемент стека содержит информацию о хранимом значении (<tex>value</tex>) и указатель на следующий элемент (<tex>next</tex>). Также имеем указатель на голову стека <tex>H</tex>, который будем изменять при помощи операции <tex>CAS</tex>. Если при этом голова указывает на <tex>null</tex>, то стек — пуст.
 +
 
 
=== Удаление элементов ===
 
=== Удаление элементов ===
 
Запомним, на что указывает голова стека (запишем в локальную переменную <tex>head</tex>). Значение, которое хранит в себе <tex>head</tex>, — то, что необходимо будет вернуть. Попробуем переместить голову стеком <tex>CAS</tex>ом. Если удалось — вернем <tex>head.value</tex>. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
 
Запомним, на что указывает голова стека (запишем в локальную переменную <tex>head</tex>). Значение, которое хранит в себе <tex>head</tex>, — то, что необходимо будет вернуть. Попробуем переместить голову стеком <tex>CAS</tex>ом. Если удалось — вернем <tex>head.value</tex>. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.
Строка 32: Строка 37:
  
 
== Псевдокод ==
 
== Псевдокод ==
  fun '''pop'''(): Int {
+
  '''fun''' pop(): '''Int'''
     while (true) { <font color=green>//Cas loop</font>
+
     '''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) {
+
  '''fun''' push(x: '''Int''')
     while (true) { <font color=green>//Cas loop</font>
+
     '''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'''
    }
+
 
}
 
 
==Примечания==
 
==Примечания==
  
 
<references />
 
<references />
 +
 +
==См. также==
 +
* [[Алгоритмы_взаимного_исключения]]
 +
 
== Источники информации==
 
== Источники информации==
 
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]
 
* [https://en.wikipedia.org/wiki/Treiber_Stack Wikipedia Treiber {{---}} Stack]

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

Эта статья находится в разработке!

Стек Трайбера (англ. Treiber Stack) — масштабируеммый стек без блокировок (англ. lock-free). Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber[1]. Алгоритм использует примитив [math]CAS[/math] (compare and set).

Описание

Требования к алгоритму

Основное отличие стека Трайбера от однопоточного заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы. Необходимо как-то контролировать процесс взаимодействия потоков. Конечно, это можно было бы сделать, просто блокируя каждую операцию, производимую на стеке. Но такая блокировка уменьшает параллелизм, а значит, уменьшаем масштабируемость программы. Уходя от данной стратегии, разрешим потокам работать одновременно со стеком и потребуем от алгоритма условие неблокируемости.

Lock-free алгоритмы и CAS

Свойство неблокируемости (англ. Lock-freedom) гарантирует прогресс в системе. Для его реализации используется операция [math]CAS[/math].

Определение:
Сравнение с обменом (англ. compare and set, compare and swap, CAS) — атомарная инструкция, сравнивающая значение в памяти с первым аргументом и, в случае успеха, записывающая второй аргумент в память.

Ниже представлен псевдокод операции [math]CAS[/math] для целочисленных переменных.

fun cas(int* p, int old, int new): bool
    if *p != old 
        return false
    *p = new
    return true

[math]CAS[/math] используется для реализации таких примитивов синхронизации, как mutex и semaphore. Это своеобразный базовый "кирпичик" для Lock-free алгоритмов, ведь если [math]CAS[/math] привел к неудаче, то другой поток изменил старое значение. [math]CAS[/math] реализован на уровне атомарных переменных во многих языках программирования.

Алгоритм

Идеи

Переходя от требований к конкретной реализации, введем следующие условия:

  1. Добавлять новый элемент только убедившись, что на момент окончания операции, указатель на голову стека остался тот же. Другими словами, элемент, выбранный нами в качестве [math]next[/math], на момент окончания операции все еще актуален.
  2. При удалении элемента, перед его возвратом, нужно быть уверенным, что мы действительно удаляем текущую голову стека и в качестве новой головы предъявляем [math]H.next[/math].

Структура стека

Как всегда, каждый элемент стека содержит информацию о хранимом значении ([math]value[/math]) и указатель на следующий элемент ([math]next[/math]). Также имеем указатель на голову стека [math]H[/math], который будем изменять при помощи операции [math]CAS[/math]. Если при этом голова указывает на [math]null[/math], то стек — пуст.

Удаление элементов

Запомним, на что указывает голова стека (запишем в локальную переменную [math]head[/math]). Значение, которое хранит в себе [math]head[/math], — то, что необходимо будет вернуть. Попробуем переместить голову стеком [math]CAS[/math]ом. Если удалось — вернем [math]head.value[/math]. Если нет, то это означает, что с момента начала операции стек был изменен. Поэтому попробуем проделать операцию заново.

Добавление элементов

Запомним, куда указывает голова стека (запишем в локальную переменную [math]head[/math]). Создадим новый элемент, который хотим добавить в начало стека. Указатель на следующее значение для него — [math]head[/math]. Попробуем переместить [math]H[/math] на новый элемент, при помощи [math]CAS[/math]. Если это удалось — добавление прошло успешно. Если нет, то кто-то другой изменил стек, пока мы пытались добавить элемент. Придется начинать сначала.

Псевдокод

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

Примечания

См. также

Источники информации