Интервью: Чтобы зайти на Али, перечитал реализацию concurrent CAS (Compare and Swap)

интервью

предисловие

На собеседовании обязательно должны быть заданы параллельные вопросы о безопасности потоков. Также необходимо понимать основные принципы CAS, чтобы вы могли добавлять баллы на собеседовании. Давайте посмотрим на вопросы, которые могут быть заданы на собеседовании:

  • Что такое оптимистическая блокировка и пессимистическая блокировка
  • В чем заключается реализация оптимистической блокировки - CAS (Compare and Swap), принцип реализации CAS (Compare and Swap)
  • Использование в параллельных пакетах JDK
  • Недостатки CAS

1. Что такое оптимистичная блокировка и пессимистическая блокировка?

пессимистический замок

Всегда предполагайте наихудший случай, каждый раз, когда данные считываются, другие потоки будут изменять данные по умолчанию, поэтому требуется операция блокировки, и когда другие потоки хотят получить доступ к данным, они должны блокироваться и приостанавливаться. Реализация пессимистической блокировки:

  • Традиционные реляционные базы данных используют этот механизм блокировки, например блокировки строк, таблиц и т. д., блокировки чтения, блокировки записи и т. д., которые блокируются до выполнения операций;
  • Синхронизация в JavasynchronizedРеализация ключевого слова.

оптимистическая блокировка

Оптимистическая блокировка на самом деле своего рода идея.Он всегда думает, что не будет проблем с параллелизмом.Каждый раз, когда он читает данные, он думает, что другие потоки не будут модифицировать данные, поэтому он не блокируется, а будет судить в этот период когда он обновляется.Независимо от того, изменили ли данные другие потоки, оптимистическая блокировка подходит для сценариев с большим количеством операций чтения, что может повысить производительность программы. Метод реализации:

  • Реализация CAS: атомарные переменные в пакете java.util.concurrent.atomic в Java используют реализацию оптимистической блокировки CAS.См. следующий раздел для анализа CAS.
  • Контроль номера версии: как правило, в таблицу данных добавляется поле версии номера версии данных, которое указывает, сколько раз данные были изменены.При изменении данных значение версии увеличивается на единицу. Когда поток A хочет обновить значение данных, он также считывает значение версии при чтении данных.При отправке обновления, если только что прочитанное значение версии равно значению версии в текущей базе данных, оно будет обновлено, в противном случае повторите попытку. Операция обновления, пока обновление не будет успешным

Оптимистичные блокировки подходят для сценариев с большим количеством операций чтения и меньшим количеством операций записи (сценарии с несколькими операциями чтения), а пессимистичные блокировки больше подходят для сценариев с большим количеством операций записи и меньшим количеством операций чтения.

2. Реализация оптимистической блокировки - CAS (Compare and Swap), принцип реализации CAS (Compare and Swap)

задний план

Он использовался до jdk1.5synchronizedКлючевое слово гарантирует синхронизацию,synchronizedГарантируется, что независимо от того, какой поток удерживает блокировку общей переменной, он будет обращаться к этим переменным монопольным образом, что приведет к следующим проблемам:

  • В условиях многопоточной конкуренции блокировка и снятие блокировки вызовет больше переключений контекста и задержек планирования, вызывая проблемы с производительностью.
  • Если один поток удерживает блокировку, все остальные потоки зависают, ожидая, пока поток, удерживающий блокировку, освободит блокировку.
  • Если поток с высоким приоритетом ожидает, пока поток с низким приоритетом освободит блокировку, это вызовет инверсию приоритета, что приведет к риску производительности.

Чтобы оптимизировать эти проблемы пессимистической блокировки, появляется оптимистическая блокировка:

Предполагая, что конфликт параллелизма отсутствует, каждый раз оперируйте одной и той же переменной без блокировки.

Принцип CAS (Сравни и обменяй)

