Блокировка с чтением-записью¶

Блокировка с чтением-записью (англ. readers–writer lock, shared-exclusive lock) — механизм синхронизации доступа к разделяемому ресурсу в многопоточном программировании, позволяющий одновременно нескольким потокам читать данные, но предоставляющий исключительный доступ только одному потоку при записи. Этот тип блокировки повышает производительность в сценариях, где операции чтения значительно преобладают над операциями записи.

¶История

Концепция блокировки с разделением на чтение и запись возникла как развитие простых мьютексов (mutex), которые обеспечивают исключительный доступ к ресурсу для любого потока. В 1970-х годах, с ростом популярности многопоточных систем и баз данных, стала очевидна необходимость в более гибких механизмах синхронизации. Первые реализации появились в операционных системах и системах управления базами данных (СУБД). В 1980-х годах алгоритмы блокировки с чтением-записью были формализованы в научной литературе, в частности в работах по параллельным вычислениям. В современных языках программирования (C++, Java, Python) и операционных системах (Linux, Windows) существуют встроенные или библиотечные реализации этого механизма.

¶Принцип работы

Блокировка с чтением-записью управляет двумя типами доступа:

• Блокировка чтения (shared lock): может быть захвачена несколькими потоками одновременно. Пока хотя бы один поток удерживает блокировку чтения, ни один другой поток не может захватить блокировку записи.
• Блокировка записи (exclusive lock): может быть захвачена только одним потоком, и только если ни один другой поток не удерживает ни блокировку чтения, ни блокировку записи.

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

¶Условия корректности

Корректная реализация должна гарантировать:

• Взаимное исключение для записи: только один поток может писать в любой момент времени.
• Отсутствие гонок данных: чтение и запись не могут выполняться одновременно.
• Отсутствие взаимоблокировок (deadlock): система должна предотвращать ситуации, когда потоки вечно ждут друг друга.
• Справедливость (fairness): в некоторых реализациях предотвращается «голодание» писателей, когда непрерывный поток читателей может бесконечно откладывать запись.

¶Реализации

¶В языках программирования

• C++: В стандарте C++17 появился std::shared_mutex (доступен в заголовочном файле <shared_mutex>). В более ранних версиях использовались boost::shared_mutex.
• Java: Класс ReentrantReadWriteLock из пакета java.util.concurrent.locks поддерживает повторный захват блокировок одним потоком.
• Python: В модуле threading нет встроенной блокировки с чтением-записью, но её можно реализовать с помощью threading.Lock и threading.Condition или использовать сторонние библиотеки (например, readerwriterlock).
• C#: В .NET Framework класс ReaderWriterLockSlim предоставляет функциональность блокировки с чтением-записью с оптимизацией производительности.

¶В операционных системах

• Linux: В ядре Linux используется rwlock_t (read-write lock) для синхронизации доступа к разделяемым данным между процессорами.
• Windows: В Windows API доступны функции InitializeSRWLock, AcquireSRWLockShared, AcquireSRWLockExclusive и др.

¶Классификация

¶По приоритету

• Блокировки с предпочтением читателей (readers-priority): читатели не ждут, если блокировка записи не захвачена. Это может привести к «голоданию» писателей.
• Блокировки с предпочтением писателей (writers-priority): при наличии ожидающих писателей новые читатели блокируются, что предотвращает голодание писателей, но может снизить параллелизм чтения.
• Сбалансированные блокировки: используют очереди для обеспечения чередования доступа.

¶По реентерабельности

• Реентерабельные (reentrant): один и тот же поток может повторно захватить блокировку, которую он уже удерживает. Например, ReentrantReadWriteLock в Java.
• Нереентерабельные: повторный захват приводит к взаимоблокировке.

¶Применение

¶Базы данных

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

¶Файловые системы

Операционные системы применяют блокировки с чтением-записью для синхронизации доступа к файлам. Например, системный вызов flock() в Linux поддерживает блокировки чтения (LOCK_SH) и записи (LOCK_EX).

¶Кэширование

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

¶Параллельные алгоритмы

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

¶Преимущества и недостатки

¶Преимущества

• Повышение производительности в системах с преобладанием чтения (например, 80% операций чтения, 20% записи).
• Снижение конкуренции за ресурс по сравнению с простыми мьютексами.
• Гибкость в управлении приоритетами.

¶Недостатки

• Сложность реализации и отладки, особенно при необходимости обеспечения справедливости.
• Накладные расходы на управление счётчиками и очередями, которые могут быть выше, чем у мьютекса, при малом числе потоков.
• Риск «голодания» писателей или читателей при неправильной политике приоритетов.
• Неэффективность при высокой частоте записи, когда блокировка записи становится узким местом.

¶Альтернативы

• Мьютекс (mutex): простейший механизм, обеспечивающий исключительный доступ, но не допускающий параллельного чтения.
• Семафор (semaphore): позволяет ограничить количество одновременных читателей, но не различает чтение и запись.
• Блокировка без ожидания (lock-free): использует атомарные операции для синхронизации без блокировок, что может быть эффективнее, но сложнее в реализации.
• Транзакционная память (transactional memory): позволяет выполнять операции над разделяемыми данными в изолированных транзакциях, автоматически разрешая конфликты.

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

• В ядре Linux блокировки с чтением-записью используются для защиты списков процессов и таблиц страниц памяти.
• В некоторых реализациях (например, в pthread_rwlock_t в POSIX) можно задать атрибуты, определяющие поведение при повторном захвате и приоритете.
• Алгоритм блокировки с чтением-записью может быть реализован с помощью аппаратной поддержки, например, с использованием инструкций CAS (compare-and-swap) на процессорах x86.

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы» (4-е издание). — СПб.: Питер, 2015.
• Херлихи М., Шавит Н. «Искусство многопроцессорного программирования». — М.: ДМК Пресс, 2012.
• Документация Oracle Java: «ReentrantReadWriteLock».
• Стандарт C++17: раздел 33.4.3 «Shared mutexes».
• Linux man pages: pthread_rwlock_init, flock.