Синхронізація

Навіщо це

Дві функції, кожна правильна сама по собі, разом дають неправильний результат. Тест проходить сто разів і падає на сто перший. Помилка зникає, щойно ви додасте printf. Містики тут немає, це конкурентний доступ до спільних даних, і теорія в нього цілком точна.

Передумови. Що потоки ділять (модуль 8), витіснення планувальником (модуль 7).

Один рядок коду — три операції

Жоден потік не помилився. Помилилося припущення, що x++ виконується неподільно.

У вихідному коді x++ виглядає неподільним, але процесор виконує три окремі дії: прочитати з пам’яті, змінити в регістрі, записати назад. Між будь-якими двома може втрутитися інший потік — чи то тому, що планувальник витіснив перший, чи то тому, що другий фізично виконується на іншому ядрі.

Стан гонитви (race condition) — це коли результат залежить від того, у якому порядку встигли виконатися операції різних потоків. Слово «встигли» тут ключове: порядок ніде не визначений, тому й помилка відтворюється не щоразу.

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

Три вимоги до розв’язку

Будь-який механізм захисту критичної секції мусить задовольняти три умови, і зламати можна кожну з них окремо:

1. Взаємне виключення — у критичній секції одночасно не більше одного потоку.
2. Прогрес — якщо секція вільна, а хтось хоче ввійти, вибір не відкладається нескінченно.
3. Обмежене очікування — той, хто вже стоїть у черзі, врешті туди потрапить. Порушення цієї умови називають голодуванням.

Спроби зробити це вручну на звичайних змінних, як-от алгоритм Петерсона, математично коректні, але на сучасному залізі без додаткових заходів не працюють: і процесор, і компілятор мають право переставляти операції з пам’яттю. Про це буде нижче.

Апаратна основа

З подільних операцій неподільну програмно не збереш, тут потрібна допомога процесора. Він надає атомарні інструкції, які виконуються цілком або ніяк.

Базова з них — порівняти й обміняти, вона ж compare-and-swap або просто CAS: якщо за адресою лежить очікуване значення, заміни його на нове й повідом, чи вдалося. Одна інструкція, яку неможливо перервати посередині. З неї будується все інше: лічильники, блокування, черги без блокувань.

// x++ атомарно, без блокувань
int old;
do { old = x; } while (!compare_and_swap(&x, old, old + 1));

Цикл потрібен, бо між читанням x і CAS значення могло змінитися — тоді CAS не спрацює і спробу треба повторити.

Інструменти

М’ютекс забезпечує взаємне виключення для однієї критичної секції. Захоплений одним потоком, він змушує решту чекати. Найважливіша його властивість у тому, що м’ютекс має власника: звільнити його може лише той, хто захопив.

Спін-блокування робить те саме, але потік не засинає, а крутиться в циклі й перевіряє, чи звільнилося. Виправдовує себе тільки тоді, коли очікування свідомо коротше за вартість двох перемикань контексту, тобто всередині ядра, на кількох інструкціях. У прикладному коді це майже завжди помилка.

Умовна змінна розв’язує зовсім іншу задачу. Не «пусти мене всередину», а «розбуди, коли настане умова». Потік атомарно відпускає м’ютекс і засинає, інший потік змінює стан і сигналізує. Без неї довелося б опитувати умову в циклі й марнувати процесор.

Семафор є лічильником із двома операціями: wait зменшує його і блокується на нулі, signal збільшує. Двійковий семафор схожий на м’ютекс, але власника не має, тож збільшити його може будь-хто. Це робить семафор придатним для сигналізації між потоками і водночас небезпечним як заміну м’ютекса.

Задача	Інструмент
Захистити спільні дані	м’ютекс
Дочекатися умови	умовна змінна
Обмежити кількість одночасних учасників	лічильний семафор
Повідомити про подію	семафор або умовна змінна
Лічильник без критичної секції	атомарна операція

Умову перевіряють у циклі, а не в if

Прокидання умовної змінної не гарантує, що умова справді настала: буває хибне прокидання, а між сигналом і поверненням мʼютекса стан міг змінити третій потік. Тому завжди while (!умова) wait(...), ніколи не if. Це найчастіша помилка в коді з умовними змінними.

Модель пам’яті

Ось де ховається найнеочевидніше. Ви написали: записати data, потім записати ready = 1. Інший потік читає ready, бачить одиницю, читає data і отримує старе значення.

