Углубленный анализ AQS и CAS, все сказали хорошо после прочтения

Java

предисловие

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

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

Теперь каждое письмо похоже на произведение искусства, каждый раз тщательно вырезанное и обработанное. статьи"логический","разборчивость",а также"Эстетика оформления статьи", следует внимательно рассмотреть.

Напишите перед тарелкой куриного супа:"И мир не спаситель, это если есть ты сам; нет на свете чуда, если было другое имя, только пытающийся Бэйл."

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

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

Введение в AQS

AQS（AbstractQueuedSynchronizer）за"Абстрактный синхронизатор очереди",Проще говоря"AQS — это абстрактный класс", абстрактный классAbstractQueuedSynchronizer, не реализует никакого интерфейса,"Определены только методы для получения и освобождения синхронизированного состояния.".

это обеспечивает"FIFO-очередь", когда несколько потоков конкурируют за ресурсы, потоки, которые не конкурировали, помещаются в очередь для ожидания, и"Определяет структуру синхронизации для многопоточного доступа к общим ресурсам.".

В AQS есть два типа блокировок:"Эксклюзив (эксклюзивный замок)"а также"Поделиться (общий замок)".

"эксклюзивный замок"то есть"Одновременно работает только один поток",НапримерReentrantLock. О ReentrantLock я уже писал подробную статью с исходным кодом, если она вам нравится, вы можете взглянуть на [].

"общий замок"то есть"Может работать в нескольких потоках одновременно",какSemaphore、CountDownLatch、ReentrantReadWriteLock.

Анализ исходного кода AQS

В исходном коде AQS вы можете видеть, что для"общая переменная состояния",использовать"изменчивое ключевое слово"модифицировать так, чтобы"Гарантированная видимость", если вы не знакомы с ключевым словом volatile, вы можете обратиться к этой статье []. Как видно из приведенного выше исходного кода, операция модификации состояния обеспечиваетsetStateа такжеcompareAndSetState,"Так зачем же предоставлять эти две модификации государству?"

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

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

Проанализировав реализацию исходного кода AQS, давайте взглянем на принцип реализации AQS. Исходный код реализации и теория AQS здесь будут относительно простыми, потому что не задействован конкретный класс реализации.

Принцип реализации СКС

Как упоминалось выше, AQS поддерживает"FIFO-очередь",а также"Очередь представляет собой двусвязный список", каждый узел в связанном списке"Узел узла","Класс Node является внутренним классом в AbstractQueuedSynchronizer.".

Давайте взглянем на исходный код внутреннего класса Node в AQS, который поможет нам лучше понять внутреннюю реализацию AQS:

 static final class Node {

    static final Node SHARED = new Node();
    static final Node EXCLUSIVE = null;
    static final int CANCELLED =  1;
    static final int SIGNAL    = -1;
    static final int CONDITION = -2;
    static final int PROPAGATE = -3;
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;

    final boolean isShared() {
        return nextWaiter == SHARED;
    }

    final Node predecessor() throws NullPointerException {
        Node p = prev;
        if (p == null)
            throw new NullPointerException();
        else
            return p;
    }

    Node() {    // Used to establish initial head or SHARED marker
    }

    Node(Thread thread, Node mode) {     // Used by addWaiter
        this.nextWaiter = mode;
        this.thread = thread;
    }

    Node(Thread thread, int waitStatus) { // Used by Condition
        this.waitStatus = waitStatus;
        this.thread = thread;
    }
}


скопировать код

Можно видеть, что приведенный выше класс Node относительно прост и поддерживает только атрибуты, принадлежащие каждому узлу Node.Наиболее важными базовыми компонентами внутреннего класса Node являются следующие:

    volatile Node prev;
    volatile Node next;
    volatile Thread thread;

"По анализу исходного кода и принципу конкуренции потоков за общие ресурсы", По поводу принципа реализации AQS нарисовал тут картинку:В очереди FIFO,"Головной узел держит замок", то есть головной узел является держателем блокировки, а хвостовой указатель указывает на последний ожидающий узел потока очереди."указатель вперед"а также"указатель преемника"

поддерживается в AQS a"состояние общей переменной", определяет, удерживается ли текущий ресурс потоком, когда многопоточная конкуренция будет определять, равно ли состояние 0, попытаться изменить состояние на 1

Реализация исходного кода и принципиальная реализация AQS проанализированы, но конкретной реализации синхронизации в AQS нет.Если вы хотите понять конкретный принцип реализации AQS, вам нужно посмотреть на конкретный класс реализации AQS.ReentrantLockНапример.

Принцип реализации ReentrantLock

Если несколько потоков конкурируют за общие ресурсы,"Потоки, которые не могут конкурировать, будут добавлены в конец очереди FIFO.".

существуетReentrantLockВ конкретной реализации здесь в качестве примера используется реализация несправедливых блокировок в ReentrantLock, поскольку о реализации справедливых блокировок была написана и проанализирована статья ранее.

