Атомарни операции и неизменими обекти

Код на:JavaC#PythonJavaScript

Накратко: Атомарната операция (например +1 или compare-and-set) се изпълнява наведнъж, без друга нишка да я прекъсне, и пази споделени данни без ключалка; неизменимият обект изобщо не се променя.

Проблем

Ключалка за едно +1

Флаш разпродажба: 100 слушалки на половин цена, в 10:00. Страницата на продукта се отваря хиляди пъти в секунда, а всяко отваряне увеличава брояча на изгледите. От урока за ключалките знаеш как да не се губят увеличения: ключалка около views++.

Това е правилно. Но всяка нишка застава на опашка пред ключалката заради едно-единствено +1. Нишка, която не получи ключалката, често бива приспана и после събудена от операционната система. Това струва много повече от самото събиране.

Втората беда е по-лоша. Последната бройка се купува с „ако има, намали с 1“. Това са две стъпки, а между тях друга нишка може да вземе същата бройка.

Идеята

Неделима стъпка

Процесорът има команди, които прочитат, сменят и записват една клетка от паметта с една неделима стъпка. Никоя друга нишка не може да се намеси по средата. Това е атомарна операция (atomic). Не трябва ключалка, никой не чака на опашка и никой не заспива.

В Java те са в java.util.concurrent.atomic. AtomicInteger пази едно int, а incrementAndGet() е атомарното +1 и връща новата стойност. Има и addAndGet, getAndIncrement, AtomicLong за long.

Виж го

Броячът на изгледите

Четири нишки, всяка с по 100 000 изгледа:

AtomicInteger views = new AtomicInteger();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Изгледи: " + views.get());

Изход

Изгледи: 400000

400 000 при всяко пускане. Без атомарното +1 щеше да е по-малко и различно всеки път, както в урока за race condition.

По-точно, за любопитните

LongAdder. Когато много нишки увеличават един и същ AtomicInteger, всички удрят една клетка от паметта и процесорите си я подават. LongAdder брои в няколко клетки (по една за група нишки) и ги събира чак при sum(). Той е по-бърз под голямо натоварване, но не дава стойността след всяко увеличаване. Става за броячи, които само се четат накрая:

LongAdder views = new LongAdder();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.increment();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Изгледи: " + views.sum());

Изход

Изгледи: 400000

Колко по-бързо е от ключалка? Зависи от машината и от това колко нишки се бият за една клетка. Без борба атомарното +1 е няколко наносекунди. Ключалката без борба е близо до него. Разликата идва при много нишки: тогава ключалката приспива, а атомарната операция само повтаря.

Идеята

Провери и смени: compare-and-set

Купуването не е само −1. То е „ако има поне една, намали с 1“. Проверката и смяната трябва да са една стъпка.

За това има по-обща атомарна операция: compare-and-set (CAS, „сравни и смени“). Казваш ѝ две числа: какво мислиш, че има, и какво искаш да има. Тя сменя стойността само ако тя е още тази, която мислиш, и казва дали е успяла. Ако друга нишка я е сменила междувременно, CAS не пипа нищо и отговаря „не“.

Тогава купуването е цикъл:

1. прочети наличността;
2. ако е 0, отказ;
3. CAS: „ако е още толкова, направи я с 1 по-малко“;
4. ако CAS не успее, някой е купил междувременно: върни се на 1.

В Java това е compareAndSet(очаквано, ново), който връща true или false.

Виж го

Последните три слушалки

class FlashSale {
    private final AtomicInteger stock;

    FlashSale(int items) {
        stock = new AtomicInteger(items);
    }

    boolean tryBuy() {
        while (true) {
            int left = stock.get();
            if (left == 0) return false; // разпродадено
            if (stock.compareAndSet(left, left - 1)) {
                return true;
            }
            // друг е сменил stock: прочети пак
        }
    }

    int stock() {
        return stock.get();
    }
}

Стъпка по стъпка, с думи

1. Последните 3 слушалки: наличността е 3. Нишките A и B викат tryBuy() едновременно.
2. A прочита наличността: left = 3.
3. B я прочита, преди A да е сменила нещо: също 3.
4. B: compareAndSet(3, 2). „Ако още е 3, направи го 2.“ Още е 3, затова се записва 2. B купи.
5. A пробва същото: „ако още е 3…“. Вече е 2, затова нищо не се записва и отговорът е false. Нищо не е загубено.
6. A не чака и не се отказва: цикълът се завърта и A прочита пак: 2. Нито една нишка не е заспивала.
7. A: „ако още е 2, направи го 1“. Още е 2: записва се 1. A също купи.
8. Двама купувачи, две продадени, наличност 1. Ключалка няма: процесорът проверява и записва с една стъпка, а който загуби, само повтаря цикъла.

Никой не чака: нишката, която загуби, само повтаря два реда. Това се казва lock-free (без ключалка). Сто купувачи на 160 опита:

FlashSale sale = new FlashSale(100);
AtomicInteger sold = new AtomicInteger();
AtomicInteger refused = new AtomicInteger();
Runnable buyers = () -> {
    for (int i = 0; i < 40; i++) {
        if (sale.tryBuy()) sold.incrementAndGet();
        else refused.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(buyers);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Продадени: " + sold.get());
System.out.println("Отказани: " + refused.get());
System.out.println("Наличност: " + sale.stock());

Изход

Продадени: 100
Отказани: 60
Наличност: 0

Колко пъти се е завъртял цикълът, е различно при всяко пускане. Затова програмата не го печата. Сборът е винаги един и същ: 100 продадени, 60 отказа, 0 на склад.

Пробвай

Предвиди изхода

Тук двете „нишки“ са написани една след друга в една нишка, за да е редът същият като в сцената при всяко пускане. Какво ще отпечата?

AtomicInteger stock = new AtomicInteger(3);
int seenByA = stock.get();
int seenByB = stock.get();
System.out.println("B: " + stock.compareAndSet(seenByB, seenByB - 1));
System.out.println("A: " + stock.compareAndSet(seenByA, seenByA - 1));
seenByA = stock.get();
System.out.println("A отново: " + stock.compareAndSet(seenByA, seenByA - 1));
System.out.println("Наличност: " + stock.get());

Отговор

B: true
A: false
A отново: true
Наличност: 1

B: true
A: true
A отново: true
Наличност: 0

B: true
A: true
A отново: false
Наличност: 1

Провери

Пробвай

Попълни

Срещу какво сравнява CAS при купуването?

if (stock.compareAndSet(, left - 1)) {

Провери

Пробвай

Намери грешката

Колега е опростил купуването. Всеки ред сам е безопасен, а при разпродажбата пак се продават 103 слушалки от 100. На кой ред е грешката?

Избери реда с грешката.

1boolean tryBuy() {2 if (stock.get() > 0) {3 stock.decrementAndGet();4 return true;5 }6 return false;7}

Провери

Проблем

Ценоразписът, който се сменя по средата

В 10:00 администраторът пуска промоцията: слушалки от 60 на 48 €, калъф от 15 на 12 €, кабел от 5 на 4 €. В същото време касите смятат колички. Ако цените са в един общ речник и се сменят една по една, касата може да прочете новата цена на слушалките и старата на калъфа:

// администраторът
prices.put("headphones", 48);
prices.put("case", 12);
prices.put("cable", 4);

// касата, в същото време
int total = 0;
for (String item : cart) total += prices.get(item);

Количката излиза 68 €: сума, която не е била вярна в нито един момент. Не по старите цени (80 €), не по новите (64 €). А HashMap или Dictionary, променян от една нишка, докато друга го чете, може и да хвърли изключение или да върне грешна стойност.

Идеята

Не променяй, а смени целия

Ценоразписът се чете много пъти и се сменя рядко. Тогава не го променяй никога. Направи го неизменим обект (immutable): веднъж създаден, той остава същият. За промоцията администраторът прави нов ценоразпис и сменя една референция: „текущият ценоразпис е този“.

• Обект, който никой не променя, се чете от колкото искаш нишки без никаква защита.
• Единственото общо нещо е референцията, а смяната ѝ е една атомарна стъпка.
• Касата взима референцията веднъж, в началото на количката, и смята цялата количка по нея. Тя вижда целия стар или целия нов ценоразпис, никога смес.

record с Map.copyOf е неизменим: полетата са final, а Map.copyOf прави копие, което не може да се променя. AtomicReference държи текущия ценоразпис: set го сменя, get го чете, така че всяка нишка вижда последния записан.

record PriceList(int version, Map<String, Integer> prices) {
    PriceList {
        prices = Map.copyOf(prices); // непроменимо копие
    }

    int total(List<String> cart) {
        int sum = 0;
        for (String item : cart) sum += prices.get(item);
        return sum;
    }
}

Map<String, Integer> regular = Map.of("headphones", 60, "case", 15, "cable", 5);
Map<String, Integer> promo = Map.of("headphones", 48, "case", 12, "cable", 4);
List<String> cart = List.of("headphones", "case", "cable");
AtomicReference<PriceList> current =
        new AtomicReference<>(new PriceList(1, regular));
AtomicInteger mixed = new AtomicInteger();

Thread admin = new Thread(() -> {
    for (int v = 2; v <= 1001; v++) {
        Map<String, Integer> prices = v % 2 == 0 ? promo : regular;
        current.set(new PriceList(v, prices)); // нов снимък с една референция
    }
});
Thread checkout = new Thread(() -> {
    for (int i = 0; i < 100_000; i++) {
        PriceList list = current.get(); // един снимък за цялата количка
        int total = list.total(cart);
        if (total != 80 && total != 64) mixed.incrementAndGet();
    }
});
admin.start();
checkout.start();
admin.join();
checkout.join();
PriceList last = current.get();
System.out.println("Проверени суми: 100000");
System.out.println("Смесени суми: " + mixed.get());
System.out.println("Последна версия: " + last.version() + ", сума " + last.total(cart) + " €");

Изход

Проверени суми: 100000
Смесени суми: 0
Последна версия: 1001, сума 80 €

Касата е проверила десетки хиляди колички, докато ценоразписът се е сменял хиляда пъти, и нито една сума не е смесена. Колко колички са минали по стария и колко по новия, е различно при всяко пускане, затова програмата не го печата.

По-точно, за любопитните

Така работят и колекциите „копирай при запис“: CopyOnWriteArrayList в Java, ImmutableList в C#. Всяка промяна прави ново копие, а четенето е без ключалка. Струва си, когато се чете много, а се пише рядко. Ако се пише често, копирането става скъпо.

Неизменимостта е честна само докато е до дъно. Обект с final поле, което сочи променлив списък, не е неизменим: списъкът може да се смени отвън. Затова е Map.copyOf, а не самата Map, която е подадена.

Как е в другите езици: record и Map.copyOf с AtomicReference в Java; record с ImmutableDictionary и Volatile или Interlocked.Exchange в C#; frozen dataclass, tuple или MappingProxyType и присвояване в Python; Object.freeze и съобщения между Worker-и в JavaScript.

Идеята

Когато атомарното не стига

Резервацията мести бройка от наличността в резервираните. Правилото е, че двете заедно са винаги 10 000. Две атомарни променливи не го пазят:

AtomicInteger stock = new AtomicInteger(10);
AtomicInteger reserved = new AtomicInteger(0);

void reserve() {
    stock.decrementAndGet();    // всеки ред е атомарен,
    reserved.incrementAndGet(); // двата заедно не са
}

Между двата реда ревизорът вижда 9 999 общо. Атомарното пази една стойност. Когато правилото е за няколко стойности заедно, трябва ключалка около всички промени и около проверката:

class Warehouse {
    private final Object lock = new Object();
    private int stock;
    private int reserved;

    Warehouse(int stock) {
        this.stock = stock;
    }

    boolean reserve() {
        synchronized (lock) { // двете или нито една
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }

    int audit() {
        synchronized (lock) {
            return stock + reserved;
        }
    }

    String report() {
        synchronized (lock) {
            return "Наличност: " + stock + ", резервирани: " + reserved;
        }
    }
}

Warehouse warehouse = new Warehouse(10_000);
AtomicInteger broken = new AtomicInteger();
Runnable reserver = () -> {
    while (warehouse.reserve()) { }
};
Runnable auditor = () -> {
    for (int i = 0; i < 50_000; i++) {
        if (warehouse.audit() != 10_000) broken.incrementAndGet();
    }
};
List<Thread> threads = List.of(new Thread(reserver), new Thread(reserver), new Thread(auditor));
for (Thread thread : threads) thread.start();
for (Thread thread : threads) thread.join();
System.out.println(warehouse.report());
System.out.println("Счупени проверки: " + broken.get());

Изход

Наличност: 0, резервирани: 10000
Счупени проверки: 0

По-точно, за любопитните

Друг начин без ключалка: двете стойности в един неизменим обект (наличност, резервирани), а смяната с CAS върху референцията (AtomicReference.compareAndSet). Нов обект с двете нови стойности замества стария наведнъж. Това съчетава двете идеи от урока, но ключалката обикновено е по-ясна.

Кога кое:

• една стойност, брояч или флаг: атомарна операция;
• проверка и смяна на една стойност: цикъл с CAS;
• данни, които се четат много и се сменят рядко: неизменим обект и смяна на референцията;
• няколко свързани стойности: ключалка.

Упражнение

Купон с ограничен брой

Реши задачата в редактора си.

Купонът „SPRING20“ може да се ползва 50 пъти. Осем нишки, всяка с по 10 клиента, опитват да го ползват едновременно. Напиши Coupon с tryUse() така, че купонът никога да не се ползва повече от 50 пъти. Без ключалка: с цикъл compare-and-set. Отпечатай колко пъти е ползван, колко отказа е имало и колко остават:

Изход

Използвани: 50
Отказани: 30
Остават: 0

Още задачи

• Максимумът. Пази най-голямата поръчка на деня, докато много нишки добавят поръчки. Подсказка: CAS цикъл, който записва само ако новата е по-голяма.
• Две промоции. Направи ценоразписа с версия и пусни двама администратори, които публикуват едновременно. Как да не се загуби промоцията на единия? (Подсказка: смени референцията с CAS само ако версията е още тази, която си прочел.)
• Ревизорът без ключалка. Сложи наличността и резервираните в един неизменим обект и смени го с CAS. Провери, че ревизорът пак вижда винаги 10 000.

Тест

Провери се

1. Наличността е 6. Нишка вика CAS „ако е 5, направи го 4“. Какво става?

Нищо не се записва, а отговорът е „не успя“: нишката трябва да прочете пакНишката заспива, докато стойността стане 5Записва се 4

2. В tryBuy има „ако наличността е > 0“ и после „намали с 1“. И двата реда са атомарни. Защо пак се продава повече, отколкото има?

Защото атомарните операции понякога губят увеличенияНе може: щом всеки ред е атомарен, целият метод е безопасенМежду проверката и намаляването друга нишка може да вземе последната бройка: всяка стъпка е неделима, но двете заедно не са

3. Касите четат ценоразписа хиляди пъти в секунда, а той се сменя веднъж на ден. Какъв е най-добрият начин да го делят?

Един общ речник, в който администраторът сменя цените една по еднаНеизменим обект: администраторът прави нов ценоразпис и сменя една референция; всяка каса чете целия стар или целия новКлючалка около всяко четене на цена

4. Резервираш бройка: наличността пада с 1, а резервираните растат с 1. Ревизорът проверява, че сборът е винаги 10 000. Какво трябва?

Две атомарни променливиКлючалка около двете промени и около проверкатаНищо: сборът се смята след края

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Нишки · Защо нишки · Race condition · Заключване
• Продължава в: Deadlock · Производител и потребител · Как се тества конкурентен код
• Задачи по темата: Нишки и race conditions