CAS в JAVA

Java

Оригинальный адрес:у-у-у-у. xilidu.com/2018/02/01/…

CAS — важное средство решения проблем параллелизма в современных операционных системах.eurekaисходный код. Столкнулся с большим количеством операций CAS. Сегодня я систематически буду рассматривать CAS в Java.

Прочитав эту статью, вы узнаете:

  • Что такое КАС
  • Каков принцип реализации CAS?
  • Реальное применение CAS
    • блокировка спина
    • тип атома
    • ограничитель тока
  • Недостатки CAS

Что такое КАС

CAS: Полное название «Сравнить и поменять местами», буквально: «Сравнить и поменять местами». CAS включает следующие операции:

Мы предполагаем исходные данные V в памяти, старое ожидаемое значение A и новое значение B, которое необходимо изменить.

  1. Сравнивает A и V на равенство. (сравнивать)
  2. Если он сравнивается равным, запишите B в V. (обмен)
  3. Возвращает, была ли операция успешной.

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

Как реализована CAS

Следуя коду AtomInteger до конца, мы можем обнаружить, что последний вызовsum.misc.Unsafeэтот класс. Название Unsafe означает небезопасный класс, который использует уместную лазейку в правилах видимости классов и пакетов Java. Unsafe — это класс, который компрометирует стандарты безопасности Java для скорости.

Глядя дальше вниз, мы нашли небезопасныйcompareAndSwapIntэто собственный метод:

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

Другими словами, эти методы CAS должны использовать локальные методы. Поэтому конкретная реализация этих методов требует от нас поиска в исходном коде jdk.

Итак, я загрузил исходный код OpenJdk и продолжил изучение, мы обнаружили, что в/jdk9u/hotspot/src/share/vm/unsafe.cppЕсть такой код:

{CC "compareAndSetInt",   CC "(" OBJ "J""I""I"")Z",  FN_PTR(Unsafe_CompareAndSetInt)},

Это включает в себя вызов JNI, и заинтересованные студенты могут учиться самостоятельно. мы ищемUnsafe_CompareAndSetIntПозже нашел:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);

  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
} UNSAFE_END

Наконец мы наконец видим основной кодAtomic::cmpxchg.

Продолжайте исследовать нижний слой, в файлеjava/jdk9u/hotspot/src/os_cpu/linux_x86/vm/atomic_linux_x86.hppЕсть такой код:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value, cmpxchg_memory_order order) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

Из имени файла мы можем знать, что JVM должна иметь разные реализации Atomic::cmpxchg для разных операционных систем. Поскольку наши сервисы в основном используют 64-битный Linux, давайте взглянем на реализацию linux_x86.

Продолжим смотреть на код:

  • __asm__Это означает, что это часть встроенного ассемблерного кода. То есть с использованием ассемблерного кода на языке Си.
  • здесьvolatileПодобно JAVA, но вместо видимости памяти он говорит компилятору прекратить оптимизацию кода, который обращается к переменной.
  • LOCK_IF_MP(%4)Смысл относительно прост, то есть если операционная система многопоточная, добавить БЛОКИРОВКУ.
  • cmpxchglЭто ассемблерная версия "сравнить и поменять местами". Но мы знаем, что операция сравнения и замены, состоящая из трех шагов, не является атомарной. Так что добавьте LOCK в случае многоядерности, и его атомарность гарантируется аппаратной частью ЦП.
  • Давайте посмотрим, как реализован LOCK? Давайте зайдем на официальный сайт Intel, чтобы увидеть, что ранняя реализация LOCK заключается в том, чтобы напрямую блокировать шину чашки, что показывает, что эффективность очень низкая. Позже он был оптимизирован для процессора X86, чтобы иметь возможность блокировать определенный адрес памяти.Когда этот конкретный адрес памяти заблокирован, это может помешать другим системным шинам читать или изменять этот адрес памяти.

Вот и все для низкоуровневого исследования CAS. Подытожим, как реализован cas в JAVA:

  • cas java использует операцию cas, предоставленную небезопасным классом.
  • Unsafe cas использует Atomic::cmpxchg, реализованный jvm для разных операционных систем.
  • Реализация Atomic::cmpxchg использует операцию сборки cas и использует сигнал блокировки, предоставляемый аппаратным обеспечением процессора, чтобы гарантировать его атомарность.

Применение КАС

Поняв принцип CAS, давайте продолжим рассмотрение применения CAS:

блокировка спина

public class SpinLock {

  private AtomicReference<Thread> sign =new AtomicReference<>();

  public void lock(){
    Thread current = Thread.currentThread();
    while(!sign .compareAndSet(null, current)){
    }
  }

  public void unlock (){
    Thread current = Thread.currentThread();
    sign .compareAndSet(current, null);
  }
}

