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

Введение

Примитив синхронизации в вычислительной технике

В информатике, механизм "читатели-писатели" (одиночный замок записи, многократный замок чтения, push-замок или MRSW-замок) — это примитив синхронизации, решающий одну из задач "читатели-писатели". RW-замок обеспечивает одновременный доступ для операций только чтения, в то время как операции записи требуют исключительного доступа. Это означает, что несколько потоков могут читать данные параллельно, но для записи или изменения данных требуется эксклюзивный замок. Когда писатель осуществляет запись данных, все остальные писатели и читатели блокируются до завершения записи. Типичное применение — контроль доступа к структуре данных в памяти, которую нельзя обновить атомарно и которая становится недействительной (и не должна читаться другой нитью) до завершения обновления. Механизмы "читатели-писатели" обычно реализуются на основе мьютексов и переменных условия или семафоров.

Улучшаемый RW-замок

Некоторые RW-блокировки позволяют атомарно повышать уровень блокировки из режима чтения в режим записи, а также понижать уровень из режима записи в режим чтения. Повышение уровня блокировки из режима чтения в режим записи чревато возникновением взаимоблокировок (дедлоков), поскольку, если две потока, удерживающие блокировки чтения, одновременно попытаются повысить уровень до блокировки записи, возникнет дедлок, который можно разрешить только если один из потоков освободит свою блокировку чтения. Чтобы избежать дедлока, следует разрешать только одному потоку получать блокировку в режиме "чтения с намерением повышения до записи", при условии, что в режиме записи нет потоков и, возможно, есть потоки в режиме чтения.

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

Замки RW могут быть разработаны с различными политиками приоритета для доступа читателей и писателей. Замок может быть разработан так, чтобы всегда отдавать приоритет читателям (читателям предпочтение), всегда отдавать приоритет писателям (писателям предпочтение) или не иметь определённого приоритета. Эти политики приводят к различным компромиссам в отношении параллелизма и "голодания". Замки RW с предпочтением чтения обеспечивают максимальный параллелизм, но могут привести к "голоданию" писателей при высокой конкуренции. Это происходит потому, что поток-писатель не сможет получить замок, пока хотя бы один поток-читатель его удерживает. Поскольку несколько потоков-читателей могут одновременно удерживать замок, поток-писатель может продолжать ждать, в то время как новые потоки-читатели смогут получить замок, даже до такой степени, что писатель может все еще ждать после того, как все читатели, удерживавшие замок при первой попытке его получения, освободили его. Приоритет для читателей может быть слабым, как описано выше, или сильным, что означает, что каждый раз, когда писатель освобождает замок, блокирующие читатели всегда получают его следующими. Замки RW с предпочтением записи избегают проблемы "голодания" писателей, предотвращая получение замка новыми читателями, если есть ожидающий писатель; писатель получит замок, как только все читатели, уже удерживавшие замок, завершат работу. Недостатком является то, что замки с предпочтением записи обеспечивают меньший параллелизм в присутствии потоков-писателей по сравнению с замками RW с предпочтением чтения. Кроме того, замок менее производителен, поскольку каждая операция – получение или освобождение замка для чтения или записи – более сложна, внутренне требуя получения и освобождения двух мьютексов вместо одного. Эта разновидность также иногда известна как "смещенный к записи" замок читателей-писателей. Замки RW с неопределённым приоритетом не предоставляют никаких гарантий относительно доступа для чтения и записи. Неопределённый приоритет может быть предпочтительным в некоторых ситуациях, если он позволяет реализовать более эффективное решение.

RW locks can be designed with different priority policies for reader vs. writer access. The lock can either be designed to always give priority to readers (read preferring), to always give priority to writers (write preferring) or be unspecified with regards to priority. These policies lead to different tradeoffs with regards to concurrency and starvation. Read preferring RW locks allow for maximum concurrency, but can lead to write starvation if contention is high. This is because writer threads will not be able to acquire the lock as long as at least one reading thread holds it. Since multiple reader threads may hold the lock at once, this means that a writer thread may continue waiting for the lock while new reader threads are able to acquire the lock, even to the point where the writer may still be waiting after all of the readers which were holding the lock when it first attempted to acquire it have released the lock. Priority to readers may be weak, as just described, or strong, meaning that whenever a writer releases the lock, any blocking readers always acquire it next. Write preferring RW locks avoid the problem of writer starvation by preventing any new readers from acquiring the lock if there is a writer queued and waiting for the lock; the writer will acquire the lock as soon as all readers which were already holding the lock have completed. The downside is that write preferring locks allows for less concurrency in the presence of writer threads, compared to read preferring RW locks. Also the lock is less performant because each operation, taking or releasing the lock for either read or write, is more complex, internally requiring taking and releasing two mutexes instead of one. This variation is sometimes also known as "write biased" readers–writer lock. Unspecified priority RW locks does not provide any guarantees with regards read vs. write access. Unspecified priority can in some situations be preferable if it allows for a more efficient implementation.

Реализация

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

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

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