Race condition в C#

Проблем

Разпродажбата брои криво

Петък, разпродажба. Слушалките са на половин цена и поръчките валят. Две каси продават от един склад: всяка продажба вади 1 от наличността.

Касите са две нишки. Всяка продава по 100 000 бройки и вика Sell() за всяка:

class Stock
{
    private int left;

    public Stock(int left)
    {
        this.left = left;
    }

    public void Sell()
    {
        left--;   // прочети, извади 1, запиши
    }

    public int Left => left;
}

Stock stock = new Stock(200_000);
ThreadStart checkout = () =>
{
    for (int i = 0; i < 100_000; i++)
    {
        stock.Sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.Start();
b.Start();
a.Join();
b.Join();
Console.WriteLine($"Поръчки: {2 * 100_000}");
Console.WriteLine("Продадени според склада:");
Console.WriteLine(200_000 - stock.Left);

Клиентите са платили 200 000 поръчки. Ето колко продадени брои складът в пет пускания:

Продадени според склада: 107415
Продадени според склада: 104427
Продадени според склада: 108645
Продадени според склада: 107147
Продадени според склада: 130643

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

Идеята

left-- е три стъпки

В кода left-- е един ред. Процесорът го прави на три стъпки, както ако го разпишеш:

class Stock
{
    private int left;

    public Stock(int left)
    {
        this.left = left;
    }

    public void Sell()
    {
        int seen = left;       // 1. прочети
        int after = seen - 1;  // 2. извади 1
        left = after;          // 3. запиши
    }

    public int Left => left;
}

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

Остават 5 бройки. Каса A и каса B продават по една в един и същ момент.
Каса A прочита наличността: 5.
Каса B прочита, преди A да е записала: също 5.
Каса A изважда 1 в своята променлива: 4.
Каса B прави същото от своето 5: също 4.
Каса A записва 4. Една продажба, остават 4: дотук е вярно.
Каса B също записва 4, върху 4 на A. Две продажби, а наличността е 4, не 3.
Една продажба е изгубена: двете прочетоха едно и също число, преди някоя да запише. Това е race condition, а складът показва бройка, която вече е продадена.

Прочети наличността в своя променлива.
Извади 1 от своето копие.
Запиши копието обратно.

Две нишки могат да се редуват между всеки две стъпки. Ако и двете прочетат 5, преди някоя да запише, и двете записват 4. Две продажби, а наличността намалява с една.

Когато резултатът зависи от това коя нишка коя стъпка прави първа, това е race condition (състезание). Трите стъпки „прочети, промени, запиши“ върху общи данни са най-честата форма.

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

Компилаторът превръща left-- в отделно прочитане (ldfld), изваждане (sub) и запис (stfld) в IL. Виждат се в sharplab.io или с ILSpy. JIT компилаторът после ги прави машинни инструкции, но прочитането и записът си остават отделни.

Пробвай

Три каси, наличност 5

Ето три каси, разменени на ръка, в един от възможните редове. Всяка прочита в своя променлива, после записва с 1 по-малко:

int left = 5;
int seenA = left;      // A прочита
int seenB = left;      // B прочита
left = seenA - 1;      // A записва
int seenC = left;      // C прочита
left = seenB - 1;      // B записва
left = seenC - 1;      // C записва
Console.WriteLine("Продажби: 3");
Console.WriteLine($"Наличност: {left}");

Отговор

Продажби: 3
Наличност: 3

Продажби: 3
Наличност: 4

Продажби: 3
Наличност: 2

Идеята

„При мен работи“

Същата програма, но с по-малко продажби на каса:

Stock stock = new Stock(2_000);
ThreadStart checkout = () =>
{
    for (int i = 0; i < 1_000; i++)
    {
        stock.Sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.Start();
b.Start();
a.Join();
b.Join();
Console.WriteLine($"Поръчки: {2 * 1_000}");
Console.WriteLine("Продадени според склада:");
Console.WriteLine(2_000 - stock.Left);

Продадени според склада: 2000
Продадени според склада: 2000
Продадени според склада: 2000
Продадени според склада: 2000
Продадени според склада: 2000

Пет пъти вярно. Пускането на нишка отнема повече, отколкото 1000 продажби: първата каса свършва, преди втората да е тръгнала. Race condition има, само че не се случва.

Затова race condition е коварен:

тестът минава на лаптопа и пада на сървъра с 64 ядра и хиляди клиенти;
грешката идва „понякога“ и не се повтаря, когато я търсиш;
добавиш ли ред за отпечатване, редът на нишките се сменя и грешката изчезва.

Липсата на загуба в тест не доказва нищо. Безопасността се доказва с това как е написан кодът: кои данни са общи и кой ги пази.

Проблем

Последната бройка

Една бройка е останала. Двама купувачи натискат „Купи“ в един и същ момент. buy проверява дали има, таксува картата (около 100 ms) и чак тогава взима бройката:

class Stock
{
    private int left;

    public Stock(int left)
    {
        this.left = left;
    }

    public bool Buy()
    {
        if (left > 0)        // проверка: има ли?
        {
            Thread.Sleep(100);   // картата се таксува ~100 ms
            left--;              // действие: взимам бройката
            return true;
        }
        return false;
    }

    public int Left => left;
}

Stock stock = new Stock(1);
bool[] bought = new bool[2];
Thread first = new Thread(() => bought[0] = stock.Buy());
Thread second = new Thread(() => bought[1] = stock.Buy());
first.Start();
second.Start();
first.Join();
second.Join();
int sold = bought.Count(b => b);
Console.WriteLine("Наличност преди: 1");
Console.WriteLine("Продадени:");
Console.WriteLine(sold);
Console.WriteLine("Наличност след:");
Console.WriteLine(stock.Left);

Продадени: 2, наличност след: -1
Продадени: 2, наличност след: -1
Продадени: 2, наличност след: -1
Продадени: 2, наличност след: -1
Продадени: 2, наличност след: -1

И двамата минават проверката: докато първият плаща, вторият вижда същата 1. Двамата платиха, а складът е на -1. Тук race condition се случва всеки път, защото между проверката и действието има цели 100 ms.

Това е втората форма на race condition: проверка, после действие (check-then-act). Решението се взима по стойност, която друг може да смени, преди решението да се изпълни. Тя е навсякъде: „има ли свободна стая“, „свободно ли е потребителското име“, „има ли пари в сметката“.

Пробвай

Номерата на поръчките

Всяка поръчка получава номер: 1001, 1002, 1003… Касите са нишки и викат Take() едновременно. Понякога две поръчки получават един и същ номер. След кой ред другата нишка трябва да влезе, за да стане това?

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

Идеята

Кога може да има race condition

Трябват три неща наведнъж:

Общи данни: нещо, което виждат няколко нишки (наличността, броячът, номерът).
Поне една нишка ги променя. Ако всички само четат, няма какво да се обърка.
Нищо не подрежда достъпа: нишките влизат в стъпките си когато им дойде редът.

Махни едно от трите и race condition няма:

Не дели. Всяка нишка брои в своя променлива, а накрая резултатите се събират. Така ставаше с 1000-те фактури в „Защо нишки“: всяка част смята своето.
Не променяй. Обект, който никой не променя, може да се чете от колкото искаш нишки. Това е урокът „Атомарни операции и неизменими обекти“.
Подреди достъпа. Само една нишка наведнъж в трите стъпки. Това е ключалката, следващият урок: „Заключване“.

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

Има и по-тиха беда: видимостта. Без lock или Volatile.Read JIT може да прочете поле веднъж и да не го чете повече. Цикъл while (!done) { } може да не спре никога. Ключалката решава и това: каквото една нишка е записала, преди да я пусне, следващата го вижда, след като я вземе.

Как е в другите езици: в Java и C# count++ губи както тук. В Python губи по-рядко заради GIL, но губи. В JavaScript губи между Worker-и върху SharedArrayBuffer, а в една нишка race condition има само между два await.

Упражнение

Оборотът на разпродажбата

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

Оборотът. Две каси продават по 50 000 слушалки по 3 €. Всяка каса брои своите продажби в своя променлива, а оборотът е общ: обект Revenue с метод Add(euros), който прави total += euros. Отпечатай продажбите на всяка каса и оборота. Пусни програмата няколко пъти.

Каса 1: 50000 продажби
Каса 2: 50000 продажби
Оборот (€):
300000

Продажбите на касите са верни при всяко пускане: всяка брои в своята променлива. Оборотът е по-малък и различен всеки път. Поправката е в следващия урок.

Още задачи

Колко се губи. Пусни продажбата с 2, 4 и 8 каси. Губи ли се повече с повече каси?
Намери общото. Вземи програма с нишки, която си писал, и изброй данните, които повече от една нишка пипа. Кои от тях някоя нишка променя? - Свободна стая. Напиши хотел с метод „резервирай стая 12, ако е свободна“ и пусни двама гости наведнъж, с пауза от 100 ms между проверката и записа. Колко гости получават стаята?

Тест

Провери се

1. Две нишки викат по веднъж left-- върху общо поле, което е 5. Какво може да е накрая?Винаги 33, 4 или 53 или 4

2. Тестът с две нишки по 1000 продажби минава 100 пъти от 100. Какво значи това?Нищо за race condition: при 1000 първата нишка често свършва, преди втората да тръгнеЧе кодът е безопасен за нишкиЧе трябват повече ядра, за да се провери

3. В склада има 1 бройка. Кодът проверява „left > 0“, таксува картата за 100 ms и чак тогава вади 1. Двама купуват наведнъж. Какво става?Програмата хвърля изключениеДвамата минават проверката, двамата плащат, а наличността става -1Вторият чака първия, защото проверката е една

4. Кое от тези НЕ може да има race condition?Всяка нишка брои продажбите си в своя локална променливаЕдна нишка пише в общ брояч, а друга го чете и решава по негоДве нишки пишат в общ брояч

Race condition

Бисквитки