Bloqueo de lectores y escritores

En informática , un bloqueo de lectores-escritores ( bloqueo de un solo escritor , ^[1] un bloqueo de múltiples lectores , ^[2] un bloqueo push , ^[3] o un bloqueo MRSW ) es una primitiva de sincronización que resuelve uno de los problemas de lectores-escritores . Un bloqueo RW permite el acceso concurrente 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 está escribiendo 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 subproceso) hasta que se complete la actualización.

Los bloqueos de lectores-escritores generalmente se construyen sobre mutexes y variables de condición , o sobre semáforos .

Cerradura RW actualizable

Algunos bloqueos RW permiten que el bloqueo se actualice de forma automática de un estado en el que se encontraba bloqueado en modo lectura a uno en modo escritura, así como que se lo degrade de un estado en el que se encontraba bloqueado en modo escritura a un estado en el que se encontraba bloqueado en modo lectura. [1] Actualizar un bloqueo de un estado en el que se encontraba bloqueado en modo lectura a un estado en el que se encontraba bloqueado en modo escritura es propenso a bloqueos, ya que siempre que dos subprocesos que tienen bloqueos de lectura intentan actualizarse a bloqueos de escritura, se crea un bloqueo que solo puede romperse si uno de los subprocesos libera su bloqueo de lectura. El bloqueo puede evitarse permitiendo que solo un subproceso adquiera el bloqueo en "modo lectura con la intención de actualizarse a escritura" mientras no haya subprocesos en modo escritura y posiblemente subprocesos distintos de cero en modo lectura.

Políticas prioritarias

Los bloqueos RW se pueden diseñar con diferentes políticas de prioridad para el acceso de lectores y escritores. El bloqueo se puede diseñar para que siempre dé prioridad a los lectores ( preferencia de lectura ), para que siempre dé prioridad a los escritores ( preferencia de escritura ) o no se especifique la prioridad. Estas políticas dan lugar a diferentes compensaciones en lo que respecta a la concurrencia y la inanición .

Los bloqueos RW con preferencia de lectura permiten una concurrencia máxima, 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 tenga. Dado que varios subprocesos de lectura pueden tener 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 puede seguir esperando después de que todos los lectores que tenían el bloqueo cuando intentó adquirirlo por primera vez hayan liberado el bloqueo. La prioridad para los lectores puede ser débil , como se acaba de describir, o fuerte , lo que significa que siempre que un escritor libera el bloqueo, cualquier lector bloqueador siempre lo adquiere a continuación. ^[4]^{: 76}
Los bloqueos RW con preferencia de escritura evitan el problema de la falta de escritura al impedir que nuevos lectores adquieran el bloqueo si hay un escritor en cola esperando el bloqueo; el escritor adquirirá el bloqueo tan pronto como todos los lectores que ya tenían el bloqueo hayan completado su ejecución. ^[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 un menor 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 requerida ]} Esta variación a veces también se conoce como bloqueo de lectores-escritores "sesgado a la escritura". ^[6]
Los bloqueos RW con prioridad no especificada no ofrecen garantías en cuanto al acceso de lectura y 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 lectores-escritores, reduciéndolos a primitivos de sincronización que se supone que ya existen.

Usando dos mutexes

Raynal demuestra cómo implementar un bloqueo R/W utilizando dos mutexes y un único contador entero. El contador, $b$ , rastrea la cantidad de lectores que bloquean. Un mutex, $r$ , protege $a b$ y solo lo utilizan los lectores; el otro, $g$ (por "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 un pseudocódigo para las operaciones:

Inicializar

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

Empezar a leer

Bloqueo $r$ .
Incremento $b$ .
Si $b = 1$ , bloquea $g$ .
Desbloquear $r$ .

Fin de lectura

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

Empezar a escribir

Bloqueo $g$ .

Fin de escritura

Desbloquear $g$ .

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

Usando una variable de condición y un mutex

Como alternativa, 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 hilos que están actualmente activos o en espera. ^[7]^[8]^[9] Para un bloqueo RW que prefiere escritura, se pueden usar dos contadores 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 que esperan acceso (entero)
$writer_active$ : 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

Empezar a leer

Bloqueo $g$
Mientras num_writers_waiting > 0 o writer_active :
- espera $cond$ , $g$ ^[a]
Incrementar $el número de lectores activos$
Desbloquear $g$ .

Fin de lectura

Bloqueo $g$
Disminuir $num_readers_active$
Si num_readers_active = 0 :
- Notificar $cond$ (transmisión)
Desbloquear $g$ .

Empezar a escribir

Bloqueo $g$
Incrementar $el número de escritores en espera$
Mientras num_readers_active > 0 o writer_active sea verdadero :
- espera $cond$ , $g$
Disminuir $el número de escritores en espera$
Establezca $writer_active$ en $verdadero$
Desbloquear $g$ .

Fin de escritura

Bloqueo $g$
Establezca $writer_active$ en $falso$
Notificar $cond$ (transmisión)
Desbloquear $g$ .

Soporte de lenguaje de programación

Estándar POSIXpthread_rwlock_t y operaciones asociadas ^[10]
Interfaz ReadWriteLock ^[11] y 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_mutexbloqueos en las bibliotecas Boost C++ ^[14]
SRWLock, añadido a la API del sistema operativo Windows a partir de Windows Vista . ^[15]
sync.RWMutexen Go ^[16]
Bloqueo de lectura-escritor de fase justa, 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 lectores/escritores para Twisted ^[19]
rw_semaphoreen el núcleo de Linux ^[20]

Alternativas

El algoritmo de lectura-copia-actualización (RCU) es una solución al problema de los lectores-escritores. RCU no requiere esperas para los lectores. El núcleo de Linux implementa una solución especial para algunos escritores llamada seqlock .

Véase también

Notas

^ Esta es la operación de "espera" estándar en las 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 y un solo escritor". Grupo de noticias : comp.os.ms-windows.nt.misc. Usenet: [email protected] . Consultado el 8 de octubre de 2010 .
^ "Libertad práctica sin encierro" 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 .
^ ab Raynal, Michel (2012). Programación concurrente: algoritmos, principios y fundamentos . Springer.
^ Stevens, W. Richard ; Rago, Stephen A. (2013). Programación avanzada en el entorno UNIX . Addison-Wesley. pág. 409.
^ java.util.concurrent.locks.ReentrantReadWriteLockLa implementación del bloqueo de lectores-escritores 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. ISBN. 9781565921153.
^ Butenhof, David R. (1997). Programación con subprocesos POSIX . Addison-Wesley. págs. 253–266.
^ "Especificaciones básicas de The Open Group, número 6, IEEE Std 1003.1, edición 2004: 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 documento adoptado: N3659, bloqueo compartido en C++—Howard Hinnant, Detlef Vollmann, Hans Boehm". Fundación 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 lector-escritor para sistemas de tiempo real multiprocesador con memoria compartida" (PDF) .
^ "std::sync::RwLock – Rust" . 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 núcleo Linux: semáforos de lectura/escritura". Linux Insides . Consultado el 8 de junio de 2023 .