Bloqueo de lectores-escritores

En informática , un lector-escritor ( bloqueo de un solo escritor , ^[1] un bloqueo de múltiples lectores , ^[2] un bloqueo de empuje , ^[3] o un bloqueo MRSW ) es una primitiva de sincronización que resuelve uno de los lectores-escritores. problemas . Un bloqueo RW permite el acceso simultáneo para operaciones de solo lectura, mientras que las operaciones de escritura requieren acceso exclusivo. Esto significa que varios subprocesos pueden leer los datos en paralelo, pero se necesita un bloqueo exclusivo para escribir o modificar datos. Cuando un escritor escribe los datos, todos los demás escritores y lectores serán bloqueados hasta que el escritor termine de escribir. Un uso común podría ser controlar el acceso a una estructura de datos en la memoria que no se puede actualizar atómicamente y no es válida (y no debe ser leída por otro hilo) hasta que se complete la actualización.

Los bloqueos de lector-escritor generalmente se construyen sobre mutex y variables de condición , o sobre semáforos .

Bloqueo RW actualizable

Algunos bloqueos RW permiten que el bloqueo se actualice atómicamente desde el bloqueo en modo lectura al modo escritura, así como también que se degrade del modo escritura al modo lectura. [1] Actualizar un bloqueo del modo lectura al modo escritura es propenso a interbloqueos, ya que cada vez que dos subprocesos que contienen bloqueos de lectura intentan actualizarse a bloqueos de escritura, se crea un interbloqueo que solo puede romperse si uno de los subprocesos libera su bloqueo del lector. El punto muerto se puede evitar permitiendo que solo un subproceso adquiera el bloqueo en "modo de lectura con la intención de actualizar a escritura" mientras no hay subprocesos en modo de escritura y posiblemente subprocesos distintos de cero en modo de lectura.

Políticas prioritarias

Los bloqueos RW se pueden diseñar con diferentes políticas de prioridad para el acceso de lector o escritor. El bloqueo puede diseñarse para dar siempre prioridad a los lectores ( preferencia de lectura ), para dar siempre prioridad a los escritores ( preferencia de escritura ) o no especificarse con respecto a la prioridad. Estas políticas conducen a diferentes compensaciones con respecto a la concurrencia y el hambre .

Los bloqueos RW con preferencia de lectura permiten una máxima concurrencia, pero pueden provocar una falta de escritura si la contención es alta. Esto se debe a que los subprocesos de escritura no podrán adquirir el bloqueo mientras al menos un subproceso de lectura lo mantenga. Dado que varios subprocesos de lectura pueden mantener el bloqueo a la vez, esto significa que un subproceso de escritura puede continuar esperando el bloqueo mientras nuevos subprocesos de lectura pueden adquirir el bloqueo, incluso hasta el punto en que el escritor todavía puede estar esperando después de que todos los lectores que sostenían el candado cuando intentó adquirirlo por primera vez lo han liberado. La prioridad para los lectores puede ser débil , como se acaba de describir, o fuerte , lo que significa que cada vez que un escritor libera el bloqueo, los lectores que lo bloquean siempre lo adquieren a continuación. ^[4]^{: 76}
Los bloqueos RW con preferencia de escritura evitan el problema de la falta de escritura al evitar que nuevos lectores adquieran el bloqueo si hay un escritor en cola y esperando el bloqueo; el escritor adquirirá el candado tan pronto como todos los lectores que ya lo tenían hayan completado. ^[5] La desventaja es que los bloqueos con preferencia de escritura permiten una menor concurrencia en presencia de subprocesos de escritura, en comparación con los bloqueos RW con preferencia de lectura. Además, el bloqueo tiene menos rendimiento porque cada operación, tomar o liberar el bloqueo para lectura o escritura, es más compleja y requiere internamente tomar y liberar dos mutex en lugar de uno. ^{[ cita necesaria ]} Esta variación a veces también se conoce como bloqueo lector-escritor "sesgado en escritura". ^[6]
Los bloqueos RW de prioridad no especificada no ofrecen ninguna garantía con respecto al acceso de lectura o escritura. En algunas situaciones, una prioridad no especificada puede ser preferible si permite una implementación más eficiente. ^{[ cita necesaria ]}

