Перейти к основному содержимому

Руководство по AtomicStampedReference в Java

· 4 мин. чтения

Задача: Сумма двух чисел

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

ANDROMEDA

1. Обзор

В предыдущей статье мы узнали, что AtomicStampedReference может предотвратить проблему ABA .

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

2. Зачем нам нужен AtomicStampedReference ?

Во- первых, AtomicStampedReference предоставляет нам как переменную ссылки на объект, так и штамп, который мы можем читать и записывать атомарно . Мы можем думать о метке как о метке времени или номере версии .

Проще говоря, добавление штампа `` позволяет нам определить, когда другой поток изменил общую ссылку с исходной ссылки A на новую ссылку B и обратно на исходную ссылку A.

Посмотрим, как он поведет себя на практике.

3. Пример банковского счета

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

3.1. Чтение значения и его штампа

Во-первых, давайте представим, что наш референс удерживает остаток на счете:

AtomicStampedReference<Integer> account = new AtomicStampedReference<>(100, 0);

Обратите внимание, что мы указали баланс, 100, и штамп, 0.

Чтобы получить доступ к балансу, мы можем использовать метод AtomicStampedReference.getReference() в переменной-члене нашей учетной записи .

Точно так же мы можем получить штамп с помощью AtomicStampedReference.getStamp() .

3.2. Изменение значения и его штампа

Теперь давайте рассмотрим, как атомарно установить значение AtomicStampedReference .

Если мы хотим изменить баланс счета, нам нужно изменить и баланс, и штамп:

if (!account.compareAndSet(balance, balance + 100, stamp, stamp + 1)) {
// retry
}

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

Как мы видим, легко получить ссылку и штамп, используя их геттеры.

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

К счастью, AtomicStampedReference предоставляет нам API на основе массива для достижения этой цели. Давайте продемонстрируем его использование, реализуя метод снятия() для нашего класса Account :

public boolean withdrawal(int funds) {
int[] stamps = new int[1];
int current = this.account.get(stamps);
int newStamp = this.stamp.incrementAndGet();
return this.account.compareAndSet(current, current - funds, stamps[0], newStamp);
}

Точно так же мы можем добавить метод deposit() :

public boolean deposit(int funds) {
int[] stamps = new int[1];
int current = this.account.get(stamps);
int newStamp = this.stamp.incrementAndGet();
return this.account.compareAndSet(current, current + funds, stamps[0], newStamp);
}

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

Например, рассмотрим следующее чередование потоков:

Баланс установлен на $100. Поток 1 запускает депозит(100) до следующей точки:

int[] stamps = new int[1];
int current = this.account.get(stamps);
int newStamp = this.stamp.incrementAndGet();
// Thread 1 is paused here

означает, что депозит еще не завершен.

Затем поток 2 запускает депозит(100) и вывод(100) , доводя баланс до 200 долларов, а затем обратно до 100 долларов.

Наконец, поток 1 запускается:

return this.account.compareAndSet(current, current + 100, stamps[0], newStamp);

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

3.3. Тестирование

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

public class ThreadStampedAccountUnitTest {

@Test
public void givenMultiThread_whenStampedAccount_thenSetBalance() throws InterruptedException {
StampedAccount account = new StampedAccount();

Thread t = new Thread(() -> {
while (!account.deposit(100)) {
Thread.yield();
}
});
t.start();

Thread t2 = new Thread(() -> {
while (!account.withdrawal(100)) {
Thread.yield();
}
});
t2.start();

t.join(10_000);
t2.join(10_000);

assertFalse(t.isAlive());
assertFalse(t2.isAlive());

assertEquals(0, account.getBalance());
assertTrue(account.getStamp() > 0);
}
}

3.4. Выбор следующего штампа

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

Причина этого в том, что если штамп можно изменить на то, что было ранее, это может нарушить цель AtomicStampedReference . Сам AtomicStampedReference не применяет это ограничение, поэтому мы должны следовать этой практике. ** ** ``

4. Вывод

В заключение следует отметить, что AtomicStampedReference — это мощная утилита параллелизма, которая предоставляет как ссылку, так и штамп, которые можно читать и обновлять атомарно. Он был разработан для обнаружения ABA, и его следует предпочесть другим классам параллелизма, таким как AtomicReference , где проблема ABA вызывает беспокойство.

Как всегда, мы можем найти код, доступный на GitHub .