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

Блокировка чтения-записи — механизм синхронизации, разрешающий одновременное общее чтение некоторых разделяемых данных либо их эксклюзивное изменение, разграничивая таким образом блокировки на чтение и на запись между собой^[1]. Механизм призван решить классическую задачу о читателях-писателях, в которой некоторый объект одновременно читается и пишется конкурентными задачами^[2].

В отличие от мьютексов блокировки чтения-записи отдельно учитывают чтение данных и отдельно — запись, разрешая обращение к данным, если они в это время не изменяются. Мьютексы же допускают только эксклюзивный доступ к данным^[1]. Однако встречаются разделяемые мьютексы, предоставляющие помимо эксклюзивной блокировки общую, позволяющую совместно владеть мьютексом, если нет эксклюзивного владельца^[3]. По своей сути разделяемые мьютексы являются блокировками чтения-записи, но именуются мьютексами.

В общем случае блокировки чтения-записи решают ту же задачу, что и мьютексы, и могут быть ими заменены, причиной же появления механизма блокировок чтения-записи является повышение эффективности взаимного исключения при раздельном чтении и записи^[4]. Блокировки чтения-записи являются более предпочтительными, чем мьютексы, в случаях, когда обращения к данным происходят намного чаще, чем их запись. В этом случае читающие задачи не будут блокироваться большую части времени, лишь иногда блокируясь при изменениях объекта. Приоритет между пишущими и читающими задачами часто отдаётся пишущим задачам, чтобы избежать ресурсного голодания пишущих задач^[1].

Задача о читателях-писателяхПравить

Проблема читателей и писателей возникает в любой ситуации, когда требуется одновременное чтение и изменение структуры данных, файловой системы или базы данных конкурентными задачами. Чтение неизменных данных может осуществляться одновременно множеством задач, однако если в это время будет происходить изменение данных, параллельное их чтение может привести к получению частично изменённых данных, то есть испорченных^[2].

Решение задачи является асимметричным и предполагает разделение блокировки на чтение и на запись. Изменение данных допускается лишь эксклюзивное, то есть только одна задача может единовременно захватывать блокировку на запись, если только не захвачена блокировка на чтение. Чтение данных может осуществляться многими задачами, поэтому блокировку на чтение могут захватить одновременно сколько угодно задач, если только не захвачена блокировка на запись. То есть критические секции записи и чтения не могут исполняться параллельно, но критические секции чтения — могут^[2].

Алгоритмы реализацииПравить

Самым простым алгоритмом реализации на семафорах и мьютексах является использование выключателя бинарного семафора. Запись должна защищаться данным семафором. Первая читающая задача должна захватывать семафор с помощью выключателя, блокируя пишущие потоки, а последняя заканчивающая свою работы — должна отпускать семафор, разрешая пишущим задачам продолжить свою работу^[5]. Однако данная реализация имеет одну серьёзную проблему, сравнимую с взаимной блокировкой, — ресурсное голодание пишущих задач^[6].

Псевдокод простого алгоритма блокировок чтения-записи

Инициализация

Читающая задача

Пишущая задача

выключатель = Выключатель()
разрешение-записи = Семафор(1)

заблокировать(выключатель, разрешение-записи)
    // Критическая секция читающей задачи
разблокировать(выключатель, разрешение-записи)

захватить(разрешение-записи)
    // Критическая секция пишущей задачи
отпустить(разрешение-записи)

Универсальный алгоритм, лишённый описанной выше проблемы, включает в себя выключатель бинарного семафора А для организации критической секции читающих задач и турникет для блокировки новых читающих задач при наличии ожидающих пишущих. При появлении первой читающей задачи она захватывает семафор А с помощью выключателя, запрещая запись. Для пишущих задач семафор А защищает критическую секцию записи, поэтому, если он захвачен читающими задачами, все пишущие задачи блокируются при входе в свою критическую секцию. Однако захват пишущими задачами семафора А с последующей записью защищается семафором турникета. Поэтому, если произошла блокировка пишущей задачи из-за наличия читающих, турникет блокируется вместе с новыми читающими задачами. Как только последняя читающая заканчивает свою работу, семафор выключателя отпускается, и первая в очереди пишущая задача разблокируется. По окончании своей работы она отпускает семафор турникета, снова разрешая работу читающих задач^[7].

