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 con un bloqueo exclusivoes necesario para escribir o modificar datos. Cuando un escritor está escribiendo los datos, todos los demás escritores o lectores se bloquearán 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 se construyen normalmente sobre mutex y variables de condición , o sobre semáforos .
Cerradura RW actualizable
Algunos bloqueos RW permiten que el bloqueo se actualice atómicamente de estar bloqueado en modo de lectura a modo de escritura, así como también se puede degradar del modo de escritura al modo de lectura. [1] Los bloqueos RW actualizables pueden ser difíciles de usar de forma segura, ya que cada vez que dos subprocesos que contienen bloqueos del lector intentan actualizarse a bloqueos del escritor, se crea un interbloqueo que solo puede romperse si uno de los subprocesos libera el bloqueo del lector.
Políticas prioritarias
Los bloqueos RW se pueden diseñar con diferentes políticas de prioridad para el acceso de lector frente a escritor. El bloqueo puede diseñarse para dar siempre prioridad a los lectores (que prefieren la lectura ), para dar siempre prioridad a los escritores (que prefieren la escritura ) o no se especifica con respecto a la prioridad. Estas políticas conducen a diferentes compensaciones con respecto a la concurrencia y la inanición .
- Los bloqueos RW que prefieren la lectura permiten la máxima concurrencia, pero pueden provocar 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 del lector pueden mantener el bloqueo a la vez, esto significa que un subproceso del escritor puede continuar esperando el bloqueo mientras los nuevos subprocesos del lector 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 estaban sujetando el candado cuando intentaron adquirirlo por primera vez, han liberado el candado. 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 que prefieren la 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 tenían el candado se hayan completado. [5] La desventaja es que los bloqueos que prefieren la escritura permiten menos simultaneidad en presencia de subprocesos de escritura, en comparación con los bloqueos RW que prefieren la lectura. Además, el bloqueo es menos eficaz porque cada operación, tomando o liberando el bloqueo para lectura o escritura, es más compleja, requiriendo internamente tomar y liberar dos mutex en lugar de uno. [ cita requerida ] Esta variación a veces también se conoce como bloqueo de lector-escritor "con sesgo de escritura". [6]
- Los bloqueos RW de prioridad no especificada no ofrecen ninguna garantía con respecto al acceso de lectura frente a escritura. En algunas situaciones, la prioridad no especificada puede ser preferible si permite una implementación más eficiente. [ cita requerida ]
Implementación
Existen varias estrategias de implementación para bloqueos de lector-escritor, reduciéndolos a primitivas de sincronización que se supone que preexisten.
Usando dos mutexes
Raynal demuestra cómo implementar un bloqueo R / W usando dos mutex y un solo contador de enteros. El contador, b , rastrea el número de lectores bloqueados. Un mutex, r , protege by solo lo utilizan los lectores; el otro, g (para "global") asegura la exclusión mutua de los escritores. Esto requiere que un mutex adquirido por un subproceso pueda ser liberado por otro. El siguiente es un pseudocódigo para las operaciones:
Inicializar
- Establezca b en 0 .
- r está desbloqueado.
- g está desbloqueado.
Comenzar a leer
- Bloquear r .
- Incremento b .
- Si b = 1 , bloquee g .
- Desbloquear r .
Finalizar lectura
- Bloquear r .
- Decremento b .
- Si b = 0 , desbloquee g .
- Desbloquear r .
Comenzar a escribir
- Bloquear g .
Finalizar escritura
- Desbloquear g .
Esta implementación prefiere la lectura. [4] : 76
Usando una variable de condición y un mutex
Alternativamente, un bloqueo RW se puede implementar en términos de una variable de condición , cond , un bloqueo ordinario (mutex), g , y varios contadores y banderas que describen los subprocesos que están actualmente activos o en espera. [7] [8] [9] Para un bloqueo RW con preferencia de escritura, se pueden usar dos contadores de enteros y una bandera booleana:
- num_readers_active : el número de lectores que han adquirido el bloqueo (entero)
- num_writers_waiting : el número de escritores en espera de acceso (entero)
- escritor_activo : si un escritor ha adquirido el bloqueo (booleano).
Inicialmente, num_readers_active y num_writers_waiting son cero y writer_active es falso.
Las operaciones de bloqueo y liberación se pueden implementar como
Comenzar a leer
- Bloquear g
- Mientras num_writers_waiting > 0 o writer_active :
- espera cond , g [a]
- Incremento num_readers_active
- Desbloquear g .
Finalizar lectura
- Bloquear g
- Disminuir num_readers_active
- Si num_readers_active = 0 :
- Notificar cond (transmisión)
- Desbloquear g .
Comenzar a escribir
- Bloquear g
- Incremento num_writers_waiting
- Si bien num_readers_active > 0 o writer_active es verdadero :
- espera cond , g
- Disminuir num_writers_waiting
- Establecer escritor_activo en verdadero
- Desbloquear g .
Finalizar escritura
- Bloquear g
- Establecer escritor_activo en falso
- Notificar cond (transmisión)
- Desbloquear g .
Soporte de lenguaje de programación
- Estándar POSIX
pthread_rwlock_t
y operaciones asociadas [10] - La interfaz ReadWriteLock [11] y los bloqueos ReentrantReadWriteLock [6] en Java versión 5 o superior
System.Threading.ReaderWriterLockSlim
Bloqueo de Microsoft para C # y otros lenguajes .NET [12]std::shared_mutex
bloqueo de lectura / escritura en C ++ 17 [13]boost::shared_mutex
yboost::upgrade_mutex
bloqueos en las bibliotecas Boost C ++ [14]SRWLock
, agregado a la API del sistema operativo Windows a partir de Windows Vista . [15]sync.RWMutex
en Go [16]- Fase de bloqueo lector-escritor justo, que alterna entre lectores y escritores [17]
std::sync::RwLock
bloqueo de lectura / escritura en Rust [18]- Poco :: RWLock en las bibliotecas POCO C ++
mse::recursive_shared_timed_mutex
en la biblioteca SaferCPlusPlus hay una versión de std::shared_timed_mutexque admite la semántica de propiedad recursiva de std::recursive_mutex.txrwlock.ReadersWriterDeferredLock
Bloqueo de lectores / escritores para Twisted [19]
Alternativas
El algoritmo de 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
- Semáforo (programación)
- Exclusión mutua
- Patrón de programador
- Patrón de balking
- Bloqueo de archivos
- Lock (informática)
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 un solo escritor / lector múltiple?" . Grupo de noticias : comp.os.ms-windows.nt.misc . Usenet: [email protected] . Consultado el 8 de octubre de 2010 .
- ^ "Práctica libertad de bloqueo" por Keir Fraser 2004
- ^ "Push Locks - ¿Qué son?" . Blog de Ntdebugging . Blogs de MSDN. 2 de septiembre de 2009 . Consultado el 11 de mayo de 2017 .
- ^ a b 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.
- ^ a b
java.util.concurrent.locks.ReentrantReadWriteLock
La implementación de bloqueo de escritor y lector de Java ofrece un modo "justo" - ^ Herlihy, Maurice; 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 .
- ^ Butenhof, David R. (1997). Programación con hilos POSIX . Addison-Wesley. págs. 253–266.
- ^ "Especificaciones básicas de Open Group Issue 6, IEEE Std 1003.1, 2004 Edition: pthread_rwlock_destroy" . El IEEE y The Open Group . Consultado el 14 de mayo de 2011 .
- ^
java.util.concurrent.locks.ReadWriteLock
- ^ "Clase ReaderWriteLockSlim (System.Threading)" . Microsoft Corporation . Consultado el 14 de mayo de 2011 .
- ^ "Nuevo papel adoptado: N3659, bloqueo compartido en C ++ - Howard Hinnant, Detlef Vollmann, Hans Boehm" . Base C ++ estándar.
- ^ Anthony Williams. "Sincronización - Boost 1.52.0" . Consultado el 31 de enero de 2012 .
- ^ Alessandrini, Victor (2015). Programación de aplicaciones de memoria compartida: conceptos y estrategias en la programación de aplicaciones multinúcleo . Morgan Kaufmann.
- ^ "El lenguaje de programación Go - Sincronización de paquetes" . Consultado el 30 de mayo de 2015 .
- ^ "Sincronización de lector-escritor para sistemas en tiempo real con multiprocesador de memoria compartida" (PDF) .
- ^ "std :: sync :: RwLock - Rust" . Consultado el 26 de octubre de 2019 .
- ^ "Bloqueo de lectores / escritores para Twisted" . Consultado el 28 de septiembre de 2016 .