Причина в тому, що порядок операцій із пам’яттю ніхто не зберігає. Компілятор переставляє інструкції під час оптимізації, процесор виконує їх поза чергою і має буфери запису, через які записи стають видимими іншим ядрам зовсім не в тій послідовності, у якій виконувались.

Бар’єр пам’яті — це інструкція, яка забороняє переставляння через себе. Прикладний код рідко ставить бар’єри вручну: атомарні типи мов (std::atomic, AtomicInteger) уже містять потрібні гарантії, а м’ютекс за визначенням є бар’єром і на вході, і на виході.

Практичний висновок такий: у C і C++ ця задача через volatile не розв’язується, на відміну від Java. Він забороняє компілятору кешувати значення в регістрі й нічого не каже ні процесору, ні іншим ядрам.

Класичні задачі

Обмежений буфер. Виробники кладуть, споживачі забирають, місце скінченне. Потрібні три речі: м’ютекс на сам буфер і два семафори — один на вільні місця, другий на наявні елементи. Це модель будь-якої черги задач.

Філософи, що обідають. П’ятеро філософів, п’ять виделок, кожному потрібні дві сусідні. Якщо всі одночасно візьмуть ліву, всі чекатимуть на праву вічно. Найкоротша демонстрація взаємоблокування і того, як порядок захоплення ресурсів його знімає.

Читачі й письменники. Читати можуть багато одночасно, писати — лише один і без читачів. Задача показує, звідки береться голодування: наївна реалізація з пріоритетом читачів не пустить письменника, поки надходять нові читання.

Взаємоблокування

Взаємоблокування виникає, коли кожен учасник чекає на ресурс, який тримає інший. Трапляється це лише за одночасної дії чотирьох умов:

1. Взаємне виключення — ресурс не можна використовувати спільно.
2. Утримання й очікування — учасник тримає одне й просить друге.
3. Відсутність витіснення — ресурс не забрати силою, його треба віддати.
4. Циклічне очікування — ланцюг очікувань замкнувся в кільце.

Щоб розв’язати задачу, досить прибрати будь-яку одну з них. Найдешевше на практиці виходить із четвертою: встановити глобальний порядок захоплення ресурсів і завжди його дотримуватись. Якщо всі беруть спершу виделку з меншим номером, кільце не замкнеться ніколи.

Голодування — окрема проблема, яку часто з взаємоблокуванням плутають. При взаємоблокуванні не рухається взагалі ніхто, а при голодуванні система працює, просто конкретному учаснику постійно не дістається ресурсу.

Ще одна споріднена річ — інверсія пріоритетів, коли низькопріоритетний потік тримає блокування, потрібне високопріоритетному, і той фактично опускається до чужого пріоритету. Саме це стало причиною збоїв Mars Pathfinder у 1997 році. Лікується воно успадкуванням пріоритету: власник блокування тимчасово отримує пріоритет найвищого з тих, хто на нього чекає.

Як це насправді в Linux

cat > race.c <<'EOF'
#include <pthread.h>
#include <stdio.h>
static volatile long counter;
static void *bump(void *_) {
    for (int i = 0; i < 1000000; i++) counter++;
    return NULL;
}
int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, bump, NULL);
    pthread_create(&b, NULL, bump, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    printf("%ld (очікували 2000000)\n", counter);
}
EOF
gcc -O2 -pthread race.c -o race && ./race && ./race && ./race

Три запуски дадуть три різні числа, і жодне не буде правильним — близько мільйона замість двох. Це і є вся тема одним прикладом.

Приберіть volatile — і гонитва зникне

Спробуйте зібрати той самий код без volatile. Результат буде рівно 2000000 щоразу, і легко зробити хибний висновок, що гонитви не існує.

Причина видно в асемблері (gcc -O2 -S): без volatile компілятор доводить, що цикл додає одиницю мільйон разів, і згортає його в одну інструкцію addq $1000000, counter(%rip). Вікно, у яке міг би втрутитися інший потік, стискається майже до нуля.

volatile забороняє цю оптимізацію — і рівно тому гонитва стає видимою. Але зверніть увагу, що саме він зробив: показав помилку, а не виправив її. Результат усе одно неправильний, бо counter++ лишився трьома операціями. Це і є практична демонстрація того, про що йдеться в розділі «типові помилки» нижче.