Псевдокод универсального алгоритма блокировок чтения-записи

Инициализация

Читающая задача

Пишущая задача

выключатель = Выключатель()
разрешение-записи = Семафор(1)
турникет = Семафор(1)

захватить(турникет)
освободить(турникет)

заблокировать(выключатель, разрешение-записи)
    // Критическая секция читающей задачи
разблокировать(выключатель, разрешение-записи)

захватить(турникет)
    захватить(разрешение-записи)
    // Критическая секция пишущей задачи
отпустить(турникет)

отпустить(разрешение-записи)

На уровне операционных систем существуют реализации семафоров чтения и записи, которые специальным образом модифицируются для повышения эффективности при массовом использовании. Реализации блокировок чтения-записи могут быть основаны как на мьютексах, так и на спин-блокировках^[4].

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

Хотя блокировки чтения-записи позволяют повысить скорость работы некоторых алгоритмов, им присуща скрытая проблема, которая проявляется при равномерной плотности запросов на чтение данных. В этом случае захват блокировки на запись может откладываться на неограниченные промежутки времени, порождая ресурсное голодание пишущих задач^[4]. Ресурсное голодание пишущих задач сравнимо с взаимной блокировкой, поскольку запись данных будет невозможной, пока прибывают новые читающие задачи. При этом проблема может оказаться незаметной, пока нагрузка на систему не очень высокая, но может начать проявляться при возрастании нагрузки. Решение может быть заложено в реализацию блокировок чтения-записи и предполагает блокировку любых новых читающих задач, если в ожидании блокировки есть хотя бы одна пишущая^[6].

Повышение блокировки до пишущейПравить

Концепция повышения уровня блокировки позволяет повысить захваченную блокировку на чтение до эксклюзивной блокировки на запись. Повышение блокировки происходит, когда больше не оказывается других читающих задач, в противном случае задача блокируется до тех пор, пока читающие задачи не отпустят блокировку. Концепция также допускает понижение блокировки записи до блокировки чтения^[8]. Однако концепция зачастую является опциональной и не обязана присутствовать в конкретных реализациях.

Прикладное программированиеПравить

Поддержка в POSIXПравить

В стандарте POSIX блокировки чтения-записи представлены типом pthread_rwlock_t из заголовочного файла pthread.h. Блокировкам можно задавать некоторые параметры через атрибуты, в частности, блокировку можно определить как доступную между процессами или только между потоками, а обязательной по стандарту является блокировка, доступная между процессами. Если отсутствуют читающие задачи, порядок захвата блокировки пишущими задачами определяется выбранной политикой планировщика. Однако приоритет захвата блокировки между пишущими и читающими задачами по стандарту не определён^[1].

Поддержка в Win32 APIПравить

В прикладном интерфейсе программирования Windows блокировки представлены структурой SRWLOCK из заголовочного файла Synchapi.h и набором функций для работы с ней. Блокировки предназначены для работы с потоками в рамках одного процесса, при этом не гарантируется какой-либо порядок захвата блокировок. Из особенностей поддерживается использование блокировки вместе с условной переменной через функцию SleepConditionVariableSRW()^[9].

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

Блокировки чтения-записи в распространённых языках программирования
Язык	Модуль или библиотека	Тип данных
Си	`pthread`	`pthread_rwlock_t`^[1]
C++	`std`	`std::shared_mutex`^[3]
C#	`System.Threading`	`ReaderWriterLock`^[10]
Go	`sync`	`RWMutex`^[11]
Java	`java.base`, `java.util.concurrent.locks`	`ReentrantReadWriteLock`^[12]
Rust	`std`	`std::sync::RwLock`^[13]

См. такжеПравить

ПримечанияПравить

