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

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

Стек Трайбера (англ. Treiber Stack) — масштабируеммый стек без блокировок (англ. lock-free). Считается, что впервые данный алгоритм был опубликовал R. Kent Treiber. Алгоритм использует примитив [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

См. также

• Алгоритмы_взаимного_исключения

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

• Wikipedia Treiber — Stack
• Wikipedia — CAS