Bloqueo de lectura y escritura

El bloqueo de lectura y escritura es un mecanismo de sincronización que permite la lectura general simultánea de algunos datos compartidos o su modificación exclusiva, delimitando así los bloqueos de lectura y escritura entre sí [1] . El mecanismo está diseñado para resolver el problema clásico de lectura y escritura, en el que un objeto es leído y escrito simultáneamente por tareas concurrentes [2] .

A diferencia de los mutex , los bloqueos de lectura y escritura tienen en cuenta por separado la lectura de datos y la escritura por separado, lo que permite el acceso a los datos si no cambian en ese momento. Los mutexes solo permiten el acceso exclusivo a los datos [1] . Sin embargo, existen mutex compartidos que proporcionan, además del bloqueo exclusivo, un bloqueo compartido que permite la propiedad compartida del mutex si no hay un propietario exclusivo [3] . En esencia, los mutex compartidos son bloqueos de lectura y escritura, pero se denominan mutex.

En el caso general, los bloqueos de lectura y escritura resuelven el mismo problema que los mutex y pueden ser reemplazados por ellos, pero el motivo de la aparición del mecanismo de bloqueo de lectura y escritura es aumentar la eficiencia de la exclusión mutua con lectura y escritura separadas [ 4] . Los bloqueos de lectura y escritura son preferibles a los mutex en los casos en que se accede a los datos con mucha más frecuencia de lo que se escribe. En este caso, las tareas de lectura no se bloquearán la mayor parte del tiempo, solo algunas veces se bloquearán cuando el objeto cambie. La prioridad entre las tareas de escritura y lectura a menudo se da a las tareas de escritura para evitar la escasez de recursos de las tareas de escritura [1] .

El problema lector-escritor

El problema de los lectores y escritores surge en cualquier situación en la que tareas simultáneas requieran la lectura y modificación simultáneas de una estructura de datos, un sistema de archivos o una base de datos. La lectura de datos inmutables puede ser realizada simultáneamente por muchas tareas, sin embargo, si ocurren cambios de datos en este momento, su lectura paralela puede conducir a datos parcialmente modificados, es decir, datos corruptos [2] .

La solución al problema es asimétrica e implica la división del bloqueo en lectura y escritura. La modificación de datos solo se permite de forma exclusiva, es decir, solo una tarea puede adquirir un bloqueo de escritura a la vez, a menos que se adquiera un bloqueo de lectura. Muchas tareas pueden realizar la lectura de datos, por lo que tantas tareas como se desee pueden adquirir un bloqueo de lectura al mismo tiempo, a menos que se adquiera un bloqueo de escritura. Es decir, las secciones críticas de escritura y lectura no se pueden ejecutar en paralelo, pero las secciones críticas de lectura sí [2] .

Algoritmos de implementación

El algoritmo de implementación más simple para semáforos y mutexes es usar un interruptor de semáforo binario. La entrada debe estar protegida por este semáforo. La primera tarea que lee debe bloquear el semáforo con un interruptor, bloqueando los hilos de escritura, y la última tarea que termina su trabajo debe liberar el semáforo, permitiendo que las tareas de escritura continúen con su trabajo [5] . Sin embargo, esta implementación tiene un problema serio comparable al interbloqueo: el agotamiento de los recursos de las tareas de escritura [6] .

Pseudocódigo para un algoritmo de bloqueo de lectura y escritura simple
Inicialización tarea de lectura Tarea de escritura
interruptor = interruptor () permiso de escritura = Semáforo (1) lock(interruptor, permiso-escritura) // Sección crítica de la tarea de lectura desbloquear (cambiar, permiso de escritura) capturar (permiso de escritura) // Sección crítica de la tarea de escritura liberación (permiso de escritura)

El algoritmo universal, desprovisto del problema descrito anteriormente, incluye un interruptor de semáforo binario A para organizar una sección crítica de tareas de lectura y un torniquete para bloquear nuevas tareas de lectura en presencia de escritores en espera. Cuando llega la primera tarea para leer, toma el semáforo A con un interruptor, evitando escrituras. Para los escritores, el semáforo A protege la sección crítica del escritor, por lo que si los lectores lo capturan, todos los escritores se bloquean al ingresar a su sección crítica. Sin embargo, la captura por tareas de escritor del semáforo A y posterior escritura está protegida por el semáforo torniquete. Por lo tanto, si se produce un bloqueo de una tarea de escritura por la presencia de lectores, el torniquete se bloquea junto con nuevas tareas de lectura. Tan pronto como el último lector termina su trabajo, se libera el semáforo del interruptor y se desbloquea el primer escritor en la cola. Al final de su trabajo, libera el semáforo del torniquete, permitiendo nuevamente el trabajo de tareas de lectura [7] .

Pseudocódigo del algoritmo universal de bloqueo de lectura y escritura
Inicialización tarea de lectura Tarea de escritura
interruptor = interruptor () permiso de escritura = Semáforo (1) torniquete = Semáforo(1) apoderarse (torniquete) liberación (torniquete) lock(interruptor, permiso-escritura) // Sección crítica de la tarea de lectura desbloquear (cambiar, permiso de escritura) apoderarse (torniquete) capturar (permiso de escritura) // Sección crítica de la tarea de escritura soltar (torniquete) liberación (permiso de escritura)

