Эта статья взята из паблика WeChat [Fat Pig Learning Programming], пожалуйста, укажите источник для перепечатки
В шуточном сообщении в блоге о системе параллельного программирования мы говорили о N статьях о блокировках.Действительно, блокировки являются главным ключом к решению проблем параллелизма, но могут ли проблемы параллелизма быть решены только с помощью блокировок? Сегодня я буду играть в большой БОСС: CAS-алгоритм блокировки, который можно назвать ядром ядра параллельного программирования!
Обзор прошлого
Во-первых, давайте рассмотрим причины проблемы атомарности, см.【Комикс】Как решить проблему атомарности в параллельном программировании на JAVA.
Два потока одновременно загружают count=0 в свою рабочую память, и поток B сначала выполняет операцию count++.В это время основная память изменилась на 1, ноПоток A по-прежнему считает, что count=0, что является основной причиной проблемы..
Итак, решение:Не могу создать нить A думаю, кол-во = 0, но сделать это один раз с основной памятьюсравнивать, если значение в памяти равно 0, что указывает на то, что ни один другой поток не обновлял значение счетчика, топоменяться (обменяться), записать новое значение обратно в основную память. Если значение в памяти не равно 0, например, в этом случае счетчик в памяти был обновлен до 1 потоком B, и сравнение равно 0!=1, поэтому сравнение завершается ошибкой, и новое значение не записывается обратно в основную память.
Эта статья взята из публичного аккаунта WeChat [Fat Pig Learning Programming]. Женская программа Юань, которая сочетает в себе красоту и талант, делает программирование таким простым и интересным в виде комиксов! Пожалуйста, укажите источник
Концепция CAS
CAS (compareAndSwap), по-китайски называется биржа сравнения, своего родаБлокировочные атомарные алгоритмы.
Алгоритм CAS содержит 3 параметра CAS(V, E, N), где V представляет значение переменной в памяти, которую нужно обновить, E представляет старое ожидаемое значение, а N представляет новое значение. Значение V будет установлено равным N, только если значение V равно значению E..Если значение V и значение E отличаются, это означает, что другие потоки сделали два обновления, тогда текущий поток не обновляется, а вращается.
Имитационная реализация CAS
Теперь, когда мы поняли идею CAS, мы можем написать простую модель CAS:
// count必须用volatile修饰 保证不同线程之间的可见性
private volatile static int count;
public void addOne() {
int newValue;
do {
newValue = count++;
} while (!compareAndSwapInt(expectCount, newValue)); //自旋 循环
}
public final boolean compareAndSwapInt(int expectCount, int newValue) {
// 读目前 count 的值
int curValue = count;
// 比较目前 count 值是否 == 期望值
if (curValue == expectCount) {
// 如果是，则更新 count 的值
count = newValue;
return true;
}
//否则返回false 然后循环
return false;
}
Этот простой код моделирования в основном отражает идею CAS, но на самом деле принцип CAS намного сложнее.Давайте посмотрим, как JAVA реализует CAS!
Атомный класс
Чтобы понять реализацию CAS в JAVA, мы должны упомянуть знаменитый атомарный класс, использование атомарного класса очень просто, а эзотерическим принципом является CAS-алгоритм блокировки.
Атомарные классы, предоставляемые в параллельном пакете Java, очень богаты, и мы можем разделить их на пять категорий:Атомарные примитивные типы данных, атомарные типы ссылок на объекты, атомарные массивы, средства обновления свойств атомарных объектов и атомарные аккумуляторы.
Использование атомарных классов можно описать как очень простое.Я считаю, что вам нужно только посмотреть на API, чтобы знать, как его использовать.Поэтому я не буду слишком много объяснять.При необходимости вы можете обратиться к моему коду на github. Здесь мы берем AtomicInteger только в качестве примера, чтобы проверить, достоин ли атомарный класс своего имени и может ли он гарантировать атомарность:
private static AtomicInteger count = new AtomicInteger(0);
private static int count1 = 0;
//省略代码 同时启动10个线程 分别测试AtomicInteger和普通int的输出结果
private static void add10K() {
int idx = 0;
while (idx++ < 10000) {
//使用incrementAndGet实现i++功能
count.incrementAndGet();
}
countDownLatch.countDown();
}
private static void add10K1() {
int idx = 0;
while (idx++ < 10000) {
count1++;
}
countDownLatch.countDown();
}
В ходе тестирования можно обнаружить, что использование AtomicInteger может гарантировать, что результат вывода равен 100000, а обычный int — нет.
Эта статья взята из публичного аккаунта WeChat [Fat Pig Learning Programming]. Женская программа Юань, которая сочетает в себе красоту и талант, делает программирование таким простым и интересным в виде комиксов! Пожалуйста, укажите источник
Анализ исходного кода CAS
Исходя из этого, мы можем вернуться к теме, как JAVA реализует CAS? Следуйте методу incrementAndGet() в AtomicInteger, я думаю, ответ будет. Во-первых, обратите внимание на несколько вещей в AtomicInteger.java:
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;//数据在内存中的地址偏移量，通过偏移地址可以获取数据原值
static {
try {
//计算变量 value 在类对象中的偏移量
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
private volatile int value;//要修改的值 volatile保证可见性
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
Unsafe является основным классом CAS. Поскольку методы Java не могут напрямую обращаться к базовой системе, к ним необходимо обращаться через нативные методы. Unsafe эквивалентен бэкдору, и на основе этого класса можно напрямую манипулировать данными в определенной памяти. Переменная valueOffset представляет адрес смещения значения переменной в памяти, поскольку Unsafe получает данные на основе адреса смещения памяти. Значение переменной должно быть изменено с помощью volatile, чтобы обеспечить видимость памяти между несколькими потоками.
Конечно, нам еще нужно посмотреть на метод getAndAddInt для конкретной реализации:
//内部使用自旋的方式进行CAS更新（while循环进行CAS更新，如果更新失败，则循环再次重试）
public final int getAndAddInt(Object var1, long var2, int var4) {
//var1为当前这个对象，如count.getAndIncrement()，则var1为count这个对象
//第二个参数为AtomicInteger对象value成员变量在内存中的偏移量
//第三个参数为要增加的值
int var5;
do {
//var5 获取对象内存地址偏移量上的数值v 即预期旧值
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//循环判断内存位置的值与预期原值是否相匹配
return var5;
}
На этом этапе мы также хотим продолжить понимать реализацию compareAndSwapInt, Нажмите, чтобы увидеть, первое, что бросается в глаза, это четыре параметра: 1. Текущий экземпляр 2. Смещение адреса памяти переменной экземпляра 3. Ожидаемый старое значение 4. Обновить значение
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Я все еще хочу продолжать копать глубже, но я обнаружу, что точка не движется. Поскольку метод, украшенный нативом, представляет собой базовый метод, конечно, если вам нужно это выяснить, вы также можете найти соответствующий файл unsafe.cpp для углубленного анализа кода C:
Лично я не считаю нужным вникать в это.Ведь в арт-индустрии есть специальности.Надо только знать,что основной код этокоманда cmpxchg. cmpxchg: Инструкция «сравнить и поменять местами». Идея та же, что мы сказали выше: сравнить значение в регистре eax (compare_value) со значением в ячейке памяти двойного слова [edx] и, если они совпадают, сохранить значение в регистре ecx (exchange_value ) в [edx] ] в блоке памяти.
В итоге:Вам просто нужно помнить: CAS реализован на аппаратном уровне для повышения эффективности на аппаратном уровне. Реализация основана на инструкциях по сборке аппаратной платформы, в ЦП Intel используется инструкция cmpxchg.Основная идея:Сравните значение V обновляемой переменной с ожидаемым значением E (сравнение), и если они равны, значение V будет установлено на новое значение N (обмен).
Действительно ли CAS так хорош?
И CAS, и блокировки решают проблему атомарности.неблокирующий, он по своей природе невосприимчив к проблемам взаимоблокировки, и,Взаимодействие между потоками также очень мало. Что еще более важно, использование безблокировочного способа полностьюОтсутствуют системные накладные расходы, вызванные конкуренцией замков, и нет накладных расходов, вызванных частым планированием между потоками., так что ему принадлежит больше, чем подход на основе блокировкилучшая производительность.
Но так ли хорош CAS? Пришло время снова нанести удар!
Чтобы разочаровать нас, CAS не так хорош, в основном, в трех аспектах:
- 1. Время цикла слишком велико
- 2. Гарантируется только одна атомарная операция с общей переменной.
- 3, проблема АВА.
Время цикла слишком великоЕсли CAS не работает в течение длительного времени, мы знаем, что он будет продолжать зацикливаться, вращаться. Это неизбежно приведет к очень большой нагрузке на ЦП. Некоторые места в JUC ограничивают количество вращений CAS, например SynchronousQueue BlockingQueue.
Только одна общая переменная гарантированно будет атомарной.Глядя на реализацию CAS, мы знаем, что это можно использовать только для одной общей переменной.Если есть несколько общих переменных, можно использовать только блокировки.Конечно, если у вас есть способ интегрировать несколько переменных в одну переменную, это также хорошо использовать CAS. Например, старший и младший биты состояния в блокировке чтения-записи.
АВА-проблемаЭто вопрос интервью! Слушай внимательно!
CAS необходимо проверить, изменилось ли значение операции, и обновить его, если нет. Но есть такая ситуация: если значение изначально было A, стало B, а потом стало A, то при проверке CAS обнаружит, что оно не изменилось, а изменилось на самом деле, что называется проблемой ABA. В некоторых случаях нас не волнует проблема ABA, например, атомарное приращение значения, но ее нельзя игнорировать во всех случаях. Например, объект атомарного обновления, скорее всего, должен заботиться об ABA. проблема, потому что, хотя два А равны, свойства второго А могут измениться.
Решение проблемы ABA состоит в том, чтобы добавить номер версии, то есть добавить номер версии к каждой переменной и прибавлять 1 при каждом изменении, то есть A -> B -> A, что становится 1A -> 2B — > 3А.
AtomicStampedReference атомарного класса может решить проблему ABA, который не только поддерживает значение объекта, но также поддерживает Stamp (его можно понимать как номер версии, который использует целое число для представления значения состояния). При изменении значения, соответствующего AtomicStampedReference, в дополнение к обновлению самих данных необходимо также обновить номер версии. Когда AtomicStampedReference устанавливает значение объекта, и значение объекта, и номер версии должны соответствовать ожидаемому значению для успешной записи. Таким образом, даже если значение объекта многократно считывается и записывается, а исходное значение записывается обратно, при изменении номера версии можно предотвратить неправильную запись.
// 参数依次为：期望值 写入新值 期望版本号 新版本号
public boolean compareAndSet(V expectedReference, V
newReference, int expectedStamp, int newStamp);
//获得当前对象引用
public V getReference();
//获得当前版本号
public int getStamp();
//设置当前对象引用和版本号
public void set(V newReference, int newStamp);
Бесполезно говорить, что теорий слишком много, давайте сами проверим, сможет ли это решить проблему ABA:
private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(10, 0);
public static void main(String[] args) {
Thread main = new Thread(() -> {
int stamp = count.getStamp(); //获取当前版本
log.info("线程{} 当前版本{}",Thread.currentThread(),stamp);
try {
Thread.sleep(1000); //等待1秒 ，以便让干扰线程执行
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean isCASSuccess = count.compareAndSet(10, 12, stamp, stamp + 1); //此时expectedReference未发生改变，但是stamp已经被修改了,所以CAS失败
log.info("CAS是否成功={}",isCASSuccess);
}, "主操作线程");
Thread other = new Thread(() -> {
int stamp = count.getStamp(); //获取当前版本
log.info("线程{} 当前版本{}",Thread.currentThread(),stamp);
count.compareAndSet(10, 12, stamp, stamp + 1);
log.info("线程{} 增加后版本{}",Thread.currentThread(),count.getStamp());
// 模拟ABA问题 先更新成12 又更新回10
int stamp1 = count.getStamp(); //获取当前版本
count.compareAndSet(12, 10, stamp1, stamp1 + 1);
log.info("线程{} 减少后版本{}",Thread.currentThread(),count.getStamp());
}, "干扰线程");
main.start();
other.start();
}
Результат выглядит следующим образом:
线程Thread[主操作线程,5,main] 当前版本0
[干扰线程] INFO - 线程Thread[干扰线程,5,main] 当前版本0
[干扰线程] INFO - 线程Thread[干扰线程,5,main] 增加后版本1
[干扰线程] INFO - 线程Thread[干扰线程,5,main] 减少后版本2
[主操作线程] INFO - CAS是否成功=false
Суммировать
JAVA широка и глубока, и решение проблем параллелизма касается не только блокировок. Безблокировочный алгоритм CAS также необходим для решения проблемы атомарности. Атомарный класс — это модель класса инструментов без блокировок.Атомарный класс включает пять типов (атомарные базовые типы данных, атомарные типы ссылок на объекты, атомарные массивы, средства обновления свойств атомарных объектов и атомарные аккумуляторы).
CAS — это оптимистичный замок, который относится к вещам более оптимистично и считает, что может успешно работать. Пессимистические блокировки блокируют потоки. Таким образом, CAS имеет много преимуществ, таких как хорошая производительность и возможность избежать взаимоблокировок. Но это не так уж хорошо, вы должны учитывать проблемы ABA, долгое время цикла. Поэтому нужно комплексно подобрать тот, который подходит именно вам.
приложение:Параллельное программирование полного спектра кода github
Эта статья взята из публичного аккаунта WeChat [Fat Pig Learning Programming]. Женская программа Юань, которая сочетает в себе красоту и талант, делает программирование таким простым и интересным в виде комиксов! Добро пожаловать, чтобы следовать и общаться со мной!
Эта статья воспроизведена с официального аккаунта [Fat Pig Learning Programming] С помощью комиксов программирование становится таким простым и интересным! Добро пожаловать, чтобы обратить внимание!