Міжпроцесна взаємодія та взаємні блокування

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

Цілі лекції

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

• порівнювати pipes, FIFO, message queues, signals, shared memory і sockets;
• обирати IPC за межами зв'язку, моделлю даних, продуктивністю та синхронізацією;
• пояснювати обмеження async-signal-safe операцій;
• визначати чотири умови Коффмана та читати граф розподілу ресурсів;
• відрізняти запобігання, уникнення, виявлення й відновлення після deadlock;
• перевіряти безпечний стан алгоритмом банкіра.

Передумови

Потрібно розуміти процеси, fork, exec, файлові дескриптори, блокувальні системні виклики, mutex і semaphore. Усі демонстрації виконуються звичайним користувачем у навчальному каталозі Linux або іншої POSIX-системи.

1. Як порівнювати IPC

Поставте до механізму п'ять запитань:

1. Чи є процеси спорідненими, локальними або розміщеними на різних вузлах?
2. Передаємо потік байтів, окремі повідомлення чи спільний стан?
3. Хто визначає межі повідомлень і формат протоколу?
4. Де виконується буферизація та що означає переповнення?
5. Яка синхронізація, автентифікація й обробка відмов потрібні?

2. Pipes і FIFO

Безіменний pipe

pipe(fd) створює два дескриптори: fd[0] для читання та fd[1] для запису. Зазвичай його створюють до fork, а після fork кожен процес закриває невикористаний кінець.

Shell-конвеєр є безпечною готовою демонстрацією:

printf '%s\n' alpha beta gamma | grep 'a' | wc -l

Кожна команда працює в окремому процесі, а shell з'єднує stdout попередньої зі stdin наступної. Результат дорівнює 3.

Pipe є потоком байтів: один write не створює універсальної межі «повідомлення» для читача. Протокол має визначати довжину, роздільник або фіксований формат. read може повернути менше байтів, ніж запитано. Після закриття всіх кінців запису читач отримує EOF; тому зайва відкрита копія fd[1] може змусити його чекати нескінченно.

FIFO

FIFO, або named pipe, має шлях у файловій системі й може з'єднати неспоріднені локальні процеси. Безпечна демонстрація у двох терміналах:

tmpdir=$(mktemp -d)
mkfifo "$tmpdir/events.fifo"
printf 'FIFO path: %s\n' "$tmpdir/events.fifo"
printf '%s\n' 'job-ready' > "$tmpdir/events.fifo"

У другому терміналі після створення FIFO:

cat /tmp/actual-directory/events.fifo

Замініть шлях значенням FIFO path, яке надрукує перший термінал, або виконайте демонстрацію в одному shell із фоновим читачем:

tmpdir=$(mktemp -d)
mkfifo "$tmpdir/events.fifo"
cat "$tmpdir/events.fifo" & reader=$!
printf '%s\n' 'job-ready' > "$tmpdir/events.fifo"
wait "$reader"
rm -rf -- "$tmpdir"

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

3. Message queues

Черга повідомлень зберігає межі повідомлень, тому одержувач не відновлює їх із довільного потоку байтів. POSIX API використовує імена на кшталт /events, mq_send, mq_receive, атрибути максимальної кількості й розміру повідомлень.

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

System V message queues мають інший API (msgget, msgsnd, msgrcv). Не слід змішувати ідентифікатори та правила життєвого циклу двох сімейств.

4. Signals і async-signal-safe обмеження

Signal є асинхронним сповіщенням, а не транспортом довільних даних. Звичайні сигнали можуть зливатися: кілька однакових сигналів, що очікують, не обов'язково утворюють таку саму кількість викликів handler.

Обробник перериває код у непередбачуваній точці. Більшість бібліотечних функцій, зокрема printf, malloc і звичайні операції з mutex, не є async-signal-safe. Безпечний підхід: handler виконує мінімальну дію, наприклад присвоює volatile sig_atomic_t або пише байт у self-pipe; звичайний код обробляє подію пізніше.

