Реализации структуры данных LIFO с поддержкой потоков

1. Введение

В этом руководстве мы обсудим различные варианты реализации структуры данных LIFO с поддержкой потоков .

В структуре данных LIFO элементы вставляются и извлекаются в соответствии с принципом «последним пришел – первым вышел». Это означает, что последний вставленный элемент извлекается первым.

В информатике стек — это термин, используемый для обозначения такой структуры данных.

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

2. Понимание стеков

По сути, стек должен реализовывать следующие методы:

1. push() — добавить элемент вверху
2. pop() — извлечь и удалить верхний элемент
3. peek() — извлекает элемент, не удаляя его из базового контейнера.

Как обсуждалось ранее, давайте предположим, что нам нужен механизм обработки команд.

В этой системе отмена выполненных команд является важной функцией.

В общем, все команды помещаются в стек, а затем можно просто реализовать операцию отмены:

• метод pop() для получения последней выполненной команды
• вызовите метод undo() для всплывающего командного объекта

3. Понимание безопасности потоков в стеках

Если структура данных не является потокобезопасной, при одновременном доступе к ней могут возникнуть условия гонки .

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

Давайте рассмотрим приведенный ниже метод из класса Java Collection, ArrayDeque :

public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // ... other book-keeping operations removed, for simplicity
    head = (h + 1) & (elements.length - 1);
    return result;
}

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

• Первый поток выполняет третью строку: устанавливает объект результата с элементом в индексе 'head'
• Второй поток выполняет третью строку: устанавливает объект результата с элементом в индексе 'head'
• Первый поток выполняет пятую строку: сбрасывает индекс «голова» к следующему элементу в резервном массиве.
• Второй поток выполняет пятую строку: сбрасывает индекс «голова» на следующий элемент в резервном массиве.

Ой! Теперь оба выполнения вернут один и тот же объект результата .

Чтобы избежать таких условий гонки, в этом случае поток не должен выполнять первую строку, пока другой поток не завершит сброс индекса «голова» в пятой строке. Другими словами, доступ к элементу по индексу «голова» и сброс индекса «голова» должны происходить атомарно для потока.

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

4. Поточно-безопасные стеки с использованием блокировок

В этом разделе мы обсудим два возможных варианта конкретной реализации потокобезопасного стека.

В частности, мы рассмотрим Java Stack и потокобезопасный оформленный ArrayDeque.

Оба используют блокировки для взаимоисключающего доступа .

4.1. Использование стека Java ``

Коллекции Java имеют устаревшую реализацию потокобезопасного стека , основанную на векторе , который в основном является синхронизированным вариантом ArrayList.

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

Хотя стек Java потокобезопасен и прост в использовании, у этого класса есть серьезные недостатки:

• Не поддерживает настройку начальной емкости
• Он использует блокировки для всех операций. Это может снизить производительность при выполнении однопоточных приложений.

4.2. Использование ArrayDeque

Использование интерфейса Deque является наиболее удобным подходом для структур данных LIFO, поскольку он обеспечивает все необходимые операции со стеком. ArrayDeque является одной из таких конкретных реализаций .

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

Однако мы можем реализовать декоратор синхронизации для ArrayDeque. Хотя это работает аналогично классу Stack в Java Collection Framework , важная проблема класса Stack — отсутствие начальной настройки емкости — решена.

Давайте посмотрим на этот класс:

public class DequeBasedSynchronizedStack<T> {

    // Internal Deque which gets decorated for synchronization.
    private ArrayDeque<T> dequeStore;

    public DequeBasedSynchronizedStack(int initialCapacity) {
        this.dequeStore = new ArrayDeque<>(initialCapacity);
    }

    public DequeBasedSynchronizedStack() {
        dequeStore = new ArrayDeque<>();
    }

    public synchronized T pop() {
        return this.dequeStore.pop();
    }

    public synchronized void push(T element) {
        this.dequeStore.push(element);
    }

    public synchronized T peek() {
        return this.dequeStore.peek();
    }

    public synchronized int size() {
        return this.dequeStore.size();
    }
}

Обратите внимание, что наше решение не реализует сам Deque для простоты, так как оно содержит гораздо больше методов.

Кроме того, Guava содержит SynchronizedDeque , который является готовой реализацией оформленного ArrayDequeue.

5. Поточно-безопасные стеки без блокировок

ConcurrentLinkedDeque — это свободная от блокировок реализация интерфейса Deque . Эта реализация полностью потокобезопасна, так как использует эффективный алгоритм без блокировок.

Реализации без блокировки невосприимчивы к следующим проблемам, в отличие от реализации на основе блокировки.

• Инверсия приоритета . Это происходит, когда поток с низким приоритетом удерживает блокировку, необходимую для потока с высоким приоритетом. Это может привести к блокировке потока с высоким приоритетом.
• Взаимоблокировки — это происходит, когда разные потоки блокируют один и тот же набор ресурсов в разном порядке.

Кроме того, реализации без блокировки имеют некоторые особенности, которые делают их идеальными для использования как в однопоточных, так и в многопоточных средах.

• Для неразделяемых структур данных и однопоточного доступа производительность будет на уровне ArrayDeque.
• Для общих структур данных производительность зависит от количества потоков, одновременно обращающихся к ним .

А с точки зрения удобства использования он ничем не отличается от ArrayDeque , поскольку оба реализуют интерфейс Deque .

6. Заключение

В этой статье мы обсудили структуру данных стека и ее преимущества при разработке таких систем, как механизм обработки команд и оценщики выражений.

Кроме того, мы проанализировали различные реализации стека в среде коллекций Java и обсудили нюансы их производительности и безопасности потоков.

Как обычно, примеры кода можно найти на GitHub .