Sistemas Operativos 2022 - Clase 7 - PDF

Sistemas Operativos 2022 Clase 7 U3 Interbloqueos (Deadlocks) I Ing. Juan Manuel Calvo  Interbloqueos (Deadlocks) En un entorno de multiprogramación – varios procesos compitiendo por un número finito de recursos. Un proceso solicita recursos; – si los recursos...

Sistemas Operativos 2022 Clase 7 U3 Interbloqueos (Deadlocks) I Ing. Juan Manuel Calvo  Interbloqueos (Deadlocks) En un entorno de multiprogramación – varios procesos compitiendo por un número finito de recursos. Un proceso solicita recursos; – si los recursos no están disponibles en ese asignado a Recurso 1 momento, el proceso se bloquea esperando por A veces, un proceso bloqueado nunca más puede cambiar de estado, porque los recursos Proceso 1 Proceso 2 que ha solicitado están en manos de otros procesos, los cuales están esperando que el proceso bloqueado realice una determinada esperando por asignado a Recurso 2 acción. – Esta situación se llama un interbloqueo (Deadlock).  A principios del siglo XX se aprobó esta ley "Cuando dos trenes se aproximen en un cruce, ambos se detendrán por completo y ninguno volverá a arrancar hasta que el otro se haya ido".  Recursos ¿Qué es un recurso? – Un recurso es cualquier cosa que pueda ser utilizada por un solo proceso en cualquier instante de tiempo. Ejemplos: – Registro de una base de datos – Variable compartida entre hilos – Dispositivos de hardware: Procesadores, memoria, placas de red. – Dispositivo de medios removibles ( drive DVD/Blu-Ray, pendrive)  Interbloqueos y asignación de recursos En un entorno multiprogramación donde: – Recursos finitos, cada uno de los cuales puede ser asignado a un número límitado de procesos/hilos (habitualmente a uno solo) – Los procesos pueden pedir varios recursos ○ varios a la vez o de a uno ○ se les permite obtener nuevos recursos además de los obtenidos ○ se bloquea hasta que el recurso solicitado esté disponible – los procesos pueden liberar los recursos cuando terminaron de utilizarlos. Un interbloqueo es una situación donde un conjunto de procesos bloqueados están esperando por recursos de forma que no hay manera de satisfacer a ninguno de sus requerimientos. – Aún si todos los procesos no bloqueados liberan los recursos que tienen.  Los SO no incluyen manejo de bloqueos Los sistemas operativos no tienen generalmente facilidades de prevención de interbloqueos Es responsabilidad de los programadores asegurarse diseñar programas libres de interbloqueos.  Recursos Nos interesan aquellos recursos a los cuales el sistema operativo le da acceso exclusivo a un proceso. Un recurso puede ser un dispositivo de hardware (Ej: lectora CD) o algo de información (Ej: registro en una base de datos). Algunos recursos pueden tener varias instancias disponibles, cualquiera de estas puede usarse para cumplir una solicitud.  Recursos expropiables y no expropiables Preemptable and nonpreemptable resources Un recurso expropiable (preemptable) se le puede sacar a un proceso sin efectos dañinos. Un recurso no expropiable (nonpreemptable) no se puede sacar sin provocar una falla. En general en los bloqueos están involucrados recursos no expropiables.  Uso de recursos Un proceso utiliza un recurso con la siguiente secuencia: 1) Solicitud El proceso solicita el recurso. Si el pedido no se puede otorgar inmediatamente (por ejemplo, si el recurso está siendo utilizado por otro proceso), el proceso solicitante debe esperar hasta que pueda adquirir el recurso. 2) Uso. El proceso puede operar en el recurso (por ejemplo, si el recurso es una impresora, el proceso puede imprimir en la impresora). 3) Liberación. El proceso libera el recurso.  Adquisición de recursos Un sólo recurso Dos recursos typedef int semaphore; typedef int semaphore; semaphore resource1; semaphore resource1; semaphore resource2; void processA(void) void processA(void) { { down(&resource1); down(&resource2); down(&resource1); use both resources( ); use resource1( ); up(&resource2); up(&resource1); up(&resource1); } }  Libre de bloqueos o con bloqueo potencial Código typedef int semaphore; Código typedef int semaphore; semaphore resource1; semaphore resource1; libre de semaphore resource2; con un semaphore resource2; bloqueos bloqueo void processA(void) { potencial void processA(void) { down(&resource1); down(&resource1); down(&resource2); down(&resource2); use both resources(); use both resources(); up(&resource2); up(&resource2); up(&resource1); up(&resource1); } } void processB(void) { void processB(void) { down(&resource1); down(&resource2); down(&resource2); down(&resource1); use both resources(); use both resources(); up(&resource2); up(&resource1); up(&resource1); up(&resource2); } }  Livelock (bloqueo activo) El bloqueo activo se produce cuando un hilo intenta continuamente una acción que falla todas las veces. – Puede ser evitado repitiendo la acción después de una demora aleatoria.  Sistema bloqueado Un conjunto de procesos está bloqueado si cada proceso del conjunto está esperando por un evento que solo otro proceso del conjunto puede provocarlo. – Todos los procesos están esperando. – Ninguno de ellos causará ninguno de los eventos que podrían despertar a cualquiera de los otros miembros del conjunto. – Todos los procesos continúan esperando para siempre. – En general, el evento que cada proceso está esperando es la liberación de algún recurso que actualmente posee otro miembro del conjunto.  Interbloqueo - cuatro condiciones necesarias  Estas cuatro condiciones son necesarias para que se produzca un interbloqueo: Exclusión mutua. los recursos que tiene un proceso no pueden ser usados simultaneamente por otro. No apropiación, no es posible sacarle un recurso a quien lo tiene, los procesos se quedan con los recursos hasta que ellos mismos los liberan. Retención y espera, los procesos pueden requerir recursos adicionales y bloquearse esperando por ellos. Espera circular, cadena circular de dos o más procesos/hilos, cada uno esperando por un recurso que lo tiene el próximo de la cadena.  El secreto para prevenir bloqueos mutuos Consiste simplemente eliminar cualquiera de las cuatro precondiciones. – No interesa cual ○ Entonces el bloqueo no puede suceder – Problema solucionado!  Soluciones al problema del interbloqueo Tres maneras posibles: Ignorar el problema por completo y pretender que los interbloqueos nunca ocurren en el sistema. Usar un protocolo para prevenir o evitar interbloqueos, asegurando que el sistema nunca entre en un estado de interbloqueo. Permitir que el sistema entre en un estado de interbloqueo, detectarlo, y recuperarlo.  1: Ignorar el problema  Los interbloqueos no siempre son malos  algunas veces podemos convivir con la posibilidad que se produzcan  cuando algo se cuelge, simplemente lo reiniciamos.  adecuado para muchas aplicaciones  pero desafortunadamente, algunas veces no es posible.  dentro del sistema operativo, bases de datos, sistemas transaccionales.  2: Prevenir el problema La prevención se basa en: – Los interbloqueos son imposibles si podemos asegurar que una de la condiciones nunca se cumpla  3: Detección y recuperación  Cuando nos damos cuenta que ha ocurrido un interbloqueo, tomamos alguna acción para que el sistema comience a funcionar nuevamente  Prevención: eliminando la exclusión mutua  Exclusión mutua: recursos mantenidos por un procesos no pueden ser usado simultáneamente por otro.  Esto es dificil de evitar, normalmente la exclusión mutua se necesita o no.  Ej: Si todos los procesos acceden a un archivo en modo de lectura solamente se puede permitir que lo abran simultaneamente.  La exclusión mutua puede ser evitada haciendo el uso del recurso "atómico"  Usar el recurso en una ráfaga de acceso exclusivo  Spooling.  Prevención: sacarle recursos  Normalmete los recusos no se puede sacar: los procesos se quedan con los recursos hasta que ellos mismos los liberan.  Es posible que se pueda eliminar con alguna clase de política.  Ej: si un proceso de alta prioridad quiere un recurso, lo obtiene y el recurso es retirado del proceso de baja prioridad.  En la práctica no es fácil implementarlo  Cuando se saca un recurso la recuperación suele ser complicada.  Prevención: eliminando la retención y espera  Retención y espera: se pueden acumular recursos, me bloqueo esperando mientras mantengo otros.  Puede ser eliminada requiriendo que todo el conjunto requerido de recursos sea pedido de una sola vez.  Debe liberar todo para pedir un nuevo conjunto  Ineficiente  ¿y como hacemos con los recursos que no pueden identificarse de antemano? (Ej: nombres de archivos)  Eliminación de retención y espera: Lockeo en dos fases  Los procesos manejan los recursos en dos fases:  Fase 1: lockeo  intentan adquirir los locks  si cualquier intento falla, liberar todo y comenzar nuevamente.  Fase 2: uso usar cualquier recurso solamente después que se adquirieron todos los locks  liberar los locks cuando se termina  Seguro, pero ineficiente para muchas aplicaciones  Presenta problemas similares a los spin locks  Usado en bases de datos  Precención: eliminando la espera circular  Espera circular: cadena circular de procesos, cada uno esperando por un recurso que tiene el próximo proceso en la cadena.  Debe encontrarse la manera de organizar los pedidos tal que se rompan los ciclos.  Idea central: asignación jerárquica.  numerar los recursos; solo permitir obtener recursos con numeración más alta que la que se tiene.  requiere encontrar la manera de numerar los recursos.  Asignación jerarquica en los filósofos La solución obvia es representar cada tenedor por un semáforo: semaphore chopstik[N] DOWN antes de tomarlo y UP después de usarlo. while (TRUE) { DOWN(chopstick[i]); DOWN(chopstick[(i+1) mod N]); eat(); UP(chopstick[i]); UP(chopstick[(i+1) mod N]); think(); Código } Si a este código le agregamos la condición que los semáforos se adquieran en orden numérico – Solucionamos los bloqueos ( pero puede haber inanición)  Detección de interbloqueos  Aún si no podemos prevenir los interbloqueos, quizás podamos detectarlos sistemáticamente.  Además vamos a necesitar un esquema para la recuperación  O sea:  algoritmos para detectar los bloqueos mutuos  teoría de los grafos  Una manera de deshacer (undoing) lo hecho antes que ocurriera el bloqueo  Revertir la transacción ("Rollback”). Grafos Pedido de un recurso El proceso tiene un recurso Código con bloqueo potencial (1) typedef int semaphore; semaphore resource1; semaphore resource2; void processA(void) { down(&resource1); down(&resource2); use both resources( ); up(&resource2); up(&resource1); } void processB(void) { down(&resource2); down(&resource1); use both resources( ); up(&resource1); up(&resource2); } Código con bloqueo potencial (2) typedef int semaphore; semaphore resource1; semaphore resource2; void processA(void) { down(&resource1); down(&resource2); use both resources( ); up(&resource2); up(&resource1); } void processB(void) { down(&resource2); down(&resource1); use both resources( ); up(&resource1); up(&resource2); } Código con bloqueo potencial (3) typedef int semaphore; semaphore resource1; semaphore resource2; void processA(void) { down(&resource1); down(&resource2); use both resources( ); up(&resource2); up(&resource1); } void processB(void) { down(&resource2); down(&resource1); use both resources( ); up(&resource1); up(&resource2); } Código con bloqueo potencial (4) typedef int semaphore; semaphore resource1; semaphore resource2; void processA(void) { down(&resource1); down(&resource2); use both resources( ); up(&resource2); up(&resource1); } void processB(void) { down(&resource2); down(&resource1); use both resources( ); up(&resource1); up(&resource2); } Recursos con varias instancias Recursos con varias instancias  ¿Hay buenos algoritmos de detección de bloqueos?  Idea básica: representar la asignación de recursos como un grafo y buscar los lazos.  Sin lazos == no hay interbloqueos  Con lazos == hay interbloqueos  Detección de lazos => problema típico de la teoría de grafos.  ¿puede ser hecho eficientemente?  ¿cuando probar?  Despues de la detección: recuperación de interbloqueos  Quitar el recurso ( preemption)  Sacarle el recurso a quien lo tiene  frecuentemente imposible  Revertir la transacción (Rollback)  Puntos de chequeo periódicos guardando los estados  Volver al estado anterior antes de tomar el recurso  Usado en sistemas de bases de datos  Matar los procesos  Crudo pero simple  Ir matando los procesos hasta que el lazo se rompa.