М'ютекси, семафори й класичні задачі синхронізації

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

Цілі лекції

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

• пояснити семантику mutex і його володіння;
• розрізняти бінарний та лічильний семафори;
• правильно чекати condition variable у циклі перевірки предиката;
• визначати призначення barrier і read-write lock;
• моделювати задачі «виробник-споживач», «читачі-письменники» та «філософи»;
• обирати примітив за інваріантом, а не за схожістю API.

Передумови

Потрібно розуміти потоки POSIX, критичну секцію, стан гонитви, атомарність і базові виклики pthread_create та pthread_join. Приклади розраховані на Linux або інше POSIX-сумісне середовище з компілятором C.

1. Спочатку інваріант

Інваріант - умова, яка має залишатися істинною попри можливі перемикання потоків. Наприклад:

• баланс рахунку не змінюють два потоки одночасно;
• кількість елементів буфера завжди від 0 до його місткості;
• читач не бачить структуру під час частково виконаного запису;
• наступна фаза обчислення не починається, доки всі учасники не завершили поточну.

Примітив синхронізації обирають після формулювання інваріанта. Один mutex не вирішує автоматично очікування події, а semaphore не завжди є правильною заміною mutex.

2. Mutex: взаємне виключення з володінням

Mutex захищає критичну секцію так, щоб одночасно її виконував не більш ніж один потік. У POSIX типовий шаблон такий:

pthread_mutex_lock(&mutex);
/* перевірка й зміна спільного стану */
pthread_mutex_unlock(&mutex);

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

Mutex захищає не змінну як таку, а погоджений інваріант. Усі звернення до пов'язаного спільного стану мають використовувати той самий протокол. Якщо один шлях обходить блокування, захист неповний.

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

3. Семафори: дозволи без власника

Семафор зберігає невід'ємний лічильник дозволів. Дві основні операції:

• sem_wait чекає на додатне значення й атомарно зменшує його;
• sem_post атомарно збільшує значення й може розбудити очікувача.

Бінарний семафор

У дисциплінованому використанні має значення 0 або 1, тому зовні нагадує mutex. Проте бінарний семафор не задає володіння: один потік може виконати sem_wait, а інший - sem_post. Це корисно для сповіщення про подію або передачі дозволу, але небезпечно, якщо програміст помилково очікує перевірку власника.

Лічильний семафор

Початкове значення задає кількість однакових доступних ресурсів. Наприклад, семафор зі значенням 3 дозволяє одночасно працювати трьом потокам:

sem_t slots;
sem_init(&slots, 0, 3);

sem_wait(&slots);
/* використання одного з трьох ресурсів */
sem_post(&slots);

sem_destroy(&slots);

Другий аргумент 0 означає спільне використання потоками одного процесу. Виклики потрібно перевіряти на помилки в робочому коді. Не слід читати sem_getvalue і на його основі ухвалювати рішення «чи можна входити»: стан може змінитися одразу після читання; атомарне резервування виконує саме sem_wait.

4. Condition variable: чекати на істинність предиката

Condition variable не зберігає ресурс і не захищає дані самостійно. Вона дає потокові заснути, доки інший потік не повідомить, що пов'язаний стан міг змінитися. Стан захищає mutex.

Правильний шаблон:

pthread_mutex_lock(&mutex);
while (!ready) {
    pthread_cond_wait(&cond, &mutex);
}
/* ready істинний, mutex знову захоплено */
use_ready_data();
pthread_mutex_unlock(&mutex);

pthread_cond_wait атомарно відпускає mutex і переводить потік у очікування. Перед поверненням функція знову захоплює mutex. Перевірка потрібна саме в while, а не в if, тому що:

• POSIX дозволяє хибні пробудження;
• інший потік може першим використати ресурс після сповіщення;
• сповіщення означає «стан міг змінитися», а не «умова гарантовано істинна саме для вас».

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

5. Barrier і read-write lock

Barrier

Barrier відокремлює фази паралельного алгоритму. Кожен із наперед відомої кількості потоків викликає pthread_barrier_wait; останній учасник відкриває перехід усім. Barrier не захищає довільну критичну секцію. Його інваріант: фаза k + 1 не починається, доки всі учасники не завершили фазу k.

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

Read-write lock

Read-write lock має два режими:

• shared/read: кілька читачів можуть увійти одночасно;
• exclusive/write: один письменник входить без читачів і інших письменників.

pthread_rwlock_rdlock(&rwlock);
/* лише читання спільної структури */
pthread_rwlock_unlock(&rwlock);

pthread_rwlock_wrlock(&rwlock);
/* зміна структури */
pthread_rwlock_unlock(&rwlock);

Він може допомогти, коли читання значно частіші та достатньо довгі, а записи рідкісні. Для коротких секцій звичайний mutex може бути простішим і швидшим. Політика переваги читачів або письменників залежить від реалізації; не можна без перевірки покладатися на конкретну справедливість.

