En informática , los problemas de lectores-escritores son ejemplos de un problema informático común en concurrencia . [1] Existen al menos tres variaciones de los problemas, que tratan 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á escribiendo en él. (En particular, queremos evitar que más de un subproceso 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 lectura-escritura fue formulado y resuelto por primera vez por Courtois et al. [2] [3]
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 no pueden acceder a los datos dos subprocesos al mismo tiempo. Sin embargo, esta solución no es ó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 terminara antes de comenzar su propia operación de lectura; en cambio, se debería 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. Esta es la motivación para el primer problema de lectores-escritores , en el que se agrega la restricción de que no se mantendrá a ningún lector esperando si el recurso compartido está abierto actualmente para lectura. Esto también se llama preferencia de lectores , con su solución:
recurso semáforo = 1 ; semáforo rmutex = 1 ; recuento de lectura = 0 ;/* resource.P() es equivalente a esperar(recurso) resource.V() es equivalente a signal(resource) rmutex.P() es equivalente a wait(rmutex) rmutex.V() es equivalente a signal(rmutex)*/escritor () { recurso . P (); //Bloquear el archivo compartido para un escritor < Sección CRÍTICA > // La escritura está hecha < Sección SALIR > resource . V (); //Libera el archivo compartido para que lo usen otros lectores. Se permite el uso de escritores si no hay lectores que lo soliciten. }lector () { rmutex . P (); //Asegúrese de que ningún otro lector pueda ejecutar la sección <Entry> mientras usted esté en ella < Sección CRÍTICA > readcount ++ ; //Indica que eres un lector que intenta ingresar a la Sección Crítica if ( readcount == 1 ) //Comprueba si eres el primer lector que intenta ingresar a CS resource . P (); //Si eres el primer lector, bloquea el recurso para que los escritores no puedan acceder a él. El recurso permanece reservado para los lectores posteriores < SALIR DE LA SECCIÓN CRÍTICA > rmutex . V (); //Liberar // Hacer la lectura rmutex . P (); //Asegúrese de que ningún otro lector pueda ejecutar la sección <Exit> mientras usted 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 resource . V (); //Si eres el último lector, puedes desbloquear el recurso. Esto lo pone a disposición de los escritores. < SALIR DE LA SECCIÓN CRÍTICA > rmutex . V (); //Liberar }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 necesidad de volver a bloquearlo.
Antes de entrar en la sección crítica , cada nuevo lector debe pasar por la sección de entrada. Sin embargo, solo puede haber un único 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 activan simultáneamente e intentan entrar en la sección crítica; sin más restricciones, el comportamiento no es determinista. Por ejemplo, dos lectores incrementan el recuento de lecturas al mismo tiempo y ambos intentan bloquear el recurso, lo que hace que un lector se bloquee). Para lograr esto, cada lector que ingrese a la <Sección de ENTRADA> bloqueará la <Sección de ENTRADA> para sí mismo hasta que termine con ella. En este punto, los lectores no están bloqueando el recurso. Solo están bloqueando la sección de entrada para que ningún otro lector pueda ingresar mientras estén en ella. Una vez que el lector termina de ejecutar la sección de entrada, la desbloqueará señalando el mutex. Señalarlo es equivalente a: mutex.V() en el código anterior. Lo mismo es válido para la <Sección de SALIDA>. No puede haber más de un lector a la vez en la sección de salida, por lo tanto, cada lector debe reclamar y bloquear la sección de Salida para sí mismo antes de usarla.
Una vez que el primer lector se encuentre en la sección de entrada, bloqueará el recurso. Al hacerlo, 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, dejándolo así disponible para 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 dejarlos sin recursos. 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 liberará el último lector. Por lo tanto, esta solución no satisface la equidad.
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, antes que W ; si eso sucediera con suficiente frecuencia, W se quedaría sin recursos . En cambio, W debería comenzar lo antes posible. Esta 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 de lo absolutamente necesario . Esto también se llama preferencia de escritores .
Una solución al escenario de preferencia de los escritores es: [2]
int recuento de lecturas , recuento de escrituras ; //(valor inicial = 0) semáforo rmutex , wmutex , readTry , recurso ; //(valor inicial = 1) //LECTORlector () { < Sección ENTRADA > readTry . P (); //Indica que un lector está intentando ingresar rmutex . P (); //bloquea la sección de entrada para evitar una condición de carrera con otros lectores readcount ++ ; //regístrate como lector if ( readcount == 1 ) //comprueba si eres el primer lector recurso . P (); //si eres el primer lector, bloquea el recurso rmutex . V (); //liberar la sección de entrada para otros lectores readTry . V (); //indica que ya no intentas acceder al recurso < Sección CRÍTICA > //se realiza la lectura< Sección SALIR > rmutex . P (); //reservar sección de salida - evita condiciones de carrera con los lectores readcount -- ; //indica que estás saliendo if ( readcount == 0 ) //comprueba si eres el último lector que sale recurso . V (); //si es el último, debe liberar el recurso bloqueado rmutex . V (); //libera la sección de salida para otros lectores }//ESCRITORescritor () { < Sección ENTRADA > wmutex . P (); //reserva la sección de entrada para escritores - evita condiciones de carrera writecount ++ ; //regístrate como escritor ingresando if ( writecount == 1 ) //comprueba si eres el primer escritor readTry . P (); //si eres el primero, debes bloquear a los lectores para evitar que intenten ingresar a CS wmutex . V (); //liberar sección de entrada 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 (); //archivo de liberación < Sección SALIR > wmutex . P (); //reservar sección de salida writecount -- ; //indica que estás saliendo if ( writecount == 0 ) //comprueba si eres el último escritor readTry . V (); //si eres el último escritor, debes desbloquear a los lectores. Les permite intentar ingresar a 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á el 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 de readtry, abriendo así la puerta para que los lectores intenten leer.
Ningún lector puede acceder a la sección de entrada si el semáforo de readtry ha sido establecido previamente por un escritor. El lector debe esperar a que el último escritor desbloquee el recurso y los semáforos de readtry. Por otro lado, si un lector en particular ha bloqueado el semáforo de readtry, esto indicará a cualquier escritor concurrente potencial 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 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 autor 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 readtry, lo que solo puede hacer uno de ellos a la vez.
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 se quedarán colgados en el semáforo de lectura esperando que los escritores terminen con el recurso y abran la puerta liberando la lectura.
Los rmutex y wmutex se utilizan exactamente de la misma manera que en la primera solución. Su único propósito es evitar condiciones de carrera en los lectores y escritores mientras se encuentran en sus secciones de entrada o salida.
De hecho, las soluciones implícitas en ambos enunciados del problema pueden dar lugar a una situación de inanición: la primera puede dejar sin recursos a los escritores de la cola, y la segunda puede dejar sin recursos a los lectores. Por lo tanto, a veces se propone el tercer problema de lectores-escritores , que añade la restricción de que no se debe permitir que ningún hilo se quede sin recursos ; es decir, la operación de obtener un bloqueo de los datos compartidos siempre terminará en un tiempo limitado. Una solución justa tanto para los lectores como para los escritores podría ser la siguiente:
int readcount ; // inicializar a 0; número de lectores que actualmente acceden al recurso // todos los semáforos se inicializan en 1recurso semáforo ; // controla el acceso (lectura/escritura) al recurso. Semáforo binario. semáforo rmutex ; // para sincronizar cambios en la variable compartida readcount semáforo serviceQueue ; // IMPARCIALIDAD: conserva el orden de las solicitudes (la señalización debe ser FIFO) //LECTORlector () { < Sección ENTRADA > serviceQueue . P (); // esperar en la cola para ser atendido rmutex . P (); // solicitar acceso exclusivo a readcount readcount ++ ; // actualiza el recuento de lectores activos if ( readcount == 1 ) // si soy el primer lector recurso . P (); // solicitar acceso al recurso para lectores (escritores bloqueados) serviceQueue . V (); // permite que se atienda el siguiente en la línea rmutex . V (); // liberar acceso a readcount < Sección CRÍTICA > //se realiza la lectura < Sección SALIR > rmutex . P (); // solicitar acceso exclusivo a readcount readcount -- ; // actualiza el recuento de lectores activos if ( readcount == 0 ) // si no quedan lectores recurso . V (); // liberar acceso al recurso para todos rmutex . V (); // liberar acceso a readcount }//ESCRITORescritor () { < Sección ENTRADA > serviceQueue . P (); // esperar en la cola para ser atendido recurso . P (); // solicitar acceso exclusivo al recurso serviceQueue . V (); // permite que se atienda el siguiente en la línea < Sección CRÍTICA > // se realiza la escritura < Sección SALIR > recurso . V (); // liberar acceso al recurso para el próximo lector/escritor }Esta solución sólo puede satisfacer la condición de que "no se permitirá que ningún subproceso se quede sin energía" si y sólo si los semáforos conservan el orden de primero en entrar, primero en salir al bloquear y liberar subprocesos. De lo contrario, un escritor bloqueado, por ejemplo, puede permanecer bloqueado indefinidamente con un ciclo de otros escritores que decrementen el semáforo antes de que pueda hacerlo.
El problema de lector-escritor más simple que utiliza 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 es más simple que el caso general porque se hace equivalente al problema del búfer acotado y, por lo tanto, solo N lectores pueden ingresar en paralelo, siendo N el tamaño del búfer.
hacer { esperar ( leer ) ............ leyendo datos ............ señal ( escribir ) } mientras ( VERDADERO ); hacer { esperar ( escribir ) ............. escribiendo datos ............. señal ( leer ) } mientras ( VERDADERO ); En el escritor, el valor del semáforo de escritura se da al semáforo de lectura y en el lector, el valor de lectura se da al semáforo de escritura al completarse el bucle.