Treiber stack

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

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

Описание

Идея

Основное отличие Treiber stack от однопоточного случая, заключается в том, что несколько потоков имеют доступ к данным в стеке одновременно, а значит, могут удалять и добавлять элементы независимо. Поэтому хотелось бы как-то контролировать процесс взаимодействия потоков. Для этого введем следующие условия:

1. Добавлять новый элемент только если уверены, что добавляемый элемент — единственный с момента начала операции.
2. При удалении элемента, перед его возвратом, нужно быть уверенным,что никакой другой поток не добавил новый элемент в стек с начала операции.

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

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

Определение:

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

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

fun cas(p, old, new): bool {
    if *p ≠ old {
        return false
    }
    *p ← new
    return true
}

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

Алгоритм

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

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

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

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

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

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

Источники

• Treiber Stack
• CAS