Implementación

Existen varias estrategias de implementación para bloqueos de lector-escritor, reduciéndolos a primitivas de sincronización que se supone preexisten.

Usando dos mutex

Raynal demuestra cómo implementar un bloqueo R/W usando dos mutex y un único contador entero. El contador, $b$ , rastrea el número de lectores bloqueados. Un mutex, $r$ , protege $b$ y solo lo utilizan los lectores; el otro, $g$ (de "global") garantiza la exclusión mutua de los escritores. Esto requiere que un mutex adquirido por un hilo pueda ser liberado por otro. El siguiente es el pseudocódigo para las operaciones:

Inicializar

Establezca $b$ en $0$ .
$r$ está desbloqueado.
$g$ está desbloqueado.

Empezar a leer

Bloquear $r$ .
Incremento $b$ .
Si $b = 1$ , bloquee $g$ .
Desbloquear $r$ .

Finalizar lectura

Bloquear $r$ .
Decremento $b$ .
Si $b = 0$ , desbloquea $g$ .
Desbloquear $r$ .

Empezar a escribir

Bloquear $g$ .

Fin de escritura

Desbloquear $g$ .

Esta implementación prefiere la lectura. ^[4]^{: 76}

Usando una variable de condición y un mutex

Alternativamente, se puede implementar un bloqueo RW en términos de una variable de condición , $cond$ , un bloqueo ordinario (mutex), $g$ , y varios contadores e indicadores que describen los subprocesos que están actualmente activos o en espera. ^[7]^[8]^[9] Para un bloqueo RW que prefiere escritura, se pueden usar dos contadores de números enteros y un indicador booleano:

$num_readers_active$ : el número de lectores que han adquirido el bloqueo (entero)
$num_writers_waiting$ : el número de escritores esperando acceso (entero)
$escritor_activo$ : si un escritor ha adquirido el bloqueo (booleano).

Inicialmente, $num_readers_active$ y $num_writers_waiting$ son cero y $escritor_active$ es falso.

Las operaciones de bloqueo y liberación se pueden implementar como

Empezar a leer

Bloquear $g$
Mientras num_writers_waiting > 0 o escritor_activo :
- espera $cond$ , $g$ ^[a]
Incrementar $num_readers_active$
Desbloquear $g$ .

Finalizar lectura

Bloquear $g$
Disminuir $num_readers_active$
Si num_readers_active = 0 :
- Notificar $cond$ (transmitir)
Desbloquear $g$ .

Empezar a escribir

Bloquear $g$
Incrementar $num_writers_waiting$
Mientras num_readers_active > 0 o escritor_active es verdadero :
- espera $cond$ , $g$
Disminuir $num_writers_waiting$
Establecer $escritor_activo$ en $verdadero$
Desbloquear $g$ .

Fin de escritura

Bloquear $g$
Establecer $escritor_activo$ en $falso$
Notificar $cond$ (transmitir)
Desbloquear $g$ .

Soporte de lenguaje de programación

Estándar POSIXpthread_rwlock_t y operaciones asociadas ^[10]
La interfaz ReadWriteLock ^[11] y los bloqueos ReentrantReadWriteLock ^[6] en Java versión 5 o superior
Bloqueo de Microsoft System.Threading.ReaderWriterLockSlimpara C# y otros lenguajes .NET ^[12]
std::shared_mutexbloqueo de lectura/escritura en C++17 ^[13]
boost::shared_mutexy boost::upgrade_mutexbloquea las bibliotecas Boost C++ ^[14]
SRWLock, agregado a la API del sistema operativo Windows a partir de Windows Vista . ^[15]
sync.RWMutexen ir ^[16]
Bloqueo de fase justa entre lector y escritor, que alterna entre lectores y escritores ^[17]
std::sync::RwLockbloqueo de lectura/escritura en Rust ^[18]
Poco::RWBloquear en las bibliotecas POCO C++
mse::recursive_shared_timed_mutexen la biblioteca SaferCPlusPlus hay una versión de std::shared_timed_mutex que admite la semántica de propiedad recursiva de std::recursive_mutex.
txrwlock.ReadersWriterDeferredLockBloqueo de lector/escritor para Twisted ^[19]
rw_semaphoreen el kernel de Linux ^[20]

