Стан гонитви, критична секція та атомарні операції

Два потоки можуть бути окремо правильними, але разом давати неправильний результат. Причина часто не в арифметиці, а в тому, що операція на кшталт counter++ складається з читання, обчислення і запису, між якими може виконатися інший потік.

Цілі лекції

Після опрацювання матеріалу ви зможете:

розпізнати race condition за залежністю результату від interleaving;
знайти критичну секцію у роботі зі спільним станом;
пояснити mutual exclusion, progress і bounded waiting;
описати атомарну семантику Test-and-Set і Compare-and-Swap;
пояснити роботу й межі застосування spinlock;
відрізнити атомарність від видимості та порядку операцій пам'яті;
пояснити, чому volatile не є засобом міжпотокової синхронізації.

Передумови

Потрібно знати різницю між процесом і потоком, спільні ресурси потоків, витискальне планування та можливість перемикання виконання між будь-якими двома інструкціями.

1. Race condition і lost update

Race condition, або стан гонитви, виникає, коли коректність результату залежить від неконтрольованого порядку конкурентних подій. Не кожна паралельна робота є гонитвою: читання незмінних даних кількома потоками безпечне. Проблема з'являється, коли є конфліктні доступи до спільного змінного стану без належної синхронізації.

Операцію збільшення подамо як три кроки:

R: register = counter
M: register = register + 1
W: counter = register

Для counter = 10 можливе чергування:

Крок	Потік A	Потік B	`counter`
1	читає 10		10
2		читає 10	10
3	обчислює 11		10
4		обчислює 11	10
5	записує 11		11
6		записує 11	11

Два збільшення мали дати 12, але одне оновлення втрачено. Це lost update.

У C або C++ неатомарний конфліктний доступ між потоками є data race і призводить до undefined behavior за моделлю мови. Тому не можна обіцяти лише «іноді неправильне число»: компілятор не зобов'язаний підтримувати жодний конкретний результат такої програми.

2. Критична секція

Критична секція - ділянка коду, яка працює зі спільним ресурсом і не може безпечно виконуватися одночасно з конфліктною секцією іншого потоку.

Класична структура:

entry section
critical section
exit section
remainder section

Коректний механізм має задовольняти три вимоги:

Mutual exclusion. У критичній секції для цього ресурсу одночасно перебуває не більше одного потоку.
Progress. Якщо секція вільна й є охочі увійти, рішення не відкладається нескінченно потоками, які не беруть участі.
Bounded waiting. Після запиту потоку існує межа кількості входів інших потоків до того, як увійде він; це протидіє starvation.

Mutual exclusion саме по собі не гарантує bounded waiting. Простий алгоритм може не допустити двох учасників одночасно, але постійно надавати перевагу одному.

3. Атомарна read-modify-write операція

Атомарна операція спостерігається конкурентними учасниками як неподільна: вони не бачать її напіввиконаного стану. Процесорні інструкції та мовні atomic API дають змогу атомарно прочитати старе значення й записати нове.

Атомарний вибір власника через Test-and-Set і CAS

Атомарність однієї змінної не робить автоматично атомарним складний інваріант кількох об'єктів. Якщо треба узгоджено змінити баланс, журнал і лічильник, окремі atomic increments можуть бути недостатніми.

4. Test-and-Set

Test-and-Set атомарно повертає старе значення прапорця й установлює його в true:

TestAndSet(lock):
    old = lock
    lock = true
    return old

Псевдокод простого блокування:

while TestAndSet(lock) == true:
    wait

critical section
lock = false

Якщо старе значення було false, потік установив true і став власником. Інші отримують true та продовжують чекати. Ключове слово тут атомарно: звичайні окремі читання й запис прапорця знову мали б race window.

5. Compare-and-Swap

Compare-and-Swap (CAS) порівнює поточне значення з очікуваним і лише за рівності записує нове. Порівняння та можливий запис є однією атомарною дією:

CAS(object, expected, desired):
    if object == expected:
        object = desired
        return success
    else:
        return failure

CAS підтримує optimistic retry loop: прочитати стан, побудувати бажане значення, спробувати CAS, а після невдачі перечитати актуальний стан. Невдача не обов'язково є помилкою: вона означає, що конкурент уже змінив об'єкт.

У C11 функція atomic_compare_exchange_weak може змінити аргумент expected на фактичне значення та іноді дати spurious failure, тому її типово використовують у циклі.

6. Spinlock на C11

Стандартний atomic_flag дає компактний навчальний spinlock:

#include <stdatomic.h>

typedef struct {
    atomic_flag held;
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    while (atomic_flag_test_and_set_explicit(
        &lock->held, memory_order_acquire)) {
        /* busy wait */
    }
}

void spin_unlock(spinlock_t *lock) {
    atomic_flag_clear_explicit(&lock->held, memory_order_release);
}

spinlock_t lock = { ATOMIC_FLAG_INIT };

spin_lock повторює атомарну спробу, доки не побачить вільний прапорець. memory_order_acquire не дозволяє наступним операціям критичної секції перейти перед успішним захопленням; memory_order_release публікує попередні зміни перед звільненням.

Spinlock витрачає CPU під час очікування. Він може бути доречним у низькорівневому коді, якщо секція гарантовано дуже коротка й власник може виконуватися паралельно на іншому CPU. Для довгого очікування у прикладній програмі краще блокувальний mutex, який дозволяє ОС приспати потік. На одному CPU spinning особливо невигідний: очікувач може витрачати квант, потрібний власнику для звільнення.

Простий Test-and-Set spinlock також не гарантує справедливість або bounded waiting. Production-реалізації враховують contention, backoff, черги та архітектуру.

7. Атомарний лічильник без зовнішнього lock

Якщо інваріант справді обмежений одним лічильником, C11 має готову атомарну операцію:

#include <stdatomic.h>
#include <stdio.h>

int main(void) {
    atomic_int counter = 0;

    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);

    printf("%d\n", atomic_load_explicit(&counter, memory_order_relaxed));
    return 0;
}

Компіляція:

cc -std=c11 -Wall -Wextra atomic_counter.c -o atomic_counter
./atomic_counter

Результат дорівнює 2. memory_order_relaxed тут достатній лише тому, що приклад вимагає атомарного підрахунку й не публікує через лічильник інші дані.

8. Memory-order caveat

Атомарність відповідає на питання «чи може інший потік побачити розірвану read-modify-write операцію?». Memory ordering відповідає на інше питання: «у якому порядку інші потоки можуть спостерігати пов'язані операції?»

Основні орієнтири C11:

memory_order_relaxed гарантує атомарність конкретного atomic-об'єкта, але не створює загальної публікації інших даних;
release-запис та acquire-читання того самого synchronization object можуть утворити happens-before для попередніх записів;
memory_order_seq_cst дає сильнішу й простішу для міркування модель, але не виправляє неправильний алгоритм;
правильний порядок залежить від інваріанта, мови, компілятора та архітектури.

На x86 деякі слабкі помилки можуть не проявитися в тесті, але з'явитися на ARM або після оптимізації. Не виводьте коректність із фрази «на моєму комп'ютері працює».

Чому не `volatile`

У C/C++ volatile потрібен для спеціальних доступів, наприклад memory-mapped I/O або сигналів у визначених мовою межах. Він не робить counter++ атомарним, не створює mutual exclusion і не встановлює міжпотоковий happens-before. Для синхронізації використовуйте atomic API, mutex, semaphore чи інший механізм із визначеною семантикою.

Практичні завдання

Завдання 1. Знайдіть lost update

Для початкового counter = 20 побудуйте interleaving двох неатомарних збільшень, що завершується значенням 21. Позначте R, M, W кожного потоку.

Завдання 2. Виберіть механізм

Для кожної ситуації оберіть atomic counter, spinlock або mutex і поясніть вибір: лічильник запитів; зміна трьох пов'язаних полів, яка може тривати 5 мс; критична секція ядра на десятки інструкцій без можливості сну.

Завдання 3. Перевірте порядок пам'яті

Потік A записує звичайні дані, а потім атомарно встановлює ready = true. Потік B чекає ready і читає дані. Поясніть, чому лише relaxed-доступ до ready недостатній для публікації даних і яку пару семантик слід розглянути.

Підсумок

Race condition робить коректність залежною від неконтрольованого interleaving.
Критична секція захищає спільний інваріант, а не просто рядок коду.
Класичні вимоги: mutual exclusion, progress і bounded waiting.
Test-and-Set атомарно встановлює прапорець; CAS умовно замінює значення.
Spinlock активно чекає, тому придатний лише для дуже коротких спеціальних секцій.
Atomic-операція не замінює проєктування інваріанта з кількох об'єктів.
Memory ordering визначає видимість і порядок пов'язаних операцій.
volatile не забезпечує атомарність або міжпотокову синхронізацію.