Теория и практика Java: Переход к атомарности

Новые атомарные классы - это золотой запас нового ПО java.util.concurrent

До появления JDK 5.0 было невозможно писать алгоритмы, не требующие ожидания (wait-free) и не поддающиеся блокировке (lock-free) на языке Java, если вы не пользовались собственным кодом. Появление атомарных переменных классов в программе java.util.concurrent меняет ситуацию. Изучите проблематику параллельной обработки вместе с ведущим специалистом Брайаном Гетцем, и он расскажет вам, как эти новые классы создали возможность разрабатывать высокомасштабируемые безблокировочные алгоритмы на языке Java.

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

Брайан Гетц (Brian Goetz) - консультант по ПО и последние 15 лет работал профессиональными разработчиком ПО. Сейчас он является главным консультантом в фирме Quiotix, занимающейся разработкой ПО и консалтингом и находящейся в Лос-Альтос, Калифорния. Следите за публикациями Брайана в популярных промышленных изданиях. Вы можете связаться с Брайаном по адресу brian@quiotix.com



08.02.2007

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

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

Суть проблемы: координация между потоками

Мало какие задачи могут выполняться полностью параллельно, без координации с другими потоками. Рассмотрим сумму потоков (thread pool), в которой выполняемые задачи в основном независимы друг от друга. Если сумма потоков создает общую очередь заданий, то процесс снятия из очереди и добавления элементов в очередь должен обеспечивать защищенность потока, то есть, нужна координация ссылок, указывающих на заголовки, конечные строки и средние части узлов. Именно эта координация часто порождает проблемы.

Стандартный подход: блокирование

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

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

Изменяемые (volatile) переменные тоже можно использовать для более экономного хранения переменных совместного доступа (по сравнению с синхронизацией), но это наложит некоторые ограничения. Если записи в изменяемых переменных гарантированно видны остальным потокам, то передать последовательность читать-модифицировать-читать в операциях атомарных невозможно, а это, например, означает, что изменяемую переменную нельзя использовать для надежной реализации взаимного исключения (mutex - мьютекс) или счетчика.

Реализация счетчиков и мьютексов с блокировкой

Рассмотрим разработку класса счетчиков с защитой потока, где видны операции get(), increment() и decrement(). Листинг 1 дает пример того, как можно реализовать этот класс при помощи блокировки (синхронизации). Обратите внимание: все эти методы, даже get(), нуждаются в синхронизации для обеспечения защиты потока, чтобы обновления не потерялись и чтобы все потоки могли видеть обновленные показания счетчика.

Листинг 1. Класс счетчика с синхронизацией
public class SynchronizedCounter {
    private int value;

    public synchronized int getValue() { return value; }
    public synchronized int increment() { return ++value; }
    public synchronized int decrement() { return --value; }
}

Операции обновления величины increment() и decrement() являются атомарными типа "чтение-модифицикация-запись", и для того, чтобы надежно обновить показания счетчика, необходимо взять текущую величину параметра, увеличить ее на 1 и выписать новую величину, все это одной операцией, которую не могут прерывать другие потоки. Иначе, если бы 2 потока попытались осуществить внедрение одновременно, случилось бы неудачное чередование (интерливинг - interleaving) операций, что привело бы к тому, что счетчик сменил бы показания только один раз, а не два. (Обратите внимание на то, что надежность этой операции пострадает, если переменную этой величины сделать изменяемой.)

Атомарная комбинация "чтение-модификация-запись" встречается во многих параллельных алгоритмах. Код в Листинге 2 реализует простой мьютекс, а метод acquire() также является атомарной операцией читать-модифицировать-записать. Для получения этого мьютекса надо убедиться, никто в данное время не блокирует его. (curOwner == null), а потом сделать запись о том, что вы забираете его (curOwner = Thread.currentThread()), все это исключит возможность появления в середине работы другого потока и модификации поля curOwner field.

Листинг 2. Класс мьютекса с синхронизацией
public class SynchronizedMutex {
    private Thread curOwner = null;

    public synchronized void acquire() throws InterruptedException {
        if (Thread.interrupted()) throw new InterruptedException();
        while (curOwner != null) 
            wait();
        curOwner = Thread.currentThread();
    }

    public synchronized void release() {
        if (curOwner == Thread.currentThread()) {
            curOwner = null;
            notify();
        } else
            throw new IllegalStateException("not owner of mutex");
    }
}

Класс счетчика в Листинге 1 работает надежно при отсутствии конфликтов (или их минимальном наличии). Однако при серьезных конфликтах производительность может серьезно снизиться, так как виртуальная машина JVM будет затрачивать больше времени на планирование очередей в потоках и на разрешение конфликтов, у нее останется меньше времени на саму работу, например, на обновление показаний счетчиков. Вспомните таблицы из нашей предыдущей статьи , которые показывали, как объем выполненной работы может серьезно снизиться, если несколько потоков заявляют права на встроенный блок при методе синхронизации. Хотя в той статье мы видели, что новый класс ReentrantLock обладает большей масштабируемостью при синхронизации, для некоторых проблем есть и более эффективный метод.

Проблемы, связанные с блокировкой

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

Использование блокировок связано и с некоторыми другими опасностями, например, может привести к взаимоблокировке (deadlock), если несколько блокировок применить в неправильной последовательности. Даже при отсутствии такой опасности блокировка остается относительно крупномодульным средством координирования и поэтому довольно неуклюже управляет такими простыми операциями, как смена показания счетчика или обновление информации о том, кто использует мьютекс. Было бы хорошо иметь более тонкий механизм для надежного управления параллельными обновлениями индивидуальными переменными; и на большинстве современных процессоров такие механизмы уже имеются.


Базовые элементы аппаратной синхронизации (Hardware synchronization primitives)

Мы уже говорили, что большинство современных процессоров имеют поддержку многопроцессорной обработки. Конечно, это означает, что несколько процессоров могут совместно пользоваться периферийными устройствами и ОЗУ, и кроме этого имеет такие дополнения к набору команд, которые обеспечивают многопроцессорную обработку. В частности, почти все новые процессоры имеют команды для обновления переменных совместного доступа таким образом, чтобы распознать или предотвратить параллельный доступ разными процессорами.

Сравнение и замена (Compare and swap - CAS)

Первые процессоры, поддерживавшие параллелизм в обработке, обеспечивали атомарные операции команд установки семафора (test-and-set), которые обычно применялись к отдельному биту. Наиболее частый подход в современных процессорах, включая Intel и Sparc, - использование базового элемента под названием Сравнение и замена (CAS) (В процессорах Intel он осуществляется группой команд cmpxchg. Процессоры PowerPC имеют 2 команды: load and reserve (загрузить и резервировать) и store conditional (сохранить при условии); они предназначены для выполнения той же задачи, то же можно сказать о MIPS-процессорах, хотя в них первая носит название load linked (загрузить со связкой)).

Операция CAS включает 3 объекта-операнда: адрес ячейки памяти (V), ожидаемое старое значение (A) и новое значение (B). Процессор атомарно обновляет адрес ячейки, если новое значение совпадает со старым, иначе изменений не зафиксируется. В любом случае, будет выведена величина, которая предшествовала времени запроса. Некоторые варианты метода CAS просто сообщают, успешно ли прошла операция, вместо того, чтобы отобразить само текущее значение. Фактически, CAS только сообщает: "Наверное, адрес V равняется A; если так оно и есть, поместите туда же B, в противном случае не делайте этого, но обязательно скажите мне, какая величина - текущая."

Самым естественным методом использования CAS для синхронизации будет чтение значения A с адреса V, проделать многошаговое вычисление для получения нового значения B, и затем воспользоваться методом CAS для замены значения параметра V с прежнего, A, на новое, B. CAS выполнит задание, если V за это время не менялось.

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

Листинг 3. Код, иллюстрирующий ход выполнения (но не характеристики) метода Сравнить и заменить
public class SimulatedCAS {
     private int value;

     public synchronized int getValue() { return value; }

	public synchronized int compareAndSwap(int expectedValue, int newValue) {
         int oldValue = value;
         if (value == expectedValue)
             value = newValue;
         return oldValue;
     }
}

Реализация счетчиков методом CAS

Параллельные алгоритмы на основе CAS называют безблокировочными безблокировочными, потому что потокам не приходится ожидать блокировки (иногда ее называют разделом совместного доступа (mutex) или критическим разделом, в зависимости от того, какой терминологией пользуется ваша потоковая платформа). Операция CAS проходит успешно или неуспешно, но независимо от исхода она завершается в предсказуемые сроки. Если CAS не реализуется, вызывающая программа может повторить попытку операции CAS или предпринять иные шаги, которые она считает нужными. Листинг 4 показывает класс счетчика, переписанный для использования CAS вместо блокировки:

Листинг 4. Реализация счетчика с методом Сравнение и замена
public class CasCounter {
    private SimulatedCAS value;

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

    public int increment() {
        int oldValue = value.getValue();
        while (value.compareAndSwap(oldValue, oldValue + 1) != oldValue)
            oldValue = value.getValue();
        return oldValue + 1;
    }
}

Безблокировочные алгоритмы и алгоритмы, не требующие ожидания (wait-free)

Алгоритм называют wait-free, если каждый поток будет продолжать обработку при наличии произвольной задержки (arbitrary delay) или сбоя других потоков. Напротив, алгоритм lock-free требует только того, чтобы работа постоянно шла хотя бы в одном потоке шла обработка. (Еще один способ дать определение wait-free: при этом методе каждый поток гарантированно правильно производит вычисления по своим операциям в ограниченном количестве своих шагов, независимо от действий, хронометража, чередования (interleaving) и скорости остальных потоков. Это ограничение может накладываться функцией количества потоков в системе; например, если каждый из 10 потоков выполнит по одному разу операцию CasCounter.increment(), то самое худшее, что может случиться, это дополнительные 9 попыток со стороны каждого потока до того, как завершится обновление значения (increment).)

Алгоритмам wait-free и безблокировочным алгоритмам (lock-free, nonblocking) за последние 15 лет было посвящено много исследований, и были открыты безблокировочные механизмы для многих структур с общими данными. Безблокировочные алгоритмы широко используют на уровне операционной системы и в виртуальной машине Java для решения задач планирования потоков и процессов. Хотя их труднее реализовывать, они обладают несколькими преимуществами по сравнению с блокировочными методами - исчезает опасность смены приоритетов и взаимного блокирования, уменьшаются затраты на разрешение конфликтов и координация происходит на уровне более мелких ячеек, что обеспечивает более высокий уровень параллелизма.

Классы атомарных переменных

До версии JDK 5.0 на языке Java нельзя было создавать алгоритмы wait-free и безблокировочные без использования собственного кода. С появлением классов атомарных переменных в пакете java.util.concurrent.atomic все изменилось. Все атомарные классы переменных имеют базовый элемент Сравнение и назначение (compare-and-set) (аналогичный элементу Сравнение и замена), который реализуется при помощи самого быстрого собственного структурного компонента, кооторый имеется в платформе (Сравнение и замена, Загрузить в связке, Сохранить при условии или в крайнем случае спин-блокировками). В пакет java.util.concurrent.atomic входят 9 видов атомарных переменных (AtomicInteger; AtomicLong; AtomicReference; AtomicBoolean; формы для массивов атомарных целых чисел; длинные (long); ссылки; а также атомарные с пометкой Класс эталона (reference), которые атомарно обновляют две величины).

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

Хотя классы атомарных переменных могут показаться похожими на пример кода SynchronizedCounter в Листинге 1, сходство только поверхностное. Под поверхностью операции с атомарными переменными превращаются в аппаратные базовые элементы, которые платформа предоставляет для параллельного доступа, например, в методе Сравнение и замена.

Мелкоячеистость означает отсутствие тяжеловесности

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

Проблема ABA

Листинга 1Листинга 2AtomicStampedReference

Атомарные переменные в java.util.concurrent

Почти все классы в пакете java.util.concurrent используют атомарные переменные вместо синхронизации, либо прямо, либо косвенно. Такие классы, как ConcurrentLinkedQueue используют атомарные переменные для прямой реализации алгоритмов wait-free и такие классы, как ConcurrentHashMap используют ReentrantLock для блокировки, если это необходимо. В свою очередь, ReentrantLock использует атомарные переменные для соблюдения очередности потоков, ожидающих блокировки.

Эти классы невозможно было бы сконструировать без усовершенствования машины JVM в версии JDK 5.0, которая сделала явным (для библиотек классов, но не для библиотек пользователей) интерфейс доступа к базовым элементам синхронизации аппаратного уровня. Классы атомарных переменных и, в свою очередь, другие классы в java.util.concurrent экспонируют эти характеристики классам пользователей.


