Учебный кейс: «Потерянные инкременты» — простой race condition и его устранение.
Краткое описание бага
- Две (или более) нити инкрементируют общий счётчик без синхронизации → потерянные обновления (condition race).
Исходный пример (псевдо-C, упрощённо)
- Общий счётчик: `int counter = 0;`
- Каждая нить выполняет:
for (i = 0; i < N; ++i) { tmp = counter; tmp = tmp + 1; counter = tmp; usleep(SLEEP); }
Параметры (в KaTeX)
- число нитей: $T=2$ - итераций на нить: $N=10^6$ - ожидаемый итог: $expected=T\times N$
Шаги репликации
1. Соберите/запустите программу без синхронизации, с параметрами $T$ и $N$. Повторите запуск несколько раз. Ожидаемый симптом: итоговый счётчик < $expected$.
2. Для увеличения вероятности гонки вставьте небольшую паузу в критическом участке, например `usleep(SLEEP)` с $SLEEP=1000$ мкс — это расширит окно гонки.
3. Автоматизируйте множественные запуски (например, $R=100$ раз) и посчитайте частоту несоответствий: fraction = number_of_failures / $R$.
4. Запустите инструмент динамического анализа (см. ниже) и соберите трассировки.
Инструменты и команды
- ThreadSanitizer (Clang/GCC): собирайте с флагами `-fsanitize=thread -g -O1`. Запуск: программа -> TSan выдаст стек-трейсы данных гонок.
- Valgrind/Helgrind: `valgrind --tool=helgrind ./prog` — медленнее, но даёт другой ракурс.
- GDB: поставить watchpoint на `counter` или breakpoints в местах чтения/записи, воспроизвести конкретную сессию.
- Логирование/printf: добавлять детальные логи с id нити и значениями, чтобы увидеть конкурентные переходы.
- Скрипты для стресс-тестов: циклы запусков, изменение $SLEEP$, параллельных нитей $T$, итераций $N$.
Анализ
- TSan/Helgrind выдадут стек-трейсы двух конфликтующих операций (чтение/запись). По стеку найдите участок кода (обычно инкремент).
- Вручную изучите interleaving: последовательности операций чтение/модификация/запись двух нитей, которые приводят к потере инкремента.
Способы исправления (варианты)
1. Мьютекс:
- Оборачиваем инкремент в критическую секцию:
pthread_mutex_lock(&m); counter = counter + 1; pthread_mutex_unlock(&m);
- Плюс: простота; минус: контенция при высокой частоте.
2. Атомарные операции:
- В C++: `std::atomic counter; counter.fetch_add(1, std::memory_order_relaxed);`
- Плюс: низкая задержка; минус: требует подходящей модели памяти для сложных операций.
3. Алгоритмические изменения:
- Каждая нить накапливает локально и периодически флашит суммарно под блокировкой (снижение количества захватов).
4. Барьеры/флаши памяти для специфичных архитектур (редко нужен для простого инкремента).
Критерии успешного исправления
1. Корректность значений:
- После фикса итоговый счётчик равен $expected=T\times N$ во всех запусках (например при $R=100$ запусках — ноль отклонений).
2. Отсутствие отчётов о гонках от динамических анализаторов:
- TSan/Helgrind не сообщают о data races для данного кода.
3. Регресс-тесты:
- Добавить автоматический тест, который выполняет программу с параметрами $T,N$ и проверяет равенство итогового счётчика $expected$.
4. Производительность:
- Оценить накладные расходы (время выполнения) до и после фикса; для атомиков/мьютексов замерить задержку и пропускную способность и убедиться, что они в приемлемых пределах для задачи.
Примерный план обучения (практическое задание)
1. Запустить ненадёжную версию, измерить частоту ошибок при $T=2,N=10^6,R=100$.
2. Проанализировать вывод TSan и выделить проблемный код.
3. Внести исправление (mutex или atomic), повторить тесты:
- Тест корректности: итог == $expected$ во всех $R$ запусках.
- Проверка TSan: отсутствуют сообщения.
4. Сравнить производительность (время выполнения исходной версии, версии с mutex, версии с atomic) и аргументировать выбор.
Краткое резюме
- Воспроизвести: многократные запуски с небольшими задержками в критическом участке (например $SLEEP=1000$ мкс) повышают шанс проявления гонки.
- Инструменты: TSan, Helgrind, GDB, логирование.
- Исправление: использовать mutex или атомики; подтвердить отсутствие гонок инструментами и стабильность результата $expected=T\times N$ во всех тестах.