↑ ¹ ² ³ ⁴ ⁵ Rationale for System Interfaces, General Information, 2018, Threads Extensions.
↑ ¹ ² ³ Allen B. Downey, 2016, 4.2 Readers-writers problem, с. 65.
↑ ¹ ² C++17, 2017, 33.4.3.4 Shared mutex types, p. 1373.
↑ ¹ ² ³ Олег Цилюрик. Инструменты программирования в ядре: Часть 73. Параллелизм и синхронизация. Блокировки. Часть 1. — www.ibm.com, 2013. — 13 августа. — Дата обращения: 12.06.2019.
↑ Allen B. Downey, 2016, 4.2.2 Readers-writers solution, с. 69—71.
↑ ¹ ² Allen B. Downey, 2016, 4.2.3 Starvation, с. 71.
↑ Allen B. Downey, 2016, 4.2.5 No-starve readers-writers solution, с. 75.
↑ Synchronization : [арх. 24.06.2020] // Boost 1.73.0 documentation. — Дата обращения: 24.06.2020.
↑ Michael Satran, McLean Schofield, Drew Batchelor, Bill Ticehurst. Slim Reader/Writer (SRW) Locks (англ.). Microsoft Docs. Microsoft (31 мая 2018). Дата обращения: 23 июня 2020. Архивировано 23 июня 2020 года.
↑ ReaderWriterLock Class // Microsoft Docs. — Microsoft. — Дата обращения: 23.06.2020.
↑ Package sync : [арх. 23.06.2020] // The Go Programming Language. — Дата обращения: 23.06.2020.
↑ Class ReentrantReadWriteLock (англ.). Java API Reference. Oracle. Дата обращения: 23 июня 2020. Архивировано 23 июня 2020 года.
↑ std::sync::RwLock : [арх. 23.06.2020] // Rust documentation. — doc.rust-lang.org. — Дата обращения: 23.06.2020.

ЛитератураПравить

IEEE, The Open Group. Rationale for System Interfaces, General Information : [англ.] : [арх. 21 июня 2020] // The Open Group Base Specifications Issue 7, 2018 edition. — 2018.
SC22/WG14 working group. ISO/IEC 14882:2017 : Standard for Programming Language C++ : Working Draft : [англ.] : [арх. 18 июня 2020]. — 2017. — 21 March. — P. 1368—1376. — 1608 p.
Allen B. Downey. The Little Book of Semaphores : [англ.] : [арх. 20 мая 2020]. — Second Edition, Version 2.2.1. — 2016. — 279 p.

[_4d197ae61b53d3ac-1] ¹ ² ³ ⁴ ⁵ Rationale for System Interfaces, General Information, 2018, Threads Extensions.

[_9c1339744baf1eb7-2] ¹ ² ³ Allen B. Downey, 2016, 4.2 Readers-writers problem, с. 65.

[_0224f52bcb5f40d0-3] ¹ ² C++17, 2017, 33.4.3.4 Shared mutex types, p. 1373.

[:0-4] ¹ ² ³ Олег Цилюрик. Инструменты программирования в ядре: Часть 73. Параллелизм и синхронизация. Блокировки. Часть 1. — www.ibm.com, 2013. — 13 августа. — Дата обращения: 12.06.2019.

[_c9b7fd8e15231265-5] Allen B. Downey, 2016, 4.2.2 Readers-writers solution, с. 69—71.

[_32c11604488c0e74-6] ¹ ² Allen B. Downey, 2016, 4.2.3 Starvation, с. 71.

[_ce2e2ce5e49d416c-7] Allen B. Downey, 2016, 4.2.5 No-starve readers-writers solution, с. 75.

[8] Synchronization : [арх. 24.06.2020] // Boost 1.73.0 documentation. — Дата обращения: 24.06.2020.

[9] Michael Satran, McLean Schofield, Drew Batchelor, Bill Ticehurst. Slim Reader/Writer (SRW) Locks (англ.). Microsoft Docs. Microsoft (31 мая 2018). Дата обращения: 23 июня 2020. Архивировано 23 июня 2020 года.

[10] ReaderWriterLock Class // Microsoft Docs. — Microsoft. — Дата обращения: 23.06.2020.

[11] Package sync : [арх. 23.06.2020] // The Go Programming Language. — Дата обращения: 23.06.2020.

[12] Class ReentrantReadWriteLock (англ.). Java API Reference. Oracle. Дата обращения: 23 июня 2020. Архивировано 23 июня 2020 года.

[13] std::sync::RwLock : [арх. 23.06.2020] // Rust documentation. — doc.rust-lang.org. — Дата обращения: 23.06.2020.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]