Конкурентность

Введение

Основы конкурентности и когда она необходима на ООП интервью

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

На ООП интервью конкурентность встречается не всегда. Это зависит от компании, команды и вашего уровня. Но если вы проходите собеседование на уровень Senior и выше, вопросов про конкурентность вам не избежать.

Собеседования по ООП проектированию сфокусированы на одной программе. Под конкурентностью здесь подразумеваются потоки и общая память внутри одного процесса. На System Design интервью рассматривают конкурентность между различными процессами и компонентами - это уже другая тема. Если вы ищете информацию об этом, посмотрите нашу статью про Управление конкуренцией.

На собеседованиях конкурентность проявляется двумя способами. Иногда классическая задача ООП проектирования становится сложнее: парковка работала прекрасно, но теперь две машины соревнуются за одно место, или в системе управления инвентарем два заказа пытаются зарезервировать последний товар. В других случаях задача изначально строится вокруг конкурентности: пулы потоков, ограничители запросов (rate limiters), пулы соединений, планировщики. В обоих случаях интервьюер хочет увидеть, понимаете ли вы, что ломается, когда одновременно происходят несколько конкурирующих действий, и как исправить это без лишнего усложнения.

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

Основы конкурентности

Конкурентность начинается с базового факта: потоки в одном процессе используют общую память.

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

Конкурентность возникает всегда, когда несколько потоков могут работать независимо и их выполнение может пересекаться. На многоядерных процессорах потоки могут выполняться параллельно. На одном ядре операционная система быстро переключается между потоками и чередует их инструкции. С точки зрения программы оба случая идентичны: операции из разных потоков могут чередоваться непредсказуемым образом.

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

Большинство языков и сред выполнения по умолчанию работают в многопоточном мире. Java, C++, Go, Rust, C# и Python выполняют код конкурентно в реальных системах. Это значит, что конкурентность следует предполагать всегда, когда есть общее состояние.

JavaScript и TypeScript являются исключениями, поскольку пользовательский код выполняется в одном основном потоке, а конкурентность выражается через циклы событий (event loops) и асинхронные callback-функции, а не через потоки с общей памятью.

Инструменты

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

Атомарные операции (Atomics)

Атомарные операции, или атомики, обеспечивают потокобезопасные действия над отдельными переменными без использования блокировок. Под капотом они используют инструкции процессора, такие как compare-and-swap (CAS), которые выполняются за один непрерываемый шаг.

Атомарные операции

import threading

# Python - особый случай, потому что в нем нет встроенных атомарных переменных,
# поэтому для безопасного увеличения счетчиков из нескольких потоков нужны
# блокировки. Пример ниже показывает использование `threading.Lock` для защиты
# общего счетчика.

lock = threading.Lock()
counter = 0

with lock:
    counter += 1  # Protected increment (Python lacks native atomics)

Используйте атомарные операции для счетчиков или флагов. Они быстры, но ограничены одиночными переменными. Когда вам нужно атомарно обновить две переменные, атомики не помогут.

Используются в: Корректность для операций read-modify-write над одиночными переменными.

Блокировки (Locks / Mutexes)

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

Блокировки

import threading

lock = threading.Lock()

with lock:
    # Only one thread can be here at a time
    balance += amount

Блокировки - основной инструмент для защиты общего состояния. Главные варианты:

широкие (coarse-grained), то есть одна блокировка для всего
точечные (fine-grained), то есть блокировки для каждого ресурса
блокировки чтения-записи (read-write), где разрешены либо несколько читателей, либо один писатель.

Используются в: Корректность для операций check-then-act и обновлений нескольких полей.

Семафоры (Semaphores)

Семафоры - это счетные блокировки. Вместо бинарного состояния "заблокировано/разблокировано" семафор имеет N разрешений. Потоки получают разрешения перед продолжением и освобождают их по завершении. Когда количество разрешений достигает нуля, потоки блокируются до тех пор, пока кто-то их не освободит.

Семафоры

import threading

permits = threading.Semaphore(5)  # Allow 5 concurrent operations
permits.acquire()  # Block if no permits available
try:
    do_work()
finally:
    permits.release()  # Always release, even on exception

Используйте семафоры для ограничения конкурентных операций, например, когда у вас может быть не более 5 одновременных загрузок или не более 10 вызовов API.

Используются в: Дефицит ресурсов для ограничения количества конкурентных операций.

