Теория и практика Java: Введение в неблокирующие алгоритмы

Смотрите, блоков нет!

Версия Java™ 5.0 впервые сделала возможной разработку неблокирующих алгоритмов на языке программирования Java, и эта возможность широко используется в пакете java.util.concurrent. Неблокирующие алгоритмы представляют собой параллельные алгоритмы, потокозащищенность которых обеспечивается не блокировками, а низкоуровневыми атомарными аппаратными примитивами, такими как сравнение-и-замена. Разработка и реализация неблокирующих алгоритмов может быть чрезвычайно сложной задачей, но они могут предложить лучшую производительность и большую стойкость к проблемам живучести, таким как взаимоблокировки и инверсия приоритетов. В этой очередной статье серии «Теория и практика Java» гуру параллельности Брайан Гец рассматривает работу некоторых неблокирующих алгоритмов.

Брайан Гец, главный консультант, Quiotix

Брайан Гец (Brian Goetz) занимается профессиональной разработкой программного обеспечения более 18 лет. Он является главным консультантом в Quiotix, компании, расположенной в Los Altos, California и занимающейся разработкой программного обеспечения и консультациями, а также работает в нескольких JCP Expert Groups. Книга Брайана "Параллельность на практике" будет опубликована в начале 2006 в издательстве Addison-Wesley. Вы можете найти его опубликованные и готовящиеся к публикации статьи в популярных отраслевых изданиях.



18.04.2006

Когда к разделяемой переменной обращаются несколько потоков, все они должны использовать синхронизацию, в противном случае может возникнуть нехорошая ситуация. Главным средством синхронизации в языке программирования Java является ключевое слово synchronized (этот способ синхронизации известен также под названием внутренняя блокировка (intrinsic locking)), которое обеспечивает взаимное исключение и гарантирует, что действия одного потока, выполняющего блок synchronized, видимы для остальных потоков, которые будут выполнять блок synchronized, защищенный этой же блокировкой. При правильном применении внутренняя блокировка позволяет сделать наши программы потокозащищенными, но она может быть тяжеловесной операцией при использовании для защиты маленьких участков кода, когда потоки часто соревнуются за блокировку.

В статье "Going atomic" мы рассмотрели атомарные переменные (atomic variable), которые предоставляют атомарные операции чтение-изменение-запись для безопасного изменения разделяемых переменных без блокировок. Атомарные переменные аналогичны по семантике использования памяти переменным volatile, но поскольку они также могут меняться автоматически, их можно использовать в качестве базы для свободных от блокировок параллельных алгоритмов.

Неблокирующий счетчик

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

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

Листинг 1. Потокозащищенный счетчик, использующий синхронизацию
public final class Counter {
    private long value = 0;

    public synchronized long getValue() {
        return value;
    }

    public synchronized long increment() {
        return ++value;
    }
}

Класс NonblockingCounter в листинге 2 демонстрирует один из простейших неблокирующих алгоритмов: счетчик AtomicInteger, использующий метод compareAndSet() (CAS). Метод compareAndSet() означает "Обновить переменную этим новым значеним, но отказать, если другой поток изменил значение после моего последнего просмотра" (см. в статье "Going atomic" подробное объяснение атомарных переменных и функции сравнить-и-установить).

Листинг 2. Неблокирующий счетчик, использующий CAS
public class NonblockingCounter {
    private AtomicInteger value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        while (!value.compareAndSet(v, v + 1));
        return v + 1;
    }
}

Классы атомарных переменных называются атомарными, потому что они предоставляют мелкомодульные атомарные обновления чисел и объектных ссылок, но они также атомарны и в том смысле, что являются основными строительными блоками для неблокирующих алгоритмов. Неблокирующие алгоритмы являются предметом изучения уже более 20 лет, но стали возможными в языке программирования Java только с появлением Java 5.0.

Современные процессоры имеют специальные инструкции для атомарного обновления разделяемых данных, которые могут обнаружить вмешательство других потоков, и compareAndSet() использует их вместо блокирования. Если все что нам нужно – это инкрементировать счетчик, AtomicInteger предлагает методы для инкрементирования, но они основаны на compareAndSet(), например, NonblockingCounter.increment().

