Блокировка чтения-записи

В информатике читатели -писатели ( блокировка одиночной записи , ^[1] блокировка нескольких считывателей , ^[2] блокировка push , ^[3] или блокировка MRSW ) — это примитив синхронизации , который решает одну из проблем читатели-писатели . Блокировка RW обеспечивает одновременный доступ для операций только чтения, тогда как операции записи требуют исключительного доступа. Это означает, что несколько потоков могут читать данные параллельно, но для записи или изменения данных требуется исключительная блокировка . Когда писатель записывает данные, все другие писатели и читатели будут заблокированы до тех пор, пока писатель не закончит запись. Распространенным применением может быть управление доступом к структуре данных в памяти, которая не может быть обновлена атомарно и является недействительной (и не должна читаться другим потоком) до тех пор, пока обновление не будет завершено.

Блокировки чтения-записи обычно строятся на основе мьютексов и условных переменных или на основе семафоров .

Модернизируемый замок RW

Некоторые блокировки RW позволяют атомарно обновить блокировку с блокировки в режиме чтения до режима записи, а также понизить ее с режима записи до режима чтения. [1] Обновление блокировки с режима чтения до режима записи подвержено взаимоблокировкам, поскольку всякий раз, когда два потока, удерживающие блокировки чтения, пытаются обновиться до блокировок записи, создается взаимоблокировка, которую можно разорвать только одним из потоков, сняв свою блокировку чтения. Взаимоблокировки можно избежать, разрешив только одному потоку получить блокировку в «режиме чтения с намерением обновиться до записи», пока нет потоков в режиме записи и, возможно, ненулевых потоков в режиме чтения.

Приоритетные политики

Блокировки RW могут быть разработаны с различными политиками приоритета для доступа чтения и записи. Блокировка может быть разработана так, чтобы всегда отдавать приоритет читателям ( read-preferring ), всегда отдавать приоритет писателям ( write-preferring ) или быть неопределенной в отношении приоритета. Эти политики приводят к различным компромиссам в отношении параллелизма и голодания .

Блокировки RW с предпочтением чтения обеспечивают максимальный параллелизм, но могут привести к голоданию записи, если конкуренция высока. Это происходит потому, что потоки записи не смогут получить блокировку, пока ее удерживает хотя бы один поток чтения. Поскольку несколько потоков чтения могут удерживать блокировку одновременно, это означает, что поток записи может продолжать ждать блокировки, в то время как новые потоки чтения могут получить блокировку, даже до точки, когда писатель может все еще ждать после того, как все читатели, которые удерживали блокировку, когда он впервые попытался ее получить, сняли блокировку. Приоритет для читателей может быть слабым , как только что описано, или сильным , что означает, что всякий раз, когда писатель снимает блокировку, любые блокирующие читатели всегда получают ее следующими. ^[4]^{: 76}
Блокировки RW с предпочтением записи позволяют избежать проблемы нехватки записи, предотвращая получение блокировки любыми новыми читателями, если в очереди есть писатель, ожидающий блокировки; писатель получит блокировку, как только все читатели, которые уже удерживали блокировку, завершат работу. ^[5] Недостатком является то, что блокировки с предпочтением записи допускают меньшую параллельность при наличии потоков записи по сравнению с блокировками RW с предпочтением чтения. Кроме того, блокировка менее производительна, поскольку каждая операция, устанавливающая или снимающая блокировку для чтения или записи, является более сложной, внутренне требуя установки и снятия двух мьютексов вместо одного. ^{[ требуется ссылка ]} Этот вариант иногда также называют блокировкой чтения–записи с «предвзятостью записи». ^[6]
Неуказанный приоритет RW-блокировок не дает никаких гарантий относительно доступа чтения или записи. Неуказанный приоритет может быть предпочтительнее в некоторых ситуациях, если он позволяет более эффективную реализацию. ^{[ необходима цитата ]}

Выполнение

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

Использование двух мьютексов

Raynal демонстрирует, как реализовать блокировку чтения/записи с помощью двух мьютексов и одного целочисленного счетчика. Счетчик $b$ отслеживает количество блокирующихся читателей. Один мьютекс $r$ защищает $b$ и используется только читателями; другой $g$ (для «глобального») обеспечивает взаимное исключение писателей. Для этого требуется, чтобы мьютекс, полученный одним потоком, мог быть освобожден другим. Ниже приведен псевдокод для операций:

Инициализировать

Установите $b$ на $0$ .
$r$ разблокирован.
$g$ разблокирован.

Начать читать

Замок $р$ .
Приращение $б$ .
Если $b = 1$ , заблокировать $g$ .
Разблокировать $р$ .

Конец чтения

Замок $р$ .
Уменьшение $б$ .
Если $b = 0$ , разблокировать $g$ .
Разблокировать $р$ .

Начать писать

Блокировка $г.$

Конец записи

Разблокировать $г.$

Эта реализация является предпочтительной для чтения. ^[4]^{: 76}

Использование условной переменной и мьютекса

В качестве альтернативы блокировка RW может быть реализована в терминах условной переменной cond $,$ обычной (мьютексной) блокировки $g$ и различных счетчиков и флагов, описывающих потоки, которые в данный момент активны или ожидают. ^[7]^[8]^[9] Для блокировки RW с предпочтением записи можно использовать два целочисленных счетчика и один логический флаг:

$num_readers_active$ : количество читателей, получивших блокировку (целое число)
$num_writers_waiting$ : количество писателей, ожидающих доступа (целое число)
$writer_active$ : получил ли писатель блокировку (логическое значение).

Изначально $num_readers_active$ и $num_writers_waiting$ равны нулю, а $writer_active$ — false.

Операции блокировки и разблокировки могут быть реализованы следующим образом:

Начать читать

Блокировка $г$
Пока num_writers_waiting > 0 или writer_active :
- ожидание $cond$ , $g$ ^[a]
Увеличить $num_readers_active$
Разблокировать $г.$

Конец чтения

Блокировка $г$
Уменьшить $num_readers_active$
Если num_readers_active = 0 :
- Уведомить $условие$ (трансляция)
Разблокировать $г.$

Начать писать

Блокировка $г$
Увеличить $num_writers_waiting$
Пока num_readers_active > 0 или writer_active имеет значение true :
- ожидание усл $.$ , $г$
Уменьшить $num_writers_waiting$
Установите $writer_active$ в $значение true$
Разблокировать $г.$

Конец записи

Блокировка $г$
Установите $writer_active$ на $false$
Уведомить $условие$ (трансляция)
Разблокировать $г.$

Поддержка языков программирования

Стандарт POSIXpthread_rwlock_t и связанные с ним операции ^[10]
Интерфейс ReadWriteLock ^[11] и блокировки ReentrantReadWriteLock ^[6] в Java версии 5 или выше
Блокировка Microsoft System.Threading.ReaderWriterLockSlimдля C# и других языков .NET ^[12]
std::shared_mutexБлокировка чтения/записи в C++17 ^[13]
boost::shared_mutexи boost::upgrade_mutexблокировки в библиотеках Boost C++ ^[14]
SRWLock, добавлен в API операционной системы Windows , начиная с Windows Vista . ^[15]
sync.RWMutexв Го ^[16]
Фазовая справедливая блокировка чтения-записи, которая чередуется между читателями и писателями ^[17]
std::sync::RwLockБлокировка чтения/записи в Rust ^[18]
Poco::RWLock в библиотеках POCO C++
mse::recursive_shared_timed_mutexв библиотеке SaferCPlusPlus есть версия std::shared_timed_mutex, которая поддерживает семантику рекурсивного владения std::recursive_mutex.
txrwlock.ReadersWriterDeferredLockБлокировка чтения/записи для Twisted ^[19]
rw_semaphoreв ядре Linux ^[20]

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

Алгоритм чтения-копирования-обновления (RCU) является одним из решений проблемы читателей-писателей. RCU не требует ожидания для читателей. Ядро Linux реализует специальное решение для нескольких писателей, называемое seqlock .

Смотрите также

Примечания

^ Это стандартная операция «ожидания» над условными переменными, которая, среди прочих действий, освобождает мьютекс $g$ .

Ссылки

^ Гамильтон, Дуг (21 апреля 1995 г.). «Предложения по блокировке нескольких читателей/одного писателя?». Группа новостей : comp.os.ms-windows.nt.misc. Usenet: [email protected] . Получено 8 октября 2010 г.
^ «Практическая свобода от блокировки» Кейра Фрейзера 2004 г.
^ "Push Locks – What are they?". Блог Ntdebugging . Блоги MSDN. 2 сентября 2009 г. Получено 11 мая 2017 г.
^ ab Raynal, Michel (2012). Параллельное программирование: алгоритмы, принципы и основы . Springer.
^ Стивенс, В. Ричард ; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX . Addison-Wesley. стр. 409.
^ ab java.util.concurrent.locks.ReentrantReadWriteLockРеализация блокировки чтения-записи Java предлагает «справедливый» режим
^ Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования . Elsevier. С. 184–185.
^ Николс, Брэдфорд; Баттлар, Дик; Фаррелл, Жаклин (1996). Программирование PThreads: стандарт POSIX для лучшей многопроцессорной обработки . O'Reilly. стр. 84–89. ISBN 9781565921153.
^ Бутенхоф, Дэвид Р. (1997). Программирование с потоками POSIX . Addison-Wesley. С. 253–266.
^ "The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy". IEEE и The Open Group . Получено 14 мая 2011 г.
^ java.util.concurrent.locks.ReadWriteLock
^ "ReaderWriteLockSlim Class (System.Threading)". Microsoft Corporation . Получено 14 мая 2011 г.
^ "Новая принятая статья: N3659, Shared Locking in C++ — Howard Hinnant, Detlef Vollmann, Hans Boehm". Standard C++ Foundation.
^ Энтони Уильямс. "Synchronization – Boost 1.52.0" . Получено 31 января 2012 г.
^ Алессандрини, Виктор (2015). Программирование приложений с общей памятью: концепции и стратегии в программировании многоядерных приложений . Морган Кауфманн.
^ "Язык программирования Go – Синхронизация пакетов" . Получено 30 мая 2015 г.
^ «Синхронизация чтения–записи для многопроцессорных систем реального времени с общей памятью» (PDF) .
^ "std::sync::RwLock – Rust" . Получено 26 октября 2019 г. .
^ "Блокировка чтения/записи для Twisted". GitHub . Получено 28 сентября 2016 г.
^ "Примитивы синхронизации в ядре Linux: семафоры чтения/записи". Linux Insides . Получено 8 июня 2023 г.