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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

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

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

Идеята

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

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

В C# те са в класа Interlocked. Interlocked.Increment(ref views) е атомарното +1 върху обикновено поле или променлива int и връща новата стойност. Има и Interlocked.Add, Interlocked.Decrement и версии за long.

Виж го

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

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

int views = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 100_000; i++)
        {
            Interlocked.Increment(ref views);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Изгледи: {views}");

Изход

Изгледи: 400000

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

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

Брой в свое място. Когато много нишки увеличават едно и също поле, всички удрят една клетка от паметта и процесорите си я подават. Ако стойността трябва само накрая, по-бързо е всяка нишка да брои в своя локална променлива и да направи едно Interlocked.Add в края. Java има готов клас за това: LongAdder.

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

Идеята

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

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

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

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

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

В C# това е Interlocked.CompareExchange(ref поле, ново, очаквано). Внимавай с реда: новото е преди очакваното. Методът връща стойността, която е намерил. Ако тя е очакваната, смяната е станала. Volatile.Read чете полето така, че да видиш последното записано от друга нишка.

Виж го

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

class FlashSale
{
    private int stock;

    public FlashSale(int items)
    {
        stock = items;
    }

    public bool TryBuy()
    {
        while (true)
        {
            int left = Volatile.Read(ref stock);
            if (left == 0) return false; // разпродадено
            int was = Interlocked.CompareExchange(
                ref stock, left - 1, left);
            if (was == left) return true;
            // друг е сменил stock: прочети пак
        }
    }

    public int Stock => Volatile.Read(ref stock);
}

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

1. Последните 3 слушалки: наличността е 3. Нишките A и B викат TryBuy() едновременно.
2. A прочита наличността: left = 3.
3. B я прочита, преди A да е сменила нещо: също 3.
4. B: CompareExchange(…, 2, 3). „Ако още е 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 опита:

var sale = new FlashSale(100);
int sold = 0, refused = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 40; i++)
        {
            if (sale.TryBuy()) Interlocked.Increment(ref sold);
            else Interlocked.Increment(ref refused);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Продадени: {sold}");
Console.WriteLine($"Отказани: {refused}");
Console.WriteLine($"Наличност: {sale.Stock}");

Изход

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

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

Пробвай

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

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

int stock = 3;
int seenByA = Volatile.Read(ref stock);
int seenByB = Volatile.Read(ref stock);
bool b = Interlocked.CompareExchange(ref stock, seenByB - 1, seenByB) == seenByB;
Console.WriteLine($"B: {b}");
bool a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A: {a}");
seenByA = Volatile.Read(ref stock);
a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A отново: {a}");
Console.WriteLine($"Наличност: {stock}");

Отговор

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

B: True
A: False
A отново: True
Наличност: 1

B: True
A: True
A отново: False
Наличност: 1

Провери

Пробвай

Попълни

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

int was = Interlocked.CompareExchange(
    ref stock, left - 1, );

Провери

Пробвай

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

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

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

1public bool TryBuy()2{3 if (Volatile.Read(ref stock) > 0)4 {5 Interlocked.Decrement(ref stock);6 return true;7 }8 return false;9}

Провери

Проблем

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

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

// администраторът
prices["headphones"] = 48;
prices["case"] = 12;
prices["cable"] = 4;

// касата, в същото време
int total = cart.Sum(item => prices[item]);

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

Идеята

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

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

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

record с ImmutableDictionary (от System.Collections.Immutable) е неизменим: свойствата са само за четене, а речникът не може да се променя. Текущият ценоразпис е обикновена променлива. Volatile.Write го сменя, а Volatile.Read го чете, така че всяка нишка вижда последния записан. Interlocked.Exchange също сменя референцията и връща старата.

record PriceList(int Version, ImmutableDictionary<string, int> Prices)
{
    public int Total(List<string> cart) => cart.Sum(item => Prices[item]);
}

var regular = new Dictionary<string, int> { ["headphones"] = 60, ["case"] = 15, ["cable"] = 5 }.ToImmutableDictionary();
var promo = new Dictionary<string, int> { ["headphones"] = 48, ["case"] = 12, ["cable"] = 4 }.ToImmutableDictionary();
var cart = new List<string> { "headphones", "case", "cable" };
var current = new PriceList(1, regular);
int mixed = 0;

var admin = new Thread(() =>
{
    for (int v = 2; v <= 1001; v++)
    {
        var prices = v % 2 == 0 ? promo : regular;
        Volatile.Write(ref current, new PriceList(v, prices)); // нов снимък с една референция
    }
});
var checkout = new Thread(() =>
{
    for (int i = 0; i < 100_000; i++)
    {
        var list = Volatile.Read(ref current); // един снимък за цялата количка
        int total = list.Total(cart);
        if (total != 80 && total != 64) Interlocked.Increment(ref mixed);
    }
});
admin.Start();
checkout.Start();
admin.Join();
checkout.Join();
Console.WriteLine("Проверени суми: 100000");
Console.WriteLine($"Смесени суми: {mixed}");
Console.WriteLine($"Последна версия: {current.Version}, сума {current.Total(cart)} €");

Изход

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

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

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

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

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

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

Идеята

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

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

int stock = 10;
int reserved = 0;

void Reserve()
{
    Interlocked.Decrement(ref stock);    // всеки ред е атомарен,
    Interlocked.Increment(ref reserved); // двата заедно не са
}

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

class Warehouse
{
    private readonly object sync = new object();
    private int stock;
    private int reserved;

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

    public bool Reserve()
    {
        lock (sync) // двете или нито една
        {
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }

    public int Audit()
    {
        lock (sync)
        {
            return stock + reserved;
        }
    }

    public string Report()
    {
        lock (sync)
        {
            return $"Наличност: {stock}, резервирани: {reserved}";
        }
    }
}

var warehouse = new Warehouse(10_000);
int broken = 0;
ThreadStart reserver = () =>
{
    while (warehouse.Reserve()) { }
};
ThreadStart auditor = () =>
{
    for (int i = 0; i < 50_000; i++)
    {
        if (warehouse.Audit() != 10_000) Interlocked.Increment(ref broken);
    }
};
var threads = new List<Thread> { new Thread(reserver), new Thread(reserver), new Thread(auditor) };
foreach (var thread in threads) thread.Start();
foreach (var thread in threads) thread.Join();
Console.WriteLine(warehouse.Report());
Console.WriteLine($"Счупени проверки: {broken}");

Изход

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

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

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

Кога кое:

• една стойност, брояч или флаг: атомарна операция;
• проверка и смяна на една стойност: цикъл с 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