Неблокирующая версия имеет некоторые преимущества в производительности по отношению к версии, основанной на блокировках. Она выполняет синхронизацию на более низком уровне модульности (конкретное место в памяти), используя аппаратный примитив вместо фрагмента кода блокировки JVM. Проигравшие потоки могут выполнить повторную попытку немедленно, без останова и продолжения. Более мелкая модульность уменьшает шанс возникновения состязания, а возможность повторения попытки без останова и продолжения уменьшает стоимость состязания.

NonblockingCounter - это, возможно, простой пример, но он демонстрирует основную характеристику всех неблокирующих алгоритмов – некоторый шаг алгоритма выполняется гипотетически, с осознанием того, что он должен быть выполнен повторно, если операция CAS закончилась неудачно. Неблокирующие алгоритмы часто называют оптимистическими, потому что они выполняются с предположением о том, что не будет конфликтных ситуаций. Если такая ситуация возникает, они возвращаются на шаг назад и повторяют действие. В случае со счетчиком гипотетическим шагом является операция инкрементирования – она извлекает и добавляет единицу к старому значению в надежде на то, что оно не изменится за время вычисления обновленного значения. Если это не так, она должна повторно извлечь значение и снова выполнить инкрементирование.


Неблокирующий стек

Менее тривиальный пример неблокирующего алгоритма ConcurrentStack приведен в листинге 3. Операции push() и pop() в ConcurrentStack подобны по структуре операции increment() в NonblockingCounter. Они гипотетически выполняют определенную работу и надеются на то, что предполагаемые допущения не будут нарушены, когда придет время "подтвердить" работу. Метод push() просматривает текущий верхний элемент, создает новый элемент, который надо поместить в стек, и, затем, если самый верхний элемент не был изменен со времени последнего просмотра, помещает новый элемент в стек. Если CAS завершается неудачно - значит другой поток изменил стек, поэтому процесс выполняется снова.

Листинг 3. Неблокирующий стек, использующий алгоритм Трайбера (Treiber)
public class ConcurrentStack<E> {
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();

    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = head.get();
            newHead.next = oldHead;
        } while (!head.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = head.get();
            if (oldHead == null) 
                return null;
            newHead = oldHead.next;
        } while (!head.compareAndSet(oldHead,newHead));
        return oldHead.item;
    }

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

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

Анализ производительности

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

В условиях жесткой конкуренции (когда множество потоков обращаются к одному месту в памяти) основанные на блокировках алгоритмы начинают предлагать лучшую производительность, чем неблокирующие, поскольку при блокировании потока он прекращает попытки достучаться к ресурсу и терпеливо ждет своей очереди, уменьшая конкуренцию. Однако конкуренция такого высокого уровня – это необычная ситуация, поскольку основную часть времени потоки чередуют локальные вычисления с операциями, требующими разделяемых данных, давая другим потокам шанс использовать эти разделяемые данные. Высокий уровень конкуренции указывает также на то, что нужно подумать об изменении вашего алгоритма в сторону меньшего использования разделяемых данных. Граф в статье "Going atomic" немного сбивал с толку, поскольку анализируемая программа имела настолько нереалистично высокую конкуренцию, что казалось, будто блокировки имеют преимущество даже для небольшого числа потоков.


Неблокирующий связный список

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

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

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

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

LinkedQueue в листинге 4 демонстрирует операцию вставки для неблокирующего алгоритма очереди Майкла-Скотта (Michael-Scott), реализованного ConcurrentLinkedQueue:

Листинг 4. Вставка в неблокирующем алгоритме очереди Майкла-Скотта
public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;

        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }

    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;

    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

Как и во многих алгоритмах очереди, пустая очередь состоит из одного фиктивного элемента. Указатель "головы" очереди всегда ссылается на фиктивный элемент; Указатель "хвоста" очереди всегда указывает либо на последний элемент, либо на второй от конца элемент. На рисунке 1 изображена очередь с двумя элементами в нормальных условиях:

Рисунок 1. Очередь с двумя элементами в статическом состоянии
Очередь с двумя элементами в статическом состоянии

Как показано в листинге 4, вставка элемента требует обновления двух указателей, оба из которых производятся операциями CAS: связывание нового элемента с текущим последним элементом очереди (C) и переключение указателя "хвоста" очереди на новый последний элемент. Если первая операция завершается неудачно – состояние очереди не изменится, и поток будет продолжать попытки вставки элемента. После удачного выполнения этого шага считается, что операция вставки имела место, и другие потоки могут увидеть изменение. Все еще требуется переключение указателя "хвоста" очереди на новый элемент, но эта операция может рассматриваться как своего рода "зачистка", поскольку любой поток, который приступает к работе с очередью, может сказать, нужна ли такая зачистка, и знает, как ее выполнить.

Очередь всегда находится в одном из двух состояний: нормальном, или статическом (рисунки 1 и 3), или промежуточном (рисунок 2). Очередь находится в статическом состоянии перед операцией вставки и после успешной второй операции CAS (D); она находится в промежуточном состоянии после успешной первой операции CAS (C). В статическом состоянии поле next элемента, на который указывает "хвост" очереди, всегда равно null; в промежуточном состоянии – всегда не null. Любой поток может увидеть, в каком состоянии находится очередь, сравнив значение tail.next с null. В этом состоит суть разрешения потокам помогать другим потокам "завершать" свои операции.

Рисунок 2. Очередь в промежуточном состоянии во время операции вставки после добавления элемента, но перед обновлением указателя на "хвост" очереди
Очередь в промежуточном состоянии во время операции вставки после добавления элемента, но перед обновлением указателя на

Операция вставки сначала проверяет, находится ли очередь в промежуточном состоянии перед попыткой вставки нового элемента (A), как показано в листинге 4. Если это так, значит какой-то другой поток должен находиться в середине операции вставки элемента между шагами (C) и (D). Вместо ожидания завершения другого потока текущий поток может "помочь" завершить операцию за него посредством перемещения вперед указателя на "хвост" очереди (B). Он продолжает проверку указателя "хвоста" очереди и передвигает его при необходимости до тех пор, пока очередь не перейдет в статическое состояние, после чего он может начать свою собственную операцию вставки.

Первая операция CAS (C) может завершиться неудачно, поскольку два потока могут конкурировать за доступ к текущему последнему элементу очереди; в этой ситуации не выполняется никаких изменений, и данный поток снова читает указатель "хвоста" очереди и пытается выполнить операцию. Если неудачно завершается вторая операция CAS (D), вставляющий поток может не пытаться выполнить ее повторно, поскольку второй поток завершил эту операцию на шаге (B)!

Рисунок 3. Очередь снова находится в статическом состоянии после обновления указателя на "хвост" очереди
Очередь снова находится в статическом состоянии после обновления указателя на

Неблокирующие алгоритмы в действии

Если вы углубитесь в дебри JVM и OS, то обнаружите неблокирующие алгоритмы повсеместно. Сборщик мусора использует их для ускорения параллельных операций сборки мусора; планировщик использует их для эффективного планирования потоков и процессов и для реализации внутренней блокировки. В Mustang (Java 6.0) основанный на блокировках алгоритм SynchronousQueue заменен новой неблокирующей версией. Немногие разработчики используют SynchronousQueue напрямую, но она применяется в качестве рабочей очереди для пулов потоков, созданных фабрикой Executors.newCachedThreadPool(). Тесты производительности пула кешированных потоков показывают примерно трехкратное увеличение скорости работы по сравнению с текущей реализацией. Планируются и дальнейшие улучшения в следующей за Mustang версии под кодовым названием Dolphin.


Резюме

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

Ресурсы

Научиться

Получить продукты и технологии

  • JDK 5.0 Update 6: Получите последнее обновление JDK 5.0.

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=145111
ArticleTitle=Теория и практика Java: Введение в неблокирующие алгоритмы
publish-date=04182006