1. CAS
CAS:Compare and Swap, что переводится как «Сравнить и поменять местами».
java.util.concurrentПакет реализует отличие от CAS с помощью CASsynchronouseОптимистическая блокировка для блокировок синхронизации.
Эта статья начинается с применения CAS, а затем переходит к основному анализу.
2. Приложение КАС
CAS имеет 3 операнда: значение памяти V, старое ожидаемое значение A и новое значение B, которое необходимо изменить. Измените значение памяти V на B тогда и только тогда, когда ожидаемое значение A и значение памяти V совпадают, в противном случае ничего не делайте.
2.1 Неблокирующие алгоритмы
Сбой или приостановка одного потока не должны влиять на алгоритм отказа или приостановки других потоков.
Современные процессоры предоставляют специальные инструкции для автоматического обновления общих данных и обнаружения помех со стороны других потоков.compareAndSet()Используйте их вместо блокировки.
выигратьAtomicIntegerИзучим, как добиться корректности данных без блокировок.
private volatile int value;
Во-первых, нет никакой идеи о том, что volatile-примитивы могут понадобиться для обеспечения того, чтобы данные между потоками были видны (разделялись) без механизма блокировки.
Только таким образом вы можете напрямую прочитать значение переменной.
public final int get() {
return value;
}
Тогда давайте посмотрим, как это делает ++i.
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
}
Здесь используется операция CAS, каждый раз данные считываются из памяти и затем над этими данными выполняется операция CAS и результат после +1, в случае успеха возвращается результат, в противном случае повторяется попытка до успеха.
а такжеcompareAndSetИспользуйте JNI для завершения работы инструкций ЦП.
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
Общий процесс выглядит следующим образом: используется инструкция CAS ЦП и используется JNI для завершения неблокирующего алгоритма Java. Другие атомарные операции выполняются с аналогичными свойствами.
в
unsafe.compareAndSwapInt(this, valueOffset, expect, update);
аналогичный:
if (this == expect) {
this = update
return true;
} else {
return false;
}
Тогда возникает вопрос, в успешном процессе требуется 2 шага: сравнитьthis == expect,заменятьthis = update,
compareAndSwapIntКак насчет атомарности этих двух шагов? Обратитесь к принципу CAS.
3. Принцип КАС
CAS реализуется путем вызова кода JNI.JNI:Java Native InterfaceДля собственного вызова JAVA, позволяющего java вызывать другие языки.
а такжеcompareAndSwapIntЭто достигается вызовом низкоуровневых инструкций ЦП с помощью языка C.
Далее объясняется принцип реализации CAS на основе анализа наиболее часто используемого процессора (intel x86).
Нижеsun.misc.UnsafeКатегорияcompareAndSwapInt()Исходный код метода:
public final native boolean compareAndSwapInt(Object o, long offset,
int expected,
int x);
Вы можете видеть, что это нативный вызов метода. Код С++, который этот собственный метод вызывает в свою очередь в openjdk:unsafe.cpp,atomic.cppа такжеatomic*windows*x86.inline.hpp. Окончательная реализация этого нативного метода находится в следующем месте openjdk:openjdk-7-fcs-src-b147-27*jun*2011\openjdk\hotspot\src\os*cpu\windows*x86\vm\ atomic*windows*x86.inline.hpp(соответствует операционной системе Windows, процессору X86). Ниже приведен фрагмент исходного кода, соответствующий процессору Intel x86:
// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
__asm je L0 \
__asm _emit 0xF0 \
__asm L0:
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
// alternative for InterlockedCompareExchange
int mp = os::is_MP();
__asm {
mov edx, dest
mov ecx, exchange_value
mov eax, compare_value
LOCK_IF_MP(mp)
cmpxchg dword ptr [edx], ecx
}
}
Как показано в исходном коде выше, программа решает, добавлять ли префикс блокировки к инструкции cmpxchg в зависимости от типа текущего процессора. Если программа работает на нескольких процессорах, поставьте перед командой cmpxchg префикс блокировки (lock cmpxchg). И наоборот, если программа выполняется на однопроцессорном процессоре, префикс блокировки опускается (сам однопроцессорный процессор поддерживает последовательную согласованность внутри однопроцессорного процессора и не требует эффекта барьера памяти, обеспечиваемого префиксом блокировки).
Руководство Intel описывает префикс блокировки следующим образом:
- Гарантирует, что операции чтения-изменения-записи в память выполняются атомарно. существуетPentiumа такжеPentiumВ предыдущих процессорах инструкции с префиксом блокировки блокировали шину во время выполнения, делая временно невозможным доступ других процессоров к памяти через шину. Очевидно, что это приведет к дорогостоящим накладным расходам. Начиная с процессоров Pentium 4, Intel Xeon и P6, Intel провела значительную оптимизацию, основанную на оригинальной блокировке шины:area of memory) был заблокирован во внутреннем кэше процессора во время выполнения инструкции префикса блокировки (т. е. строка кэша, содержащая область памяти, в данный момент находится в монопольном или измененном состоянии), а область памяти полностью содержится в одной строке кэша (cache line), то процессор выполнит инструкцию напрямую. Поскольку строка кэша всегда блокируется во время выполнения инструкции, другие процессоры не могут читать/записывать область памяти, к которой будет обращаться инструкция, поэтому атомарность выполнения инструкции может быть гарантирована. Эта операция называется блокировкой кэша (cache locking), блокировка кеша значительно уменьшит накладные расходы на выполнение инструкций с префиксом блокировки, но шина все равно будет заблокирована, когда уровень конкуренции между несколькими процессорами высок или адреса памяти, к которым обращаются инструкции, не выровнены.
- Изменение порядка этой инструкции с предыдущими и последующими инструкциями чтения и записи отключено.
- Сбросить все данные из буфера записи в память.
Примечания знания:
Существует три типа блокировки процессора:
1. Процессор автоматически гарантирует атомарность основных операций с памятью
Во-первых, процессор автоматически гарантирует атомарность основных операций с памятью. Процессор гарантирует, что чтение или запись байта из системной памяти является атомарным, а это означает, что когда один процессор читает байт, другие процессоры не могут получить доступ к адресу памяти этого байта. Pentium 6 и более новые процессоры автоматически гарантируют атомарность для 16/32/64-битных операций в одной и той же строке кэша одним процессором, но процессоры для сложных операций с памятью, например, для разных размеров шины, не могут автоматически гарантировать атомарность для нескольких строк кэша. через доступ к таблице страниц. Однако процессор предоставляет два механизма, блокировку шины и блокировку кэша, чтобы обеспечить атомарность сложных операций с памятью.
2. Используйте блокировки шины для обеспечения атомарности
Первый механизм — гарантировать атомарность с помощью блокировок шины. Если несколько процессоров читают и записывают общую переменную одновременно (i++ — это классическая операция чтения-записи), то общая переменная будет обрабатываться несколькими процессорами одновременно, поэтому операция чтения-записи не является атомарной, а общая переменная разделяется после операции Значение переменной будет несовместимо с ожидаемым значением, например: если i=1, мы делаем две операции i++, мы ожидаем, что результат будет 3, но результат может быть 2 . Как показано ниже
Причина в том, что возможно, что несколько процессоров одновременно считывают переменную i из своих соответствующих кэшей, добавляют по одной к каждому, а затем записывают их в системную память по отдельности. Затем, если вы хотите, чтобы операция чтения, изменения и записи общей переменной была атомарной, вы должны убедиться, что, когда CPU1 читает и записывает общую переменную, CPU2 не может использовать кэш, который кэширует адрес памяти общей переменной.
Процессор использует блокировки шины для решения этой проблемы. Так называемая блокировка шины заключается в использовании сигнала **LOCK#**, предоставляемого процессором.Когда процессор выводит этот сигнал на шину, запросы других процессоров будут заблокированы, тогда процессор может использовать только общую память. .
3. Используйте блокировки кеша для обеспечения атомарности
Второй механизм — гарантировать атомарность за счет блокировки кеша. В то же время нам нужно только обеспечить атомарность работы определенного адреса памяти, но блокировка шины блокирует связь между ЦП и памятью, что делает другие процессоры неспособными оперировать данными других адресов памяти во время работы. Таким образом, накладные расходы на блокировку шины относительно велики, и современные процессоры в некоторых случаях используют блокировку кэша вместо блокировки шины для оптимизации.
Часто используемая память кэшируется в кэшах L1, L2 и L3 процессора, поэтому атомарные операции могут выполняться непосредственно во внутреннем кэше процессора без объявления блокировки шины, что возможно в процессорах Pentium 6 и более поздних. добиться сложной атомарности. Так называемая «блокировка кеша» означает, что если кеш находится в строке кеша процессора, то область памяти находится вLOCKблокируется во время операции, когда он выполняет операцию блокировки для обратной записи в память, процессор не устанавливает сигнал LOCK#** на шине, а вместо этого изменяет адрес внутренней памяти и позволяет механизму когерентности кэша гарантировать атомарность операции Поскольку механизм когерентности кэша предотвратит одновременное изменение данных области памяти, кэшированной двумя или более процессорами, когда другие процессоры записывают обратно данные заблокированной строки кэша, строка кэша становится недействительной. В примере 1, когда CPU1 использует блокировку кэша при изменении i в строке кэша, CPU2 не может одновременно кэшировать строку кэша i.
Но есть два случая, когда процессор не будет использовать блокировку кеша. Во-первых, когда обрабатываемые данные не могут кэшироваться внутри процессора или обрабатываемые данные занимают несколько строк кэша (cache line), процессор вызывает блокировку шины. Второй случай: некоторые процессоры не поддерживают блокировку кеша. Для процессоров Inter486 и Pentium блокировка шины вызывается, даже если заблокированная область памяти находится в строке кэша процессора.
Мы можем реализовать два вышеупомянутых механизма с помощью инструкций, предоставляемых процессором Inter с большим количеством префиксов LOCK. Например, инструкции битовой проверки и модификации BTS, BTR, BTC, инструкции обмена XADD, CMPXCHG и некоторые другие операнды и логические инструкции, такие как ADD (добавить), OR (или) и т. д., область памяти, управляемая этими инструкциями, будет быть заблокирован, Заставляет другие процессоры не иметь доступа к нему в то же время.
4. Недостатки CAS
Хотя CAS очень эффективно решает атомарные операции, у CAS все еще есть три основные проблемы. Проблема ABA, длительное время цикла и высокие накладные расходы, а также гарантируют атомарные операции только с одной общей переменной.
4.1 Проблема АВА
Поскольку CAS необходимо проверить, изменилось ли значение при работе со значением, и обновить его, если изменений нет, но если значение изначально было A, стало B, а затем стало A, то при использовании CAS для проверки вы обнаружите что Его значение не изменилось, но на самом деле изменилось. Решение проблемы ABA заключается в использовании номера версии. Добавьте номер версии перед переменной и добавляйте единицу к номеру версии каждый раз, когда переменная обновляется, тогда A-B-A станет 1A-2B-3A. Начиная с Java 1.5, пакет atomic JDK предоставляет класс AtomicStampedReference для решения проблемы ABA. этого классаcompareAndSetЧто делает метод, так это сначала проверяет, равна ли текущая ссылка ожидаемой ссылке, и равен ли текущий флаг ожидаемому флагу, и если все равны, атомарно устанавливает ссылку и значение флага для заданного обновленного стоимость.
Справочная документация по вопросам ABA:blog.brownhas.net/2011/09/горячая вода…
4.2 Длительное время цикла и высокие накладные расходы.
Если прокрутка CAS будет безуспешной в течение длительного времени, это вызовет очень большие накладные расходы на выполнение ЦП. Если JVM может поддерживать инструкцию паузы, предоставленную процессором, эффективность будет в определенной степени повышена.Инструкция паузы имеет две функции.Во-первых, она может задерживать выполнение инструкций в конвейере (de-pipeline), чтобы ЦП не потреблял слишком много ресурсов выполнения, время задержки зависит от конкретной версии реализации, а на некоторых процессорах время задержки равно нулю. Во-вторых, это позволяет избежать конфликтов порядка памяти при выходе из цикла (memory order violation) и привести к очистке конвейера ЦП (CPU pipeline flush), тем самым повышая эффективность выполнения ЦП.
4.3 Атомарные операции, которые могут гарантировать только общую переменную.
При выполнении операций над общей переменной мы можем использовать циклический CAS для обеспечения атомарности операций, но при работе с несколькими общими переменными циклический CAS не может гарантировать атомарность операций, в этом случае можно использовать блокировки или есть хитрость заключается в объединении нескольких общих переменных в одну общую переменную для работы. Например, есть две общие переменные i=2, j=a, объединяются ij=2a, а затем используется CAS для работы с ij. Начиная с Java 1.5, JDK предоставляетAtomicReference, чтобы обеспечить атомарность между ссылочными объектами, вы можете поместить несколько переменных в один объект для выполнения операций CAS.
5. Реализация параллельного пакета
Поскольку CAS Java имеет обаvolatileчитать иvolatileНапишите семантику памяти, чтобы связь между потоками Java теперь осуществлялась четырьмя способами:
- Поток пишетvolatileпеременная, то поток B читает этоvolatileПеременная.
- Поток пишетvolatileпеременная, затем поток B обновляет ее с помощью CASvolatileПеременная.
- Поток обновляет один с помощью CASvolatileпеременная, затем поток B обновляет ее с помощью CASvolatileПеременная.
- Поток обновляет один с помощью CASvolatileпеременная, то поток B читает этоvolatileПеременная.
CAS Java использует эффективные атомарные инструкции машинного уровня, доступные на современных процессорах, которые атомарно выполняют операции чтения-модификации-записи в памяти, что является ключом к достижению синхронизации в многопроцессорных системах (по сути, вычислительная машина, которая может поддерживать атомарные инструкции чтения-модификации-записи). является асинхронным эквивалентом последовательной машины Тьюринга, поэтому любой современный мультипроцессор будет поддерживать какую-то память, которая может выполнять атомарные операции чтения-модификации-записи (атомарные инструкции). в то же время,volatileЧтение/запись переменных и CAS обеспечивают связь между потоками. Совокупность этих признаков вместе образует весьconcurrentКраеугольный камень упаковки. Если мы внимательно проанализируемconcurrentРеализация исходного кода пакета найдет обобщенный шаблон реализации:
- Сначала объявите общую переменную какvolatile;
- Затем используйте атомарное условное обновление CAS для достижения синхронизации между потоками;
- В то же время сvolatileЧтение/запись и CAS имеют энергозависимую семантику чтения и записи памяти для реализации связи между потоками.
AQS, неблокирующие структуры данных и классы атомарных переменных (java.util.concurrent.atomicпакет), этиconcurrentБазовые классы в пакете реализованы с использованием этого шаблона, в то время какconcurrentКлассы высокого уровня в пакете реализованы с опорой на эти базовые классы. Из общего вида,concurrentСхема реализации пакета выглядит следующим образом: