Блокировка чтения-писателя - Readers–writer lock

О психологических трудностях, с которыми иногда сталкиваются писатели, см. блок писателя.

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

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

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

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

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

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

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

Выполнение

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

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

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

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

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

Конец чтения

  • Замок р.
  • Декремент б.
  • Если б = 0, разблокировать грамм.
  • Разблокировать р.

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

  • Замок грамм.

Конец записи

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

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

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

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

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

Первоначально num_readers_active и num_writers_waiting равны нулю и writer_active ложно.

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

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

  • Замок грамм
  • Пока num_writers_waiting > 0 или же writer_active:
    • ждать cond, грамм[а]
  • Инкремент num_readers_active
  • Разблокировать грамм.

Конец чтения

  • Замок грамм
  • Декремент num_readers_active
  • Если num_readers_active = 0:
    • Уведомлять cond (транслировать)
  • Разблокировать грамм.

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

  • Замок грамм
  • Инкремент num_writers_waiting
  • Пока num_readers_active > 0 или же writer_active является истинный:
    • ждать cond, грамм
  • Декремент num_writers_waiting
  • Набор writer_active к истинный
  • Разблокировать грамм.

Конец записи

  • Замок грамм
  • Набор writer_active к ложный
  • Уведомлять cond (транслировать)
  • Разблокировать грамм.

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

  • POSIX стандарт pthread_rwlock_t и сопутствующие операции[10]
  • ReadWriteLock[11] интерфейс и ReentrantReadWriteLock[6] замки в Ява версия 5 или выше
  • Microsoft System.Threading.ReaderWriterLockSlim замок для C # и другие .СЕТЬ языки[12]
  • std :: shared_mutex чтение / запись блокировки C ++ 17[13]
  • boost :: shared_mutex и boost :: upgrade_mutex замки в Библиотеки Boost C ++[14]
  • SRWLock, добавлен в Windows API операционной системы по состоянию на Виндоус виста.[15]
  • sync.RWMutex в Идти[16]
  • Фазовая справедливая блокировка читателя-писателя, которая переключается между читателями и писателями.[17]
  • std :: sync :: RwLock чтение / запись блокировки Ржавчина[18]
  • Poco :: RWLock in Библиотеки POCO C ++
  • mse :: recursive_shared_timed_mutex в SaferCPlusPlus библиотека - это версия std :: shared_timed_mutex который поддерживает семантику рекурсивного владения std :: recursive_mutex.
  • txrwlock.ReadersWriterDeferredLock Блокировка чтения / записи для Скрученный[19]

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

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

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

Примечания

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

Рекомендации

  1. ^ Гамильтон, Дуг (21 апреля 1995 г.). "Предложения для блокировки нескольких читателей / одного писателя?". Группа новостей: comp.os.ms-windows.nt.misc. Usenet:  [email protected]. Получено 8 октября 2010.
  2. ^ «Практическая свобода от замков» Кейр Фрейзер, 2004 г.
  3. ^ "Push Locks - какие они?". Блог Ntdebugging. Блоги MSDN. 2 сентября 2009 г.. Получено 11 мая 2017.
  4. ^ а б Рейналь, Мишель (2012). Параллельное программирование: алгоритмы, принципы и основы. Springer.
  5. ^ Стивенс, В. Ричард; Раго, Стивен А. (2013). Расширенное программирование в среде UNIX. Эддисон-Уэсли. п. 409.
  6. ^ а б java.util.concurrent.locks.ReentrantReadWriteLock Реализация блокировки чтения и записи Java предлагает "справедливый" режим
  7. ^ Херлихи, Морис; Шавит, Нир (2012). Искусство многопроцессорного программирования. Эльзевир. С. 184–185.
  8. ^ Николс, Брэдфорд; Батлар, Дик; Фаррелл, Жаклин (1996). Программирование PThreads: стандарт POSIX для лучшей многопроцессорности. О'Рейли. стр.84–89.
  9. ^ Бутенхоф, Дэвид Р. (1997). Программирование с использованием потоков POSIX. Эддисон-Уэсли. С. 253–266.
  10. ^ "Базовые спецификации Open Group, выпуск 6, IEEE Std 1003.1, издание 2004 г .: pthread_rwlock_destroy". IEEE и открытая группа. Получено 14 мая 2011.
  11. ^ java.util.concurrent.locks.ReadWriteLock
  12. ^ "Класс ReaderWriteLockSlim (System.Threading)". Корпорация Майкрософт. Получено 14 мая 2011.
  13. ^ «Новая принятая статья: N3659, Совместное блокирование в C ++ - Ховард Хиннант, Детлеф Фоллманн, Ганс Бём». Стандартный C ++ Foundation.
  14. ^ Энтони Уильямс. «Синхронизация - Boost 1.52.0». Получено 31 января 2012.
  15. ^ Алессандрини, Виктор (2015). Программирование приложений с общей памятью: концепции и стратегии программирования многоядерных приложений. Морган Кауфманн.
  16. ^ «Язык программирования Go - Синхронизация пакетов». Получено 30 мая 2015.
  17. ^ «Синхронизация устройства чтения и записи для многопроцессорных систем реального времени с общей памятью» (PDF).
  18. ^ "std :: sync :: RwLock - Rust". Получено 26 октября 2019.
  19. ^ «Блокировка чтения / записи для Twisted». Получено 28 сентября 2016.