Давайте посмотрим на логику реализации исходного кода только что добавленного узла:Введите напрямую, когда поток, конкурирующий за ресурс блокировки, терпит неудачуacquire(1)метод, давайте взглянем на конкретную реализацию метода Acquisition(1):Как видно из исходного кода, в реализации accept(1) в основном используется логика этих трех шагов:

  1. tryAcquire(arg): повторная попытка получить блокировку.
  2. addWaiter(Node.EXCLUSIVE): если получение блокировки не удается, текущий поток будет собран в узел Node, и будет выполнена правильная операция.
  3. acquireQueued(addWaiter(Node.EXCLUSIVE), arg)): методAcquireQueued принимает головной узел, возвращенный addWaiter, в качестве параметра, а внутренняя реализация выполняет цикл блокировки и определяет, следует ли приостановить поток выполнения.

Давайте взглянемtryAcquire(arg)Исходный код , из приведенного выше, мы можем видеть, что значение arg равно 1. Конкретный исходный код реализации выглядит следующим образом:

Из анализа исходного кода видно, чтоtryAcquire(arg)Реализация должна определить, было ли выпущено значение состояния,"Если она будет освобождена, текущий поток установит состояние CAS в 1. Если он не будет освобожден, он определит, может ли блокировка быть повторно введена.".

После анализаtryAcquire(arg)реализация посмотримaddWaiter, исходный код реализации операции постановки в очередь выглядит следующим образом:Из приведенного выше анализа исходного кода видно, что метод вставки хвоста используется для добавления вновь добавленного потока в двусвязный список.Конкретная схема реализации выглядит следующим образом.Из приведенного выше анализа видно, что когда поток находится в очереди, он в основном выполняет следующие действия."Вновь добавленный указатель prev узла указывает на исходный хвостовой узел, а следующий указатель исходного хвостового узла указывает на вновь добавленный узел.", это тоже обычное дело"двусторонняя интерполяция хвоста списка"операция.

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

Конечно, предпосылка здесь заключается в том, что"Очередь не пуста", если он пуст, он не будет следовать приведенной выше логике, ноenq(node), чтобы инициализировать узел, давайте посмотримenq(node)Операция, исходный код выглядит следующим образом:После выполнения описанной выше операции сопряжения выполнитеacquireQueuedметод, давайте взглянем на его конкретный исходный код реализации:Как видно из исходного кода выше, он включает в себя"Удалите головной узел из очереди"операция и будет"Узел узла текущего потока повышается до головного узла".

потому что только"Головной узел является держателем замка", поэтому для операции удаления из очереди головного узла направление головы изменится в любое время Я нарисовал схематическую диаграмму следующим образом:Конкретная реализация показана на рисунке выше, а"Исходный головной узел удаляется из очереди, то есть указатель исходного головного узла next указывает на null, а указатель prev исходного второго узла указывает на null".

Наконец, наведите указатель на второй узел Конечно, поток 2 также изменит значение общей переменной состояния state, тем самым завершив снятие блокировки.

Когда блокировка будет снята, она будет выполненаshouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()Чтобы определить, следует ли приостановить текущий поток, давайте взглянем на его реализацию в исходном коде:существуетshouldParkAfterFailedAcquireРеализация в , количество состояний текущего узла драйвераwaitStatusзаSIGNAL, он будет висеть.Благодаря приведенному выше анализу у нас есть относительно четкое представление о реализации AQS, в основном для класса реализации.ReentrantLockУглубленный анализ принципа реализации , и основан на"несправедливый замок"а также"эксклюзивный замок"реализация.

Поддерживается в нижней части AQS a"FIFO-очередь", когда несколько потоков конкурируют за общие ресурсы,"Неудачные потоки добавляются в очередь","несправедливый замок"В реализации вновь добавленный узел потока будет"вращение"Попытка получить замок.

Проанализировав AQS, давайте проанализируем CAS,"Так что же такое КАС?"

Введение в CAS

в анализеReentrantLockВ исходном коде конкретной реализации видно, что все операции, связанные с установкой общих переменных, будут указывать на операции CAS для обеспечения атомарных операций.

CAS(compare and swap)Примитивное понимание означает сравнение и обмен."CAS — это реализация оптимистической блокировки.".

В алгоритме реализации CAS есть три значения:"обновленная переменная","старое значение","новое значение". При изменении общего ресурса оно будет сравниваться с исходным значением, и если оно равно исходному значению, оно будет изменено на новое значение.

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

Но CAS также может вызвать проблемы с ABA,"В чем проблема АБА?"Не паникуйте, пожалуйста, выслушайте меня подробно

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

Проблема ABA заключается в том, что если есть два потока, читающие общую переменную одновременноstate=1, после чего оба потока присвоили копию состояния своей рабочей памяти.

Когда изменяется пара состояний потоковstate=state+1, и писать в оперативную память, а потом нитьstate=state-1При записи в основную память состояние основной памяти менялось дважды, но возвращалось к исходному значению.

Затем, когда поток 2 изменит состояние, оно будет успешно изменено, что является проблемой ABA. за"Решение проблемы ABA заключается в добавлении номера версии (версии)", при каждом сравнении также сравнивается номер версии.

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

Анализ производительности CAS

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

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

Категории