что такое атомарная операция java

Атомарные классы пакета util.concurrent

Пакет java.util.concurrent.atomic содержит девять классов для выполнения атомарных операций. Операция называется атомарной, если её можно безопасно выполнять при параллельных вычислениях в нескольких потоках, не используя при этом ни блокировок, ни синхронизацию synchronized. Прежде, чем перейти к рассмотрению атомарных классов, рассмотрим выполнение наипростейших операций инкремента и декремента целочисленных значений.

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

Описание атомарного класса AtomicLong

Рассмотрим принцип действия механизма оптимистической блокировки на примере атомарного класса AtomicLong, исходный код которого представлен ниже. В этом классе переменная value объявлена с модификатором volatile, т.е. её значение могут поменять разные потоки одновременно. Модификатор volatile гарантирует выполнение отношения happens-before, что ведет к тому, что измененное значение этой переменной увидят все потоки.

Метод compareAndSet реализует механизм оптимистической блокировки. Знакомые с набором команд процессоров специалисты знают, что ряд архитектур имеют инструкцию Compare-And-Swap (CAS), которая является реализацией этой самой операции. Таким образом, на уровне инструкций процессора имеется поддержка необходимой атомарной операции. На архитектурах, где инструкция не поддерживается, операции реализованы иными низкоуровневыми средствами.

Основная выгода от атомарных (CAS) операций появляется только при условии, когда переключать контекст процессора с потока на поток становится менее выгодно, чем немного покрутиться в цикле while, выполняя метод boolean compareAndSwap(oldValue, newValue). Если время, потраченное в этом цикле, превышает 1 квант потока, то, с точки зрения производительности, может быть невыгодно использовать атомарные переменные.

Список атомарных классов

Атомарные классы пакета java.util.concurrent.atomic можно разделить на 4 группы :

Полная документация по атомарным классам на английском языке представлена на оффициальном сайте Oracle. Наиболее часто используемые классы (не трудно догадаться) сосредоточены в первой группе.

Производительность атомарных классов

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

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

Пример неблокирующего генератора последовательности

Листинг класса SequenceGenerator для генерирования последовательности

Для работы в многопоточной среде без блокировок используем атомарную ссылку AtomicReference, которая обеспечит хранение целочисленного значения типа java.math.BigInteger. Метод next возвращает текущее значение; переменная next вычисляет следующее значение. Метод compareAndSet атомарного класса element обеспечивает сохранение нового значения, если текущее не изменилось. Таким образом, метод next возвращает текущее значение и увеличивает его в 2 раза.

Листинг последовательности Sequence

Для тестирования генератора последовательности SequenceGenerator используем класс Sequence, реализующий интерфейс Runnable. В качестве параметра конструктор класса получает идентификатор потока id, размер последовательности count и генератор последовательности sg. В методе run в цикле с незначительными задержками формируется последовательность чисел sequence. После завершения цикла значения последовательности «выводятся» в консоль методом printSequence.

Листинг примера SequenceGeneratorExample

В примере SequenceGeneratorExample сначала создается генератор последовательности SequenceGenerator. После этого в цикле формируется массив из десяти Sequence, которые в паралелльных потоках по три раза обращаются к генератору последовательсности.

Результаты выполнения примера

При выполнении примера в консоль будет выведена следующая информация :

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

Скачать примеры

Рассмотренный на странице пример использования атомарного класса в виде проекта Eclipse можно скачать здесь (7.41 Кб).

Источник

Модель памяти Java и атомарность операций (java memory model)

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

Рассмотрим такой программный код:

Переменную я объявил с модификатором volatile для того, чтобы гарантировать, что все потоки всегда будут видеть самое актуальное значение переменной.

При запуске на экран будут выводится числа 0 и 1. Естественно, так как значение переменной i в потоке попеременно инкрементируется и декрементируется.

Можно сделать предположение, что если раскомментировать первую строку метода main, то значение i будет принимать максимум 3 разных значения, например 0, 1 и 2.

На самом деле в System.out будет выводится что-то типа такого:

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

Исправить ошибку в коде помогает synchronized блок:

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

После исправления и запуска класса в консоли видим следующее:

Атомарность говорит о том, что некоторое действие (или их последовательность) должно происходить «все и сразу». Осутствие синхронизации может привести к катострофическим последствиям. Это далеко не NullPointerException, который можно обнаружить сразу. Программа может работать достаточно долго и визаульно никаких неполадок обнаружено не будет.

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

Чтобы гарантировать атомарность записи в long и double необходимо объявлять их как volatile.

