Введение в структуры данных без блокировки с примерами Java

Автор оригинала: Michael Krimgen.

1. введение

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

Во-первых, мы рассмотрим некоторые термины, такие как без препятствий , без блокировки и без ожидания .

Во-вторых, мы рассмотрим основные строительные блоки неблокирующих алгоритмов, таких как CAS (сравнение и обмен).

В-третьих, мы рассмотрим реализацию очереди без блокировки в Java и, наконец, изложим подход к достижению wait-freedom .

2. Замок Против Голода

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

На приведенном выше рисунке поток 2 получает блокировку структуры данных. Когда поток 1 также пытается получить блокировку, ему нужно подождать, пока поток 2 не освободит блокировку; он не продолжит работу, прежде чем сможет получить блокировку. Если мы приостановим поток 2, пока он удерживает блокировку, потоку 1 придется ждать вечно.

Следующая картина иллюстрирует голодание нитей:

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

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

Позже мы увидим, как операция compare-and-swap обеспечивает неблокирующий доступ.

3. Типы неблокирующих структур данных

Мы можем различать три уровня неблокирующих структур данных.

3.1. Отсутствие препятствий

Препятствие-свобода-это самая слабая форма неблокирующей структуры данных. Здесь мы требуем, чтобы поток гарантированно продолжался, только если все остальные потоки приостановлены .

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

3.2. Без блокировки

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

3.3. Без ожидания

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

3.4. Резюме

Давайте обобщим эти определения в графическом представлении:

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

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

Последняя часть показывает свободу ожидания. Здесь мы гарантируем, что поток 1 может продолжаться (зеленая стрелка) после определенного периода голодания (красные стрелки).

4. Неблокирующие примитивы

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

4.1. Сравнение и обмен

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

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

Здесь оба потока извлекают значение 3 из основной памяти. Поток 2 завершается успешно (зеленый) и обновляет переменную до 8. Поскольку в первом СЛУЧАЕ по потоку 1 ожидается, что значение по-прежнему будет равно 3, CAS терпит неудачу (красный). Поэтому поток 1 снова извлекает значение, и второй CAS завершается успешно.

Здесь важно то, что CAS не получает блокировку структуры данных, а возвращает истинный если обновление прошло успешно, в противном случае оно возвращается ложный .

Следующий фрагмент кода описывает, как работает CAS:

volatile int value;

boolean cas(int expectedValue, int newValue) {
    if(value == expectedValue) {
        value = newValue;
        return true;
    }
    return false;
}

Мы обновляем значение новым значением только в том случае, если оно все еще имеет ожидаемое значение, в противном случае оно возвращает false . Следующий фрагмент кода показывает, как можно вызвать CAS:

void testCas() {
    int v = value;
    int x = v + 1;

    while(!cas(v, x)) {
        v = value;
        x = v + 1;
    }
}

Мы пытаемся обновить наше значение до тех пор, пока операция CAS не завершится успешно, то есть не вернет true .

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

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

Java предоставляет реализацию compare-and-swap в классе sun.misc.Unsafe . Однако в большинстве случаев мы не должны использовать этот класс напрямую, а вместо этого Атомарные переменные .

Кроме того, compare-and-swap не предотвращает проблему A-B-A. Мы рассмотрим это в следующем разделе.

4.2. Загрузка-Ссылка/Хранение-Условно

Альтернативой compare-and-swap является load-link/store-conditional . Давайте сначала вернемся к compare-and-swap . Как мы видели ранее, CAS обновляет значение только в том случае, если значение в основной памяти по-прежнему соответствует ожидаемому значению.

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

Приведенное ниже изображение иллюстрирует эту ситуацию:

И поток 1, и поток 2 считывают значение переменной, которое равно 3. Затем поток 2 выполняет CAS, который успешно устанавливает переменную в 8. Затем снова поток 2 выполняет CAS, чтобы вернуть переменной значение 3, которое также успешно выполняется. Наконец, поток 1 выполняет CAS, ожидая значения 3, и также успешно, несмотря на то, что значение нашей переменной было изменено дважды в промежутке.

Это называется проблемой ABA. Конечно, это поведение не может быть проблемой в зависимости от варианта использования. Однако это может быть нежелательно для других. Java предоставляет реализацию load-link/store-conditional с классом AtomicStampedReference .

4.3. Извлечение и добавление

Другой альтернативой является fetch-and-add . Эта операция увеличивает переменную в основной памяти на заданное значение. Опять же, важным моментом является то, что операция выполняется атомарно, что означает, что никакой другой поток не может вмешиваться .

Java предоставляет реализацию fetch-and-add в своих атомарных классах. Примерами являются AtomicInteger.incrementAndGet() , который увеличивает значение и возвращает новое значение; и AtomicInteger.getAndIncrement() , который возвращает старое значение, а затем увеличивает значение.

5. Доступ к связанной очереди из нескольких потоков

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

Очередь, которую мы рассмотрим, представляет собой двусвязную очередь FIFO, в которой мы добавляем новые элементы после последнего элемента (L), а переменная tail указывает на этот последний элемент:

