Эта статья участвовала в "Проект «Звезда раскопок»”, чтобы выиграть творческий подарочный пакет и бросить вызов творческим поощрительным деньгам.
Что такое КАС
CAS также называется сравнением и обменом. Это алгоритм без блокировки. В повседневной разработке CAS в основном не используется напрямую. Он используется через некоторые классы инструментов параллелизма, инкапсулированные JDK в пакете JUC.
CAS содержит три значения: адрес памяти (V), ожидаемое значение (A), новое значение (B). Сначала сравните значение адреса памяти с ожидаемым значением, если они равны, присвойте новое значение адресу памяти, иначе ничего не делайте. Действуйте следующим образом:
1. Получить ожидаемое значение поля (oldValue).
2. Вычислите новое значение, которое необходимо заменить (newValue).
3. Поместите новое значение (newValue) в адрес памяти поля через CAS.Если CAS не работает, повторяйте шаги с 1 по 2 до тех пор, пока CAS не добьется успеха.Это повторение CAS spin.
Когда CAS сравнивает значение адреса памяти с ожидаемым значением, если оно равно, это доказывает, что значение адреса памяти не было изменено, и может быть заменено новым значением, а затем продолжить работу; если оно не равно, это означает, что значение адреса памяти было изменено.Измените, отмените операцию замены и повторите вращение. Когда количество одновременно модифицируемых потоков невелико и вероятность конфликта мала, количество циклов будет небольшим, а производительность CAS будет высокой; когда имеется много одновременно модифицируемых потоков и высока вероятность конфликта, количество количество вращений будет высоким, производительность CAS будет значительно снижена. Таким образом, ключом к повышению эффективности CAS-программирования без блокировки является снижение вероятности конфликта.
Анализ принципа CAS
Взяв в качестве примера атомарный целочисленный класс AtomicInteger, давайте рассмотрим базовый механизм реализации CAS.
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
//这里主要就是获取AtomicInteger类value这个这个字段在地址的偏
//移量，也就是地址，这个value字段是使用的volatile 进行修饰的，保证了字段的可见性
static {
try {
//获取value值的内存偏移量
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;
//AtomicInteger初始化就是对value进行赋值
public AtomicInteger(int initialValue) {
value = initialValue;
}
//实际对数据操作的是unsafe的类的getAndAddInt方法
public final int getAndAdd(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta);
}
// 提供自增易用的方法，返回增加1后的值
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
// 额外提供的compareAndSet方法
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// Unsafe类的提供的方法
public final int getAndAddInt (Object o,long offset, int delta){
int v;
do {
v = getIntVolatile(o, offset);
} while (!weakCompareAndSetInt(o, offset, v, v + delta));
return v;
}
Внутренние методы AtomicInteger реализованы на основе класса Unsafe, который представляет собой класс инструментов репликации, взаимодействующий с базовыми инструкциями аппаратного ЦП. Взгляните на конкретное содержимое метода unsafe.getAndAddInt:
//CAS自旋，通过getIntVolatile方法通过内存偏移量获取对象最新的值，再调用cas方法，如果失败了就不断的重
//试获取对象新值然后CAS,直到成功
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
//先去内存中获取内存地址所指向的值，这个将这个内存值赋值给var5，这个方法是native方法
//var5是预期值
var5 = this.getIntVolatile(var1, var2);
//在修改前先比较一次内存的值还是否是预期值var5，将偏移量var2、对应的unsafe对象var1
//和var5带进compareAndSwapInt去获取此时内存中偏移量所指向的数值然后
//和预期值var5进行比较，如果是相等的就将偏移量var2指向的主内存地址中的值修改为
//var5 + var4，失败就进行重试,每次重试都会去内存中重新获取值赋值给var5,然后修改时再比较一下
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
Посмотрите, как получить valueOffset:
// Unsafe实例
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
static {
try {
// 获得value在AtomicInteger中的偏移量
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
// 实际变量的值
private volatile int value;
Фактическая переменная value модифицируется ключевым словом volatile, чтобы обеспечить видимость памяти при многопоточности.
Проблемы с CAS
АВА-проблема
Операция CAS заключается в том, чтобы сначала сравнить, совпадает ли ожидаемое значение A со значением в адресе памяти. Если оно совпадает, считается, что ни один другой поток не изменил значение A в это время. Однако, если в это время поток считывает значение A, другой поток изменяет значение A на B, а затем заменяет B обратно на A. В это время сравнение между A и ожидаемым значением такое же, и считается, что что A Значение не изменилось. Чтобы решить проблему ABA, вы можете использовать номер версии.Каждый раз, когда вы изменяете переменную, добавляйте 1 к номеру версии этой переменной.Таким образом, просто A->B->A, хотя значение А не изменился, его номер версии изменился, и тогда, судя по номеру версии, вы обнаружите, что А в это время был тайно изменен другими.
Обходной путь: атомарная ссылка AtomicReference.
проблемы с производительностью
Если прокрутка будет неудачной в течение длительного времени, это вызовет очень большие накладные расходы на выполнение ЦП.
public final int getAndSet(int newValue) {
for (;;) {
int current = get();
if (compareAndSet(current, newValue))
return current;
}
}
Видно, что спин в исходном коде возвращается только при успешном выполнении CAS. Следовательно, также необходимо учитывать проблемы с производительностью, связанные с CAS. Spin также является функцией CAS.Spin — это неблокирующий алгоритм.По сравнению с другими блокирующими алгоритмами, неблокирующий алгоритм не требует от ЦП переключения временных интервалов для сохранения контекста, что значительно снижает потребление производительности. Преимущества CAS перед блокировками синхронизации: если параллелизм не очень высок, механизм CAS повысит эффективность, но в случае интенсивной конкуренции и большого параллелизма эффективность очень низкая, потому что время вращения слишком велико и количество сбоев слишком велико Слишком много попыток.
Только гарантированные атомарные операции над общей переменной
При выполнении операций над общей переменной мы можем использовать циклический CAS для обеспечения атомарных операций, но при работе с несколькими общими переменными циклический CAS не может гарантировать атомарность операции, и в это время можно использовать блокировки. Еще один сложный способ — объединить несколько общих переменных в одну общую переменную для работы. Например, если есть две общие переменные i=2, j=a, объедините их с ij=2a, а затем используйте CAS для работы с ij. Начиная с Java 1.5, JDK предоставляет класс AtomicReference для обеспечения атомарности между ссылочными объектами, так что несколько переменных могут быть помещены в один объект для операций CAS.
Решение проблем АВА
плюс номер версии
Каждый раз, когда переменная модифицируется, к номеру версии переменной добавляется 1. Таким образом, просто A->B->A, хотя значение A не изменилось, его номер версии изменился, и тогда, судя по номер версии найдете В это время был изменен. Ссылаясь на номер версии оптимистической блокировки, этот подход может обеспечить проверку достоверности данных.
Метод compareAndSet класса AtomicStampReference сначала проверяет, равно ли текущее значение ссылки на объект ожидаемой ссылке и равен ли флаг текущей отметки (Stamp) ожидаемому флагу, и, если все равны, атомарно обновляет значение ссылки и значение флага штампа до заданного значения обновления значения .
Использование AtomicMarkableReference
AtomicMarkableReference не заботит, сколько раз он был изменен, только был ли он изменен. Метка его атрибута метки имеет логический тип, а не числовой тип, а метка атрибута метки только записывает, было ли изменено значение. AtomicMarkableReference применим до тех пор, пока вы знаете, был ли изменен объект, а не для сценариев, в которых объект неоднократно изменяется.
Сценарии использования CAS
CAS имеет приложения для реализации важных параллельных классов контейнеров, таких как атомарный класс, AQS и CurrentHashMap в пакете JUC. Взгляните еще раз на пример AQS:
protected final boolean compareAndSetState(int expect, int update) {
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
Для операций CAS с переменной состояния многие классы синхронизации используют эту переменную для обеспечения потокобезопасности, поэтому в AQS первое, что нужно сделать, — это убедиться, что присваивание состоянию является потокобезопасным.
В атомарных классах пакета java.util.concurrent.atomic, таких как AtomicXXX, CAS используется для обеспечения атомарности операций над числовыми элементами. Большинство классов JUC (включая блокировки отображения и параллельные контейнеры) реализованы на основе AQS и AtomicXXX, а AQS гарантирует атомарность своих внутренних двунаправленных операций начала и конца очереди через CAS.
Инструкции по розыгрышу
1. Это событие официально поддерживается Nuggets, подробности можно посмотретьnuggets.capable/post/701221…
2. Вы можете участвовать, комментируя содержание, связанное со статьей, и это должно быть связано с содержанием статьи!
3. Все статьи этого месяца будут участвовать в лотерее, и все желающие могут взаимодействовать еще больше!
4. В дополнение к официальной лотерее Наггетс, я также отправлю периферийные подарки (кружка и несколько значков Наггетс, кружка будет передана внимательным комментаторам, значки будут выбраны случайным образом, и количество будет увеличиваться в зависимости от количества комментариев).