Операционные системы и язык C / Взаимодействие процессов и синхронизация / урок 39 из 49

Гонки и критические секции

⏱ 30 мин · 🧩 заданий: 5

Состояние гонки

Гонка (race condition) — ситуация, когда результат зависит от того, в каком порядке выполнятся операции параллельных процессов или потоков.

Классический пример — счётчик в общей памяти:

/* общая память */
mem->counter++;

Одна строка C превращается в три машинных шага:

mov  eax, [counter]    ; 1. прочитать
add  eax, 1            ; 2. прибавить
mov  [counter], eax    ; 3. записать
время процесс A процесс B counter в памяти │ mov eax, [counter] (0) 0 │ mov eax, [counter] (0) 0 │ add eax, 1 (1) 0 │ mov [counter], eax 1 │ add eax, 1 (1) 1 ▼ mov [counter], eax 1 ← потеряно одно увеличение

На многопроцессорной машине процессы и вовсе выполняются одновременно, а на одном процессоре переключение может произойти между любыми двумя инструкциями.

Критическая секция

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

  1. Взаимное исключение — в секции не больше одного.
  2. Прогресс — если секция свободна, кто-то из желающих войдёт.
  3. Ограниченное ожидание — никто не ждёт бесконечно.
  4. Никаких предположений о скоростях и числе процессоров.
вход_в_секцию();
/* критическая секция: работа с общими данными */
выход_из_секции();

Гонки в задаче 8

Все процессы работают с одной структурой Mem в разделяемой памяти:

Место Проблема
mem->counter++ неатомарно (в этой программе увеличения идут по цепочке друг за другом, но в общем случае — гонка)
mem->pid = ...; mem->ppid = ...; разные процессы перезаписывают одну пару полей; пара может «склеиться» из двух процессов
for (i < mem->counter) printf(mem->ppid, mem->pid) родитель читает значения, пока их меняют другие; counter может расти во время цикла
wait(NULL) ждёт только своего потомка, а не всю цепочку

Наивные решения не работают

Флаг-замок

while (mem->state != 0) ;   /* ждать */
mem->state = 1;              /* занять — но между проверкой и записью может вклиниться другой! */

volatile

volatile запрещает компилятору держать значение в регистре — каждый раз будет чтение из памяти. Но неделимости он не даёт и порядок операций на других процессорах не гарантирует.

Запрет прерываний

На однопроцессорной машине ядро может запретить прерывания на время секции. Процессам это недоступно (привилегированная инструкция), и на многопроцессорной машине не помогает.

Алгоритм Петерсона

Программное решение для двух процессов только на чтениях и записях:

volatile int flag[2] = {0, 0};
volatile int turn;

void lock(int i)              /* i = 0 или 1 */
{
    int j = 1 - i;
    flag[i] = 1;              /* хочу войти */
    turn = j;                 /* уступаю очередь */
    while (flag[j] && turn == j)
        ;                     /* ждать */
}

void unlock(int i) { flag[i] = 0; }

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

Атомарные инструкции

Процессор предоставляет неделимые операции «прочитать-изменить-записать»:

Инструкция Действие
test-and-set записать 1 и вернуть старое значение
compare-and-swap (CAS, cmpxchg) если значение равно ожидаемому — заменить, вернуть успех
fetch-and-add (lock xadd) прибавить и вернуть старое значение 
/* атомарный счётчик */
__atomic_fetch_add(&mem->counter, 1, __ATOMIC_SEQ_CST);

/* или C11 */
#include <stdatomic.h>
atomic_uint counter;
atomic_fetch_add(&counter, 1);

/* спин-блокировка на test-and-set */
while (__atomic_test_and_set(&mem->lock, __ATOMIC_ACQUIRE))
    ;                                   /* крутимся */
/* критическая секция */
__atomic_clear(&mem->lock, __ATOMIC_RELEASE);

Спин-блокировка тратит процессорное время, пока ждёт. Если ждать долго, лучше усыпить процесс — этим занимаются семафоры и мьютексы ядра (следующий урок).

Итог

  • Гонка — результат зависит от порядка выполнения; counter++ — три шага.
  • Критическая секция требует взаимного исключения, прогресса и ограниченного ожидания.
  • Флаг-замок и volatile не дают неделимости «проверить и занять».
  • Решения: алгоритм Петерсона (теория), атомарные инструкции (test-and-set, CAS, fetch-and-add), а для долгого ожидания — примитивы с засыпанием.

Практика решено 0 из 5

Вы не вошли — ответы проверяются, но прогресс не сохранится. Войти или зарегистрироваться.
Задание 1 Расставить по порядку

Расставьте шаги, из-за которых два процесса, выполняя counter++ одновременно, получают 1 вместо 2 (начальное значение 0):

  1. Планировщик переключает на процесс B; B читает counter: 0
  2. A продолжает: прибавляет 1 к своему регистру (0 + 1) и записывает: counter = 1
  3. B прибавляет 1 и записывает в память: counter = 1
  4. Процесс A читает counter из памяти в регистр: 0
Задание 2 Несколько вариантов

Какие требования предъявляются к решению задачи критической секции?

Задание 3 Один вариант ответа

В задаче 8 несколько процессов выполняют mem->pid = getpid(); mem->ppid = getppid();. Какая проблема возможна?

Задание 4 Один вариант ответа

Почему такой «замок» не работает?

while (mem->state != 0) ;   /* ждать */
mem->state = 1;              /* занять */
/* критическая секция */
mem->state = 0;
Задание 5 Написать код

Сделайте увеличение счётчика в разделяемой памяти атомарным с помощью встроенной функции GCC: __atomic_fetch_add(&mem->counter, 1, __ATOMIC_SEQ_CST); вместо mem->counter++;.

Войдите, чтобы отмечать пройденные уроки.