Повышение пропускной способности при помощи атомарных переменных

В прошлом месяце я рассказывал читателям, как класс ReentrantLock приводит к выигрышу в масштабируемости за счет синхронизации и построил простой эталонный тест, рассчитанный на высококонфликтную среду (high-contention example benchmark), который симулирует игру в кости генератором псевдослучайных чисел. Я продемонстрировал вам реализации, которые осуществляют координацию при помощи синхронизации, ReentrantLock и честного (fair) ReentrantLock и показал результаты. В этом месяце я добавлю еще одну реализацию к этому тесту, которая использует AtomicLong для обновления состояния генератора псевдослучайных чисел (PRNG).

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

Листинг 5. Реализация PRNG с защищённым потоком, синхронизацией и атомарными переменными
public class PseudoRandomUsingSynch implements PseudoRandom {
    private int seed;

    public PseudoRandomUsingSynch(int s) { seed = s; }

    public synchronized int nextInt(int n) {
        int s = seed;
        seed = Util.calculateNext(seed);
        return s % n;
    }
}

public class PseudoRandomUsingAtomic implements PseudoRandom {
    private final AtomicInteger seed;

    public PseudoRandomUsingAtomic(int s) {
        seed = new AtomicInteger(s);
    }

    public int nextInt(int n) {
        for (;;) {
            int s = seed.get();
            int nexts = Util.calculateNext(s);
            if (seed.compareAndSet(s, nexts))
                return s % n;
        }
    }
}

Графики на Рисунках 1 и 2 похожи на те, которые я построил в прошлом месяце, добавилась только линия с атомарным подходом. Эти графики показываю пропускную способность (в прокрутках в секунду) при генерации случайных чисел с помощью различного количества потоков на 8-канальной машине Ultrasparc3 и на однопроцессорной машине Pentium 4. Количество потоков в этих тестах обманчиво, эти потоки обнаруживают гораздо больше конфликтов, чем обычно, поэтому они показывают коэффициент доходной загрузки (break-even) между ReentrantLock и атомарными переменными при гораздо меньшем количестве потоков, чем это выглядело бы в более реальной программе. Вы видите, что атомарные переменные предлагают дополнительное усовершенствование по сравнению с ReentrantLock, который и без того имел то преимущество перед синхронизацией. (Поскольку на каждом этапе работы выполняется столь мало, нижеприведенные графики, возможно, занижают реальную выгоду, получаемую благодаря увеличению масштабируемости, которое появилось при замене блока ReentrantLock на атомарные переменные.)

Рисунок 1. Тест пропускной способности при синхронизации, блоке ReentrantLock, справедливом блоке и AtomicLong на 8-канальном Ultrasparc3
Пропускная способность на 8-канальном Ultrasparc3
Рисунок 2. Тест пропускной способности при синхронизации, блоке ReentrantLock, справедливом блоке и AtomicLong на однопроцессорном Pentium 4
Пропускная способность на однопроцессорном Pentium 4

Едва ли многие пользователи станут самостоятельно разрабатывать безблокировочные алгоритмы с атомарными переменными - скорее всего, они используют версии, предоставляемые в java.util.concurrent, такие, где повышение продуктивности является результатом ConcurrentLinkedQueue. Но если вам все-таки хочется узнать, за счет чего так возрастает производительность по сравнению с аналогами в предыдущих версиях JDK, знайте: все дело в том, что используются мелкоячеистые аппаратные базовые элементы, выраженные через классы атомарных переменных.

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


Выводы

JDK 5.0 представляет собой огромный шаг вперед в разработке высокопроизводительных парллельных классов. Поскольку эта версия представляет низкоуровневые координационные базовые элементы изнутри и снабжена набором распространенных атомарных изменяемых классов, сейчас впервые реально встает вопрос о разработке не требующих ожидания и неблокирующих алгоритмов на языке Java. Классы в java.util.concurrent, в свою очередь, созданы из этих низкоуровневых атомарных переменных средств, что дает последним значительный выигрыш в масштабируемости перед ранее использовавшимися для этих функций классами. Хотя, возможно, вам и не потребуется пользоваться атомарными переменными ваших классов, их наличие все же обоснованно радует.

Ресурсы

Комментарии

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=194634
ArticleTitle=Теория и практика Java: Переход к атомарности
publish-date=02082007