С начала года основное внимание в области параллельных алгоритмов уделяетсяалгоритм отсутствия перегрузок, этот алгоритм опирается на поддержку базовым оборудованием атомарных инструкций и избегает использования блокировок для обеспечения согласованности данных и безопасности многопоточности. Хотя алгоритм без перегрузки более сложен по дизайну, он обладает лучшей масштабируемостью и производительностью и широко используется для реализации счетчиков, секвенсоров, сборщиков статистики и т. д.
1. Недостатки замков
В предыдущей статье встроенная блокировка метода синхронизации сравнивалась с явной блокировкой, чтобы проиллюстрировать их соответствующие преимущества, но независимо от того, является ли это встроенной или явной блокировкой, суть заключается в поддержании многопоточной безопасности посредством блокировки. .
Из-за механизма блокировки потоки неизбежно будут приостанавливать и возобновлять потоки в процессе применения блокировок и ожидания блокировки.Такое переключение потоков между текстами принесет много накладных расходов, особенно когда конкуренция за ресурсы блокировки является жесткой.
В то же время в процессе ожидания блокировки поток ничего не делает из-за блокировки, а бесконечное условное ожидание не только неэффективно, но и легко может вызвать взаимоблокировку.
2. Пессимистическая блокировка и оптимистичная блокировка
Будь то встроенная блокировка или явная блокировка, это эксклюзивная блокировка, ипессимистический замок. Так называемая пессимистическая блокировка с пессимистической точки зрения, полагая, что если она не заблокирована, другие потоки изменят данные, нарушат согласованность и повлияют на безопасность многопоточности.Поэтому поток должен быть заблокирован, чтобы монополизировать ресурсы.
По сравнению с пессимистическими блокировками есть более эффективные методы —оптимистическая блокировка, этот замок требует помощимеханизм проверки конфликтовЧтобы определить, есть ли помехи от других потоков в процессе обновления, если помех нет, операция выполнена успешно, если есть помехи, операция завершается ошибкой, и вы можете повторить попытку или применить другие стратегии. Другими словами,оптимистическая блокировкаТребуется поддержка атомарных инструкций «чтение-изменение-запись», чтобы считывать, были ли данные изменены другими потоками, перезаписывать содержимое данных и записывать последние данные обратно по исходному адресу. Большинство современных процессоров также могут поддерживать такие операции.
3. Сравнить и поменять местами операции CAS
Большинство платформ процессоров реализуют оптимистическую блокировку, реализуя инструкцию сравнения и замены (CAS). Инструкция CAS содержит три операнда: ячейку памяти V для чтения и записи, значение A для сравнения и новое значение B для записи. Если и только если значение в V равно A, это означает, что значение в V не было изменено, и инструкция атомарно обновит его до значения B, в противном случае она не будет выполнять никаких операций. CAS возвращает исходное значение в V независимо от того, выполнена операция или нет. Код ниже имитирует семантику CAS.
public class SimulatedCAS {
@GuardedBy("this") private int value;
public synchronized int get() {
return value;
}
// CAS = compare and swap
public synchronized int compareAndSwap(int expectedValue,
int newValue) {
int oldValue = value;
if (oldValue == expectedValue)
value = newValue;
return oldValue;
}
public synchronized boolean compareAndSet(int expectedValue,
int newValue) {
return (expectedValue
== compareAndSwap(expectedValue, newValue));
}
}
Когда несколько потоков пытаются обновить одно и то же значение, только один поток завершается успешно, а все остальные потоки терпят неудачу, но в CAS сбойный поток не будет перегружен, и вы можете определить, как поступить в случае сбоя, повторить или отменить операцию. больше гибкости.
Обычно CAS используется следующим образом: сначала считывается значение A из V, вычисляется значение B в соответствии со значением A, а затем атомарно обновляется значение в V через CAS. Возьмите счетчик в качестве примера
public class CasCounter {
private SimulatedCAS value;
public int getValue() {
return value.get();
}
public int increment() {
int v;
do {
// 获得当前的值
v = value.get();
} while (v != value.compareAndSwap(v, v + 1));
// 如果返回值不同，则说明更新成功了
return v + 1;
}
}
Атомарные операции «чтение-изменение-запись» реализованы без блокировок.
Метод CAS имеет большие преимущества в производительности: в случае, когда степень конкуренции не очень велика, работа на основе CAS намного превосходит по производительности счетчик на основе блокировки, при отсутствии конкуренции производительность CAS выше.
Но недостатком CAS является то, что проблема конкуренции остается на усмотрение вызывающей стороны, а пессимистическая блокировка сама может справиться с конкуренцией.
4. Атомарные переменные
Благодаря поддержке инструкций по атомарным операциям на оборудовании CAS также представлен в Java. Для ссылок типа int, long и object Java поддерживает операции CAS, т. е.Класс атомарной переменной, JVM будет компилировать операции над классами атомарных переменных в наиболее эффективный метод, предоставляемый базовым оборудованием: если оборудование поддерживает CAS, оно будет скомпилировано в инструкцию CAS, если нет, оно будет скомпилировано в заблокированную операцию.
Атомарные переменные более детализированы и легче, чем блокировки, сохраняя конкуренцию за одну переменную. Поскольку его не нужно блокировать, он не приведет к приостановке и восстановлению потока, что позволит избежать переключения контекста между потоками, повысить производительность и с меньшей вероятностью вызвать задержки и взаимоблокировки.
Общие атомарные переменныеAtomicInteger,AtomicLong,AtomicBooleanа такжеAtomicReference, эти классы поддерживают атомарные операции, используя методы get и set для получения и обновления объектов.массив атомарных переменныхтолько поддержкаAtomicInteger,AtomicLongа такжеAtomicReferenceтип, который гарантирует, что каждый элемент в массиве может быть доступен с изменчивой семантикой.
Следует отметить, что атомарные переменные не определяют методы hashCode и equals, поэтому каждый экземпляр отличается и не подходит в качестве ключа для хеш-контейнера.
Атомарные переменные можно рассматривать как лучший тип изменчивых переменных.compareAndSetМетод пытается обновить данные в методе CAS.Ниже приведен пример кода для реализации числового интервала, чтобы показать, как его использовать.AtomicReference.
public class CasNumberRange {
@Immutable
private static class IntPair {
// INVARIANT: lower <= upper
final int lower;
final int upper;
public IntPair(int lower, int upper) {
this.lower = lower;
this.upper = upper;
}
}
//源自引用 IntPair 初始化为[0，0]
private final AtomicReference<IntPair> values =
new AtomicReference<IntPair>(new IntPair(0, 0));
public int getLower() {
return values.get().lower;
}
public int getUpper() {
return values.get().upper;
}
//设置下限
public void setLower(int i) {
//开始循环尝试
while (true) {
// 获得变量值
IntPair oldv = values.get();
// 如果下限设置比当前上限还要大
if (i > oldv.upper)
//抛出异常
throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
IntPair newv = new IntPair(i, oldv.upper);
//原子性更新
if (values.compareAndSet(oldv, newv))
//如果更新成功则直接返回，否者重新尝试
return;
}
}
//设置上限 过程和setLower类似
public void setUpper(int i) {
while (true) {
IntPair oldv = values.get();
if (i < oldv.lower)
throw new IllegalArgumentException("Can't set upper to " + i + " < lower");
IntPair newv = new IntPair(oldv.lower, i);
if (values.compareAndSet(oldv, newv))
return;
}
}
}
Сравнение производительности:
Как упоминалось выше, атомарные переменные имеют большие преимущества в производительности из-за использования в них CAS: в случае, когда степень конкуренции не очень велика, операции на основе CAS намного превосходят по производительности счетчики на основе блокировок; производительность CAS выше, но в случае высокой конкуренции производительность блокировки будет превосходить производительность атомарных переменных (аналогично, при небольшой загруженности трафика эффект драгирования с обходом хороший, но при сильной загруженности трафика , семафор обеспечивает более высокую пропускную способность).
Однако следует отметить, что в среде реального использования интенсивность конкуренции за ресурсы не будет достаточно большой, чтобы в большинстве случаев производительность блокировки превышала производительность атомарной переменной. Следовательно, использование атомарных переменных все же должно быть предпочтительным.
Разница в производительности между блокировками и атомарными переменными на разных уровнях конкуренции является хорошей иллюстрацией их соответствующих преимуществ: при низкой и средней конкуренции атомарные переменные обеспечивают более высокую масштабируемость, в то время как при высокой конкуренции блокировки могут эффективно избегать конкуренции.
Конечно, если вы можете избежать использования общего состояния в нескольких потоках, вместо этого используйте закрытие потока (например,ThreadLocal), производительность кода будет улучшена.
5. Неблокирующий алгоритм
Если отказ или приостановка одного потока не приводит к отказу и приостановке других потоков в алгоритме, алгоритмнеблокирующий алгоритм. Алгоритм является неблокирующим, если существует поток, который может выполнять его на каждом шаге алгоритма.
Если в алгоритме используется только CAS для координации операций между потоками, и его можно правильно реализовать, то алгоритм является одновременно неблокирующим алгоритмом и алгоритмом без блокировки. В неперегруженном алгоритме проблема инверсии приоритета тупика не возникает (но не исключена проблема лайвлока и нехватки ресурсов, т.к. алгоритм будет повторять попытки).
вышесказанноеCasNumberRangeЭто неблокирующий алгоритм, который иллюстрирует базовую схему разработки алгоритма без перегрузок: существует неопределенность при обновлении значения, и если это не удается, попробуйте еще раз. Ключевым моментом является сужение объема выполнения CAS до одной переменной.
5.1 Неблокирующий стек
Мы возьмем неблокирующий стек в качестве примера, чтобы проиллюстрировать идею дизайна алгоритма без перегрузки. Ключом к созданию неблокирующего алгоритма является сокращение объема атомарных модификаций до одной переменной при сохранении согласованности данных.
Стек представляет собой простейшую структуру данных с цепочкой: каждый элемент указывает только на один элемент, и на каждый элемент ссылается только один элемент, а ключевые операции со стеком (push) и pop (выталкивание) относятся к верхнему элементу стека. (сверху). Следовательно, каждой операции нужно только обеспечить согласованность верхнего элемента стека и контролировать область действия атомарной операции по ссылке на верхний элемент стека. Пример кода выглядит следующим образом:
//非阻塞的并发栈
public class ConcurrentStack <E> {
//原子对象 栈顶元素
AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();
public void push(E item) {
Node<E> newHead = new Node<E>(item);
Node<E> oldHead;
do { //循环尝试
oldHead = top.get();//获得旧值
newHead.next = oldHead;
} while (!top.compareAndSet(oldHead, newHead)); //比较旧值是否被修改，如果没有则操作成功，否者继续尝试；
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = top.get();
if (oldHead == null)
return null;
newHead = oldHead.next;
} while (!top.compareAndSet(oldHead, newHead));
return oldHead.item;
}
private static class Node <E> {
public final E item;
public Node<E> next;
public Node(E item) {
this.item = item;
}
}
}
Приведенный выше код полностью отражает характеристики неблокирующего алгоритма:Завершение операции является неопределенным и должно быть выполнено повторно в случае неудачи. Этот стек проходит черезcompareAndSetЧтобы изменить верхний элемент стека, этот метод является атомарной операцией. Если будет обнаружено, что другие потоки мешают ему, операция модификации завершится ошибкой, и метод попытается повторить попытку.
Безопасность многопоточности в алгоритмах зависит отcompareAndSet, который обеспечивает такую же безопасность, как запорный механизм. Это не только гарантирует атомарность, но и гарантирует видимость. Помимо,AtomicReferenceИспользование метода get для объекта также гарантирует видимость памяти, а использованиеvolatileпеременные одинаковые.
5.2 Неблокирующие связанные списки
Структура связанного списка сложнее, чем у стека, он должен поддерживать указатель на начало и указатель на хвост, и есть два указателя, указывающих на хвост одновременно, а именно указатель на хвост и указатель на последний элемент, следующий за ним. . Как обеспечить согласованность данных двух указателей — сложная задача, которую нельзя решить с помощью операции CAS.
Эту проблему можно решить, применив хитрость: когда поток B обнаруживает, что поток A модифицирует структуру данных, в структуре данных должно быть достаточно информации, чтобы поток B мог помочь потоку A завершить операцию и обеспечить согласованность данных. структура.
Возьмем операцию вставки в качестве примера для анализа. Процесс вставки состоит из двух шагов:
- Вставьте новый узел и укажите следующее поле исходного хвостового узла на этот узел;
- Переместите указатель хвоста на новый хвостовой узел.
Следовательно, мы можем судить о том, находится ли связанный список в стабильном состоянии по следующему полю хвостового узла: если следующее поле хвостового узла равно нулю, это означает, что связанный список находится в стабильном состоянии, и никакой другой потоки выполняют операцию вставки, иначе следующее поле узла не равно null , это означает, что другие потоки вставляют данные.
Что делать, если связанный список не находится в стабильном состоянии? Поток, который прибывает позже, может помочь потоку, выполняющему вставку, переместить хвостовой указатель обратно к только что вставленному узлу. Пример кода выглядит следующим образом:
public class LinkedQueue <E> {
private static class Node <E> {
final E item;
//下一个节点
final AtomicReference<Node<E>> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = new AtomicReference<Node<E>>(next);
}
}
//哑结点 也是头结点
private final Node<E> dummy = new Node<E>(null, null);
private final AtomicReference<Node<E>> head
= new AtomicReference<Node<E>>(dummy);
//尾部节点
private final AtomicReference<Node<E>> tail
= new AtomicReference<Node<E>>(dummy);
public boolean put(E item) {
Node<E> newNode = new Node<E>(item, null);
while (true) {
Node<E> curTail = tail.get();
Node<E> tailNext = curTail.next.get();
//得到尾部节点
if (curTail == tail.get()) {
// 1. 尾部节点的后续节点不为空，则队列处于不一致的状态
if (tailNext != null) {
// 2. 将为尾部节点向后退进；
tail.compareAndSet(curTail, tailNext);
} else {
// 3. 尾部节点的后续节点为空，则队列处于一致的状态，尝试更新
if (curTail.next.compareAndSet(null, newNode)) {
// 4. 更新成功，将为尾部节点向后退进；
tail.compareAndSet(curTail, newNode);
return true;
}
}
}
}
}
}
Если обнаружится, что связанный список находится в нестабильном состоянии на первом шаге, он попытается атомарным образом переместить хвостовой указатель на вновь вставленный узел. в стабильное состояние, tail.next=null, а затем еще раз, чтобы повторить попытку. Если шаг 2 переместил хвостовой указатель связанного списка, то атомарная операция на шаге 4 завершится неудачно, но это не имеет значения, потому что другие потоки уже помогли ей завершить операцию, и связанный список остается стабильным.
5.3 Средство обновления атомарного домена
Неперегруженный связанный список, упомянутый выше, вConcurrentLinkedQueueприменяется, ноConcurrentLinkedQueueВместо использования атомарных переменных используйте обычные переменные volatile с помощью средства обновления атомарного поля на основе отражения (AtomicReferenceFieldUpdater) обновить.
Средство обновления атомарного поля представляет собой «представление» существующих изменчивых полей на основе отражения, позволяющее использовать инструкции CAS для изменчивых полей. У средств обновления атомных полей нет конструкторов, для создания объектов необходимо использовать фабричные методы.newUpdater, функция аннотируется следующим образом
/**
* @param tclass 持有待更新域的类
* @param vclass 待更新域的类型
* @param fieldName 待更新域的名字
*/
public static <U,W> AtomicReferenceFieldUpdater<U,W> newUpdater(Class<U> tclass,
Class<W> vclass,
String fieldName)；
Преимущество использования средства обновления заключается в том, чтобы избежать накладных расходов на создание атомарных переменных, но это подходит только для объектов, которые часто выделяются и имеют короткий жизненный цикл, например узлы списка.В других случаях можно использовать атомарные переменные. .
5.4 Атомарные переменные с номерами версий
Операция CAS определяет, было ли изменено исходное значение путем сравнения значения, но может быть и такая ситуация: исходное значение A модифицируется на B, а затем модифицируется на A, то есть модификация A-B-A. В настоящее время невозможно судить, было ли оно изменено, путем сравнения исходного значения. Эта проблема также известна какАВА-проблема.
Решение проблемы ABA заключается в добавлении номера версии к значению переменной. Если номер версии меняется, это означает, что исходное значение было изменено. Это атомарная переменная с отметкой времени.AtomicStampedReference
//原值和时间戳
public AtomicStampedReference(V initialRef, int initialStamp)；
Суммировать
Алгоритм отсутствия перегрузки обеспечивает безопасность многопоточности с помощью базовой инструкции CAS. Инструкция CAS инкапсулируется в виде атомарных переменных и доступна для общественности. Это лучшая изменчивая переменная, которая может обеспечить лучшую масштабируемость и предотвратить тупиковые ситуации. Однако дизайн и реализация более сложны и предъявляют высокие требования к разработчикам.
Дальнейшее чтение:
- Безопасность многопоточности: об этом говорят все, но не все
- Совместное использование объектов: раздражает в среде параллелизма Java
- Понимание безопасной инициализации с точки зрения модели памяти Java
- От задач к потокам: структурированные параллельные приложения в Java
- Правильный способ закрытия потока: «изящные» прерывания
- Освоение пулов потоков Java: настройка и расширение
- Изучение модулей параллелизма Java: контейнеры и служебные классы
- Расширенный механизм блокировки Java: явная блокировка ReentrantLock