Условные переменные (Condition Variables)

Условные переменные позволяют потокам эффективно ждать, пока условие не станет истинным. Поток захватывает блокировку, проверяет условие и, если оно не выполняется, переходит в режим ожидания. При этом он атомарно освобождает блокировку и засыпает. Когда другой поток отправляет сигнал, ожидающие потоки просыпаются и проверяют условие заново.

Условные переменные

import threading

condition = threading.Condition()

with condition:
    while not ready:
        condition.wait()  # Release lock and sleep
    # Condition is now true

Условные переменные являются строительным блоком для блокирующих очередей. На собеседованиях вы редко будете использовать их напрямую.

Используются в: Координация как основа для блокирующих очередей.

Блокирующие очереди (Blocking Queues)

Блокирующие очереди объединяют очередь с условными переменными, чтобы обеспечить потокобезопасную передачу данных между производителем и потребителем. Производители вызывают put() для добавления элементов; если очередь полна, они блокируются. Потребители вызывают take() (или get()) для удаления элементов; если очередь пуста, они блокируются.

Блокирующие очереди

import queue

q = queue.Queue(maxsize=100)
q.put(task)   # Blocks if queue is full
t = q.get()   # Blocks if queue is empty

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

Используются в: Координация для паттерна производитель-потребитель и асинхронной обработки. Также в Дефицит ресурсов для пулов ресурсов.

Справочник по языкам

Вот краткий справочник по примитивам конкурентности в популярных языках.

Концепция	Java	Python	Go	C++	C#
Lock/Mutex	`synchronized` / `ReentrantLock`	`threading.Lock`	`sync.Mutex`	`std::mutex`	`lock` / `Monitor`
Read-write lock	`ReentrantReadWriteLock`	Нет (нужны сторонние библиотеки)	`sync.RWMutex`	`std::shared_mutex`	`ReaderWriterLockSlim`
Condition variable	`Object.wait` / `notify`	`threading.Condition`	`sync.Cond`	`std::condition_variable`	`Monitor.Wait` / `Pulse`
Semaphore	`Semaphore`	`threading.Semaphore`	`x/sync/semaphore`	`std::counting_semaphore`	`SemaphoreSlim`
Blocking queue	`LinkedBlockingQueue`	`queue.Queue`	buffered channel	реализовывается вручную	`BlockingCollection`
Atomic integer	`AtomicInteger`	Нет (используйте `Lock`)	`sync/atomic`	`std::atomic<int>`	`Interlocked`
Concurrent map	`ConcurrentHashMap`	Нет (из-за GIL)	`sync.Map`	`tbb::concurrent_hash_map`	`ConcurrentDictionary`

Примечания:

GIL (global interpreter lock) в Python означает, что код, привязанный к процессору, не получает преимуществ от использования потоков, а код, привязанный к вводу-выводу - получает. Для параллелизма используйте multiprocessing.
Каналы в Go заменяют блокирующие очереди и условные переменные. Если сомневаетесь, используйте канал.
В C++ часто требуется ручная реализация примитивов. Рассмотрите возможность использования Intel TBB для более высокоуровневых абстракций.

Три типа задач

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

Корректность (Correctness): проблемы возникают при повреждении общего состояния. Два потока проверяют доступность места, видят положительный ответ и оба его бронируют. Одно бронирование теряется.

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

Дефицит ресурсов (Scarcity): проблемы возникают из-за ограничения ресурсов. У вас есть 10 соединений с базой данных и 100 одновременных запросов. Некоторым запросам придется подождать.

Тип проблемы	Что ломается	Решения	Типичные задачи
Корректность	Общее состояние обновляется конкурентно	Блокировки, атомарные операции, ограничение состояния одним потоком	Check-then-act, read-modify-write
Координация	Потокам нужно упорядочивание или передача данных	Блокирующие очереди, акторы, event loops	Асинхронная обработка запросов, скачкообразный трафик
Дефицит ресурсов	Ресурсы ограничены	Семафоры, пулы ресурсов	Лимиты на конкурентные операции, потребление ресурсов, переиспользование объектов

Большинство вопросов начинаются с корректности. Координация и дефицит ресурсов часто появляются как follow-up вопросы, когда уже есть общее состояние или увеличивается пропускная способность. Реальные системы часто включают больше одной категории, но разделение помогает рассуждать о каждой проблеме отдельно.

Что дальше

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

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