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

В информатике блокировка чтения -записи ( блокировка одиночной записи , ^[1] блокировка нескольких считывателей , ^[2]push-блокировка , [ ^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$ : количество записывающих устройств, ожидающих доступа (целое число)
$Writer_active$ : получил ли писатель блокировку (логическое значение).

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

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