Экспоненциальный откат

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Шестнадцать потоков увидели свободный замок. Один успешно выполнил атомарный захват, пятнадцать проиграли. Если все повторят попытку через одинаковую фиксированную паузу, что произойдёт после следующего освобождения? Они могут снова прийти одной группой. Уменьшение частоты ещё не означает, что попытки перестали сталкиваться.

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

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

Механизм: от определения к алгоритму

В TAS каждая попытка выполняет атомарную модификацию общей ячейки. TTAS сначала читает её до освобождения и только затем пробует атомарный захват. Но между чтением «свободно» и захватом другой поток может успеть первым. Именно такая неудача указывает на соперника, который тоже заметил освобождение. Само наблюдение занятого замка ещё не доказывает высокой конкуренции: внутри может быть всего один долгий владелец.

После проигранной попытки выбери задержку из [0,limit), затем удвой limit, ограничив его значением maxDelay. Следующую попытку выполняй после задержки. Начальное окно minDelay и верхняя граница задаются в согласованных единицах: циклах ожидания или времени. При новом независимом захвате окно обычно начинают заново; сохранять большое окно между редкими вызовами означало бы переносить старую конкуренцию на уже свободный замок.

Случайная задержка нарушает синхронность повторов. Максимум предотвращает неограниченный рост окна, однако не ограничивает число неудачных попыток. Поток может много раз проигрывать и при максимальном окне. Поэтому откат не превращает блокирующий замок в lock-free структуру и не гарантирует ограниченного времени ожидания отдельному потоку.

В реальной реализации важно различать короткую инструкцию ожидания процессора, активный спин и усыпление потока ОС. Переключение контекста само стоит времени; короткую критическую секцию иногда выгоднее переждать на ядре. Для долгих ожиданий активный спин расходует процессор. Это инженерный выбор, который модель слотов ниже не предсказывает.

Независимые источники случайности должны действительно разносить решения. Одинаковые зерно и последовательность обращений у всех участников синхронно выдают одинаковые задержки. Нельзя брать учебный фиксированный seed как готовую рекомендацию для всех потоков production: здесь он нужен только для воспроизводимости объясняющего эксперимента.

Правило

Увеличивай случайное окно после проигранного атомарного захвата, ограничивай максимум и проверяй выигрыш на целевой нагрузке; гарантий справедливости это не создаёт.

Разбор: проследим вычисление

Модель считает коллизией слот, который одновременно выбрали несколько участников. В каждом раунде единственные в своём слоте завершаются, остальные расширяют окно. Это модель конкуренции за слоты, а не таймерная модель настоящей блокировки: владелец замка, длительность секции и кеш-когерентность здесь отсутствуют. Фиксированные числа не следует выдавать за ускорение программы на машине.

import random

rng = random.Random(17)
waiting = set(range(12))
limits = {i: 2 for i in waiting}
rounds = collisions = 0
while waiting:
    rounds += 1
    slots = {}
    for i in sorted(waiting):
        slot = rng.randrange(limits[i])
        slots.setdefault(slot, []).append(i)
    completed = set()
    for ids in slots.values():
        if len(ids) == 1:
            completed.add(ids[0])
        else:
            collisions += len(ids)
            for i in ids:
                limits[i] = min(32, 2 * limits[i])
    waiting -= completed
    assert rounds < 1000
print("завершились", 12 - len(waiting))
print("раундов", rounds, "участий в коллизиях", collisions)

# Одинаковый выбор не нарушает симметрию.
fixed = [4] * 12
assert len(set(fixed)) == 1
print("фиксированная задержка: в одном слоте", len(fixed))
# Окно ограничено, число повторов этим не ограничено.
limit = 2
for _ in range(20):
    limit = min(32, 2 * limit)
print("после 20 неудач окно", limit)

завершились 12
раундов 4 участий в коллизиях 31
фиксированная задержка: в одном слоте 12
после 20 неудач окно 32

Разбор: где проходит граница

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

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

Слишком маленькое окно сохраняет всплески, слишком большое повышает задержку при слабой конкуренции. Неограниченное удвоение создаёт огромные паузы и переполнение счётчика. Откат после любого чтения «занято» реагирует и на долгую секцию одного владельца, хотя исходный сигнал о конкуренции был другим. А завершение модели при seed=17 не доказывает, что каждый возможный набор случайных решений быстро завершится.

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

Откат применяют в конкурентных структурах, сетевых повторах и протоколах разрешения конфликтов, но параметры и сигналы неудачи у них различаются. Для замка измеряй пропускную способность, хвост задержек и число атомарных попыток при разном числе ядер и длине секции. Если задача требует ограниченного обгона, нужна очередь, например MCS или билетный замок, а не увеличение случайной паузы.

Теперь сам

Начальное окно 4, максимум 20. Запиши размеры окон для первых пяти неудач, если задержка выбирается до удвоения. Ограничен ли числом 20 весь срок ожидания?