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

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

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

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

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

Приоритетная политика

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

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

Выполнение

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

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

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

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

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

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

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

Завершить чтение

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

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

Замок $г.$

Конец записи

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

Эта реализация предпочитает чтение. ^[4]^: 76

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

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

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

Первоначально $num_readers_active$ и $num_writers_waiting$ равны нулю, а $write_active$ имеет значение false.

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

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

Замок $г$
Пока num_writers_waiting > 0 или write_active :
- ожидания $условия$ , $г$ ^[а]
Увеличение $num_readers_active$
Разблокировать $г.$

Завершить чтение

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

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

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

Конец записи

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

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

POSIX стандарт pthread_rwlock_t и связанные с ними операции ^[10]
ЧтениеЗаписьБлокировка ^[11] интерфейс и ReentrantReadWriteLock ^[6] блокировки в Java версии 5 или выше
Майкрософт 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: [электронная почта защищена] . Проверено 8 октября 2010 г.
^ «Практическая свобода блокировки» Кейра Фрейзера, 2004 г.
^ «Нажимные замки – что это такое?» . Блог Ntdebugging . Блоги MSDN. 2 сентября 2009 года . Проверено 11 мая 2017 г.
^ Перейти обратно: ^а ^б Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Спрингер.
^ Стивенс, В. Ричард ; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX . Аддисон-Уэсли. п. 409.
^ Перейти обратно: ^а ^б java.util.concurrent.locks.ReentrantReadWriteLock Реализация блокировки чтения и записи Java предлагает «честный» режим.
^ Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования . Эльзевир. стр. 184–185.
^ Николс, Брэдфорд; Баттлар, Дик; Фаррелл, Жаклин (1996). Программирование PThreads: стандарт POSIX для лучшей многопроцессорной обработки . О'Рейли. стр. 84–89 . ISBN 9781565921153 .
^ Бутенхоф, Дэвид Р. (1997). Программирование с использованием потоков POSIX . Аддисон-Уэсли. стр. 253–266.
^ «Базовые спецификации открытой группы, выпуск 6, IEEE Std 1003.1, издание 2004 г.: pthread_rwlock_destroy» . IEEE и Открытая группа . Проверено 14 мая 2011 г.
^ java.util.concurrent.locks.ReadWriteLock
^ «Класс ReaderWriteLockSlim (System.Threading)» . Корпорация Майкрософт . Проверено 14 мая 2011 г.
^ «Новый принятый документ: N3659, Совместная блокировка в C++ — Говард Хиннант, Детлеф Фоллманн, Ханс Бём» . Стандартная основа C++.
^ Энтони Уильямс. «Синхронизация — Boost 1.52.0» . Проверено 31 января 2012 г.
^ Алессандрини, Виктор (2015). Программирование приложений с общей памятью: концепции и стратегии программирования многоядерных приложений . Морган Кауфманн.
^ «Язык программирования Go – синхронизация пакетов» . Проверено 30 мая 2015 г.
^ «Синхронизация чтения и записи для многопроцессорных систем реального времени с общей памятью» (PDF) .
^ "std::sync::RwLock — Rust" . Проверено 26 октября 2019 г.
^ «Блокировка чтения/записи для Twisted» . Гитхаб . Проверено 28 сентября 2016 г.
^ «Примитивы синхронизации в ядре Linux: семафоры чтения/записи» . Линукс изнутри . Проверено 8 июня 2023 г.

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

[Hamilton-1] Гамильтон, Дуг (21 апреля 1995 г.). «Предложения по блокировке с несколькими устройствами чтения и одной записи?» . Группа новостей : comp.os.ms-windows.nt.misc . Usenet: [электронная почта защищена] . Проверено 8 октября 2010 г.

[2] «Практическая свобода блокировки» Кейра Фрейзера, 2004 г.

[3] «Нажимные замки – что это такое?» . Блог Ntdebugging . Блоги MSDN. 2 сентября 2009 года . Проверено 11 мая 2017 г.

[raynal-4] Перейти обратно: ^а ^б Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы . Спрингер.

[5] Стивенс, В. Ричард ; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX . Аддисон-Уэсли. п. 409.

[reentrantRW-6] Перейти обратно: ^а ^б java.util.concurrent.locks.ReentrantReadWriteLock Реализация блокировки чтения и записи Java предлагает «честный» режим.

[herlihy-7] Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования . Эльзевир. стр. 184–185.

[pthreads-8] Николс, Брэдфорд; Баттлар, Дик; Фаррелл, Жаклин (1996). Программирование PThreads: стандарт POSIX для лучшей многопроцессорной обработки . О'Рейли. стр. 84–89 . ISBN 9781565921153 .

[butenhof-9] Бутенхоф, Дэвид Р. (1997). Программирование с использованием потоков POSIX . Аддисон-Уэсли. стр. 253–266.

[11] «Базовые спецификации открытой группы, выпуск 6, IEEE Std 1003.1, издание 2004 г.: pthread_rwlock_destroy» . IEEE и Открытая группа . Проверено 14 мая 2011 г.

[12] java.util.concurrent.locks.ReadWriteLock

[13] «Класс ReaderWriteLockSlim (System.Threading)» . Корпорация Майкрософт . Проверено 14 мая 2011 г.

[14] «Новый принятый документ: N3659, Совместная блокировка в C++ — Говард Хиннант, Детлеф Фоллманн, Ханс Бём» . Стандартная основа C++.

[15] Энтони Уильямс. «Синхронизация — Boost 1.52.0» . Проверено 31 января 2012 г.

[16] Алессандрини, Виктор (2015). Программирование приложений с общей памятью: концепции и стратегии программирования многоядерных приложений . Морган Кауфманн.

[17] «Язык программирования Go – синхронизация пакетов» . Проверено 30 мая 2015 г.

[18] «Синхронизация чтения и записи для многопроцессорных систем реального времени с общей памятью» (PDF) .

[19] "std::sync::RwLock — Rust" . Проверено 26 октября 2019 г.

[20] «Блокировка чтения/записи для Twisted» . Гитхаб . Проверено 28 сентября 2016 г.

[21] «Примитивы синхронизации в ядре Linux: семафоры чтения/записи» . Линукс изнутри . Проверено 8 июня 2023 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[а]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]