Стек драйверов

Алгоритм стека Трейбера без блокировок, представляет собой масштабируемый стек использующий мелкозернистый примитив параллельного выполнения сравнения и обмена . Считается, что Р. Кент Трайбер был первым, кто опубликовал его в своей статье 1986 года «Системное программирование: борьба с параллелизмом».

Основной принцип

Основной принцип алгоритма заключается в том, чтобы добавлять что-то новое в стек только в том случае, если вы знаете, что элемент, который вы пытаетесь добавить, является единственным, что было добавлено с момента начала операции. Это делается с помощью сравнения и замены. Помещение элемента в стек осуществляется путем взятия верхней части стека (старой головы) и помещения ее после нового элемента, чтобы создать новую голову. Затем вы сравниваете старую голову с нынешней. Если они совпадают, вы можете поменять старую головку на новую, если нет, то это означает, что другой поток добавил элемент в стек, и в этом случае вам придется повторить попытку.

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

Корректность

В некоторых языках, особенно в тех, в которых нет сборки мусора, стек Трейбера может подвергаться риску возникновения проблемы ABA . Когда процесс собирается удалить элемент из стек (непосредственно перед сравнением и установкой в ​​процедуре извлечения ниже) другой процесс может изменить стек так, что голова останется той же, но второй элемент будет другой. Сравнение и замена установят начало стека на старый второй элемент стека, что приведет к смешиванию всей структуры данных. Однако версия Java на этой странице не подвержена этой проблеме из-за более строгих гарантий, предлагаемых средой выполнения Java (невозможно, чтобы вновь созданная ссылка на объект без псевдонимов была равна ссылке на любой другой достижимый объект).

Тестирование на такие сбои, как ABA, может быть чрезвычайно трудным, поскольку проблемная последовательность событий встречается очень редко. Проверка модели — отличный способ выявить такие проблемы. См., например, упражнение 7.3.3 в разделе «Моделирование и анализ взаимодействующих систем».

Пример Java

Ниже приведена реализация стека Treiber на Java, основанная на реализации Java Concurrency in Practice.

import java.util.concurrent.atomic.*;

import net.jcip.annotations.*;

/**
 * ConcurrentStack
 *
 * Nonblocking stack using Treiber's algorithm
 *
 * @author Brian Goetz and Tim Peierls
 */
@ThreadSafe
public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;

        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;

        do {
            oldHead = top.get();
            if (oldHead == null)
                return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));

        return oldHead.item;
    }

    private static class Node <E> {
        public final E item;
        public Node<E> next;

        public Node(E item) {
            this.item = item;
        }
    }
}