Кстати, запись ссылки на объект (reference) всегда атомарна, не зависимо от того, имеем мы дело с 32-х или 64-х битной реализацией JVM.

В Java Memory Model рассказано много еще чего интересного, например о видимости (Visibility) и упорядоченности (Ordering). Но это уже совсем другая история.

Надеюсь, статья была вам интересна. В любом случае, жду ваших комментариев.

Источник

Введение в атомарные переменные в Java

Узнайте, как использовать атомарные переменные для решения проблем параллелизма.

1. введение

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

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

2. Замки

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

В случае однопоточной среды это работает идеально; однако, как только мы разрешаем писать более одного потока, мы начинаем получать противоречивые результаты.

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

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

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

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

3. Атомарные операции

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

Типичная операция CAS работает с тремя операндами:

Операция CAS атомарно обновляет значение в M до B, но только в том случае, если существующее значение в M совпадает с A, в противном случае никаких действий не предпринимается.

В обоих случаях возвращается существующее значение в M. Это объединяет три этапа – получение значения, сравнение значения и обновление значения – в одну операцию на уровне машины.

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

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

4. Атомарные переменные в Java

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

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

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

Источник

Многопоточное программирование в Java 8. Часть третья. Атомарные переменные и конкурентные таблицы

Авторизуйтесь

Многопоточное программирование в Java 8. Часть третья. Атомарные переменные и конкурентные таблицы

AtomicInteger

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

Как видите, использование AtomicInteger вместо обычного Integer позволило нам корректно увеличить число, распределив работу сразу по двум потокам. Мы можем не беспокоиться о безопасности, потому что incrementAndGet() является атомарной операцией.

Класс AtomicInteger поддерживает много разных атомарных операций. Метод updateAndGet() принимает в качестве аргумента лямбда-выражение и выполняет над числом заданные арифметические операции:

Среди других атомарных классов хочется упомянуть такие как AtomicBoolean, AtomicLong и AtomicReference.

LongAdder

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

LongAccumulator

ConcurrentMap

Интерфейс ConcurrentMap наследуется от обычного Map и предоставляет описание одной из самой полезной коллекции для конкурентного использования. Чтобы продемонстрировать новые методы интерфейса, мы будем использовать вот эту заготовку:

Если же вам нужно изменить таким же образом только один ключ, это позволяет сделать метод compute() :

ConcurrentHashMap

Это значение может быть специально изменено с помощью параметра JVM:

Для примеров ниже мы будем использовать всё ту же таблицу, что и выше (однако объявим её именем класса, а не интерфейса. чтобы нам были доступны все методы):

ForEach

Search

Или вот другой пример, который полагается только на значения:

Reduce

На этом всё. Надеюсь, мои статьи были вам полезны 🙂

Источник

Многопоточность в Java. Лекция 5: атомарные переменные и многопоточные коллекции

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

5.1 Атомарные переменные

Рассмотрим ситуацию, когда два или более потоков пытаются изменить общий разделяемый ресурс: одновременно выполнять операции чтения или записи. Для избежания ситуации race condition нужно использовать synchronized-методы, synchronized-блоки или соответствующие блокировки. Если этого не сделать, разделяемый ресурс будет в неконсистентном состоянии, и значение не будет иметь никакого смысла. Однако использование методов synchronized или synchronized-блоков кода — очень дорогостоящая операция, потому что получение и блокировка потока обходятся недешево. Также этот способ является блокирующим, он сильно уменьшает производительность системы в целом.

Для решения этой проблемы придумали так называемые неблокирующие алгоритмы — non blocking thread safe algorithms. Эти алгоритмы называются compare and swap(CAS) и базируются на том, что современные процессоры поддерживают такие операции на уровне машинных инструкций. С выходом Java 1.5 появились классы атомарных переменных: AtomicInteger AtomicLong, AtomicBoolean, AtomicReference. Они находятся в пакете java.util.concurrent.atomic. Алгоритм compare and swap работает следующим образом: есть ячейка памяти, текущее значение в ней и то значение, которое хотим записать в эту ячейку. Сначала ячейка памяти читается и сохраняется текущее значение, затем прочитанное значение сравнивается с тем, которое уже есть в ячейке памяти, и если значение прочитанное ранее совпадает с текущим, происходит запись нового значения. Следует упомянуть, что значение переменной после чтения может быть изменено другим потоком, потому что CAS не является блокирующей операцией.

5.2 Проблема ABA или lost update

