Базовые знания, связанные с CAS
Полное название CAS — Compare And Swap, то есть сравнивать и обменивать. В CAS обычно разрабатываются три параметра:
- значение памяти В
- старое ожидаемое значение A
- новое значение B для изменения
Измените значение памяти V на B тогда и только тогда, когда ожидаемое значение A и значение памяти V совпадают, в противном случае ничего не делайте.
Глубокой проработки поддержки инструкций ЦП для CAS здесь нет, и те, кому это интересно, могут узнать об этом сами.
КАС несколько вопросов
Несколько проблем с ним поднимаются во многих книгах и статьях:
- 1. Длительное время цикла и высокие накладные расходы
- 2. Гарантируется только атомарная операция общей переменной
- 3. Проблема АВА
Давайте обсудим эти три вопроса.
1. Сомнения и проверки по поводу «длительного времени цикла и высоких накладных расходов»
Если спин CAS будет безуспешным в течение длительного времени, это принесет очень большие накладные расходы на ЦП. Но так ли это на самом деле? Насколько параллелизм увеличивается количество спинов CAS? Кроме того, для текущей машины и JDK, в случае отсутствия блокировок и CAS, так ли очевидно влияние на результаты? Для этой проблемы я провел простой тест ниже, но результаты теста относятся только к моей локальной среде.Вы можете извлечь код, запустить его на своем компьютере и оставить информацию о машине, версию JDK и результаты теста в области комментариев.
Кейс-стади можно найти здесь:glmapper-blog-sample-cas
Здесь я использую очень простой случай, то есть целочисленное автоинкрементирование. Для тестирования используются два метода: один неблокирующий и не требует работы CAS, а другой основан на CAS. (Нет проверки способа блокировки, я добавлю ее, когда у меня будет время~)
Класс счетчика
В счетчике есть два метода: один — метод вращения CAS, а другой — прямое приращение. код показывает, как показано ниже:
public class Counter {
public AtomicInteger safeCount = new AtomicInteger(0);
public int unsafe = 0;
// 使用自旋的方式
public void safeCount(){
for (;;){
int i = safeCount.get();
boolean success = safeCount.compareAndSet(i,++i);
if (success){
break;
}
}
}
// 普通方式自增
public void unsafeCount(){
unsafe++;
}
}
Имитация параллелизма
Здесь мы моделируем использование 1000 потоков и выполняем 30 раз, чтобы увидеть результаты, включая общее потребление времени и правильность результатов.
- CAS-метод
public static int testSafe() throws InterruptedException {
// 记录开始时间
long start = System.currentTimeMillis();
// 实例化一个 Counter 计数器对象
Counter counter = new Counter();
CountDownLatch countDownLatch = new CountDownLatch(testCounts);
for (int i =0 ;i < testCounts;i++){
new Thread(()->{
// 调用 safeCount 方法
counter. safeCount();
countDownLatch.countDown();
}).start();
}
countDownLatch.await();
// 结束时间
long end = System.currentTimeMillis();
safeTotalCostTime += (end-start);
return counter.safeCount.get();
}
- общий путь
public static int testUnSafe() throws InterruptedException {
// 记录开始时间
long start = System.currentTimeMillis();
// 实例化一个 Counter 计数器对象
Counter counter = new Counter();
CountDownLatch countDownLatch = new CountDownLatch(testCounts);
for (int i =0 ;i< testCounts;i++){
new Thread(()->{
// 调用 unsafeCount 方法
counter.unsafeCount();
countDownLatch.countDown();
}).start();
}
countDownLatch.await();
// 结束时间
long end = System.currentTimeMillis();
unsafeTotalCostTime += (end-start);
return counter.unsafe;
}
- основной метод
public static void main(String[] args) throws InterruptedException {
// 执行 300 次
for (int i =0 ;i< 300;i++){
// 普通方式
int unSafeResult = testUnSafe();
// cas 方式
int safeResult = testSafe();
// 结果验证，若果正确就将成功次数增加
if (unSafeResult == testCounts){
totalUnSafeCount++;
}
// 同上
if (safeResult == testCounts){
totalSafeCount++;
}
}
System.out.println("test count = " + testCounts);
System.out.println("非安全计数器正确个数 = " + totalUnSafeCount);
System.out.println("非安全计数器耗时 = " + unsafeTotalCostTime);
System.out.println("安全计数器正确个数 = " + totalSafeCount);
System.out.println("安全计数器耗时 = " + safeTotalCostTime);
}
Информация о моей машине выглядит следующим образом:
- MacBook Pro (Retina, 15-inch, Mid 2015)
- Процессор: Intel Core i7 с тактовой частотой 2,2 ГГц
- Память: 16 ГБ 1600 МГц DDR3
Ниже приведены некоторые тестовые данные.
1000(количество потоков) * 300(количество раз)
Результаты теста следующие:
test count = 1000
非安全计数器正确个数 = 300
非安全计数器耗时 = 27193
安全计数器正确个数 = 300
安全计数器耗时 = 26337
На самом деле обнаружено, что метод без CAS на самом деле занимает почти на 1 секунду больше времени, чем использование спинового CAS. Еще один неожиданный момент, я пытался несколько раз, и правильная скорость результатов, полученных без CAS, в основном скорость более 4 9s, и очень мало случаев, когда результаты расчета неверны.
3000 (количество потоков) * 30 (количество раз)
Результаты теста следующие:
test count = 3000
非安全计数器正确个数 = 30
非安全计数器耗时 = 7816
安全计数器正确个数 = 30
安全计数器耗时 = 8073
Здесь мы видим, что он очень близок по времени. Еще один момент, который здесь необходимо учитывать, заключается в том, что, поскольку testUnSafe выполняется до testSafe, влияние «прогрева JVM и самой машины» очень мало, но определенное влияние все же имеет.
5000 (количество потоков) * 30 (количество раз)
Результаты теста следующие:
test count = 5000
非安全计数器正确个数 = 30
非安全计数器耗时 = 23213
安全计数器正确个数 = 30
安全计数器耗时 = 14161
С увеличением параллелизма, что странно, так как обычный способ потребляет больше времени, чем трудоемкий способ CAS почти на 8-9 секунд.
При попытке 10000 раз, да вы догадались, выбрасывался OOM. Однако, судя по результатам выполнения, это не говорит о том, что с увеличением параллелизма будет увеличиваться вероятность ошибок в обычном режиме, а также не кажется, что ожидаемое время CAS-режима больше, чем у обычного. режим.
Из-за относительно простых данных тестовых образцов, вывод о результатах испытаний невозможен.Вы можете предоставить результаты своих соответствующих машин для справки. Кроме того, я видел много студентов, у которых в последнее время брали интервью, и если им задают этот вопрос, им все равно нужно хорошенько подумать. Необходимы дополнительные результаты тестов о том, следует ли «получить пощечину» или «получить пощечину».
Как работает КАС
- Инструкции процессора
- Небезопасный класс
2. Простое воспроизведение задачи АВА
Еще одним моментом в онлайн-дискуссии о CAS является вопрос ABA в CAS.Я считаю, что если большинству студентов задают вопрос CAS во время собеседования, то и вопрос ABA будет задан, и тогда следующим шагом будет то, как избежать этой проблемы.Да , процедура такая.
Я считаю, что более 90% разработчиков никогда не сталкивались с этой проблемой в реальном инжиниринге, а если и сталкивались, то при определенных обстоятельствах это не повлияет на результаты расчетов. Но поскольку эта проблема будет упоминаться неоднократно, должен быть сценарий, при котором она приводит к ошибкам.Я нашел случай для вашей справки:Задача ABA и схема оптимизации под CAS.
Вместо того, чтобы думать, как избежать этой проблемы, мы хотим воспроизвести эту проблему ABA с помощью простого моделирования. На самом деле это тоже очень просто, если вы понимаете чередование потоков и последовательное выполнение.
Как реализовать перекрестное выполнение нескольких потоков
Этот вопрос на самом деле является основным вопросом, который очень часто встречается в процессе собеседования. Я предоставил три метода реализации в предоставленном коде. Заинтересованные студенты могут извлечь код, чтобы увидеть его.
Ниже приведен способ блокировки для моделирования этого сценария, код выглядит следующим образом:
public class ConditionAlternateTest{
private static int count = 0;
// 计数器
public AtomicInteger safeCount = new AtomicInteger(0);
// lock
private Lock lock = new ReentrantLock();
// condition 1/2/3 用于三个线程触发执行的条件
Condition c1 = lock.newCondition();
Condition c2 = lock.newCondition();
Condition c3 = lock.newCondition();
// 模拟并发执行
CountDownLatch countDownLatch = new CountDownLatch(1);
// 线程1 ，A
Thread t1 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 0){
c1.await();
}
safeCount.compareAndSet(0, 1);
System.out.println("thread1:"+safeCount.get());
count++;
// 唤醒条件2
c2.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 线程2 ，B
Thread t2 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 1){
c2.await();
}
safeCount.compareAndSet(1, 0);
System.out.println("thread2:"+safeCount.get());
count++;
// 唤醒条件3
c3.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 线程2 ，A
Thread t3 = new Thread(()-> {
try {
lock.lock();
while (count % 3 != 2){
c3.await();
}
safeCount.compareAndSet(0, 1);
System.out.println("thread3:"+safeCount.get());
count++;
// 唤醒条件1
c1.signal();
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
lock.unlock();
}
});
// 启动启动线程
public void threadStart() {
t3.start();
t1.start();
t2.start();
countDownLatch.countDown();
}
public static void main(String[] args) throws InterruptedException {
ConditionAlternateTest test = new ConditionAlternateTest();
test.threadStart();
test.countDownLatch.await();
}
}
Результаты:
thread1:1
thread2:0
thread3:1
Приведенный выше случай пересечения нитей на самом деле не является воспроизведением задачи АВА в строгом смысле, здесь представлен лишь простейший процесс, сгенерированный при моделировании. Если у вас есть хороший случай, вы также можете поделиться им.
АВА решение проблем
Обычная практика: сравнение «номеров версий», одна версия одних данных, версия меняется, даже если значение одинаковое, оно не должно быть успешно изменено.
Класс AtomicStampedReference предоставляется в java для решения этой проблемы ABA. Атомарный класс AtomicStampedReference представляет собой ссылку на объект с отметкой времени, после каждой модификации AtomicStampedReference не только устанавливает новое значение, но и записывает время изменения. Когда AtomicStampedReference устанавливает значение объекта, и значение объекта, и отметка времени должны соответствовать ожидаемому значению для успешной записи, что также решает дилемму невозможности предсказать, было ли изменено значение во время повторного чтения и записи.
Код реализации здесь публиковаться не будет. На основе предыдущего преобразования кода текущие результаты опубликованы ниже:
thread1,第一次修改;值为=1
thread2,已经改回为原始值;值为=0
thread3,第二次修改;值为=1
3. Только атомная работа общей переменной гарантирована
При выполнении операций над общей переменной мы можем использовать CAS для обеспечения атомарных операций, но при работе с несколькими переменными циклический CAS не может гарантировать атомарность операций, поэтому в этом сценарии нам нужно использовать заблокированный способ решения.