gcc -O2 -pthread -fsanitize=thread race.c -o race-tsan && ./race-tsan

ThreadSanitizer знаходить гонитву навіть тоді, коли конкретний запуск дав правильну відповідь. Для конкурентного коду це обов’язковий інструмент: покладатися на те, що тест «пройшов», тут не можна.

grep -E 'futex' /proc/self/status; man 2 futex | head -20

futex — механізм, на якому в Linux побудовані м’ютекси й семафори. Захоплення вільного м’ютекса не виходить у ядро взагалі: це атомарна операція в просторі користувача. У ядро йдуть лише ті, кому довелося чекати.

Типові помилки розуміння

«volatile робить змінну потокобезпечною». У C і C++ не робить. Він забороняє компілятору кешувати значення в регістрі й не гарантує нічого ні про атомарність, ні про порядок між ядрами. Потрібні атомарні типи або блокування.

«Операція одна, значить атомарна». В x++ операцій три. Ба більше, присвоєння 64-бітного значення на 32-бітній платформі теж може розпастися надвоє.

«Помилка не відтворюється, отже її немає». Гонитва проявляється лише за рідкісного збігу планувань, а зміна навантаження чи нове залізо роблять цей збіг звичайним. Тест, який пройшов, не доводить нічого; доводить санітайзер.

«Семафор — це той самий м’ютекс». У м’ютекса є власник, а в семафора немає. Семафор, звільнений не тим потоком, що його захопив, — цілком законна операція, і через це він небезпечний як заміна м’ютекса.

«Спін-блокування швидше, бо немає перемикань». Швидше тільки тоді, коли очікування коротше за два перемикання контексту. Інакше потік спалює квант часу, нічого при цьому не роблячи, та ще й заважає власнику блокування дістатися процесора.

«Більше блокувань — безпечніше». Кожне додаткове блокування додає ще одну можливість замкнути кільце. Безпечніше мати менше спільного стану.

Перевір себе

1. Два потоки виконують x++ мільйон разів кожен. Яким буде кінцеве значення?

Рівно 2 000 000Від 1 000 000 до 2 000 000, різне за кожного запускуРівно 1 000 000Завжди 0

2. Що гарантує volatile у C для змінної, яку читають два потоки?

Атомарність доступуЛише те, що компілятор не кешуватиме значення в регістрі — ні атомарності, ні порядку між ядрамиВзаємне виключенняБар’єр памʼяті на кожному доступі

3. Чим мʼютекс принципово відрізняється від двійкового семафора?

Мʼютекс швидшийУ мʼютекса є власник: звільнити його може лише потік, який його захопивСемафор працює лише між процесамиМʼютекс не блокує потік

4. Чому умову умовної змінної перевіряють у while, а не в if?

Так коротший кодПрокидання не гарантує, що умова настала: буває хибне прокидання, і стан міг змінити інший потікif не працює з мʼютексамиwhile зменшує кількість перемикань контексту

5. Пʼять філософів одночасно взяли ліву виделку. Яку з чотирьох умов взаємоблокування найдешевше прибрати?

Взаємне виключення — дозволити спільне використання виделкиЦиклічне очікування — ввести глобальний порядок захоплення ресурсівУтримання й очікування — заборонити тримати щось під час очікуванняВідсутність витіснення — дозволити забирати виделки силою

6. Низькопріоритетний потік тримає блокування, потрібне високопріоритетному. Як це називається і чим лікується?

Взаємоблокування; лікується перезапускомІнверсія пріоритетів; лікується успадкуванням пріоритету власником блокуванняГолодування; лікується старіннямГонитва; лікується атомарними операціями

Лабораторна

A3 — producer–consumer. Перша частина: м’ютекс і умовна змінна, з перевіркою через ThreadSanitizer. Друга: кільцевий буфер без блокувань на CAS — і замір, за яких навантажень він справді виграє, а за яких програє.

Джерела

• OSTEP: Locks, Condition Variables, Semaphores, Deadlock
• Silberschatz, Operating System Concepts, розділи 6–8
• man 7 pthreads, man 2 futex, man 3 pthread_cond_wait
• The Little Book of Semaphores — задачник із семафорів
• Memory Barriers: a Hardware View — модель пам’яті ядра Linux