Повний приклад self-pipe:

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static int signal_fd = -1;

static void on_signal(int signo) {
    unsigned char byte = (unsigned char)signo;
    int saved_errno = errno;
    if (signal_fd >= 0) {
        (void)write(signal_fd, &byte, 1);
    }
    errno = saved_errno;
}

int main(void) {
    int fds[2];
    if (pipe(fds) == -1) {
        perror("pipe");
        return EXIT_FAILURE;
    }
    signal_fd = fds[1];

    struct sigaction action = {0};
    action.sa_handler = on_signal;
    sigemptyset(&action.sa_mask);
    action.sa_flags = SA_RESTART;
    if (sigaction(SIGUSR1, &action, NULL) == -1) {
        perror("sigaction");
        return EXIT_FAILURE;
    }

    if (raise(SIGUSR1) != 0) {
        fputs("raise failed\n", stderr);
        return EXIT_FAILURE;
    }

    unsigned char event;
    ssize_t n;
    do {
        n = read(fds[0], &event, 1);
    } while (n == -1 && errno == EINTR);

    if (n == 1) {
        printf("received signal %u in normal flow\n", (unsigned)event);
    }
    close(fds[0]);
    close(fds[1]);
    return n == 1 ? EXIT_SUCCESS : EXIT_FAILURE;
}

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

У handler викликається лише write, який POSIX відносить до async-signal-safe, та зберігається errno. printf виконується у звичайному потоці керування. Для інтенсивного реального потоку сигналів write-end роблять неблокувальним і визначають політику переповнення self-pipe; цей приклад надсилає один байт і не може заповнити pipe.

5. Shared memory

Shared memory відображає ті самі фізичні сторінки в адресні простори кількох процесів. POSIX-послідовність зазвичай містить shm_open, ftruncate, mmap, а наприкінці munmap, close і shm_unlink.

Перевага - після налаштування великі дані не потрібно копіювати через ядро для кожного обміну. Але shared memory не надає автоматично:

• меж повідомлень;
• узгодженого формату та версії структури;
• атомарності складених змін;
• повідомлення про готовність даних;
• відновлення після завершення власника.

Для конкурентної зміни потрібна міжпроцесна синхронізація: named POSIX semaphore, semaphore у спільній пам'яті з pshared != 0, або process-shared mutex/condition variable з коректно налаштованими атрибутами. Звичайний process-private pthread_mutex_t, скопійований у кожен процес, не координує їх.

6. Sockets

Socket є двосторонньою кінцевою точкою. Unix domain sockets працюють на одному вузлі й можуть використовувати шлях або абстрактний namespace Linux. Internet sockets працюють через IP. Потоковий SOCK_STREAM дає надійний упорядкований потік байтів, але не зберігає меж повідомлень. SOCK_DGRAM зберігає datagram, проте має інші гарантії доставки.

Для TCP-сервера типовий порядок: socket → bind → listen → accept → recv/send. Для клієнта: socket → connect → send/recv. send і recv можуть опрацювати лише частину буфера; завершений протокол має цикли, framing, ліміти довжини, тайм-аути та обробку розриву.

Unix domain socket часто є кращим за TCP для локального клієнт-серверного сервісу: не потребує мережевої адресації та дає змогу контролювати доступ через права й облікові дані. Для взаємодії між вузлами потрібні мережеві sockets і окремо продумана автентифікація та шифрування.

7. Deadlock і чотири умови Коффмана

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

Для можливості deadlock одночасно потрібні чотири умови:

1. Mutual exclusion: принаймні один ресурс не можна спільно використовувати.
2. Hold and wait: процес утримує ресурс і чекає інший.
3. No preemption: ресурс не можна примусово безпечно відібрати; власник звільняє його сам.
4. Circular wait: існує цикл процесів, де кожен чекає ресурс наступного.

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

8. Граф розподілу ресурсів