6. Виробник-споживач: повний POSIX-приклад

Маємо обмежений кільцевий буфер. Mutex захищає buffer, head, tail і count. Дві condition variables виражають різні предикати: «буфер не повний» і «буфер не порожній».

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

enum { CAPACITY = 4, ITEMS = 10 };

static int buffer[CAPACITY];
static size_t head = 0, tail = 0, count = 0;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER;
static pthread_cond_t not_full = PTHREAD_COND_INITIALIZER;

static void *producer(void *unused) {
    (void)unused;
    for (int value = 1; value <= ITEMS; ++value) {
        pthread_mutex_lock(&mutex);
        while (count == CAPACITY) {
            pthread_cond_wait(&not_full, &mutex);
        }
        buffer[tail] = value;
        tail = (tail + 1) % CAPACITY;
        ++count;
        pthread_cond_signal(&not_empty);
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

static void *consumer(void *unused) {
    (void)unused;
    for (int i = 0; i < ITEMS; ++i) {
        pthread_mutex_lock(&mutex);
        while (count == 0) {
            pthread_cond_wait(&not_empty, &mutex);
        }
        int value = buffer[head];
        head = (head + 1) % CAPACITY;
        --count;
        pthread_cond_signal(&not_full);
        pthread_mutex_unlock(&mutex);
        printf("consumed %d\n", value);
    }
    return NULL;
}

int main(void) {
    pthread_t p, c;
    if (pthread_create(&p, NULL, producer, NULL) != 0 ||
        pthread_create(&c, NULL, consumer, NULL) != 0) {
        fputs("pthread_create failed\n", stderr);
        return EXIT_FAILURE;
    }
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&not_empty);
    pthread_cond_destroy(&not_full);
    return EXIT_SUCCESS;
}

Збережіть як producer_consumer.c, скомпілюйте та запустіть:

cc -std=c11 -Wall -Wextra -Wpedantic -pthread producer_consumer.c -o producer_consumer
./producer_consumer

Через одного виробника й одного споживача значення виводяться від 1 до 10. Планувальник може змінювати моменти перемикань, але інваріант 0 <= count <= CAPACITY зберігається.

Семафорний варіант часто використовує empty = CAPACITY, full = 0 і mutex для структури буфера. Семафори рахують вільні та зайняті місця, а mutex захищає саму зміну індексів.

7. Читачі-письменники

Задача моделює спільну структуру, яку багато потоків читають і зрідка змінюють. Базова вимога:

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

pthread_rwlock_t прямо виражає цю політику. Але задача має додатковий вимір - голодування. Постійний потік нових читачів може надовго затримати письменника за політики переваги читачів; перевага письменників може затримувати читачів. Тому правильність взаємного виключення ще не гарантує справедливості.

8. Філософи, які обідають

П'ять філософів сидять навколо столу; між сусідами лежить по одній виделці. Для їжі потрібні обидві сусідні виделки. Якщо кожен спочатку захопить ліву, а потім чекатиме праву, утвориться цикл очікування.

Коректні стратегії:

1. Глобальний порядок ресурсів: пронумерувати виделки й завжди захоплювати меншу за номером першою.
2. Офіціант: окремий координатор дозволяє почати захоплення лише безпечній кількості філософів.
3. Асиметрія: один філософ бере виделки у протилежному порядку, руйнуючи цикл; цей прийом складніше узагальнювати.

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

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

Завдання 1. Відтворіть і поясніть

Скомпілюйте producer_consumer.c. Для кожної спільної змінної вкажіть mutex, що її захищає, і предикат кожної condition variable. Поясніть, чому заміна обох while на if неправильна.

Завдання 2. Додайте конкуренцію

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

Завдання 3. Спроєктуйте пул з'єднань

Сервіс має п'ять однакових з'єднань із базою та 30 робочих потоків. Запропонуйте:

1. лічильний примітив для кількості доступних з'єднань;
2. захист структури, з якої беруть конкретний об'єкт з'єднання;
3. порядок отримання й повернення дозволу та об'єкта;
4. обробку помилки так, щоб дозвіл не втрачався;
5. критерій, за яким перевірите відсутність голодування.

Підсумок

• Mutex забезпечує взаємне виключення й має власника; розблоковує його потік-власник.
• Бінарний semaphore може мати схожі значення, але не задає володіння й придатний для передачі дозволу або події.
• Лічильний semaphore моделює кількість однакових доступних ресурсів.
• Condition variable завжди пов'язана з предикатом і mutex; очікування виконується в циклі while.
• Barrier синхронізує завершення фаз, а read-write lock розділяє паралельне читання та виключний запис.
• Класичні задачі показують не готові рецепти, а інваріанти, голодування, порядок ресурсів і межі кожного примітива.