Sistemas Operativos 2021

Clase 7

Bloqueos mutuos (Deadlocks)

Ing. Juan Manuel Calvo

Bloqueos (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 momento, el proceso entra en un
estado de espera.

A veces, un proceso en espera nunca más puede cambiar de estado, porque los
recursos que ha solicitado están en manos de otros procesos, los cuales están
esperando que el proceso haga una determinada acción.

Esta situación se llama un bloqueo (Deadlock).

Ley aprobada a principios del siglo XX

"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:
 Dispositivo de medios removibles ( drive DVD/Blu-Ray, pendrive)
 Registro de una base de datos
 Variable compartida entre hilos
 Dispositivos de hardware: Procesadores, memoria, placas de red.
Bloqueos mutuos 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 bloqueo mutuo 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
generalmente no tienen
facilidades de prevención de
bloqueos mutuos y sigue
siendo responsabilidad de los
programadores asegurarse
de que diseñen programas
libres de bloqueos mutuos.
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 los bloqueos involucran 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
typedef int semaphore;
semaphore resource1;
typedef int semaphore;
semaphore resource2;
semaphore resource1;
void processA(void) {
void processA(void) down(&resource1);
{ down(&resource2);
down(&resource1); use both resources( );
use resource1( ); up(&resource2);
up(&resource1); up(&resource1);
} }

Caso un recurso Caso dos recursos

Libre de bloqueos o con bloqueo potencial
typedef int semaphore; typedef int semaphore;
semaphore resource1; semaphore resource1;
semaphore resource2; semaphore resource2;

void processA(void) { 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);
} }
Código libre de bloqueos Código con un potencial bloqueo
Livelock (bloqueo activo)


El bloqueo activo se produce cuando un hilo intenta continuamente una
acción que continuamente falla.
 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.
Las cuatro precondiciones para un bloqueo mutuo


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 de bloqueo mútuo

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 bloqueos mutuos 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 usarlo.
 dentro del sistema operativo, bases de datos, sistemas
transaccionales.
2: Prevenir el problema


2a: solución a medida
 usa el ingenio par descubrir los probables bloqueos
 solo funciona para problemas simples

2b: busqueda exaustiva de todos los posibles estados
 recorrer cada posible estado, buscando los bloqueos
 exponencial, crece rápidamente

En general preferiremos algo más sistemático.
3: Detección y recuperación


cuando nos damos cuenta que ha ocurrido un bloqueo mutuo,
comenzamos a matar procesos hasta que las cosas comiencen a moverse
nuevamente.

Tenemos que ser cuidadosos que los procesos matados puedan ser
reinicializados o repetidos seguramente.

Si no somos cuidadosos puede haber que rebootear el sistema operativo.

También preferiremos algo más sistemático
Prevención de bloqueos mutuos


¡parece fácil!
 solo hay que eliminar una cualquiera de las cuatro
precondiciones para el bloqueo mutuo

pero eliminar las precondiciones es habitualmente dificil

A veces la espera circular puede ser eliminada por medio de la
asignación jerárquica.
Eliminando precondiciones: 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
Eliminando precondiciones: sacarle recursos


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
 la recuperación es complicada cuando se saca un recurso
Eliminando precondiciones: 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 ocasionalmente en bases de datos
Eliminación de precondiciones: 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) { /* philosopher i loop */

DOWN(chopstick[i]);
DOWN(chopstick[i+1 mod N]);
eat();
UP(chopstick[i]);
UP(chopstick[i+1 mod N]);
lookforwork()
complain();
}

Si a este código le agregamos la condición que los semáforos se adquieran en orden numérico
solucionamos los bloqueos ( pero no la inanición)
Detección de bloqueos mutuos

Aún si no podemos prevenir los bloqueos mutuos, 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 "undoing" (deshacer) lo que nosotros hicimos
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 bloqueos
mutuos
 Con lazos == hay bloqueos mutuos

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 los bloqueos


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.