Alternativas

El algoritmo lectura-copia-actualización (RCU) es una solución al problema de lectores-escritores. RCU no tiene que esperar para los lectores. El kernel de Linux implementa una solución especial para algunos escritores llamada seqlock .

Ver también

Notas

^ Esta es la operación estándar de "espera" en variables de condición que, entre otras acciones, libera el mutex $g$ .

Referencias

^ Hamilton, Doug (21 de abril de 1995). "¿Sugerencias para el bloqueo de múltiples lectores/escritor único?". Grupo de noticias : comp.os.ms-windows.nt.misc. Usenet: [email protected] . Consultado el 8 de octubre de 2010 .
^ "Práctica libertad de bloqueo" de Keir Fraser 2004
^ "Cerraduras de empuje: ¿qué son?". Blog de ntdepuración . Blogs de MSDN. 2 de septiembre de 2009 . Consultado el 11 de mayo de 2017 .
^ ab Raynal, Michel (2012). Programación concurrente: algoritmos, principios y fundamentos . Saltador.
^ Stevens, W. Richard ; Rago, Stephen A. (2013). Programación Avanzada en el Entorno UNIX . Addison-Wesley. pag. 409.
^ ab java.util.concurrent.locks.ReentrantReadWriteLockLa implementación de bloqueo de lectores y escritores de Java ofrece un modo "justo"
^ Herlihy, Mauricio; Shavit, Nir (2012). El arte de la programación multiprocesador . Elsevier. págs. 184-185.
^ Nichols, Bradford; Buttlar, Dick; Farrell, Jacqueline (1996). Programación PThreads: un estándar POSIX para un mejor multiprocesamiento . O'Reilly. págs. 84–89. ISBN 9781565921153.
^ Butenhof, David R. (1997). Programación con Hilos POSIX . Addison-Wesley. págs. 253–266.
^ "Especificaciones básicas de Open Group, edición 6, IEEE Std 1003.1, edición de 2004: pthread_rwlock_destroy". El IEEE y el Open Group . Consultado el 14 de mayo de 2011 .
^ java.util.concurrent.locks.ReadWriteLock
^ "Clase ReaderWriteLockSlim (System.Threading)". Corporación Microsoft . Consultado el 14 de mayo de 2011 .
^ "Nuevo artículo adoptado: N3659, bloqueo compartido en C++: Howard Hinnant, Detlef Vollmann, Hans Boehm". Fundación C++ estándar.
^ Antonio Williams. "Sincronización: Boost 1.52.0" . Consultado el 31 de enero de 2012 .
^ Alessandrini, Víctor (2015). Programación de aplicaciones de memoria compartida: conceptos y estrategias en programación de aplicaciones multinúcleo . Morgan Kaufman.
^ "El lenguaje de programación Go: sincronización de paquetes" . Consultado el 30 de mayo de 2015 .
^ "Sincronización lector-escritor para sistemas en tiempo real multiprocesador de memoria compartida" (PDF) .
^ "std::sync::RwLock - Óxido" . Consultado el 26 de octubre de 2019 .
^ "Bloqueo de lectores/escritores para Twisted". GitHub . Consultado el 28 de septiembre de 2016 .
^ "Primitivas de sincronización en el kernel de Linux: semáforos de lector/escritor". Interiores de Linux . Consultado el 8 de junio de 2023 .