Принцип CAS параллельного программирования

Java задняя часть алгоритм Безопасность

CAS 的原理

предисловие

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


synchronized void function(int b){
  a = a + b；
}

Если синхронизация не добавлена, многопоточная модификация значения a приведет к неправильным результатам и проблемам с безопасностью потоков. Но блокировки — это операции, требовательные к производительности. Будь то блокировка, разблокировка или ожидание блокировки или блокировки, это очень требовательно к производительности. Так нельзя ли его заблокировать?

Может.

Что это обозначает? Давайте посмотрим на приведенный выше код, разделенный на несколько шагов:

  1. читать
  2. добавить а и б
  3. Присвойте вычисленное значение a.

Мы знаем, что это не атомарная операция, и будут проблемы с многопоточностью: когда два потока обращаются к a одновременно, они оба получают значение a, и уведомляют о прибавлении 1 к a, а затем присваивают вычисленное значение в a одновременно. Это приведет к тому, что значение a увеличится только на 1, но на самом деле мы хотим увеличить его на 2.

в чем проблема? Третий шаг — присвоить значение а. Если есть мнение, что а было изменено другим потоком, вам необходимо пересчитать его. Например следующее:


void function(int b) {
   int backup = a;
   int c = a + b;
   compareAndSwap(a, backup, c);
}

void compareAndSwap(int backup ,int c ){
       if (a == backup) {
           a = c;
       }
}

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

Вот проблема: метод compareAndSwap состоит из нескольких шагов, не является атомарным и не использует блокировки, как обеспечить потокобезопасность. На самом деле арендодатель здесь просто псевдокод. Поговорим о том, что такое CAS (compareAndSwap);

Что такое КАС?

CAS (compareAndSwap), по-китайски называемый свопом сравнения, атомарным алгоритмом без блокировок. Процедура такова: она содержит 3 параметра CAS(V,E,N), V представляет собой значение обновляемой переменной, E представляет собой ожидаемое значение, а N представляет новое значение. Значение V устанавливается равным N только тогда, когда значение V равно значению E. Если значения V и E отличаются, это означает, что другие потоки сделали два обновления, а текущий поток ничего не делает. Наконец, CAS возвращает текущее истинное значение V. CAS работает с оптимизмом, всегда думая, что сможет успешно завершить операцию.

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

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

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

Так как же реализован этот CAS? То есть сравнение и обмен — это фактически две операции, как это можно превратить в атомарную операцию?

2. Основополагающий принцип CAS

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

  1. Тест и установка (Tetst-and-Set)
  2. Выборка и увеличение
  3. Менять
  4. Сравнить и поменять местами
  5. Связанный с загрузкой/условный магазин

Среди них первые три относятся к 20 веку, большинство процессоров уже есть, а последние два добавлены современными процессорами. Назначение и функции этих двух инструкций аналогичны: в IA64 в наборе инструкций x86 есть инструкция cmpxchg для завершения функции CAS, в sparc-TSO также есть реализация инструкции casa, а в архитектуре ARM и PowerPC вам нужно использовать пару Инструкция ldrex/strex для завершения функции LL/SC.

ЦП может реализовать атомарные инструкции двумя способами:

  1. Атомарность гарантируется блокировкой шины. Блокировка шины на самом деле означает, что процессор использует блокировку шины.Так называемая блокировка шины заключается в использовании сигнала LOCK#, предоставленного процессором.Когда процессор выводит этот сигнал на шину, запросы других процессоров будут заблокированы, тогда обработка Процессор может монополизировать разделяемую память. Но этот метод слишком дорог. Итак, есть следующий способ.

  2. Атомарность гарантируется блокировкой кеша. Так называемая блокировка кэша означает, что если область памяти кэшируется в строке кэша процессора и блокируется во время операции блокировки, то при выполнении операции блокировки и обратной записи в память процессор не выставляет сигнал LOCK#. на шине, и когда Изменить адрес внутренней памяти и разрешить механизм когерентности кеша для обеспечения атомарности операции, потому что механизм когерентности кеша предотвратит одновременное изменение данных области памяти, кэшированных более чем двумя процессорами ( это то же самое, что и принцип видимости volatile), который делает строку кэша недействительной, когда другие процессоры записывают обратно данные заблокированной строки кэша.

