Bloqueos Mortales
description
Transcript of Bloqueos Mortales
Bloqueos Mortales
Cecilia Hernández
2007
Bloqueos Mortales
Definición Un proceso/hebra esta bloqueada cuando esta
esperando por un evento que nunca ocurrirá Un proceso/hebra que esta en sección critica 1
espera por entrar a sección critica 2, mientras otro proceso/hebra esta en sección critica 2 y quiere entrar a sección critica 1
Condiciones bajo las cuales se produce bloqueo mortal
Exclusión mutua: Sólo un proceso a la vez puede usar el recurso
No apropiación: Sistema no puede quitar arbitrariamente recurso a proceso
Retención y espera: Existen procesos que poseen recursos y esperan por otros recursos sin liberar los que tienen
Espera circular: Existe un conjunto de procesos { P0, P1, …, Pn) tales que Pi está esperando por un recurso retenido por Pi+1 para 0<= i<= n, y Pn está esperando recurso que posee P0
Grafo de recursos
P1 P2
R1
R2
Proceso tiene Recurso
Proceso espera Recurso
Bloqueo Mortal ocurre cuando hay un ciclo cerrado en el grafode recursos como se muestra arriba
Grafo de recursos sin ciclo cerrado
P1 P2 P3
R1 R2
R3R4
Hay bloqueo mortalen este grafo?
Grafo de recursos 1
P1 P2 P3
R1 R2
R3
Hay bloqueo mortal en este grafo de recursos?
Grafo de recursos 2
P1 P2
R1
R2
P3
P4
Grafo de recursos conciclo.Hay bloqueo mortal?Por que?
Usando semáforos
Hay bloqueo mortal al invertir operaciones wait sobre semáforosen el consumer? Cuando ocurre?
Productorwhile (true) { /* produce un item en proxProd */ wait(mutex); wait(vacio); buffer[in] = proxProd; in = (in + 1) % N; contador++; signal(mutex); signal(lleno);}
Consumidor
While(true){ wait(lleno); wait(mutex); proxCons = buffer[out]; out = (out + 1) % N; contador--; signal(mutex); signal(vacio); /* consume proxCons */ }
int contador = 0; //indica número de items en bufferchar buffer[N];int in = 0; int out = 0;sem mutex=1; sem vacio = N; sem lleno = 0;
Como enfrentar bloqueos mortales?
Prevención: No permitir que bloqueo mortal ocurra Proceso/Hebra adquiera todos los recursos a
ocupar al inicio• Problemas?
Numerar recursos y procesos/hebras los adquieren en secuencia (implica que pueden obtener algunos antes que los necesiten)
• Por que funciona?• Problemas?
Detección y corrección Periódicamente revisar si hay ciclos y eliminarlos
Caso de Filósofos Comensales
Problema de Filósofos comensales Cada filósofo tiene su plato de arroz, con 5 palitos 5 filósofos se sientan a la mesa. Piensan por un rato y
cuando les da hambre comen Hay sólo 5 palitos en la mesa (cada persona necesita 2
palitos para comer arroz a la manera china) Para poder comer cada filósofo tiene que
obligatoriamente conseguir dos palitos Problema es importante porque introduce posibles
problemas de Deadlock(bloqueo mortal) y Starvation(inanición)
Animación disponible en : http://www.doc.ic.ac.uk/~jnm/book/book_applets/Diners.html
Ilustración
Posible solución usando semáforos
Problemas Produce deadlock Si todos simultaneamente toman
palito izquierdo, no pueden tomar el palito derecho pues ya esta tomado por su vecino
Posibles soluciones Solo 4 filósofos puedan comer a la
vez Uno de los filósofos toma primero el
tenedor derecho y luego el izquierdo Permitir que un filósofo tome sus
tenedores sólo si ambos están disponibles (y hacerlo dentro de sección crítica)
Nota: cuando se evita bloqueo tambien se tiene que tener en cuenta que exista condicion en la cual algun filósofo de muera de hambre
semaforo palito[5];
do {…pensar();…wait(palito[i]);wait(palito[(i+1)%5];….comer();…signal(palito[i]);signal(palito[(i+1)%5]);
} while(1);