Атомарные операции в Java
Давай разберем данный пример, который поможет понять работу атомарных операций:
public class Counter < int count; public void increment() < count++; >>
Когда у нас один поток, все работает классно, но если мы добавляем многопоточку, то получаем неправильные результаты, а все из-за того, что операция инкремента составляет не одну операцию, а три: запрос на получение текущего значения count , потом увелечение ее на 1 и запись снова в count .
И когда два потока захотят увеличить переменную, скорее всего, ты потеряешь данные. То есть оба потока получают 100, в результате оба запишут 101 вместо ожидаемого значения 102.
И как же это решить? Нужно использовать блокировки. Ключевое слово synchronized помогает решить данную проблему, использование этого слова дает вам гарантию, что один поток будет обращаться к методу единовременно.
public class SynchronizedCounterWithLock < private volatile int count; public synchronized void increment() < count++; >>
Плюс надо добавлять ключевое слово volatile , которое обеспечивает корректную видимость ссылок среди потоков. Мы разбирали его работу выше.
Но все же есть минусы. Самый большой — это производительность, в тот момент времени, когда много потоков пытаются получить блокировку и один получает возможность для записи, остальные потоки будут или заблокированы, или приостановлены до момента освобождения потока.
Все эти процессы, блокировка, переход в другой статус — очень дороги для производительности системы.
Атомарные операции
Алгоритм использует низкоуровневые машинные инструкции, такие как сравнение и замена (CAS, compare-and-swap, что обеспечивает целостность данных и по ним уже существует большое количество исследований).
Типичная операция CAS работает с тремя операндами:
- Место в памяти для работы (M)
- Существующее ожидаемое значение (A) переменной
- Новое значение (B), которое необходимо установить
CAS атомарно обновляет M до B, но только если значение M совпадает с A, в противном случае никаких действий предприниматься не будет.
В первом и втором случае вернут значение М. Это позволяет объединить три шага, а именно — получение значения, сравнение значения и его обновление. И это все превращается в одну операцию на машинном уровне.
В тот момент времени, когда многопоточное приложение обращается к переменной и пытается обновить его и применяется CAS, то один из потоков получит его и сможет обновить его. Но в отличии от блокировок, другие потоки просто получат ошибки о том, что им не удалось обновить значение. Потом они перейдут к дальнейшей работе, а переключение полностью исключено при таком типе работе.
При этом логика становится труднее из-за того, что мы должны обработать ситуацию, когда операция CAS не отработала успешно. Мы просто смоделируем код таким образом, чтобы он не двигался дальше, пока операция не произойдет успешно.
Знакомство с атомарными типами
Ты столкнулся с ситуацией, когда тебе нужно настроить синхронизацию для самой простой переменной типа int ?
Первый способ, который мы уже разобрали – это использование volatile + synchronized . Но есть еще специальные классы Atomic*.
Если у нас используется CAS, то операции работают быстрее по сравнению с первым способом. И в дополнение у нас есть специальные и очень удобные методы для добавления значения и операции инкремента и декремента.
AtomicBoolean , AtomicInteger , AtomicLong , AtomicIntegerArray , AtomicLongArray —классы в которых операции атомарны. Ниже мы разберем работу с ними.
AtomicInteger
Класс AtomicInteger предоставляет операции с значением int , которые могут быть прочитаны и записаны атомарно, в дополнение содержит расширенные атомарные операции.
У него есть методы get и set , которые работают, как чтение и запись по переменным.
То есть “происходит до (happens-before)” с любым последующим получением той же переменной, о которой мы говорили ранее. У атомарного метода compareAndSet также есть эти особенности согласованности памяти.
Все операции, которые возвращают новое значение, выполняются атомарно:
| int addAndGet (int delta) | Добавляет определенное значение к текущему значению. |
| boolean compareAndSet (ожидаемое int, обновление int) | Устанавливает значение для данного обновленного значения, если текущее значение совпадает с ожидаемым значением. |
| int decrementAndGet () | Уменьшает на единицу текущее значение. |
| int getAndAdd (int delta) | Добавляет данное значение к текущему значению. |
| int getAndDecrement () | Уменьшает на единицу текущее значение. |
| int getAndIncrement () | Увеличивает на единицу текущее значение. |
| int getAndSet (int newValue) | Устанавливает заданное значение и возвращает старое значение. |
| int incrementAndGet () | Увеличивает на единицу текущее значение. |
| lazySet (int newValue) | В конце-концов устанавливается на заданное значение. |
| boolean weakCompareAndSet (ожидаемое, обновление int) | Устанавливает значение для данного обновленного значения, если текущее значение совпадает с ожидаемым значением. |
ExecutorService executor = Executors.newFixedThreadPool(5); IntStream.range(0, 50).forEach(i -> executor.submit(atomicInteger::incrementAndGet)); executor.shutdown(); executor.awaitTermination(Long.MAX_VALUE, TimeUnit.HOURS); System.out.println(atomicInteger.get()); // выведет 50
Атомарные и неатомарные операции (java)
Операция в общей области памяти называется атомарной, если она завершается в один шаг относительно других потоков, имеющих доступ к этой памяти. Во время выполнения такой операции над переменной, ни один поток не может наблюдать изменение наполовину завершенным. Атомарная загрузка гарантирует, что переменная будет загружена целиком в один момент времени. Неатомарные операции не дают такой гарантии.
Т.е. как я поняла, атомарные операции — это достаточно мелкие, выполняющиеся «за один шаг относительно других потоков». Но что значит этот «шаг»? Один шаг == одной машинной операции? Или чему-то другому? Как определить точно, какие операции относятся к атомарным, а какие к неатомарным? P.S.: Я нашла похожий вопрос, но там речь идёт о C#.
Отслеживать
задан 18 янв 2017 в 10:01
10.7k 6 6 золотых знаков 47 47 серебряных знаков 98 98 бронзовых знаков
@Ksenia я не обладаю достаточной квалификацией для того, чтобы дать ее самостоятельно, но в википедии приводится следующая формулировка (хоть она и туманна): an operation (or set of operations) is atomic, linearizable, indivisible or uninterruptible if it appears to the rest of the system to occur instantaneously.. Попробую не забыть накатать вечером свой ответ.
18 янв 2017 в 10:38
Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
29 янв 2017 в 8:34
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Как можно определить атомарность?
Атомарность операции чаще всего принято обозначать через ее признак неделимости: операция может либо примениться полностью, либо не примениться вообще. Хорошим примером будет запись значений в массив:
public class Curiousity < public volatile int[] array; public void nonAtomic() < array = new int[1]; array[0] = 1; >public void probablyAtomic() < array = new int[] < 1 >; > > При использовании метода nonAtomic существует вероятность того, что какой-то поток обратится к array[0] в тот момент, когда array[0] не проинициализирован, и получит неожиданное значение. При использовании probablyAtomic (при том условии, что массив сначала заполняется, а уже потом присваивается — я сейчас не могу гарантировать, что в java это именно так, но представим, что это правило действует в рамках примера) такого быть не должно: array всегда содержит либо null, либо проинициализированный массив, но в array[0] не может содержаться что-то, кроме 1. Эта операция неделима, и она не может примениться наполовину, как это было с nonAtomic — только либо полностью, либо никак, и весь остальной код может спокойно ожидать, что в array будет либо null, либо значения, не прибегая к дополнительным проверкам.
Кроме того, под атомарностью операции зачастую подразумевают видимость ее результата всем участникам системы, к которой это относится (в данном случае — потокам); это логично, но, на мой взгляд, не является обязательным признаком атомарности.
Почему это важно?
Атомарность зачастую проистекает из бизнес-требований приложений: банковские транзакции должны применяться целиком, билеты на концерты заказываться сразу в том количестве, в котором были указаны, и т.д. Конкретно в том контексте, который разбирается (многопоточность в java), задачи более примитивны, но произрастают из тех же требований: например, если пишется веб-приложение, то разбирающий HTTP-запросы сервер должен иметь очередь входящих запросов с атомарным добавлением, иначе есть риск потери входящих запросов, а, следовательно, и деградация качества сервиса. Атомарные операции предоставляют гарантии (неделимости), и к ним нужно прибегать, когда эти гарантии необходимы.
Кроме того, атомарные операции линеаризуемы — грубо говоря, их выполнение можно разложить в одну линейную историю, в то время как просто операции могут производить граф историй, что в ряде случаев неприемлимо.
Почему примитивные операции не являются атомарными сами по себе? Так же было бы проще для всех.
Современные среды исполнения очень сложны и имеют на борту некислый ворох оптимизаций, которые можно сделать с кодом, но, в большинстве случаев, эти оптимизации нарушают гарантии. Так как большинство кода этих гарантий на самом деле не требует, оказалось проще выделить операции с конкретными гарантиями в отдельный класс, нежели наоборот. Чаще всего в пример приводят изменение порядка выражений — процессор и JVM имеют право выполнять выражения не в том порядке, в котором они были описаны в коде, до тех пор, пока программист не будет форсировать определенный порядок выполнения с помощью операций с конкретными гарантиями. Также можно привести пример (не уверен, правда, что формально корректный) с чтением значения из памяти:
thread #1: set x = 2 processor #1: save_cache(x, 2) processor #1: save_memory(x, 2) thread #2: set x = 1 processor #2: save_cache(x, 1) processor #2: save_memory(x, 1) thread #1: read x processor #1: read_cache(x) = 2 // в то время как х уже был обновлен значением 1 в thread #2 Здесь не используется т.н. single source of truth для того, чтобы управлять значением Х, поэтому возможны такие аномалии. Насколько понимаю, чтение и запись напрямую в память (или в память и в общий кэш процессоров) — это как раз то, что форсирует модификатор volatile (здесь могу быть неправ).
Конечно, оптимизированный код выполняется быстрее, но необходимые гарантии никогда не должны приноситься в жертву производительности кода.
Это относится только к операциям связанным с установкой переменных и прочей процессорной сфере деятельности?
Нет. Любая операция может быть атомарной или неатомарной, например, классические реляционные базы данных гарантируют, что транзакция — которая может состоять из изменений данных на мегабайты — либо применится полностью, либо не будет применена. Процессорные инструкции здесь не имеют никакого отношения; операция может быть атомарной до тех пор, пока она является атомарной сама по себе или ее результат проявляется в виде другой атомарной операции (например, результат транзакции базы данных проявляется в записи в файл).
Кроме того, насколько понимаю, утверждение «инструкция не успела за один цикл — операция неатомарна» тоже неверно, потому что есть некоторые специализированные инструкции, и никто не мешает атомарно устанавливать какое-либо значение в памяти на входе в защищенный блок и снимать его по выходу.
Любая ли операция может быть атомарной?
Нет. Мне очень сильно не хватает квалификации для корректных формулировок, но, насколько понимаю, любая операция, подразумевающая два и более внешних эффекта (сайд-эффекта), не может быть атомарной по определению. Под сайд-эффектом в первую очередь подразумевается взаимодействие с какой-то внешней системой (будь то файловая система или внешнее API), но даже два выражения установки переменных внутри synchronized-блока нельзя признать атомарной операцией, пока одно из них может выкинуть исключение — а это, с учетом OutOfMemoryError и прочих возможных исходов, может быть вообще невозможно.
У меня операция с двумя и более сайд-эффектами. Могу ли я все-таки что-нибудь с этим сделать?
Да, можно создать систему с гарантией применения всех операций, но с условием, что любой сайд-эффект может быть вызван неограниченное число раз. Вы можете создать журналируемую систему, которая атомарно записывает запланированные операции, регулярно сверяется с журналом и выполняет то, что еще не применено. Это можно представить следующим образом:
client: journal.push , reserveTicket , sendEmail > client: journal: process withdrawMoney journal: markCompleted withdrawMoney journal: process reserveTicket journal: journal: journal: process reserveTicket # сайд-эффект вызывается еще раз, но только в случае некорректной работы journal: markCompleted reserveTicket journal: process sendEmail journal: markCompleted sendEmail Это обеспечивает прогресс алгоритма, но снимает все обязательства по временным рамкам (с которыми, формально говоря, и без того не все в порядке). В случае, если операции идемпотентны, подобная система будет рано или поздно приходить к требуемому состоянию без каких-либо заметных отличий от ожидаемого (за исключением времени выполнения).
Как все-таки определить атомарность операций в java?
Первичный источник правды в этом случае — это Java Memory Model, которая определяет, какие допущения и гарантии применяются к коду в JVM. Java Memory Model, впрочем, довольно сложна для понимания и покрывает значительно большую сферу операций, нежели сфера атомарных операций, поэтому в контексте этого вопроса достаточно знать, что модификатор volatile обеспечивает атомарное чтение и запись, а классы Atomic* позволяют производить compare-and-swap операции, чтобы атомарно менять значения, не боясь, что между чтением и записью придет еще одна чья-то запись, а в комментариях ниже на момент прочтения наверняка добавили еще что-то, что я забыл.
Понимание атомарности в программировании
Атомарность — одно из ключевых понятий в программировании, особенно в контексте многопоточности.
Часто возникают ситуации, когда несколько потоков пытаются одновременно изменить значение одной и той же переменной. Если это происходит без какого-либо контроля, результат может быть непредсказуемым и привести к ошибкам. Например, один поток может прочитать значение переменной, затем другой поток может изменить это значение, а затем первый поток может записать обратно старое значение, тем самым перезаписывая изменения, сделанные вторым потоком.
Вот пример такой ситуации на псевдокоде:
thread1: x = read(variable) x = x + 1 write(variable, x) thread2: y = read(variable) y = y * 2 write(variable, y) Если эти два потока выполняются одновременно и без синхронизации, исходное значение переменной может быть случайно перезаписано одним из потоков, что приведет к неверному итоговому значению.
Здесь и вступает в игру понятие атомарности. Операция считается атомарной, если она выполняется как единое целое без возможности прерывания. Это означает, что если операция является атомарной, она либо полностью выполняется, либо не выполняется вовсе, и никакие другие операции не могут вмешаться в ее выполнение.
В контексте Java, чтение или запись переменной является атомарной операцией, за исключением переменных типа long или double . Это означает, что когда поток читает или записывает значение такой переменной, никакой другой поток не может вмешаться в эту операцию. Это помогает предотвратить вышеупомянутые проблемы с многопоточностью.
Однако стоит помнить, что атомарность операции чтения или записи не гарантирует атомарность более сложных операций, таких как инкрементирование. Для обеспечения атомарности таких операций необходимо использовать специальные синхронизационные механизмы, такие как блокировки или атомарные переменные.
Atomic operations
Атомарные операции — операции, выполняющиеся как единое целое либо не выполняющиеся вовсе. Т. е. это операция, во время исполнения которой данные, читаемые/изменяемые этой операцией не могут быть изменены другой операцией. Есть специальные ассемблерные команды, которые указывают процессору, что операция будет атомарной. Есть несколько типов команд, с помощью которых можно добиться атомарности: load-link and store-conditional (LL/SC), compare-and-swap (CAS) и другие.
1. LL/SC
Примеры команд LL/SC:
ldl_l/stl_c и ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).
Команды даны парами, т. к. первая загружает текущее значение операнда в регистр или другое контролируемое место, вторая сохраняет новое значение в операнд, если операнд за промежуток между 1-ой и 2-ой не изменился. Вместе они гарантируют, что все команды между ними работают с одной версией операнда, которая была загружена с помощью LL. Для примера возьмем пару lwarx/stwcx (PowerPC):
void atomic_incr(int * operand, int incr) < asm volatile ( "loop:\n\t" /* repeat until this succeeds */ "lwarx 6,0,%0\n\t" /* reserve the operand */ "add 6,6,%1\n\t" /* add incr to it */ "stwcx. 6,0,%0\n\t" /* put the sum back, and release it */ "bne- loop" /* start-over on failure */ : : "r" (operand), "r" (incr) : "r6" ); >Код взят отсюда.
В 6-ой регистр загружаются данные из операнда и он(операнд) резервируется. Потом в 6-ом регистре получаем сумму операнда и incr. В конце выгружаем из регистра полученную сумму в операнд и отпускаем его. Если в промежуток между резервированием и освобождением операнда его значение будет изменено где-то еще помимо текущей операции(даже если было присвоено тоже самое значение, которое уже хранилось в операнде), то мы получим ошибку. Это проверяет 5-я строка, запускающая операцию снова в случае ошибки.
Ассемблерные параметры gcc
2. CAS
Принцип работы простой — смотрим, какое значение хранится в операнде. Если оно то, какое мы ожидаем, то меняем его на новое.
Алгоритм:
int compare_and_swap (int* reg, int oldval, int newval)
Расширение CAS — Double Compare And Swap (CAS2). Даются указатели на две независимые переменные вместо одной, соответственно, два ожидаемых значения и два новых значения для каждой переменной соответственно.
Но эта группа команд более «слабая», чем LL/SC, т. к. возможна ситуация:
начальные условия: compare_and_swap( reg, 5, 7 ) и *reg = 5;
1) int old_reg_val = *reg; (old_reg_val = 5)
2) другая операция делает *reg = 42; funny_stuff; *reg = 5;
3) if (old_reg_val == oldval) — утверждение верно, хотя произошло два изменения значения переменной. Т. е. произошло изменение, но наша операция об этом не знает. Эта ситуация называется ABA problem.
Есть много методов обхода этой проблемы. Мне показался интересным метод с использованием Double-Word Compare-And-Swap (часто путается с Double Compare And Swap).
Пример:
/* double-compare-and-swap: atomically sets the two-word data at address @mem * to the two-word value of @new if value at @mem * equals @old * @mem: pointer to value * @old: old value * @new: new value * * returns: 0 on failure, non-zero on success */ static inline char DWCAS(volatile DWORD *mem, DWORD old, DWORD new) < char r = 0; unsigned long old_h = old >> SHIFT, old_l = old; unsigned long new_h = new >> SHIFT, new_l = new; __asm__ __volatile__("lock; " CMPXCHGxB " (%6);" "setz %7; " : "=a" (old_l), "=d" (old_h) : "0" (old_l), "1" (old_h), "b" (new_l), "c" (new_h), "r" (mem), "m" (r) : "cc", "memory"); return r; >Код взят отсюда.
Префикс «lock;» означает, что шина доступа к памяти может быть использована только следующей за ней командой.
В передаваемом слове содержится указатель на память с требуемым значением и ABA номер, который изменяется с каждой операцией (увидел это в одном из патентов).
3. Простые атомарные операции.
Обычно это сложение или инкрементация.
Примеры команд: addl(i386), xaddl(x86).
Вот реализация атомарного сложения из википедии:
void atomic_add(int * operand, int incr) < asm volatile ( "lock; xaddl %1, (%0)\n" // add incr to operand : // no output : "r" (operand), "r" (incr) ); >На некоторых архитектурах префикс «lock;» не нужна. Пример — инкрементирование на Итаниуме (взят отсюда):
void atomic_oneup(int * operand) < uint64_t res; // this MUST be 64 bits asm volatile ( "fetchadd4.rel %0=%1,%2" : "=r" (res) : "m" (*operand), "i" (1) : "memory" ); >Кстати, инкремент, декремент, +=, -= в С++ атомарные (по крайней мере на х86 и х86_64). Префикса «lock;» нет, так что атомарности тоже нет. Атомарные операции появились в С++11.
int a =0; ++a;компилируется в
c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp) 83 45 fc 01 addl $0x1,-0x4(%rbp)Для декремента будет subl.
Заключение
Q: Это известно каждому школьнику! Зачем об этом писать?
A: Мне было интересно, как же оно работает. Представлял только, что там есть какие-то lock’и. Надеюсь, это было интересно еще кому-то.
Q: В статье куча ошибок и неточностей.
A: Пишите, с радостью исправлю.
Q: Что? Уже заключение? Где сама статья? Где MSI, Cache Coherence и %еще_куча_умных_слов%?
A: Я не копал глубоко. Надеюсь, об этом напишут люди, которые знают эти темы.
UPD: За исправления спасибо lesha_penguin и TheShade.