Есть два потока. Поток А прочитал значение из памяти, после чего предположим, планировщик потока прервал выполнение потока А. Затем значение из памяти читает поток B, а потом меняет его на ДРУГОЕ несколько раз. Предположим, что изначально значение атомарной переменной было 5, потом 4, в конце оно снова стало равно 5. Получилось так, что поток B в последний раз записал то же значение, что было изначально, т. е. значение, которое было прочитано потоком А. Затем планировщик возобновляет работу потока А, тот сравнивает значение, которое изначально прочитал ( 5) с тем,что есть в памяти сейчас (тоже 5). Эти значения равны — выполняется операция CAS. Возникает такая ситуация, когда новое для системы значение, установленное потоком B (которые, кстати, было равно изначальному значению, которое мы наблюдали до начала работы потоков А и В), затирается старым значением, которое должен был установить поток А. Возникает закономерный вопрос: почему значение теряется? Ведь поток А не записал в память значение, которые он пытался записать, а вот когда планировщик потоков возобновил работу потока А, значение наконец записалось?

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

Возвращаясь к примеру про lost update: когда поток А получит управление и попытается выполнить CAS-операцию, значения памяти будут равны, а значения счетчиков равны не будут. Поэтому поток А опять прочитает значение из памяти и значение счетчика — и опять попытается выполнить CAS-операцию. Это будет происходить до тех пор пока CAS-операция не выполниться успешно. Однако и при использовании счетчика возникают определенные проблемы, рассмотрение которых выходит за рамки нашего цикла статей. На практике сейчас используется алгоритм safe memory reclamation (SMR).

Рассмотрим, как работает класс AtomicLong (Листинги 1, 2 и 3).

Листинг 1: класс AtomicLong:

public final long getAndAdd(long delta) <
return unsafe.getAndAddLong(this, valueOffset, delta);
>

Здесь видно, что выполнение делегируется классу Unsafe.

Листинг 2: класс Unsafe:

public final long getAndAddLong(Object object, long offset, long newValue) <
long oldValue;
do <
oldValue = this.getLongVolatile(object, offset);
> while(!this
.compareAndSwapLong(object, offset, oldValue, oldValue + newValue));
return oldValue;
>

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

Листинг 3: класс AtomicLong. Получение смещения поля value в объекте AtomicLong.

static <
try <
valueOffset = unsafe
.objectFieldOffset(AtomicLong.class.getDeclaredField(«value»));
> catch (Exception ex) <
throw new Error(ex);
>
>

5.3 Многопоточные коллекции

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

В Java есть коллекции, которые предназначены для использования в многопоточной среде. Они реализуют разные механизмы синхронизации данных. До выхода Java 1.5 в наличии были следующие многопоточные коллекции: Stack, Vector, HashTable. Все методы этих классов являются synchronized. Это означает, что при вызове любого метода этих классов другой поток будет заблокирован, даже если вызванный метод — метод чтения. Эти коллекции появились еще с версией Java 1 и в современной разработке их не стоит использовать. C выходом Java 1.2 появился утилитный класс Collections, который предоставляет статические методы для оборачивания стандартных коллекций в их синхронизированные представления. Это сделано для совместимости с Java версией 1.

После релиза Java 1.5, 1.6 и 1.7 появилась возможность использовать следующие классы коллекций, которые предназначены и оптимизированы для работы в многопоточной среде:

Первые две коллекции — copy on write структуры. Третья коллекция — skip list структура. Следующие две коллекции — классы Map, предназначенные для использования в многопоточных программах. Использование классов этих коллекций позволяет увеличить производительность программы по сравнению с использованием устаревших классов из Java 1. Рассмотрим статические методы утилитарного класса Collections.

5.4 Статические методы из класса Collections

Статические методы для работы с многопоточностью в классе Collections:

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

5.5 Copy On Write структуры данных

CopyOnWriteArrayList используется, когда есть много потоков, которые читают элементы из коллекции, и несколько потоков, которые редко записывают данные в коллекцию. Copy on write структура создает новую копию данных при записи в эту структуру. Это позволяет нескольким потокам одновременно читать данные, и одному потоку записывать элементы в коллекцию в каждый конкретный момент времени. Внутри структура данных содержит volatile массив элементов и при КАЖДОМ изменении коллекции: добавлении, удалении или замене элементов, создается новая локальная копия массива для изменений. После модификации измененная копия массива становится текущей. Массив элементов используется с ключевым словом volatile для того, чтобы все потоки сразу увидели изменения в массиве. Такой алгоритм работы с данными гарантирует, что читающие потоки будут читать не изменяющиеся во времени данные, и не будет сгенерирован ConcurrentModificationException при параллельном изменение массива. Если для чтения коллекции используется Iterator, при попытке вызвать remove() при обходе коллекции будет сгенерировано UnsupportedOperationException, потому что текущая копия коллекции не подлежит изменению. Для операций записи внутри класса CopyOnWriteArrayList создается блокировка, чтобы в конкретный момент времени только один поток мог изменять copy on write структуру данных (Листинг 1). Пример добавления элемента представлен в Листинге 4.

Листинг 4:

final ReentrantLock lock = new ReentrantLock();
public boolean add(E e) <
lock.lock();
try <
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
> finally <
lock.unlock();
>
>

Без блокировки наличие нескольких потоков, изменяющих структуру данных, могут привести к потере данных, записываемых потоками. Несколько потоков делают копию исходного массива данных, вносят изменения и записывают их. Какой-то из потоков завершает работу быстрее, какой-то — медленнее. Поток, который завершит свою работу последним, удалит изменения, сделанные другими потоками. С использованием блокировки ReentrantLock такая проблема исчезает. Рассмотрим программу из Листинга 5, которая показывает, что чтение элементов из CopyOnWriteArrayList происходит быстрее, чем чтение из полностью синхронизированной коллекции, либо коллекции, которая обернута соответствующим статическим методом из класса Collections.

Листинг 5:

import java.util.*;
public class PerformanceComparision <
public static void main(String[] args)
throws ExecutionException, InterruptedException <
List syncList = Collections.synchronizedList(new ArrayList<>());
List cowLst = new CopyOnWriteArrayList<>();
fillLst(syncList);
fillLst(cowLst);
System.out.println(«List synchronized:»);
checkList(syncList);
System.out.println(«CopyOnWriteArrayList:»);
checkList(cowLst);
>
private static void fillLst(List list) <
IntStream.rangeClosed(1, 100).forEach(list::add);
>
private static void checkList(List list)
throws ExecutionException, InterruptedException <
CountDownLatch latch = new CountDownLatch(1);
ExecutorService executors = Executors.newFixedThreadPool(2);
Future f1 = executors.submit(new ListRunner(latch, 0, 49, list));
Future f2 = executors.submit(new ListRunner(latch, 50, 99, list));
executors.shutdown();
latch.countDown();
System.out.println(«Thread1: » + f1.get()/1000);
System.out.println(«Thread2: » + f2.get()/1000);
>
>

public class ListRunner implements Callable <
private CountDownLatch latch;
private int start;
private int end;
private List list;
public ListRunner(CountDownLatch latch, int start, int end, List list) <
this.latch = latch;
this.start = start;
this.end = end;
this.list = list;
>
@Override
public Long call() throws Exception <
latch.await();
Integer integer;
long startTime = System.nanoTime();
for (int i = start; i

Реализация ConcurrentSkipListSet базируется на ConcurrentSkipListMap, структура ConcurrentSkipListSet похожа на структуру LinkedHashMap. Каждый элемент skip list структуры, кроме значения, содержит ссылку на соседние элементы. Также есть ссылки высших порядков, которые указывают на элементы, находящиеся впереди текущего, на произвольное число в определенном диапазоне, заданном для этого уровня ссылок. Для следующего уровня ссылок это число больше, чем для предыдущего.

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

5.7 Интерфейс BlockingQueue

BlockingQueue — интерфейс потокобезопасных очередей, в которую несколько потоков могут записывать данные и читать их оттуда. Это достигается за счет способности очереди блокировать поток, который добавляет или читает элементы из очереди. Например, когда поток пытается получить элемент из очереди, но очередь пустая — поток блокируется. Или когда поток пытается положить объект в очередь, которая уже заполнена, поток тоже блокируется.

Блокирующие очереди используются, когда одни потоки добавляют элементы в очередь, а другие читают их оттуда. Этот паттерн известен как producer consumer. Потоки, которые добавляют объекты в очередь, называются producer (Производитель). Добавлять элементы в очередь можно до тех пор, пока она не заполнится. Потоки которые читают значения, называются consumer (Потребитель). Читать из очереди можно только в случаях, когда в ней есть элементы.

BlockingQueue хранит свои элементы по принципу FIFO. Элементы отсортированы по времени нахождения в очереди, а голова находится там дольше всех остальных.

BlockingQueue не поддерживает значение null, при попытке вставить его генерируется NullPointerException.

Интерфейс BlockingQueue поддерживает четыре наборов методов, которые поддерживают разное поведение при добавлении или получении элементов из очереди.

Источник