Раздел 06 — Синхронизация и взаимоблокировки

Потоки одного процесса делят память (раздел 04). Пока они только читают общие данные, всё хорошо. Когда хотя бы один пишет, результат может зависеть от того, в каком порядке планировщик их выполнил. Такая ошибка называется гонкой данных (race condition).

Программа race.c: два потока по 50 миллионов раз прибавляют единицу к общему счётчику. Ожидается 100 миллионов:

/* Гонка: два потока увеличивают общий счётчик. С ключом lock — под мьютексом. */
#include <pthread.h>
#include <stdio.h>
#include <string.h>

#define N 50000000
long counter = 0;
int use_lock = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *work(void *arg) {
    for (int i = 0; i < N; i++) {
        if (use_lock) pthread_mutex_lock(&m);
        counter++;                      /* прочитать, прибавить 1, записать */
        if (use_lock) pthread_mutex_unlock(&m);
    }
    return NULL;
}

int main(int argc, char **argv) {
    use_lock = argc > 1 && strcmp(argv[1], "lock") == 0;
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("ожидалось %d, получилось %ld\n", 2 * N, counter);
    return 0;
}

$ gcc -O0 -pthread -o race race.c
$ ./race
ожидалось 100000000, получилось 54963609
$ ./race
ожидалось 100000000, получилось 51481832
$ ./race
ожидалось 100000000, получилось 52113477

Каждый запуск даёт своё число, и всегда меньше. Дело в том, что counter++ — не одно действие, а три: прочитать значение из памяти в регистр, прибавить 1, записать обратно. Если потоки на двух ядрах сделают это одновременно, одно прибавление потеряется:

Гонки коварны: при малой нагрузке программа может годами работать правильно и ошибаться только на загруженном сервере. С миллионом прибавлений вместо 50 миллионов на нашем стенде ошибка не проявилась ни разу: первый поток успевал закончить, пока запускался второй.

Участок кода, который работает с общими данными, называют критической секцией. Правильное решение должно обеспечить:

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

Простейший инструмент — мьютекс (mutual exclusion, «взаимное исключение»): замок с двумя операциями. lock захватывает замок; если он занят, поток засыпает, пока замок не освободят. unlock освобождает и будит ждущего. В race.c с ключом lock прибавление выполняется под мьютексом:

$ ./race lock
ожидалось 100000000, получилось 100000000

Последняя строка — ровно 100 миллионов. Цена — скорость: потоки больше не работают параллельно внутри секции, а каждый захват замка — лишняя работа. Поэтому критические секции делают как можно короче.

Мьютексы есть во всех ОС: в Windows — объекты Mutex и CRITICAL_SECTION, в Linux — pthread_mutex и механизм ядра futex. Важно, что ожидающий поток спит (состояние «ожидает», раздел 04) и не тратит процессор.

Семафор (Э. Дейкстра, 1965) — счётчик с двумя операциями. P (wait): если счётчик больше нуля — уменьшить и пройти, иначе ждать. V (signal): увеличить и разбудить одного ждущего. Семафор со значением 1 работает как мьютекс; со значением N — пропускает не больше N потоков сразу. Так ограничивают число одновременных подключений к базе или заданий на печать.

Классическая задача — производитель и потребитель. Один поток кладёт данные в буфер на N мест (например, принимает запросы из сети), другой забирает (обрабатывает). Производитель должен ждать, если буфер полон, потребитель — если пуст, и оба не должны менять буфер одновременно. Решение — три семафора:

производитель:                 потребитель:
  P(empty)   ждать место         P(full)    ждать данные
  P(mutex)                       P(mutex)
  положить в буфер               взять из буфера
  V(mutex)                       V(mutex)
  V(full)    стало больше данных V(empty)   стало больше мест

Порядок важен: если производитель сначала захватит mutex, а потом будет ждать empty при полном буфере, потребитель не сможет войти и освободить место — оба застрянут навсегда. Это уже взаимоблокировка, о ней ниже.

Процессы тоже синхронизируются — через ОС. Самый частый случай, с которым сталкивается администратор, — занятый файл. В Windows программа при открытии файла указывает, что разрешает другим: читать, писать, удалять. Если она открыла файл без общего доступа, остальные получат ошибку:

PS> # другой процесс открыл report.txt без общего доступа (FileShare None) и держит его
PS> Add-Content report.txt "строка"
Add-Content : Процесс не может получить доступ к файлу "C:\Users\student\os\report.txt", так как этот файл используется другим процессом.
PS> Remove-Item report.txt
Remove-Item : Процесс не может получить доступ к файлу "C:\Users\student\os\report.txt", так как этот файл используется другим процессом.
PS> Get-Content report.txt
Get-Content : Процесс не может получить доступ к файлу "C:\Users\student\os\report.txt", так как этот файл используется другим процессом.
PS> # процесс закрыл файл
PS> Add-Content report.txt "строка"; Get-Content report.txt
отчёт
строка

Пока файл открыт, его нельзя ни дописать, ни удалить, ни даже прочитать. Как только процесс закрыл файл, всё работает. Так Windows защищает файлы, которые программа сейчас меняет: базу, документ, журнал.

Кто держит файл? Монитор ресурсов (resmon) → вкладка «ЦП» → «Связанные дескрипторы» → в поиске имя файла: увидите процесс и сможете завершить его. В Linux то же показывают lsof путь и fuser -v путь.

В Linux блокировки по умолчанию рекомендательные: их соблюдают только программы, которые сами о них спрашивают. Например, команда flock не даст запустить два экземпляра одного скрипта. Первый держит блокировку 3 секунды; второй с ключом -n не ждёт и сразу сообщает об отказе, третий без ключа ждёт освобождения:

$ flock lock.txt -c "sleep 3" &
$ flock -n lock.txt -c "echo записал" || echo "файл занят, код $?"
файл занят, код 1
$ time flock lock.txt -c "echo дождался и записал"
дождался и записал

real	0m2,702s
user	0m0,000s
sys	0m0,003s

Так же устроен менеджер пакетов: пока работает одна установка, вторая apt сообщает «Could not get lock /var/lib/dpkg/lock-frontend». Удалять этот файл вручную нельзя — две одновременные установки испортят базу пакетов; нужно дождаться завершения первой.

Взаимоблокировка (тупик, deadlock) — несколько потоков ждут друг друга, и ни один не может продолжить. Программа deadlock.c: поток 1 захватывает замок A и ждёт B, поток 2 захватывает B и ждёт A. Чтобы программа не висела вечно, ожидание ограничено двумя секундами:

$ gcc -pthread -o deadlock deadlock.c
$ ./deadlock
поток 1 захватил A
поток 2 захватил B
поток 1 ждёт B
поток 2 ждёт A
поток 1: B не получен за 2 с — взаимоблокировка
поток 2 получил A

Оба потока захватили по замку и ждут второй. Без ограничения времени они ждали бы вечно. Поток 1 сдался по тайм-ауту, освободил A — и поток 2 смог продолжить. Отказ от ожидания и откат — один из способов выхода из тупика.

Взаимоблокировка возможна, только если одновременно выполнены четыре условия Коффмана:

Ситуацию изображают графом распределения ресурсов: стрелка «поток → ресурс» — поток ждёт ресурс, «ресурс → поток» — ресурс выделен потоку. Если у каждого ресурса один экземпляр, взаимоблокировка есть тогда и только тогда, когда в графе есть цикл:

  Поток 1 ──ждёт──▶ B ──выделен──▶ Поток 2
     ▲                                │
     └──выделен── A ◀──ждёт───────────┘

В deadlock.c достаточно, чтобы второй поток тоже захватывал сначала A, а потом B: тогда он будет ждать A, ничего не держа, и цикла не будет.

Алгоритм банкира (Дейкстра) избегает тупиков: ресурс выдаётся, только если после выдачи система остаётся в безопасном состоянии — существует порядок, в котором все процессы смогут получить свой максимум и завершиться. Как банк, который выдаёт кредит, только если сможет обслужить всех клиентов.

Данные (по каждому виду ресурса — отдельное число):

• Available — свободно сейчас;
• Max — сколько процессу может понадобиться в худшем случае (объявляет заранее);
• Allocation — сколько уже выделено;
• Need = Max − Allocation — сколько ещё может запросить.

Пример: три вида ресурсов A, B, C (всего 10, 5 и 7 единиц) и пять процессов:

$ cat state.txt
# свободно ресурсов A B C
available 3 3 2
P0 max 7 5 3 alloc 0 1 0
P1 max 3 2 2 alloc 2 0 0
P2 max 9 0 2 alloc 3 0 2
P3 max 2 2 2 alloc 2 1 1
P4 max 4 3 3 alloc 0 0 2
$ python3 calc/banker.py < state.txt
            Max   Allocation        Need
P0      7  5  3      0  1  0     7  4  3
P1      3  2  2      2  0  0     1  2  2
P2      9  0  2      3  0  2     6  0  0
P3      2  2  2      2  1  1     0  1  1
P4      4  3  3      0  0  2     4  3  1
Available:  3  3  2
  P1: Need  1  2  2 ≤ Work  3  3  2 → завершится, Work =  5  3  2
  P3: Need  0  1  1 ≤ Work  5  3  2 → завершится, Work =  7  4  3
  P4: Need  4  3  1 ≤ Work  7  4  3 → завершится, Work =  7  4  5
  P0: Need  7  4  3 ≤ Work  7  4  5 → завершится, Work =  7  5  5
  P2: Need  6  0  0 ≤ Work  7  5  5 → завершится, Work = 10  5  7
Состояние безопасно, последовательность: P1, P3, P4, P0, P2

Проверка безопасности:

1. Work = Available.
2. Найти незавершённый процесс, у которого Need ≤ Work по каждому ресурсу. Такой процесс может получить всё нужное и завершиться.
3. Он завершится и вернёт всё, что держит: Work = Work + Allocation. Отметить его завершённым и повторить шаг 2.
4. Если завершились все — состояние безопасно, найденный порядок и есть безопасная последовательность. Если на шаге 2 никто не подходит — небезопасно.

Подходящий процесс ищем по кругу, начиная со следующего после выбранного. Безопасных последовательностей может быть несколько, найти достаточно одну.

Запрос ресурсов процессом Pi:

1. Запрос больше его Need — ошибка: процесс просит больше, чем объявлял.
2. Запрос больше Available — ждать: столько свободных ресурсов нет.
3. Иначе пробно выделить (Available − запрос, Allocation + запрос, Need − запрос) и проверить безопасность. Безопасно — выдать; нет — отменить пробное выделение, процесс ждёт.

P1 просит (1, 0, 2) — после пробной выдачи состояние безопасно, запрос выполняется. Затем, уже в новом состоянии (Available = 2 3 0), три запроса дают три других исхода:

$ python3 calc/banker.py P1 1 0 2 < state.txt
Запрос P1:  1  0  2
Пробно выделяем: Available =  2  3  0, Need P1 =  0  2  0
  P1: Need  0  2  0 ≤ Work  2  3  0 → завершится, Work =  5  3  2
  P3: Need  0  1  1 ≤ Work  5  3  2 → завершится, Work =  7  4  3
  P4: Need  4  3  1 ≤ Work  7  4  3 → завершится, Work =  7  4  5
  P0: Need  7  4  3 ≤ Work  7  4  5 → завершится, Work =  7  5  5
  P2: Need  6  0  0 ≤ Work  7  5  5 → завершится, Work = 10  5  7
Состояние безопасно, последовательность: P1, P3, P4, P0, P2
Запрос выполнить
$ python3 calc/banker.py P4 3 3 0 < state2.txt
Запрос P4:  3  3  0
Ждать: свободно только  2  3  0
$ python3 calc/banker.py P0 0 2 0 < state2.txt
Запрос P0:  0  2  0
Пробно выделяем: Available =  2  1  0, Need P0 =  7  2  3
Состояние НЕБЕЗОПАСНО: при Work =  2  1  0 не могут завершиться P0, P1, P2, P3, P4
Запрос отложить: выделение привело бы к небезопасному состоянию
$ python3 calc/banker.py P3 1 0 0 < state2.txt
Запрос P3:  1  0  0
Отказ: запрос больше остатка потребности Need =  0  1  1 — ошибка процесса

Небезопасное состояние ещё не тупик: процессы могут не запросить свой максимум. Но если запросят — тупик неизбежен, и банкир такого риска не допускает. Цена — нужно заранее знать максимум каждого процесса, а это редко известно. Поэтому в универсальных ОС алгоритм банкира почти не используют, но его идея — «не выдавать, если нельзя гарантировать завершение» — работает в планировщиках ресурсов и СУБД.