Критическая секция и взаимное исключение потоков

Когда два потока одновременно меняют один и тот же счётчик, итог получается непредсказуемым: то на единицу меньше, то на две. Виновата гонка данных - потоки заходят в общий участок кода вперемешку. Чтобы этого не было, такой участок объявляют критической секцией и защищают взаимным исключением: внутри секции в каждый момент может находиться только один поток. Ниже разберём условия корректной синхронизации, классические примитивы и типичные ошибки, а интерактив ниже соберёт точную формулировку вашей задачи для разбора в чате.

Что такое критическая секция

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

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

Рассчитать для своей задачи

Взаимное исключение и условия Дейкстры

Взаимное исключение (mutual exclusion) - главное свойство: если один поток находится в критической секции, ни один другой поток не может войти в свою критическую секцию по тому же ресурсу. Но одного взаимного исключения мало. Эдсгер Дейкстра сформулировал набор требований, которым должно удовлетворять любое корректное решение:

• Взаимное исключение - не более одного потока в критической секции одновременно.
• Прогресс - если секция свободна, а какой-то поток хочет войти, то решение о входе не откладывается бесконечно; потоки, не претендующие на секцию, не мешают.
• Ограниченное ожидание (отсутствие голодания) - существует предел, сколько раз другие потоки могут опередить ждущий поток; рано или поздно он войдёт.

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

Гонка данных: почему счётчик ломается

Гонка данных (race condition) - ситуация, когда корректность результата зависит от того, в каком порядке планировщик чередует потоки. Рассмотрим два потока, каждый делает x = x + 1 при начальном x = 0. Ожидаемый результат - 2. Но возможна такая раскладка во времени:

$$\begin{aligned} &T_1:\ \text{читает } x = 0 \\ &T_2:\ \text{читает } x = 0 \\ &T_1:\ \text{пишет } x = 1 \\ &T_2:\ \text{пишет } x = 1 \end{aligned}$$

Оба потока прочитали ноль до того, как кто-либо записал результат, и итог - 1, а не 2. Это и есть потерянное обновление. Чем больше потоков и итераций, тем заметнее расхождение: на миллионе приращений двумя потоками без защиты итог почти всегда меньше двух миллионов.

Программные решения: алгоритм Петерсона

Исторически взаимное исключение пробовали реализовать чисто программно, без поддержки оборудования. Самое известное корректное решение для двух потоков - алгоритм Петерсона. Он использует два флага намерения flag[0], flag[1] и переменную turn (чья очередь уступить):

$$\begin{aligned} &\text{flag}[i] := \text{true} \\ &\text{turn} := j \\ &\text{ждать, пока } \text{flag}[j] \wedge \text{turn} = j \\ &\quad \text{// критическая секция} \\ &\text{flag}[i] := \text{false} \end{aligned}$$

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

Рассчитать для своей задачи

Аппаратные и системные примитивы: мьютекс и семафор

На практике программные алгоритмы вытеснены примитивами, опирающимися на атомарные инструкции процессора (test-and-set, compare-and-swap) и поддержку ядра ОС.

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

Семафор Дейкстры - счётчик с операциями $P$ (уменьшить, ждать если ноль) и $V$ (увеличить, разбудить ждущего). Бинарный семафор с начальным значением $1$ ведёт себя как замок:

$S = 1 \xrightarrow{\;P\;} S = 0 \xrightarrow{\;V\;} S = 1$

Но семафор шире: со значением $n$ он допускает в секцию до $n$ потоков сразу - это уже не взаимное исключение, а ограничение параллелизма (например, пул из пяти соединений). Подробнее механику счётчика и классические задачи разбирает статья про семафоры и синхронизацию процессов. Когда конфликты редки, вместо блокировок применяют оптимистичную блокировку - проверку версии при записи.

Цена синхронизации: блокировки и взаимоблокировки

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

Опаснее простоя - взаимоблокировка (deadlock): поток A держит замок №1 и ждёт замок №2, а поток B держит №2 и ждёт №1. Оба зависают навсегда. Классическое средство профилактики - захватывать несколько замков всегда в одном и том же глобальном порядке. Ещё одна беда - голодание: поток бесконечно проигрывает гонку за замок другим, более «удачливым» потокам; это нарушение условия ограниченного ожидания, и решается оно справедливыми (fair) замками.

Частые ошибки

• Защищать чтение, но не запись (или наоборот). Под взаимным исключением должны быть обе операции над разделяемым ресурсом, иначе гонка остаётся.
• Захват без освобождения. Выход из критической секции через return или исключение мимо unlock оставляет замок навсегда занятым. Используйте RAII или try/finally.
• Слишком крупная критическая секция. Замок на весь метод вместо одной строки убивает параллелизм; защищайте минимальный необходимый фрагмент.
• Разные замки на один ресурс. Если два участка кода берут разные мьютексы для одной переменной, взаимного исключения между ними нет.
• Надежда на volatile вместо замка. volatile (или atomic без согласованности) гарантирует видимость, но не атомарность составных операций вроде «прочитать-изменить-записать».

FAQ

Чем мьютекс отличается от семафора? Мьютекс - это бинарный замок с владельцем: захватывает и освобождает один поток, состояний всего два. Семафор - счётчик, который может пропустить в секцию сразу несколько потоков (значение $n$) и не имеет владельца: операцию $V$ может выполнить любой поток. Для чистого взаимного исключения берут мьютекс или бинарный семафор.

Можно ли реализовать взаимное исключение без блокировок? Да, существуют lock-free и wait-free структуры данных на атомарных инструкциях compare-and-swap. Они избегают блокировки потоков, но устроены сложнее и не отменяют сам принцип защиты критической секции - просто реализуют его иначе. Алгоритм Петерсона - программное решение без аппаратных замков, но с барьерами памяти.

Почему критическую секцию нужно делать короткой? Пока поток в критической секции, остальные ждут. Чем дольше секция, тем больше времени потоки простаивают, и тем меньше выигрыш от многопоточности. В пределе слишком крупная секция сводит параллельную программу к последовательной.

Коротко

Критическая секция - участок кода с разделяемым ресурсом, который нельзя выполнять двум потокам одновременно; защита от этого называется взаимным исключением. Корректное решение обязано соблюдать условия Дейкстры: взаимное исключение, прогресс и ограниченное ожидание. Без них возникает гонка данных, где результат зависит от порядка планирования. Программно проблему решает алгоритм Петерсона, на практике - мьютексы и семафоры на атомарных инструкциях. Главные риски - взаимоблокировка, голодание и потеря производительности из-за слишком длинных секций, поэтому секцию держат минимально короткой.