Так называемая блокировка спина, я думаю, что название вполне соответствует образу, во время блокировки () цикл while () продолжается до тех пор, пока операция cas не будет успешной.

incrementAndGet() для AtomicInteger

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

Подобно спин-блокировке, он должен сохраняться до тех пор, пока операция не завершится успешно.

Ограничитель тока корзины маркеров

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

public class RateLimiter {

    private final long rateToMsConversion;

    private final AtomicInteger consumedTokens = new AtomicInteger();
    private final AtomicLong lastRefillTime = new AtomicLong(0);

    @Deprecated
    public RateLimiter() {
        this(TimeUnit.SECONDS);
    }

    public RateLimiter(TimeUnit averageRateUnit) {
        switch (averageRateUnit) {
            case SECONDS:
                rateToMsConversion = 1000;
                break;
            case MINUTES:
                rateToMsConversion = 60 * 1000;
                break;
            default:
                throw new IllegalArgumentException("TimeUnit of " + averageRateUnit + " is not supported");
        }
    }

    //提供给外界获取 token 的方法
    public boolean acquire(int burstSize, long averageRate) {
        return acquire(burstSize, averageRate, System.currentTimeMillis());
    }

    public boolean acquire(int burstSize, long averageRate, long currentTimeMillis) {
        if (burstSize <= 0 || averageRate <= 0) { // Instead of throwing exception, we just let all the traffic go
            return true;
        }

        //添加token
        refillToken(burstSize, averageRate, currentTimeMillis);

        //消费token
        return consumeToken(burstSize);
    }

    private void refillToken(int burstSize, long averageRate, long currentTimeMillis) {
        long refillTime = lastRefillTime.get();
        long timeDelta = currentTimeMillis - refillTime;

        //根据频率计算需要增加多少 token
        long newTokens = timeDelta * averageRate / rateToMsConversion;
        if (newTokens > 0) {
            long newRefillTime = refillTime == 0
                    ? currentTimeMillis
                    : refillTime + newTokens * rateToMsConversion / averageRate;

            // CAS 保证有且仅有一个线程进入填充
            if (lastRefillTime.compareAndSet(refillTime, newRefillTime)) {
                while (true) {
                    int currentLevel = consumedTokens.get();
                    int adjustedLevel = Math.min(currentLevel, burstSize); // In case burstSize decreased
                    int newLevel = (int) Math.max(0, adjustedLevel - newTokens);
                    // while true 直到更新成功为止
                    if (consumedTokens.compareAndSet(currentLevel, newLevel)) {
                        return;
                    }
                }
            }
        }
    }

    private boolean consumeToken(int burstSize) {
        while (true) {
            int currentLevel = consumedTokens.get();
            if (currentLevel >= burstSize) {
                return false;
            }

            // while true 直到没有token 或者 获取到为止
            if (consumedTokens.compareAndSet(currentLevel, currentLevel + 1)) {
                return true;
            }
        }
    }

    public void reset() {
        consumedTokens.set(0);
        lastRefillTime.set(0);
    }
}

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

индукция

Через три вышеуказанных приложения мы резюмируем сценарии применения CAS:

  • Использование CAS позволяет избежать блокировки потоков.
  • Большую часть времени мы используем while true, пока не добьемся успеха.

Недостатки CAS

  1. Проблема с ABA заключается в том, что значение изменилось с A на B, а затем на A. Операция CAS не может обнаружить, что значение изменилось.Метод обработки заключается в использовании версии AtomicStampedReference с аналогичной меткой времени.
  2. Для проблем с производительностью большую часть времени, когда мы его используем, мы используем метод while true для изменения данных до тех пор, пока он не будет успешным. Преимущество в том, что ответ очень быстрый, но когда количество потоков продолжает увеличиваться, производительность значительно падает, потому что каждый поток должен выполняться, занимая процессорное время.

Суммировать

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

С определенной точки зрения, архитектура расширяет микрореализацию, или основная идея состоит в том, чтобы уменьшить макроархитектуру. Идея компьютера раскрыта, поэтому понимание базовой реализации может улучшить архитектурные возможности, а улучшение архитектурных возможностей также может углубить понимание базовой реализации. Компьютерные знания обширны, но процедуры ограничены. Получите несколько основных рутинных прорывов и изучите компьютерные знания с точки зрения мышления и мышления. Не тратьте свою энергию на постоянное стремление к новым технологиям.Следуя «стартовой линии», можно написать только демо, а выигрыш только в демо.

Остановка и повторение основ и классики может еще больше улучшить технологию.

Надеюсь, эта статья будет полезна для всех вас.

Адрес статьи из серии рамок от руки:

Фреймворк Freehand — слияние запросов в среде с высокой степенью параллелизма

Фреймворк Freehand — реализация IoC

Фреймворк Freehand - реализация AOP

Добро пожаловать в мой публичный аккаунт WeChat

二维码