Примечание. Есть две ситуации, в которых процессор не будет использовать блокировку кэша.

  1. Когда данные операции не могут быть кэшированы внутри процессора или данные операции занимают несколько строк кэша, процессор вызоветавтобусный замок.
  2. Некоторые процессоры не поддерживают блокировку кэширования. Для процессоров Intel 486 и Pentium, заблокировка шины также вызывается для заблокированных областей памяти на линии кэша процессора.

3. Как Java реализует атомарные операции

Java предоставляет пакет java.util.concurrent.atomic в версии 1.5, и все классы в этом пакете являются атомарными операциями:

java.util.concurrent.atomic 包

Как это использовать? см. код

  public static void main(String[] args) throws InterruptedException {
    AtomicInteger integer = new AtomicInteger();
    System.out.println(integer.get());


    Thread[] threads = new Thread[1000];

    for (int j = 0; j < 1000; j++) {
      threads[j] = new Thread(() ->
          integer.incrementAndGet()
      );
      threads[j].start();
    }

    for (int j = 0; j < 1000; j++) {
      threads[j].join();
    }

    System.out.println(integer.get());
  }
}

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

Взглянем на его внутреннюю реализацию, находим метод compareAndSet этого класса, то есть сравнить и установить. Посмотрим на реализацию этого метода:

Этот метод вызывает метод compareAndSwapInt небезопасного класса с несколькими параметрами, один из которых — адрес переменной в памяти, один — ожидаемое значение, один — обновленное значение, а третий — сам объект. Полностью соответствует нашему предыдущему определению CAS. Так что же это небезопасно?

Класс rt.jar в пакете, но не под привычным пакетом java, а под пакетом sun.misc. И все файлы класса, комментарии не соответствуют его имени: небезопасность.

Можем ли мы построить его? Нет, если не отражается.

Давайте посмотрим на его исходный код:

В методе getUnsafe будет проверяться класс, вызывающий метод getUnsafe.Если ClassLoader этого класса не нулевой, то сразу будет выброшено исключение.При каких обстоятельствах оно будет нулевым? Когда загрузчик классов является загрузчиком Bootstrap, загрузчик Bootstrap не имеет объекта, то есть загруженный класс, скорее всего, находится под rt.jar.

В последней версии Java 9 этот класс был скрыт. Потому что класс использует указатели. Но недостаток указателей в том, что они небезопасны.

4. Недостатки CAS

CAS выглядит очень болтающимся, но у него все еще есть недостатки.Самая известная из них - проблема ABA. Предположим, что переменная A изменяется на B, а затем изменяется на A. Механизм CAS необнаружим, но на самом деле он был изменен. Если это примитивный тип, то все в порядке, но что, если это ссылочный тип? В этом объекте несколько переменных, как узнать, были ли они изменены? Умно, вы, должно быть, подумали об этом, добавьте номер версии. Проверяйте номер версии каждый раз, когда вы его изменяете. Если номер версии изменился, это означает, что он был изменен, даже если вы все еще А.

В пакете java.util.concurrent.atomic есть AtomicReference для обеспечения цитирования атомарности, но домовладелец чувствует себя немного безвкусно, лучше использовать синхротрон взаимоисключающие, может быть более эффективным.

Суммировать

Сегодня мы понимаем принцип CAS с разных сторон.Алгоритм очень важен, что видно из специально разработанной процессором инструкции для его реализации. В исходниках JDK везде есть небезопасные алгоритмы CAS, можно сказать, что если CAS не будет, то не будет и 1,5 concurrent-контейнеров. Хорошо, это все на сегодня.

удачи! ! !

Категории