Гонка: почему c = c + 1 теряет прибавления и что такое критическая секция

Если ты знаешь, почему инкремент не атомарен, что такое чередование и чем взаимоблокировка отличается от голодания, листай до «Теперь сам».

Как думаешь, что напечатает

Два потока, у каждого цикл из двух шагов: c = c + 1. В начале c = 0. Какие значения c возможны в конце? И насколько часто будет правильный ответ 4?

Ответь себе до чтения. «4, иногда 3» - частый ответ. Перебор всех порядков в разборе показывает, что возможны 2, 3 и 4, и из 924 возможных порядков ответ 4 дают только шесть.

На что это похоже

Два кассира ведут общую тетрадь с остатком наличных. Каждый, приняв деньги, подходит к тетради, читает остаток, считает в уме новый и записывает. Если оба подошли одновременно, прочитали «100», приняли по 10 и записали «110», - десятка пропала из учёта, хотя в кассе она есть. Никто не ошибся в сложении: ошибка в том, что между «прочитал» и «записал» тетрадь поменялась.

Решение очевидное: тетрадь в каждый момент у одного кассира. Ровно это и называют взаимным исключением.

Механизм: чередование операций

Поток выполняет свои операции по порядку, но между двумя его операциями может вклиниться сколько угодно операций другого потока. Итоговая последовательность всех операций - чередование. Для двух потоков по a и b операций чередований C(a + b, a) - число способов выбрать, какие места займёт первый поток. Три операции у каждого - 20 чередований, шесть - уже 924.

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

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

Последние два - свойства живости: «хорошее когда-нибудь случается».

Правило

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

Разбор: все чередования двух потоков

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

def itogi(k):
    # два потока, у каждого k раз: прочитать c, прибавить 1, записать;
    # перебираем все чередования этих 3k + 3k операций
    vstrecheno = {}
    # состояние: c, шаги потоков 0 и 1, регистры потоков 0 и 1
    stek = [[0, 0, 0, 0, 0]]
    vsego = 0
    while len(stek) > 0:
        c, s0, s1, r0, r1 = stek.pop()
        if s0 == 3 * k and s1 == 3 * k:
            vsego = vsego + 1
            vstrecheno[c] = vstrecheno.get(c, 0) + 1
            continue
        if s0 < 3 * k:
            faza = s0 % 3
            if faza == 0:
                stek.append([c, s0 + 1, s1, c, r1])
            elif faza == 1:
                stek.append([c, s0 + 1, s1, r0 + 1, r1])
            else:
                stek.append([r0, s0 + 1, s1, r0, r1])
        if s1 < 3 * k:
            faza = s1 % 3
            if faza == 0:
                stek.append([c, s0, s1 + 1, r0, c])
            elif faza == 1:
                stek.append([c, s0, s1 + 1, r0, r1 + 1])
            else:
                stek.append([r1, s0, s1 + 1, r0, r1])
    return [vsego, vstrecheno]

for k in [1, 2]:
    r = itogi(k)
    otvety = []
    for c in sorted(r[1]):
        otvety.append([c, r[1][c]])
    print(k, "чередований", r[0], "итог: сколько раз", otvety)

1 чередований 20 итог: сколько раз [[1, 18], [2, 2]]
2 чередований 924 итог: сколько раз [[2, 702], [3, 216], [4, 6]]

Один инкремент на поток - 20 чередований, и только 2 из них дают правильную двойку: те, где один поток закончил все три операции до того, как другой начал. Стоит им перекрыться хоть на одну операцию - результат 1. Два инкремента на поток - 924 чередования, и итог бывает 2, 3 или 4, причём правильная четвёрка - в шести случаях. Двойка встречается чаще всех, и это не случайность перебора: известно, что при двух потоках по k инкрементов итог может опуститься до 2 при любом k ≥ 2.

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

Разбор: гонка, которая проходит тест

Теперь планировщик переключает потоки случайно: после каждой операции с вероятностью q. Чем меньше q, тем дольше поток работает без помех - так похоже ведёт себя одно ядро при редких прерываниях. Числа модели - иллюстрация, а не замер: на нескольких ядрах потоки идут ещё и одновременно.

import random

def progon(n, q):
    # каждый поток n раз делает c = c + 1 в три операции;
    # после каждой операции планировщик с вероятностью q переключается
    c = 0
    shag = [0, 0]
    reg = [0, 0]
    t = 0
    while shag[0] < 3 * n or shag[1] < 3 * n:
        if shag[t] == 3 * n or random.random() < q:
            t = 1 - t
            if shag[t] == 3 * n:
                t = 1 - t
        faza = shag[t] % 3
        if faza == 0:
            reg[t] = c
        elif faza == 1:
            reg[t] = reg[t] + 1
        else:
            c = reg[t]
        shag[t] = shag[t] + 1
    return c

random.seed(4)
for q in [0.001, 0.01, 0.1, 0.5]:
    poteryano = []
    for opyt in range(4):
        poteryano.append(400 - progon(200, q))
    print("переключение", q, "потеряно из 400:", poteryano)

переключение 0.001 потеряно из 400: [51, 117, 0, 0]
переключение 0.01 потеряно из 400: [152, 161, 30, 116]
переключение 0.1 потеряно из 400: [124, 138, 135, 140]
переключение 0.5 потеряно из 400: [163, 178, 168, 175]

При частых переключениях теряется почти половина прибавлений, и ошибка видна сразу. При редких - два прогона из четырёх не потеряли НИЧЕГО: тест прошёл бы зелёным. А в двух других пропало 51 и 117 прибавлений: одно неудачное переключение посреди «прочитал - записал» стирает всю работу, которую другой поток успел сделать за это время. Именно так гонки и живут в коде: месяцами проходят тесты, а потом в нагрузку, на другой машине или после обновления компилятора теряют деньги.

Что ломается без этого

«У меня работает». Гонку на машине разработчика не видно: мало ядер, мало нагрузки, планировщик переключает редко. На сервере с 64 ядрами те же строки теряют обновления каждую секунду.

Проверка «если ещё не занято - займи». if not zanyato: zanyato = True - тоже чтение и запись с зазором между ними: оба потока видят «не занято», и оба входят. Замок, написанный так, не исключает ничего; почему - следующий урок.

Взаимоблокировка вместо гонки. Два потока захватывают два замка в разном порядке: первый держит A и ждёт B, второй держит B и ждёт A. Защиты слишком много, и программа стоит.

Зачем это в работе

Счётчик просмотров в базе (UPDATE ... SET views = views + 1 против «прочитали в приложении, прибавили, записали»), остаток на складе при одновременных заказах, баланс кошелька - всё это тот же c = c + 1. В Python с глобальной блокировкой интерпретатора c += 1 тоже не атомарен: поток могут прервать между чтением и записью. А с выходом Python 3.14 (октябрь 2025) сборка без этой блокировки стала официально поддерживаемой - код, который «случайно работал», начнёт терять обновления чаще.

Три свойства - взаимоисключение, отсутствие взаимоблокировки, отсутствие голодания - и есть техзадание на любой замок: от мьютекса в ядре до распределённой блокировки на Redis.

Теперь сам

1. Сколько чередований у двух потоков по две операции? Перечисли их.
2. Почему при двух инкрементах на поток итог не может быть 1?
3. Протокол позволяет двум потокам одновременно ждать друг друга вечно. Какое из трёх свойств нарушено? А если один поток входит снова и снова, а второй ждёт вечно?