Полное название CAS — compare and swap — механизм реализации функций синхронизации в многопоточной среде, а также lock-free оптимизация, или spin, и Adaptive Spin.

В ЖДК,CASдобавлятьvolatileКлючевые слова служат краеугольным камнем для реализации параллельных пакетов. Без CAS не было бы параллельных пакетов, в java.util.concurrent с помощью инструкции CAS реализована оптимистичная блокировка, отличная от синхронизированной.

Типичный механизм реализации оптимистической блокировки (CAS):

Оптимистическая блокировка в основном состоит из двух шагов:

  • обнаружение столкновений
  • Обновление данных

Когда несколько потоков пытаются использовать CAS для одновременного обновления одной и той же переменной, только один поток может обновить значение переменной. Повторите попытку.

Для обеспечения безопасности потоков без использования блокировок в механизме реализации CAS есть три важных операнда:

  • Место в памяти для чтения и записи (V)
  • Ожидаемое исходное значение (A)
  • новое значение (В)

Сначала прочитайте ячейку памяти (V), которую необходимо прочитать и записать, а затем сравните ячейку памяти (V), которую нужно прочитать и записать, с ожидаемым исходным значением (A).Если ячейка памяти соответствует ожидаемому исходному значению A , то ячейка памяти Значение обновляется до нового значения B. Если ячейка памяти не соответствует ожидаемому исходному значению, процессор ничего не делает. В любом случае он возвращает значение в этом месте перед инструкцией CAS. Его можно разделить на три этапа:

  • чтение (область памяти, которую необходимо прочитать и записать (V))
  • Сравнение (место памяти для чтения и записи (V) и ожидаемое исходное значение (A))
  • обратная запись (новое значение (B))

3. Использование CAS в параллельных пакетах JDK

В JDK1.5 и более поздних версиях java.util.concurrent (инструментарий параллелизма JUC java) реализован на основе алгоритма CAS.По сравнению с синхронизированной эксклюзивной блокировкой и алгоритмом блокировки, CAS является обычной реализацией неблокирующего алгоритма.Используя оптимистическую блокировку, JUC может улучшить производительность. значительно улучшилось.

Как CAS обеспечивает потокобезопасность без использования блокировок, см. в методе класса атомарных операций AtomicInteger::getAndIncrement() в параллельном пакете (эквивалентно операциям i++):

// AtomicInteger中
//value的偏移量
private static final long valueOffset; 
//获取值
private volatile int value;
//设置value的偏移量
static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
//增加1
public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

  • Прежде всего, значение должно быть изменено с помощью volatile, что обеспечивает его видимость и упорядоченность.

  • Смещение, по которому значение должно быть инициализировано

  • unsafe.getAndAddInt выполняет операцию CAS через смещение.Каждый раз, когда данные считываются из памяти, а затем данные обрабатываются +1, а затем исходные данные и результат +1 подвергаются операции CAS.В случае успеха результат будет возвращен, в противном случае повторите попытку до тех пор, пока она не будет успешной.

    //unsafe中
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        //使用偏移量获取内存中value值
        var5 = this.getIntVolatile(var1, var2);
       //比较并value加+1
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}

JAVA реализует принцип CAS, unsafe::compareAndSwapInt реализуется путем вызова инструкций нижнего уровня ЦП с помощью C. Вот исходный код метода sun.misc.Unsafe::compareAndSwapInt():

public final native boolean compareAndSwapInt(Object o, long offset,
                                               int expected, int x);

4. Дефекты КАС

АВА-проблема

В многопоточном сценарии у CAS возникнет проблема ABA. Например, есть два потока, которые одновременно выполняют операции CAS над одним и тем же значением (начальное значение — A). Три потока выглядят следующим образом.

Поток 1, ожидаемое значение — A, а обновляемое значение — B. Поток 2, ожидаемое значение — A, а обновляемое значение — B.

