Конкурентный доступ

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

История

Проблема конкурентного доступа возникла одновременно с появлением первых многопользовательских и многозадачных вычислительных систем в 1960-х годах. В ранних мейнфреймах, таких как IBM System/360, несколько терминалов и процессов могли одновременно обращаться к центральному процессору и памяти. Для предотвращения взаимных помех и потери данных были разработаны первые механизмы синхронизации, такие как семафоры (предложены Эдсгером Дейкстрой в 1965 году) и мьютексы.

В области телекоммуникаций проблема конкурентного доступа стала особенно актуальной с развитием сетей с общей средой передачи данных, таких как Ethernet. Первая версия Ethernet, разработанная в Xerox PARC в 1973 году, использовала метод CSMA/CD (Carrier Sense Multiple Access with Collision Detection), который позволял нескольким станциям конкурировать за доступ к общему коаксиальному кабелю. Этот метод стал основой для стандарта IEEE 802.3, принятого в 1983 году.

В 1980-х и 1990-х годах, с распространением персональных компьютеров и локальных сетей, конкурентный доступ стал стандартной практикой. Развитие беспроводных сетей (Wi-Fi, стандарт IEEE 802.11) привело к созданию новых методов, таких как CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance), которые учитывают особенности радиоканала.

Основные принципы

Конкурентный доступ основан на нескольких ключевых принципах:

Разделение ресурса: Несколько участников (узлов, процессов, потоков) имеют потенциальный доступ к одному и тому же ресурсу.
Конкуренция: Участники одновременно пытаются получить доступ, что приводит к конфликтам (коллизиям).
Арбитраж: Механизм, который разрешает конфликты, определяя, какой участник получит доступ в данный момент.
Синхронизация: Процессы, обеспечивающие согласованность состояний и предотвращающие состояния гонки (race conditions).

Классификация методов конкурентного доступа

Методы конкурентного доступа можно классифицировать по различным признакам.

По способу разрешения коллизий

Методы с обнаружением коллизий (Collision Detection, CD): Участники начинают передачу, когда канал свободен, и при обнаружении коллизии (одновременной передачи) прекращают её и повторяют попытку через случайный интервал времени. Пример: CSMA/CD в Ethernet.
Методы с предотвращением коллизий (Collision Avoidance, CA): Участники перед началом передачи прослушивают канал и, если он занят, ждут. Для уменьшения вероятности коллизий используются механизмы резервирования или случайные задержки. Пример: CSMA/CA в Wi-Fi.
Методы с разрешением коллизий (Collision Resolution): При возникновении коллизии используется специальный алгоритм (например, бинарный экспоненциальный backoff) для последовательного разрешения конфликта.

По централизации управления

Централизованные методы: Существует единый арбитр (контроллер, сервер), который решает, кто получит доступ. Примеры: запрос-ответ (polling), маркерный доступ (token passing).
Децентрализованные (распределённые) методы: Каждый участник самостоятельно принимает решение о доступе на основе информации о состоянии канала. Примеры: CSMA/CD, CSMA/CA.

По типу доступа к среде передачи

Случайный доступ (Random Access): Участники могут начать передачу в любой момент, что приводит к коллизиям. Примеры: ALOHA, CSMA.
Управляемый доступ (Controlled Access): Доступ строго регламентирован, коллизии исключены. Примеры: маркерный доступ (Token Ring, FDDI), опрос (polling).

Применение в различных областях

Компьютерные сети

Ethernet (IEEE 802.3): Использует CSMA/CD. В современных сетях Ethernet (на витой паре с коммутаторами) коллизии практически отсутствуют, так как коммутаторы изолируют коллизионные домены.
Wi-Fi (IEEE 802.11): Использует CSMA/CA. Из-за особенностей радиоканала (скрытый узел, замирания) обнаружение коллизий затруднено, поэтому применяется предотвращение.
Bluetooth: Использует централизованный метод с опросом (polling) ведущим устройством ведомых.

Операционные системы

Мьютексы (Mutex): Блокировка, позволяющая только одному потоку получить доступ к критической секции.
Семафоры (Semaphore): Счётчик, позволяющий ограничить количество потоков, одновременно работающих с ресурсом.
Мониторы (Monitor): Высокоуровневый механизм синхронизации, объединяющий мьютекс и условные переменные.
Спин-блокировки (Spinlock): Поток активно ожидает (циклически проверяет) освобождения блокировки, не переходя в состояние сна.

