Потокобезопасные реализации структуры данных LIFO

1. введение

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

В структуре данных LIFO элементы вставляются и извлекаются в соответствии с принципом “Последний вход-первый выход”. Это означает, что последний вставленный элемент извлекается первым.

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

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

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

В основном, Стек необходимо реализовать следующие методы:

толкать() – добавьте элемент в верхней части
хлопок() – извлеките и удалите верхний элемент
заглядывать() – извлеките элемент, не удаляя его из базового контейнера

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

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

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

хлопок() метод получения последней выполненной команды
позвоните в отменить() метод для выскочившего объекта команды

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

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

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

Давайте рассмотрим метод ниже из класса коллекции Java, 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”
Первый поток выполняет пятую строку: сбрасывает индекс “head” на следующий элемент в резервном массиве
Второй поток выполняет пятую строку: сбрасывает индекс “head” на следующий элемент в резервном массиве

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

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

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

4. Потокобезопасные Стеки С использованием Замков

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

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

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

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

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

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

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

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

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

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

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

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

Давайте взглянем на этот класс:

public class DequeBasedSynchronizedStack {

    // Internal Deque which gets decorated for synchronization.
    private ArrayDeque 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 содержит Synchronized Deque , который является готовой к производству реализацией оформленного массива Dequeue.

5. Стопки без блокировки и без резьбы

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

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

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

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

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

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

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

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

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

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