Поток 3, ожидаемое значение — B, а обновляемое значение — A.

  • Поток 1 получает квант времени ЦП первым, в то время как поток 2 заблокирован по другим причинам.Поток 1 сравнивает значение с ожидаемым значением A, находит, что оно равно, а затем обновляет значение до B,
  • В это время появляется поток 3. Значение потока 3 сравнивается с ожидаемым значением B. Если оно оказывается равным, значение обновляется до A.
  • В это время поток 2 восстанавливается после блокировки и получает квант времени процессора.В это время значение потока 2 сравнивается с ожидаемым значением A, и если оно оказывается равным, значение обновляется до B. Хотя поток 2 также завершил операцию, поток 2 не знает, что значение прошлоA->B->Aпроцесс изменения.

Опасности проблем с ABA:
Сяомин снимает 50 юаней в банкомате.Из-за проблемы с банкоматом есть два потока, и баланс меняется со 100 на 50 одновременно.
Поток 1 (банкомат): получить текущее значение 100, ожидать обновления до 50,
Поток 2 (ATM): получить текущее значение 100, ожидать обновления до 50,
Поток 1 успешно выполнен, а поток 2 по какой-то причине заблокирован.В это время кто-то переводит 50 Сяо Мину
поток 3 (по умолчанию): получить текущее значение 50, ожидать обновления до 100,
В это время поток 3 успешно выполняется, и баланс становится равным 100.
Поток 2 восстанавливается из блока и получает 100. После сравнения он продолжает обновлять баланс до 50! ! !
На данный момент вы можете видеть, что фактический баланс должен быть 100 (100-50+50), но на самом деле он стал 50 (100-50+50-50) Это успешная отправка, вызванная проблемой ABA.

Решение

  • AtomicStampedReference Ссылка на объект с отметкой времени для решения проблемы ABA. Роль метода compareAndSet этого класса состоит в том, чтобы сначала проверить, равна ли текущая ссылка ожидаемой ссылке, и равен ли текущий флаг ожидаемому флагу, и, если все равны, атомарно установить ссылку и значение флаг на заданное обновленное значение.
public boolean compareAndSet(
               V      expectedReference,//预期引用
               V      newReference,//更新后的引用
              int    expectedStamp, //预期标志
              int    newStamp //更新后的标志

)
  • Добавьте номер версии перед переменной, и каждый раз, когда переменная обновляется, номер версии переменной равен +1, то есть A->B->A становится 1A->2B->3A

Длительное время цикла и высокие накладные расходы

Spin CAS (в случае неудачи он будет выполняться в цикле до тех пор, пока не будет успешным).Если он будет безуспешным в течение длительного времени, это принесет большие накладные расходы на выполнение процессора.

Решение:

  • Ограничьте количество вращений, чтобы предотвратить вход в бесконечный цикл

  • Если JVM может поддерживать инструкцию паузы, предоставляемую процессором, эффективность в определенной степени повысится.

Только гарантированные атомарные операции над общей переменной

При выполнении операций с общей переменной мы можем использовать циклический CAS для обеспечения атомарности операций, но при работе с несколькими общими переменными циклический CAS не может гарантировать атомарность операции.

Решение:

  • Если вам нужно работать с несколькими общими переменными, вы можете использовать метод блокировки (пессимистическая блокировка), чтобы обеспечить атомарность,

  • Несколько общих переменных можно объединить в одну общую переменную для операций CAS.

Вы в порядке, офицеры? Если вам это нравится, проведите пальцем, чтобы нажать 💗, нажмите, чтобы подписаться! ! Спасибо за Вашу поддержку! Добро пожаловать, чтобы сканировать код и следовать, оригинальные технические статьи будут выпущены как можно скорее

Вы в порядке, офицеры? Если вам это нравится, проведите пальцем, чтобы нажать 💗, нажмите, чтобы подписаться! ! Спасибо за Вашу поддержку!

Добро пожаловать, чтобы сканировать код и следовать, оригинальные технические статьи будут выпущены как можно скорее

Категории