Оригинальный адрес:у-у-у-у. xilidu.com/2018/02/01/…
CAS — важное средство решения проблем параллелизма в современных операционных системах.eureka
исходный код. Столкнулся с большим количеством операций CAS. Сегодня я систематически буду рассматривать CAS в Java.
Прочитав эту статью, вы узнаете:
- Что такое КАС
- Каков принцип реализации CAS?
- Реальное применение CAS
- блокировка спина
- тип атома
- ограничитель тока
- Недостатки CAS
Что такое КАС
CAS: Полное название «Сравнить и поменять местами», буквально: «Сравнить и поменять местами». CAS включает следующие операции:
Мы предполагаем исходные данные V в памяти, старое ожидаемое значение A и новое значение B, которое необходимо изменить.
- Сравнивает A и V на равенство. (сравнивать)
- Если он сравнивается равным, запишите B в V. (обмен)
- Возвращает, была ли операция успешной.
Когда несколько потоков одновременно выполняют 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
- Проблема с ABA заключается в том, что значение изменилось с A на B, а затем на A. Операция CAS не может обнаружить, что значение изменилось.Метод обработки заключается в использовании версии AtomicStampedReference с аналогичной меткой времени.
- Для проблем с производительностью большую часть времени, когда мы его используем, мы используем метод while true для изменения данных до тех пор, пока он не будет успешным. Преимущество в том, что ответ очень быстрый, но когда количество потоков продолжает увеличиваться, производительность значительно падает, потому что каждый поток должен выполняться, занимая процессорное время.
Суммировать
CAS — одна из важных идей всего программирования. CAS присутствует во всей компьютерной реализации. На микроскопическом уровне CAS сборки является краеугольным камнем атомарных операций на уровне операционной системы. С точки зрения языка программирования CAS является краеугольным камнем для реализации многопоточных неблокирующих операций. С макро точки зрения, в распределенных системах мы можем использовать идею CAS, чтобы воспользоваться преимуществами подобныхRedis
Внешнее хранилище также может реализовать распределенную блокировку.
С определенной точки зрения, архитектура расширяет микрореализацию, или основная идея состоит в том, чтобы уменьшить макроархитектуру. Идея компьютера раскрыта, поэтому понимание базовой реализации может улучшить архитектурные возможности, а улучшение архитектурных возможностей также может углубить понимание базовой реализации. Компьютерные знания обширны, но процедуры ограничены. Получите несколько основных рутинных прорывов и изучите компьютерные знания с точки зрения мышления и мышления. Не тратьте свою энергию на постоянное стремление к новым технологиям.Следуя «стартовой линии», можно написать только демо, а выигрыш только в демо.
Остановка и повторение основ и классики может еще больше улучшить технологию.
Надеюсь, эта статья будет полезна для всех вас.
Адрес статьи из серии рамок от руки:
Фреймворк Freehand — слияние запросов в среде с высокой степенью параллелизма
Фреймворк Freehand — реализация IoC
Фреймворк Freehand - реализация AOP
Добро пожаловать в мой публичный аккаунт WeChat