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
Proceso tiene Recurso
R1
Proceso espera Recurso
P1
P2
R2
Bloqueo Mortal ocurre cuando hay un ciclo cerrado en el grafo
de recursos como se muestra arriba
Grafo de recursos sin ciclo cerrado
R1
P1
R3
R2
Hay bloqueo mortal
en este grafo?
P3
P2
R4
Grafo de recursos 1
R1
R2
Hay bloqueo mortal en este
grafo de recursos?
P1
R3
P2
P3
Grafo de recursos 2
R1
P1
P3
P2
R2
P4
Grafo de recursos con
ciclo.
Hay bloqueo mortal?
Por que?
Usando semáforos
int contador = 0; //indica número de items en buffer
char buffer[N];
int in = 0; int out = 0;
sem mutex=1; sem vacio = N; sem lleno = 0;
Productor
while (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 */
}
Hay bloqueo mortal al invertir operaciones wait sobre semáforos
en el consumer? Cuando ocurre?
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
semaforo palito[5];

Problemas


do {
Produce deadlock
Si todos simultaneamente toman
palito izquierdo, no pueden tomar
el palito derecho pues ya esta
tomado por su vecino
…
pensar();
 Posibles soluciones
…
 Solo 4 filósofos puedan comer a
la vez
wait(palito[i]);
 Uno de los filósofos toma primero
wait(palito[(i+1)%5];
el tenedor derecho y luego el
….
izquierdo
comer();
 Permitir que un filósofo tome sus
…
tenedores sólo si ambos están
signal(palito[i]);
disponibles (y hacerlo dentro de
sección crítica)
signal(palito[(i+1)%5]);
 Nota: cuando se evita bloqueo
} while(1);
tambien se tiene que tener en
cuenta que exista condicion en la
cual algun filósofo de muera de
hambre
Descargar

Bloqueos Mortales