A nivel de sistema operativo existen implementaciones de semáforos de lectura y escritura, los cuales son modificados de manera especial para aumentar la eficiencia en el uso masivo. Las implementaciones de bloqueos de lectura y escritura se pueden basar tanto en mutexes como en spinlocks [4] .

Problemas de uso

Si bien los bloqueos de lectura y escritura pueden mejorar la velocidad de algunos algoritmos, tienen un problema oculto que surge cuando hay una densidad uniforme de solicitudes de lectura. En este caso, la adquisición de un bloqueo de escritura se puede retrasar por períodos de tiempo ilimitados, provocando el agotamiento de los recursos de las tareas de escritura [4] . La falta de recursos de las tareas de escritura es comparable a un punto muerto , ya que la escritura de datos será imposible mientras llegan nuevas tareas de lectura. En este caso, es posible que el problema no se note hasta que la carga en el sistema sea muy alta, pero puede comenzar a manifestarse cuando la carga aumenta. La solución se puede integrar en la implementación de bloqueos de lectura y escritura e implica el bloqueo de cualquier nueva tarea de lectura si hay al menos un escritor esperando el bloqueo [6] .

Elevar el bloqueo a la escritura

El concepto de escalada de bloqueo permite que un bloqueo de lectura capturado se convierta en un bloqueo de escritura exclusivo. Se promueve un bloqueo cuando no hay más tareas de lectura; de lo contrario, la tarea se bloquea hasta que las tareas de lectura liberan el bloqueo. El concepto también permite degradar un bloqueo de escritura a un bloqueo de lectura [8] . Sin embargo, el concepto a menudo es opcional y no necesita estar presente en implementaciones específicas.

Programación de aplicaciones

Soporte POSIX

En el estándar POSIX , los bloqueos de lectura y escritura están representados por un tipo pthread_rwlock_ten el archivo de encabezado pthread.h. A los bloqueos se les pueden dar algunos parámetros a través de atributos, en particular, un bloqueo puede definirse como disponible entre procesos o solo entre subprocesos, y el estándar requiere un bloqueo disponible entre procesos. Si no hay tareas de lectura, el orden en que las tareas de escritura adquieren el bloqueo lo determina la política del programador seleccionada. Sin embargo, la prioridad de adquisición de bloqueo entre las tareas de escritor y lector no está definida por el estándar [1] .

Compatibilidad con la API de Win32

En la API de Windows , los bloqueos están representados por una estructura SRWLOCKde un archivo de encabezado Synchapi.hy un conjunto de funciones para trabajar con él. Los bloqueos están diseñados para funcionar con subprocesos dentro de un solo proceso y no se garantiza ningún orden para adquirir bloqueos. De las características, se admite el uso de un bloqueo junto con una variable de condición a través de una función SleepConditionVariableSRW()[9] .

Soporte en lenguajes de programación

Bloqueos de lectura y escritura en lenguajes de programación comunes
Idioma Módulo o biblioteca Tipo de datos
xi pthread pthread_rwlock_t[una]
C++ std std::shared_mutex[3]
C# System.Threading ReaderWriterLock[diez]
Vamos sync RWMutex[once]
Java java.base,java.util.concurrent.locks ReentrantReadWriteLock[12]
Óxido std std::sync::RwLock[13]

Véase también

Notas

  1. 1 2 3 4 5 Justificación de las interfaces del sistema, Información general, 2018 , Extensiones de subprocesos.
  2. 1 2 3 Allen B. Downey, 2016 , 4.2 Problema de lectores y escritores, p. sesenta y cinco.
  3. 1 2 C++17, 2017 , 33.4.3.4 Tipos mutex compartidos, p. 1373.
  4. ↑ 1 2 3 Oleg Tsilyurik. Herramientas de programación del kernel: Parte 73. Paralelismo y sincronización. Cerraduras. parte 1 - www.ibm.com, 2013. - 13 de agosto. — Fecha de acceso: 12/06/2019.
  5. Allen B. Downey, 2016 , 4.2.2 Solución de lectores y escritores, p. 69-71.
  6. 1 2 Allen B. Downey, 2016 , 4.2.3 Inanición, pág. 71.
  7. Allen B. Downey, 2016 , 4.2.5 Solución para lectores y escritores sin hambre, p. 75.
  8. Sincronización  : [ arch. 24/06/2020 ] // Documentación de Boost 1.73.0. — Fecha de acceso: 24/06/2020.
  9. Michael Satran, McLean Schofield, Drew Batchelor, Bill Ticehurst. Cerraduras Slim Reader/Writer (SRW)  . Documentos de Microsoft . Microsoft (31 de mayo de 2018). Consultado el 23 de junio de 2020. Archivado desde el original el 23 de junio de 2020.
  10. Clase ReaderWriterLock  // Microsoft Docs. —Microsoft . _ — Fecha de acceso: 23/06/2020.
  11. ↑ Sincronización de paquetes  : [ arch. 23/06/2020 ] // El lenguaje de programación Go. — Fecha de acceso: 23/06/2020.
  12. Class ReentrantReadWriteLock  . Referencia de la API de Java . Oráculo. Consultado el 23 de junio de 2020. Archivado desde el original el 23 de junio de 2020.
  13. std::sync::RwLock  : [ arch. 23/06/2020 ] // Documentación de óxido. - doc.rust-lang.org. — Fecha de acceso: 23/06/2020.

Literatura