Потоки, блокировки и гонки — Примеры

Пример 1 — Итог, который ошибается несколько раз на миллион

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

counter = 0
поток A: читает counter -> 41
поток B: читает counter -> 41
поток A: пишет 42
поток B: пишет 42        <- увеличение A потеряно

ожидаемый итог: 400 000
наблюдаемый итог: меняется от запуска к запуску, всегда меньше 400 000

Решение

чтение и запись — два отдельных шага. Когда они переплетаются, оба потока
читают одно значение и одна запись затирает другую.

lock(mutex)
    counter = counter + 1     # чтение, сложение и запись теперь один шаг
unlock(mutex)

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

Пример 2 — Два потока, каждый ждёт другого

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

поток A: lock(account_1) ... затем хочет account_2
поток B: lock(account_2) ... затем хочет account_1

A держит account_1 и ждёт account_2
B держит account_2 и ждёт account_1   <- ни один не может двинуться

Решение

цикл в графе ожидания: A ждёт блокировку, которую держит B, а B ждёт
ту, что держит A.

исправить: задайте один глобальный порядок и всегда берите обе блокировки в нём.
     поток A: lock(min(from, to)), затем lock(max(from, to))
     поток B: тот же порядок — теперь один поток ждёт, а потом завершается

Зависание вызвано не какой-то из блокировок по отдельности, а тем, что два пути берут их в разном порядке: один глобальный порядок разрывает цикл, ведь никакой поток не может держать блокировку с большим номером и ждать блокировку с меньшим, а try-lock, который отступает и повторяет попытку, — второй стандартный ответ. Ловушка в том, что взаимоблокировка появляется только когда оба пути выполняются в один миг, поэтому тест, выполняющий по одному переводу за раз, её не воспроизводит.