stringtranslate.com

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 lectura-escritor 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 .

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:

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

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

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

Referencias

  1. ^ 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 .
  2. ^ "Libertad práctica sin encierro" por Keir Fraser 2004
  3. ^ "Push Locks – ¿Qué son?". Blog de Ntdebugging . Blogs de MSDN. 2 de septiembre de 2009. Consultado el 11 de mayo de 2017 .
  4. ^ ab Raynal, Michel (2012). Programación concurrente: algoritmos, principios y fundamentos . Springer.
  5. ^ Stevens, W. Richard ; Rago, Stephen A. (2013). Programación avanzada en el entorno UNIX . Addison-Wesley. pág. 409.
  6. ^ java.util.concurrent.locks.ReentrantReadWriteLockLa implementación del bloqueo de lectores-escritores de Java ofrece un modo "justo"
  7. ^ Herlihy, Maurice; Shavit, Nir (2012). El arte de la programación multiprocesador . Elsevier. págs. 184–185.
  8. ^ 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.
  9. ^ Butenhof, David R. (1997). Programación con subprocesos POSIX . Addison-Wesley. págs. 253–266.
  10. ^ "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 .
  11. ^ java.util.concurrent.locks.ReadWriteLock
  12. ^ "Clase ReaderWriteLockSlim (System.Threading)". Microsoft Corporation . Consultado el 14 de mayo de 2011 .
  13. ^ "Nuevo documento adoptado: N3659, bloqueo compartido en C++—Howard Hinnant, Detlef Vollmann, Hans Boehm". Fundación C++ estándar.
  14. ^ Anthony Williams. «Sincronización – Boost 1.52.0» . Consultado el 31 de enero de 2012 .
  15. ^ Alessandrini, Victor (2015). Programación de aplicaciones de memoria compartida: conceptos y estrategias en la programación de aplicaciones multinúcleo . Morgan Kaufmann.
  16. ^ "El lenguaje de programación Go: sincronización de paquetes" . Consultado el 30 de mayo de 2015 .
  17. ^ "Sincronización lector-escritor para sistemas en tiempo real con multiprocesador y memoria compartida" (PDF) .
  18. ^ "std::sync::RwLock – Rust" . Consultado el 26 de octubre de 2019 .
  19. ^ "Bloqueo de lectores/escritores para Twisted". GitHub . Consultado el 28 de septiembre de 2016 .
  20. ^ "Primitivas de sincronización en el núcleo Linux: semáforos de lectura/escritura". Linux Insides . Consultado el 8 de junio de 2023 .