У resource-allocation graph процеси позначають колами, ресурси - прямокутниками:

• ребро P → R означає, що процес запитує ресурс;
• ребро R → P означає, що екземпляр ресурсу призначено процесу.

Якщо кожен тип ресурсу має один екземпляр, цикл означає deadlock. Якщо типи мають кілька екземплярів, цикл є необхідним сигналом ризику, але сам по собі може бути недостатнім доказом. Для загального випадку використовують матриці доступних, виділених і очікуваних ресурсів.

9. Виявлення та відновлення

Стратегія detection дозволяє системі входити в deadlock, періодично шукає цикл або процеси, чиї запити неможливо задовольнити, а потім запускає recovery.

Можливі способи відновлення:

• завершити всі заблоковані процеси;
• завершувати по одному, повторюючи виявлення;
• відібрати ресурс, якщо його стан можна безпечно зберегти й відкотити;
• відкотити процес до checkpoint і повторити роботу.

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

10. Алгоритм банкіра

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

Основні вектори й матриці:

Available      - вільні екземпляри кожного типу
Max            - максимальна заявлена потреба процесів
Allocation     - уже виділені ресурси
Need = Max - Allocation

Перевірка безпеки:

1. Work = Available, усі Finish = false.
2. Знайти незавершений процес Pi, для якого Need[i] <= Work покомпонентно.
3. Припустити його завершення: Work += Allocation[i], Finish[i] = true.
4. Повторювати. Якщо завершено всі процеси, знайдений порядок є безпечною послідовністю.

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

Нехай Available = 1. Спочатку може завершитися P1: після повернення його ресурсу Work = 2. Тоді завершується P0, Work = 3, потім P2. Послідовність P1 → P0 → P2 доводить безпечність.

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

11. Prevention, avoidance, detection

Для прикладного коду найчастіше застосовують prevention: єдиний порядок захоплення locks, мінімум одночасно утримуваних ресурсів, обмежені очікування й відмова від виклику невідомого коду під lock. Timeout допомагає повернути керування, але сам по собі не доводить відсутність deadlock і потребує коректного rollback.

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

Завдання 1. Простежте канал

Запустіть shell-конвеєр і FIFO-демонстрацію. Для кожної визначте процеси, напрям байтів, умову EOF, місце буферизації та системний виклик, який може блокуватися.

Завдання 2. Розширте self-pipe

Змініть приклад так, щоб звичайний код розрізняв SIGUSR1 і SIGUSR2. Handler має лише записувати однобайтовий код через write; форматований вивід залиште поза handler. Перевірте обидва сигнали через raise.

Завдання 3. Розберіть інцидент

Процес імпорту тримає lock cache, а потім просить database; процес звіту тримає database, а потім просить cache.

1. Побудуйте resource-allocation graph.
2. Назвіть усі чотири умови Коффмана в цьому сценарії.
3. Запропонуйте prevention через глобальний порядок.
4. Поясніть, що треба відкотити, якщо система обере завершення імпорту.
5. Сформулюйте метрики для detection: тривалість очікування, власники та ланцюг залежностей.

Підсумок

• Pipe і FIFO передають потік байтів; FIFO має ім'я та з'єднує неспоріднені локальні процеси.
• Message queue зберігає межі повідомлень; shared memory потребує окремої міжпроцесної синхронізації.
• Signal призначений для короткого сповіщення; handler обмежений async-signal-safe операціями.
• Sockets підтримують локальний і мережевий клієнт-серверний обмін, але протокол має враховувати часткові операції.
• Deadlock потребує одночасної дії чотирьох умов Коффмана.
• Цикл у графі є доказом deadlock для одноекземплярних ресурсів і сигналом ризику для багатоекземплярних.
• Алгоритм банкіра допускає видачу лише зі збереженням безпечної послідовності; небезпечний стан ще не є deadlock.
• Запобігання, уникнення, виявлення та відновлення мають різні вимоги й експлуатаційну ціну.