Чтобы добавить новый элемент, потоки должны выполнить три шага: 1) создать новые элементы (N и M) с указателем на следующий элемент, установленным в null ; 2) иметь ссылку на предыдущий элемент, указывающий на L, и ссылку на следующий элемент L, указывающий на N (M, соответственно). 3) Иметь хвост точку N (M, соответственно):

Что может пойти не так, если два потока выполняют эти шаги одновременно? Если шаги на приведенном выше рисунке выполняются в порядке ABC или ACB, L, а также tail , будут указывать на M. N останется отключенным от очереди.

Если шаги выполняются в порядке ACDB, tail будет указывать на N, в то время как L будет указывать на, что приведет к несогласованности в очереди:

Конечно, один из способов решить эту проблему-заставить один поток получить блокировку в очереди. Решение, которое мы рассмотрим в следующей главе, решит проблему с помощью операции без блокировки, используя операцию CAS, которую мы видели ранее.

6. Неблокирующая очередь в Java

Давайте рассмотрим базовую очередь без блокировки в Java. Во – первых, давайте посмотрим на членов класса и конструктор:

public class NonBlockingQueue {

    private final AtomicReference> head, tail;
    private final AtomicInteger size;

    public NonBlockingQueue() {
        head = new AtomicReference<>(null);
        tail = new AtomicReference<>(null);
        size = new AtomicInteger();
        size.set(0);
    }
}

Важной частью является объявление головной и хвостовой ссылок как AtomicReference s, что гарантирует, что любое обновление этих ссылок является атомной операцией . Этот тип данных в Java реализует необходимую операцию compare-and-swap .

Далее давайте рассмотрим реализацию класса Node:

private class Node {
    private volatile T value;
    private volatile Node next;
    private volatile Node previous;

    public Node(T value) {
        this.value = value;
        this.next = null;
    }

    // getters and setters 
}

Здесь важной частью является объявление ссылок на предыдущий и следующий узлы как volatile . Это гарантирует, что мы всегда обновляем эти ссылки в основной памяти (таким образом, они непосредственно видны всем потокам). То же самое для фактического значения узла.

6.1. Добавление без блокировки

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

public void add(T element) {
    if (element == null) {
        throw new NullPointerException();
    }

    Node node = new Node<>(element);
    Node currentTail;
    do {
        currentTail = tail.get();
        node.setPrevious(currentTail);
    } while(!tail.compareAndSet(currentTail, node));

    if(node.previous != null) {
        node.previous.next = node;
    }

    head.compareAndSet(null, node); // for inserting the first element
    size.incrementAndGet();
}

Существенная часть, на которую следует обратить внимание, – это выделенная линия. Мы пытаемся добавить новый узел в очередь до тех пор, пока операция CAS не завершится успешно, чтобы обновить хвост, который все еще должен быть тем же хвостом, к которому мы добавили новый узел.

6.2. Получение без блокировки

Аналогично операции добавления, операция получения без блокировки гарантирует, что мы вернем последний элемент и переместим хвост в текущее положение:

public T get() {
    if(head.get() == null) {
        throw new NoSuchElementException();
    }

    Node currentHead;
    Node nextNode;
    do {
        currentHead = head.get();
        nextNode = currentHead.getNext();
    } while(!head.compareAndSet(currentHead, nextNode));

    size.decrementAndGet();
    return currentHead.getValue();
}

Опять же, существенная часть, на которую следует обратить внимание, – это выделенная линия. Операция CAS гарантирует, что мы переместим текущую головку только в том случае, если за это время не было удалено ни одного другого узла.

Java уже предоставляет реализацию неблокирующей очереди, Concurrentlink queue . Это реализация очереди без блокировки от М. Майкла и Л. Скотта, описанной в этой статье . Интересным замечанием здесь является то, что в документации Java говорится, что это очередь без ожидания , где на самом деле без блокировки . Документация Java 8 правильно называет реализацию без блокировки .

7. Очереди Без ожидания

Как мы уже видели, приведенная выше реализация свободна от блокировки , однако не свободна от ожидания . Циклы while как в методе add , так и в методе get потенциально могут зацикливаться в течение длительного времени (или, хотя это маловероятно, навсегда), если к нашей очереди обращается много потоков.

Как мы можем достичь свободы ожидания? Реализация алгоритмов без ожидания, в общем, довольно сложна. Мы отсылаем заинтересованного читателя к этой статье , в которой подробно описывается очередь без ожидания. В этой статье давайте рассмотрим основную идею о том, как мы можем подойти к реализации очереди без ожидания .

Очередь без ожидания требует, чтобы каждый поток выполнял гарантированный прогресс (после конечного числа шагов). Другими словами, циклы while в наших методах add и get должны завершиться успешно после определенного количества шагов.

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

Поскольку вспомогательный поток сам имеет помощника, и, по всему списку потоков, у каждого потока есть помощник, мы можем гарантировать, что поток завершит вставку последним после того, как каждый поток выполнит одну вставку. На следующем рисунке показана эта идея:

Конечно, все усложняется, когда мы можем динамически добавлять или удалять потоки.

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

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

Затем мы рассмотрели базовую реализацию очереди без блокировки в Java. Наконец, мы изложили идею о том, как достичь ожидания-свободы .

Полный исходный код для всех примеров в этой статье доступен на GitHub.