En informática , los problemas de lectores-escritores son ejemplos de un problema informático común en concurrencia . Hay al menos tres variaciones de los problemas, que se ocupan de situaciones en las que muchos subprocesos de ejecución simultáneos intentan acceder al mismo recurso compartido al mismo tiempo.
Algunos subprocesos pueden leer y otros pueden escribir, con la restricción de que ningún subproceso puede acceder al recurso compartido para leer o escribir mientras otro subproceso está en el acto de escribir en él. (En particular, queremos evitar que más de un hilo modifique el recurso compartido simultáneamente y permitir que dos o más lectores accedan al recurso compartido al mismo tiempo). Un bloqueo de lectores-escritores es una estructura de datos que resuelve uno o más de los problemas de lectores-escritores.
El problema básico de lectores-escritores fue formulado y resuelto por primera vez por Courtois et al. [1] [2]
Problema de los primeros lectores-escritores
Supongamos que tenemos un área de memoria compartida (sección crítica) con las restricciones básicas detalladas anteriormente. Es posible proteger los datos compartidos detrás de un mutex de exclusión mutua , en cuyo caso dos subprocesos no pueden acceder a los datos al mismo tiempo. Sin embargo, esta solución es subóptima, porque es posible que un lector R 1 tenga el bloqueo y luego otro lector R 2 solicite acceso. Sería una tontería que R 2 esperara hasta que R 1 estuviera listo antes de iniciar su propia operación de lectura; en su lugar, se debe permitir que R 2 lea el recurso junto con R 1 porque las lecturas no modifican los datos, por lo que las lecturas simultáneas son seguras. Ésta es la motivación del primer problema de lectores-escritores , en el que se agrega la restricción de que ningún lector deberá esperar si el recurso compartido está abierto para la lectura. Esto también se llama preferencia de los lectores , con su solución:
recurso semáforo = 1 ;semáforo rmutex = 1 ;readcount = 0 ;/ * resource.P () es equivalente a wait (recurso) resource.V () es equivalente a signal (resource) rmutex.P () es equivalente a esperar (rmutex) rmutex.V () es equivalente a señal (rmutex)* /escritor () { recurso . P (); // Bloquear el archivo compartido para un escritor < Sección CRÍTICA > // La escritura está lista < Sección EXIT > recurso . V (); // Libera el archivo compartido para que lo utilicen otros lectores. Los escritores están permitidos si no hay lectores que lo soliciten.}lector () { rmutex . P (); // Asegúrese de que ningún otro lector pueda ejecutar la sección mientras está en ella < Sección CRÍTICA > readcount ++ ; // Indique que es un lector que intenta ingresar a la Sección Crítica if ( readcount == 1 ) // Comprueba si eres el primer lector que intenta ingresar CS recurso . P (); // Si es el primer lector, bloquee el recurso de los escritores. El recurso permanece reservado para lectores posteriores < SALIR Sección CRÍTICA > rmutex . V (); //Lanzamiento // Haz la lectura rmutex . P (); // Asegúrese de que ningún otro lector pueda ejecutar la sección mientras está en ella < Sección CRÍTICA > readcount - ; // Indica que ya no necesitas el recurso compartido. Un lector menos if ( readcount == 0 ) // Comprueba si eres el último (único) lector que está leyendo el archivo compartido recurso . V (); // Si eres el último lector, puedes desbloquear el recurso. Esto lo pone a disposición de los escritores. < SALIR Sección CRÍTICA > rmutex . V (); //Lanzamiento}
En esta solución del problema de lectores / escritores, el primer lector debe bloquear el recurso (archivo compartido) si está disponible. Una vez que el archivo está bloqueado para los escritores, muchos lectores posteriores pueden usarlo sin tener que volver a bloquearlo.
Antes de ingresar a la sección crítica , cada nuevo lector debe pasar por la sección de entrada. Sin embargo, es posible que solo haya un solo lector en la sección de entrada a la vez. Esto se hace para evitar condiciones de carrera en los lectores (en este contexto, una condición de carrera es una condición en la que dos o más subprocesos se despiertan simultáneamente e intentan ingresar a la sección crítica; sin más restricciones, el comportamiento es no determinista. Por ejemplo, dos los lectores incrementan el recuento de lecturas al mismo tiempo, y ambos intentan bloquear el recurso, provocando que un lector se bloquee). Para lograr esto, cada lector que ingrese a la
Una vez que el primer lector esté en la sección de entrada, bloqueará el recurso. Hacer esto evitará que los escritores accedan a él. Los lectores posteriores solo pueden utilizar el recurso bloqueado (de los escritores). El lector que termine último (indicado por la variable readcount) debe desbloquear el recurso, poniéndolo así a disposición de los escritores.
En esta solución, cada escritor debe reclamar el recurso individualmente. Esto significa que un flujo de lectores puede posteriormente bloquear a todos los escritores potenciales y matarlos de hambre. Esto es así porque después de que el primer lector bloquea el recurso, ningún escritor puede bloquearlo antes de que se libere. Y solo lo publicará el último lector. Por tanto, esta solución no satisface la equidad.
Segundo problema de lectores-escritores
La primera solución es subóptima, porque es posible que un lector R 1 tenga el bloqueo, un escritor W esté esperando el bloqueo y luego un lector R 2 solicite acceso. Sería injusto que R 2 saltara inmediatamente, por delante de W ; si eso sucediera con suficiente frecuencia, W se moriría de hambre . En cambio, W debería comenzar lo antes posible. Ésta es la motivación para el segundo problema de lectores-escritores , en el que se agrega la restricción de que ningún escritor, una vez agregado a la cola, se mantendrá esperando más tiempo del absolutamente necesario . Esto también se llama preferencia de los escritores .
Una solución al escenario de preferencia de los escritores es: [1]
int readcount , writecount ; // (valor inicial = 0)semáforo rmutex , wmutex , read Try , recurso ; // (valor inicial = 1)//LECTORlector () {< Sección ENTRY > readProbar . P (); // Indica que un lector está intentando entrar rmutex . P (); // bloquear la sección de entrada para evitar la condición de carrera con otros lectores readcount ++ ; // reportarse a sí mismo como lector if ( readcount == 1 ) // comprueba si eres el primer lector recurso . P (); // si eres el primer lector, bloquea el recurso rmutex . V (); // sección de entrada de lanzamiento para otros lectores readProbar . V (); // indica que ha terminado de intentar acceder al recurso< Sección CRÍTICA >// se realiza la lectura< Sección EXIT > rmutex . P (); // sección de salida de reserva: evita la condición de carrera con los lectores readcount - ; // indica que te vas if ( readcount == 0 ) // comprueba si eres el último lector que se va recurso . V (); // si es el último, debe liberar el recurso bloqueado rmutex . V (); // liberar la sección de salida para otros lectores}//ESCRITORescritor () {< Sección ENTRY > wmutex . P (); // sección de inscripción de reserva para escritores - evita condiciones de carrera writecount ++ ; // reportarse como escritor ingresando if ( writecount == 1 ) // comprueba si eres el primer escritor readProbar . P (); // si eres el primero, debes bloquear a los lectores. Evitar que intenten ingresar a CS wmutex . V (); // sección de entrada de lanzamiento recurso . P (); // reserva el recurso para ti mismo: evita que otros escritores editen simultáneamente el recurso compartido< Sección CRÍTICA > // se realiza la escritura recurso . V (); // liberar archivo< Sección EXIT > wmutex . P (); // sección de salida de reserva writecount - ; // indica que te vas if ( writecount == 0 ) // comprueba si eres el último escritor readProbar . V (); // si eres el último escritor, debes desbloquear los lectores. Les permite intentar ingresar CS para leer wmutex . V (); // liberar sección de salida}
En esta solución, se da preferencia a los escritores. Esto se logra obligando a cada lector a bloquear y liberar el semáforo de readtry individualmente. Los escritores, por otro lado, no necesitan bloquearlo individualmente. Solo el primer escritor bloqueará la readtry y luego todos los escritores posteriores pueden simplemente usar el recurso a medida que lo libera el escritor anterior. El último escritor debe liberar el semáforo readtry, abriendo así la puerta para que los lectores intenten leer.
Ningún lector puede participar en la sección de entrada si un escritor ha establecido previamente el semáforo de readtry. El lector debe esperar a que el último escritor desbloquee el recurso y vuelva a intentar los semáforos. Por otro lado, si un lector en particular ha bloqueado el semáforo de readtry, esto le indicará a cualquier posible escritor concurrente que hay un lector en la sección de entrada. Por lo tanto, el escritor esperará a que el lector libere el readtry y luego el escritor lo bloqueará inmediatamente para sí mismo y para todos los escritores posteriores. Sin embargo, el escritor no podrá acceder al recurso hasta que el lector actual haya liberado el recurso, lo que solo ocurre después de que el lector haya terminado con el recurso en la sección crítica.
Tanto el escritor como el lector pueden bloquear el semáforo de recursos en su sección de entrada. Solo pueden hacerlo después de bloquear primero el semáforo de readtry, lo que solo puede hacer uno de ellos a la vez.
Si no hay escritores que deseen acceder al recurso, como le indica al lector el estado del semáforo de readtry, los lectores no bloquearán el recurso. Esto se hace para permitir que un escritor tome el control inmediatamente sobre el recurso tan pronto como el lector actual termine de leer. De lo contrario, el escritor tendría que esperar a que se complete una cola de lectores antes de que el último pueda desbloquear el semáforo de readtry. Tan pronto como aparezca un escritor, intentará configurar el readtry y colgará allí esperando que el lector actual libere el readtry. Luego, tomará el control del recurso tan pronto como el lector actual termine de leer y bloqueará a todos los lectores futuros. Todos los lectores posteriores colgarán en el semáforo de readtry esperando a que los escritores terminen con el recurso y abran la puerta liberando readtry.
El rmutex y el wmutex se utilizan exactamente de la misma forma que en la primera solución. Su único propósito es evitar condiciones de carrera para los lectores y escritores mientras se encuentran en sus secciones de entrada o salida.
Problema de terceros lectores-escritores
De hecho, las soluciones implícitas en ambos enunciados del problema pueden resultar en inanición: la primera puede matar de hambre a los escritores en la cola, y la segunda puede matar de hambre a los lectores. Por lo tanto, a veces se propone el tercer problema de lectores-escritores , que agrega la restricción de que no se permitirá que ningún hilo se muera de hambre ; es decir, la operación de obtener un bloqueo en los datos compartidos siempre terminará en un período de tiempo limitado. Una solución justa tanto para lectores como para escritores podría ser la siguiente:
int readcount ; // init a 0; número de lectores que acceden actualmente al recurso// todos los semáforos inicializados a 1 recurso semáforo ; // controla el acceso (lectura / escritura) al recursosemáforo rmutex ; // para sincronizar cambios en el recuento de lectura de variables compartidassemáforo serviceQueue ; // JUSTICIA: preserva el orden de las solicitudes (la señalización debe ser FIFO)//LECTORlector () {< Sección ENTRY > serviceQueue . P (); // esperar en la fila para recibir servicio rmutex . P (); // solicitar acceso exclusivo a readcount readcount ++ ; // actualizar el recuento de lectores activos if ( readcount == 1 ) // si soy el primer lector recurso . P (); // solicitar acceso a recursos para lectores (escritores bloqueados) serviceQueue . V (); // dejar que el siguiente en la línea sea atendido rmutex . V (); // liberar acceso a readcount < Sección CRÍTICA >// se realiza la lectura < Sección EXIT > rmutex . P (); // solicitar acceso exclusivo a readcount readcount - ; // actualizar el recuento de lectores activos if ( readcount == 0 ) // si no quedan lectores recurso . V (); // liberar el acceso a los recursos para todos rmutex . V (); // liberar acceso a readcount}//ESCRITORescritor () {< Sección ENTRY > serviceQueue . P (); // esperar en la fila para recibir servicio recurso . P (); // solicita acceso exclusivo al recurso serviceQueue . V (); // dejar que el siguiente en la línea sea atendido < Sección CRÍTICA >// se realiza la escritura < Sección EXIT > recurso . V (); // liberar el acceso a los recursos para el próximo lector / escritor}
Esta solución solo puede satisfacer la condición de que "ningún hilo podrá morir de hambre" si y solo si los semáforos conservan el orden de primero en entrar, primero en salir al bloquear y liberar hilos. De lo contrario, un escritor bloqueado, por ejemplo, puede permanecer bloqueado indefinidamente con un ciclo de otros escritores disminuyendo el semáforo antes de que pueda hacerlo.
Problema de escritor de lector más simple
El problema de lector-escritor más simple que usa solo dos semáforos y no necesita una matriz de lectores para leer los datos en el búfer.
Tenga en cuenta que esta solución se vuelve más simple que el caso general porque se hace equivalente al problema del búfer limitado y, por lo tanto, solo N lectores pueden ingresar en paralelo, siendo N el tamaño del búfer.
Lector
do { esperar ( leer ) ............ leer datos ............ señal ( escribir ) } mientras ( VERDADERO );
Escritor
do { esperar ( escribir ) ............. escribir datos ............. señal ( leer ) } mientras ( VERDADERO );
Algoritmo
- Reader se ejecutará después de Writer debido al semáforo de lectura.
- Writer dejará de escribir cuando el semáforo de escritura llegue a 0.
- El lector dejará de leer cuando el semáforo de lectura llegue a 0.
En el escritor, el valor de escribir semáforo se da para leer el semáforo y en el lector, el valor de leer se da para escribir al finalizar el ciclo.
Ver también
Referencias
- ^ a b Courtois, PJ; Heymans, F .; Parnas, DL (1971). "Control concurrente con" lectores "y" escritores " " (PDF) . Comunicaciones de la ACM . 14 (10): 667–668. doi : 10.1145 / 362759.362813 . S2CID 7540747 .
- ^ Taubenfeld, Gadi (2006). Algoritmos de sincronización y programación concurrente . Educación Pearson. pag. 301.
- Morris JM (1979). Una solución sin hambre al problema de la exclusión mutua. Inf Process Lett 8: 76–80
- Solución justa al problema de lector-escritor-con semáforos solamente. H. Ballhausen, 2003 arXiv : cs / 0303005
- Solución más rápida y justa para el problema del lector-escritor. V. Popov, O. Mazonka 2013 arXiv : 1309.4507