Коротко: два потока по $1000$ инкрементов ожидаемо дают $2000$, но без синхронизации из‑за гонок итог может быть меньше. Ниже — причины, конкретные interleavings и способы фикса с обсуждением накладных расходов и поведения на многопроцессорной системе.
Что делает инкремент (атомарно не защищённый):
- логические шаги: R = чтение counter; R = R + 1; W = запись обратно.
- ожид. результат после двух независимых инкрементов от $0$: $2$.
Примеры интерливингов, приводящих к неверному результату
1) Потерянный апдейт (lost update), нач. $counter=0$ - A: R($0$)
- B: R($0$)
- A: W($1$)
- B: W($1$)
Итог: $1$ вместо $2$.
2) Другой вариант (частичные наложения), нач. $counter=0$ - A: R($0$)
- A: R+1 -> tmp=$1$
- B: R($0$)
- B: R+1 -> tmp=$1$
- B: W($1$)
- A: W($1$)
Итог: $1$ вместо $2$. Повторение таких конфликтов при $1000$ итерациях может дать итог << $2000$.
3) Суммарно: если N конфликтов — итог будет $2000-$ число потерянных инкрементов.
Способы фикса и их поведение/накладные расходы
1) Мьютекс (блокировка)
- Как: lock(); counter++; unlock();
- Плюсы: простая корректность (демонстративно исключает гонки).
- Минусы: при высокой конкуренции — переходы в ядро, контекст‑свичи, ожидание, очереди; на многопроцессоре — стоимость передачи права блокировки и разрушение локальности. Подходит при низкой частоте доступа к счётчику или когда нужна простая защита сложных критических секций.
2) Атомарные операции (hardware atomic, e.g. fetch_add / LOCK XADD)
- Как: atomic_fetch_add(&counter, 1) или counter.fetch_add(1).
- Плюсы: обычно быстрее мьютекса, не требует перехода в ядро; реализуется одной CPU-инструкцией.
- Минусы: на многопроцессоре всё равно сериализация на уровне кэш‑линии: строка кэша владеет один процессор, операция приводит к «ping‑pong» и высокой задержке при сильном контенте; возможны спин‑латентности; порядок памяти зависит от используемых memory_order (для простого счётчика можно использовать relaxed). Хорош для средней нагрузки, когда нужна простая корректность и минимальная задержка.
3) CAS‑loop (compare-and-swap) — lock‑free
- Как: do { old = counter; new = old+1 } while(!CAS(&counter, old, new));
- Плюсы: не блокирует поток; подходит в lock‑free структурах.
- Минусы: при высокой конкуренции много неудачных попыток (retry), увеличенная нагрузка на шину/кохеренцию; сложнее доказывать корректность при сложных структурах. Для простого счётчика чаще используют fetch_add, который эффективнее.
4) Шардирование / per‑thread (локальные счётчики + периодическая агрегация)
- Как: каждый поток/ядро держит локальный счетчик (неатомарно), периодически (или в конце) суммируются в глобальный, или локальные периодически сбрасываются с atomic добавлением пачки.
- Плюсы: минимизация кэшного трафика и высокая масштабируемость; подходит для частых инкрементов, когда точный глобальный счёт не нужен в каждый момент.
- Минусы: сложнее обеспечить строгую моментальную видимость; нужно добавочная память и логика агрегации; возможна потеря точности при краше, если не учтены локальные буферы.
5) Комбайнеры / batching / software combining
- Как: поток кладёт запрос в очередь/буфер, один поток (combiner) применяет все накопленные изменения к глобальному счётчику.
- Плюсы: уменьшает число глобальных модификаций; хорошо масштабируется.
- Минусы: задержка (latency) для отдельных инкрементов; сложность реализации.
Практическое поведение на многопроцессорной системе (кратко)
- Атомики и CAS приводят к постоянной передаче права владения кэш‑линии между ядрами (cache line bouncing) — это основная причина торможения при высокой частоте обновлений одного места.
- Мьютексы при контеншене могут переводить потоки в спящий режим и вызывать планировщик ОС — большие задержки, но уменьшение потребления CPU при ожидании.
- Перешардирование (per‑core) минимизирует кэш‑трафик и обычно даёт наилучшую масштабируемость для «горячих» счётчиков.
Рекомендации
- Низкая частота/простота: мьютекс — OK.
- Высокая частота инкрементов и нужна атомарная точность: atomic_fetch_add (с соответствующим memory_order) или sharded counters с периодическим объединением.
- Очень высокая нагрузка и требование масштаба: sharding/combining или специализированные lock‑free структуры.
Если нужно — могу показать пример кода (mutex/atomic/sharded) на языке по выбору.