Многопроцессорные системы

Аппаратные блокировки: Специальные инструкции процессора (например, test-and-set, compare-and-swap, load-link/store-conditional), которые обеспечивают атомарное выполнение операций.
Кэш-когерентность: Протоколы (например, MESI, MOESI), обеспечивающие согласованность данных в кэшах разных процессоров при конкурентном доступе к общей памяти.

Базы данных

Блокировки (Locks): Разделяют доступ на чтение (shared lock) и запись (exclusive lock).
MVCC (Multi-Version Concurrency Control): Каждая транзакция видит снимок данных на момент её начала, что позволяет избежать блокировок при чтении.
Оптимистическая блокировка (Optimistic Locking): Предполагает, что конфликты редки, и проверяет их только на этапе фиксации транзакции.

Проблемы и недостатки

Конкурентный доступ сопряжён с рядом фундаментальных проблем:

Состояние гонки (Race Condition): Результат работы зависит от порядка выполнения потоков, что может приводить к непредсказуемым ошибкам.
Взаимная блокировка (Deadlock): Два или более потоков ждут освобождения ресурсов, удерживаемых друг другом, и ни один не может продолжить выполнение.
Голодание (Starvation): Один или несколько потоков не могут получить доступ к ресурсу, так как он постоянно предоставляется другим.
Инверсия приоритетов (Priority Inversion): Низкоприоритетный поток удерживает блокировку, необходимую высокоприоритетному, что приводит к снижению производительности.
Снижение производительности: Накладные расходы на синхронизацию (блокировки, переключение контекста) могут снижать общую пропускную способность системы.

Примеры реализации

CSMA/CD (Ethernet): Узел прослушивает канал. Если канал свободен, начинает передачу. Если во время передачи обнаруживает коллизию (по уровню сигнала), немедленно прекращает её и отправляет jam-сигнал. Затем ждёт случайное время (backoff) и повторяет попытку.
Маркерный доступ (Token Ring): Специальный кадр (маркер) циркулирует по кольцу. Узел может начать передачу только после получения маркера. После передачи он освобождает маркер.
Мьютекс (POSIX Threads): pthread_mutex_lock(&mutex); — поток блокируется, если мьютекс уже занят. pthread_mutex_unlock(&mutex); — освобождает мьютекс.
Семафор (System V): semop(semid, &sembuf, 1); — атомарно уменьшает значение семафора (если оно > 0) или блокирует поток.

Критика

Конкурентный доступ, особенно в программном обеспечении, часто критикуется за сложность и подверженность ошибкам. Состояния гонки и взаимные блокировки являются одними из самых трудно воспроизводимых и отлаживаемых дефектов. Альтернативой конкурентному доступу является использование моделей, исключающих разделяемые состояния, таких как акторная модель (Erlang, Akka) или модель передачи сообщений (Go, Rust). В аппаратуре конкурентный доступ может приводить к недетерминированному поведению, что критично для систем реального времени.

Интересные факты

Алгоритм бинарного экспоненциального backoff, используемый в Ethernet, был разработан Робертом Меткалфом и Дэвидом Боггсом в 1973 году.
Термин «семафор» был введён Эдсгером Дейкстрой в 1965 году, который позаимствовал его из железнодорожной сигнализации.
В ранних версиях Ethernet (10BASE5) максимальная длина сегмента составляла 500 метров, а минимальное расстояние между узлами — 2,5 метра, что было связано с требованиями CSMA/CD.
Протокол MESI (Modified, Exclusive, Shared, Invalid) является одним из самых распространённых протоколов когерентности кэша в x86-совместимых процессорах.

Источники

Таненбаум Э., Уэзеролл Д. «Компьютерные сети». — 5-е изд. — СПб.: Питер, 2012.
Таненбаум Э., Бос Х. «Современные операционные системы». — 4-е изд. — СПб.: Питер, 2015.
Дейкстра Э. «Семафоры, управляющие доступом к критическим секциям» (1965).
Меткалф Р., Боггс Д. «Ethernet: Distributed Packet Switching for Local Computer Networks» (1976).
Стандарт IEEE 802.3-2018.
Стандарт IEEE 802.11-2020.
Сильбершац А., Гальвин П., Ганье Г. «Основы операционных систем». — 9-е изд. — М.: Вильямс, 2013.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →