INTERBLOQUEOS

KMC © 2019

INTERBLOQUEOS
• Modelo de Sistema
• Caracterización de Interbloqueos
• Métodos para el Manejo de Interbloqueos
• Prevención de Interbloqueos
• Evasión de Interbloqueos
• Detección de Interbloqueos
• Recuperación de Interbloqueos

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

1
EL PROBLEMA DE INTERBLOQUEO
• Un conjunto de procesos bloqueados, cada uno contiene
recursos y espera para adquirir otro recurso mantenido por otro
proceso en el conjunto.
• Ejemplo
• Un sistema tiene 2 discos.
• P1 y P2 cada uno tiene un disco y necesita otro.
• Ejemplo
• semáforos A y B, inicializados a 1
P0 P1
wait (A); wait(B)
wait (B); wait(A)

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

EJEMPLO DEL CRUCE EN EL PUENTE

• Tránsito en una sola dirección.

• Cada sección de un puente puede ser vista como un
recurso.
• Si un interbloqueo ocurre, puede ser resuelto si cada auto
retrocede (se apropia de recursos y rollback).
• Varios autos pueden retroceder si un interbloqueo
occurre.
• Es posible la inanición.
KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

2
EJEMPLO DE INTERBLOQUEOS
Progreso
Proceso Q 1 2

Liberar A
Requiere PyQ
A requieren A
Liberar B

Obtener A
3 Deadlock
PyQ
Requiere
B requieren B 5
4
Obtener B 6

Obtener A Obtener B Liberar A Liberar B Progreso

Proceso P

Requiere A
KMC © 2019 Requiere B
SISTEMAS OPERATIVOS - INTERBLOQUEOS

MODELO DE SISTEMA
• Tipos de Recursos R1, R2, . . ., Rm
ciclos CPU, espacio de memoria, dispositivos E/S
• Cada recurso tipo Ri tiene Wi instancias.
• Cada proceso utiliza un recurso como sigue:
• requerimiento
• uso Uso
• liberalización correcto

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

3
CARACTERIZACIÓN DE INTERBLOQUEOS
El Interbloqueo puede alcanzarse si se cumplen las
cuatro condiciones simultáneamente.
• Exclusión Mutua : solo un proceso a la vez puede usar un recurso.
• Retener y Esperar: un proceso mantiene al menos un recurso y está
esperando adquirir recursos adicionales tenidos por otros procesos.
• No Apropiación: Un recurso puede ser liberado solo
voluntariamente por el proceso que lo tiene, después que el proceso
ha completado su tarea.
• Espera Circular: existe un conjunto {P0, P1, …, Pn} de procesos
esperando tal que P0 está esperando por un recurso que es retenido
por P1, P1 está esperando por un recurso que es retenido por P2, …,
Pn–1 está esperando por un recurso que es retenido por Pn, y Pn está
esperando por un recurso que es retenido por P0.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

GRAFO DE ALOCACIÓN DE RECURSOS

Un conjunto de vértices V y un conjunto de lados E.

• V está particionado en dos tipos:

• P = {P1, P2, …, Pn}, el conjunto consistente de todos los
procesos en el sistema . Proceso
• R = {R1, R2, …, Rm}, el conjunto consistente de todos los
recursos tipo en el sistema. Recurso
• lado de requerimiento – lado dirigido Pi  Rj
Pi
• lado de asignamiento – lado dirigido Rj  Pi Rj

Pi
Rj

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

4
EJEMPLOS: GRAFO DE ALOCACIÓN DE
RECURSOS

a) Grafo sin ciclo

b) Grafo con interbloqueo

c) Grafo con ciclo sin interbloqueo

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

CUESTIONES BÁSICAS
• Si un grafo no contiene ciclos  no hay interbloqueo.
• Si un grafo contiene un ciclo 
• Si hay una sola instancia por tipo de recurso, entonces hay
interbloqueo.
• Si hay varias instancias por tipo de recurso, hay posibilidad de
interbloqueo.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

5
MÉTODOS PARA MANEJO DE INTERBLOQUEOS
• Asegure que el sistema no entrará nunca estado de
interbloqueo.
• Permitir al sistema entrar en un estado de interbloqueo y luego
recuperarse.
• Ignore el problema y pretenda que el interbloqueo nunca
ocurrió en el sistema; usado en la mayoría de los sistemas
operativos incluído UNIX, Linux, Windows.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

ESTRATEGIAS PARA MANEJO DE INTERBLOQUEOS

Las estrategias utilizadas para atacar el problema de
interbloqueos se establecen en tres niveles de acción: antes que
suceda, cuando los procesos están corriendo o con hechos
consumados.
Estas estrategias son:

 Prevención
 Evasión
 Detección

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

6
PREVENCIÓN DE INTERBLOQUEOS
Restringir los modos en que se pueden hacer los
requerimientos
• Exclusión Mutua – no requerido para recursos compartidos;
debe mantenerse para recursos no compartidos.
• Mantener y Esperar – debe garantizar que siempre que un
proceso requiera un recurso no mantiene otros.
• No Apropiación - Si un proceso que mantiene algunos
recursos requiere otro recurso, no le puede ser
inmediatamente alocado, entonces todos los recursos
mantenidos son liberados.
• Espera Circular – impone un orden total de todos los tipos
de recursos, y requiere que cada proceso requiera recursos
en un orden creciente de enumeración.
KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

EVASIÓN DE INTERBLOQUEOS
Requiere que el sistema tenga disponible alguna
información adicional a priori .
• El modelo más simple y útil requiere que cada proceso
declare el máximo número de recursos de cada tipo que
puede necesitar.
• El algoritmo de evasión de interbloqueos dinámicamente
examina el estado de alocación de recursos para asegurar que
no puede haber una condición de espera circular.
• El estado de alocación de recursos está definido por el
número de recursos disponibles y alocados, y las máximas
demandas de los procesos.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

7
ESTADO SEGURO
• Cuando un proceso requiere un recurso disponible, el algoritmo debe
decidir si su alocación inmediata deja al sistema en un estado seguro.
• El sistema está en un estado seguro si existe una secuencia segura de
ejecución de todos los procesos.
• La secuencia <P1, P2, …, Pn> es segura si por cada Pi, los recursos que Pi
puede aún requerir pueden ser satisfechos por recursos disponibles
corrientes mas los recursos mantenidos por todos los Pj, con j<i.
• Si los recursos que Pi necesita no están inmediatamente
disponibles, entonces Pi puede esperar hasta que todos los Pj hayan
finalizado.
• Cuando Pj finaliza, Pi obtiene los recursos necesitados, ejecuta,
retorna los recursos alocados, y termina.
• Cuando Pi termina, Pi+1 puede obtener los recursos que necesita, y
así sucesivamente.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

CUESTIONES BÁSICAS
• Si un sistema está en un estado seguro  no hay interbloqueo.
• Si un sistema está en un estado inseguro  posibilidad de
interbloqueo.
• Evasión  asegura que el sistema nunca va a entrar en un
estado inseguro.

INSEGURO
SEGURO

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

8
ALGORITMOS DE EVASIÓN
• Si sólo hay una instancia de un tipo de recurso. Use un grafo de
alocación de recursos.

• Para múltiple instancias de un tipo de recursos. Use el algoritmo

del banquero.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

ALGORITMOS DE EVASIÓN
• Ejemplo simple de evasión:
Considerar 12 recursos iguales y 3 procesos con las siguientes
necesidades máximas y alocación corriente.

Max Aloc
P0 10 5
P1 4 2
P2 9 2 probar P2 con alocación=3

Sec. segura <P1,P0,P2> Sec. insegura <P1,……..>

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

9
ALGORITMO DEL BANQUERO
• Múltiples instancias.
• Cada proceso debe reclamar a priori el máximo uso.
• Cuando un proceso requiere un recurso puede tener que
esperar.
• Cuando un proceso obtiene todos sus recursos debe retornarlos
en una cantidad finita de tiempo.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

ESTRUCTURA DE DATOS DEL ALGORITMO DEL

BANQUERO
Sea n = número de procesos, y m = número de tipos de
recursos.
• Disponible: Vector de longitud m. Si disponible[j] = k, hay k
instancias del tipo de recurso Rj disponible.
• Max: matriz n x m. Si Max[i,j] = k, entonces el proceso Pi puede
requerir a lo sumo k instancias del recurso de tipo Rj.
• Alocación: matriz n x m. Si Alocación[i,j] = k entonces Pi tiene
alocadas k instancias de Rj.
• Necesidad: matriz n x m. Si Necesidad[i,j] = k, entonces Pi puede
necesitar k instancias más de Rj para completar su tarea.

Necesidad[i,j] = Max[i,j] – Alocación[i,j].

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

10
ALGORITMO DE SEGURIDAD
1. Sean Trab y Final vectores de longitud m y n,
respectivamente. Se inicializan:
Trab := Disponible
Final[i] = falso para i - 1,3, …, n.
2.Encuentre un i tal que cumplan:
(a) Final[i] = falso
(b) Necesidadi  Trab
Si tal i no existe, vaya al paso 4.
3. Trab := Trab + Alocacióni
Final[i] := verdadero
vaya al paso 2.
4.Si Final[i] = verdadero para todo i, entonces el sistema está en
un estado seguro.
KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

ALGORITMO DE REQUERIMIENTO DE RECURSOS

PARA EL PROCESO PI
Requesti = vector de requerimento para el proceso Pi.
Si Requesti [j] = k entonces el proceso Pi quiere k instancias del tipo de
recurso Rj.
1. Si Requesti  Necesidadi vaya al paso 2. Sino condición de error,
dado que el proceso ha excedido su máximo.
2. Si Requesti  Disponible, vaya al paso 3. Sino Pi debe esperar,
dado que los recursos no están disponibles.
3. Se simula alocar los recursos requeridos Pi modificando el estado
como sigue:
Disponible := Disponible - Requesti;
Alocacióni := Alocacióni + Requesti;
Necesidadi := Necesidadi – Requesti;;
• Si seguro  los recursos son alocados a Pi.
• Si inseguro  Pi debe esperar, y es restaurado el viejo estado de
alocación de recursos
KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

11
EJEMPLO DEL ALGORITMO DEL BANQUERO
• 5 procesos P0 a P4; 3 recursos tipo A (10 instancias),
B (5 instancias), y C (7 instancias).
• Instantánea en el instante T0:
Necesidad
Alocación Max Disponible
ABC
ABC ABC ABC
P0 010 753 332 743
P1 200 322 122
P2 302 902 600
P3 211 222 011
P4 002 433 431
El sistema está en un estado seguro dado que la secuencia
< P1, P3, P4, P2, P0> satisface los criterios de seguridad.
KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

DETECCIÓN DE INTERBLOQUEOS
• Permite al sistema entrar en estado de interbloqueo
• Algoritmo de Detección
• Esquema de Recuperación

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

12
INSTANCIA SIMPLE DE CADA TIPO DE RECURSO
• Se mantiene un grafo wait-for
• Los nodos son procesos.
• Pi  Pj si Pi está esperando por Pj.
• Periódicamente se invoca un algoritmo que busca por ciclos en
el grafo.
• Un algoritmo para detectar un ciclo en un grafo requiere un
orden de n2 operaciones, donde n es el número de vértices en el
grafo.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

GRAFO DE ALOCACIÓN DE RECURSOS Y GRAFO

WAIT-FOR

Grafo de alocación de Grafo wait-for

recursos correspondiente

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

13
VARIAS INSTANCIAS DE UN TIPO DE RECURSO
• Disponible: Vector de longitud m indica el número de recursos
disponibles de cada tipo.
• Alocación: Una matriz de n x m que define el número de
recursos de cada tipo corrientemente alocados por cada
proceso.
• Request: Una matriz de n x m matrix que indica el requerimiento
corriente de cada proceso. Si Request[i,j] = k, entonces el
proceso Pi está requiriendo k instancias más del recurso de tipo
Rj.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

ALGORITMO DE DETECCIÓN
1. Sean Trab y Final vectores de longitud m y n, respectivamente inicializados:
(a) Trab = Disponible
(b) Para i = 1,2, …, n, si Alocacióni  0, entonces
Final[i] := falso; sino Final[i] := verdadero.
2. Encuentre un índice i tal que:
(a) Final[i] = falso
(b) Requesti  Trab El algoritmo requiere un orden
Si no existe tal i, vaya al paso 4. de O(m x n2) operaciones para
3. Trab := Trab + Alocacióni detectar si el sistema está en
Final[i] := verdadero un estado de interbloqueo.
vaya al paso 2.
4. Si Final[i] = falso, para algún i, 1  i  n, entonces el sistema está en un
estado de interbloqueo. Es mas, si Final[i] = falso, entonces Pi está
interbloqueado.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

14
EJEMPLO DE ALGORITMO DE DETECCIÓN
• Cinco procesos P0 a P4; tres tipos de recursos A (7 instancias), B
(2 instancias), y C (6 instancias).
• En el instante T0:
Alocación Request Disponible
ABC ABC ABC
P0 0 1 0 000 000
P1 2 0 0 202
P2 3 0 3 000
P3 2 1 1 100
P4 0 0 2 002
• La secuencia <P0, P2, P3, P1, P4> resultará en
Final[i] = verdadero para todo i.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

USO DEL ALGORITMO DE DETECCIÓN

• Cuándo y qué frecuente debe invocarse depende de:
• ¿Con qué frecuencia es probable que ocurra un
interbloqueo?
• ¿Cuántos procesos serán afectados cuando ocurra un
interbloqueo?
• Si el algoritmo de detección es invocado arbitraria-mente, puede
haber muchos ciclos en el grafo de recursos y no se puede decir
cual de los muchos procesos interbloqueados causó el
interbloqueo.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

15
RECUPERACIÓN DE INTERBLOQUEOS:
TERMINACIÓN DE PROCESOS
• Aborto de todos los procesos interbloqueados.
• Aborto de un proceso a la vez hasta que el ciclo de interbloqueo
haya sido eliminado.
• ¿En qué orden se elige abortar?
• Prioridad del proceso.
• Cuánto tiempo ha computado el proceso, y cuánto falta para
completar.
• Recursos que el proceso ha usado.
• Recursos que el proceso necesita para completar.
• Cuántos procesos necesitarán ser terminados.
• ¿Es el proceso interactivo o batch?

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

RECUPERACIÓN DE INTERBLOQUEOS:
APROPIACIÓN DE RECURSOS
• Selección de una víctima – minimiza costos.
• Rollback – retorna a algún estado seguro, reinicia el proceso
desde ese estado.
• Inanición – algunos procesos pueden ser elegidos siempre como
víctimas, incluir un número de rollbacks en el factor de costo.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

16
COMUNICACIÓN ENTRE PROCESOS
Memoria Compartida Mensajes
• Segmento de memoria • Cola de mensajes
compartida

… m5 m4 m3 m2 m1
Segmento de
memoria

p3
p1 p3
p1 p2
p2

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

COMUNICACIÓN ENTRE PROCESOS: SEGMENTO

DE MEMORIA
OPERACIONES
1.- Creación de un nuevo segmento de memoria compartida o acceder a
uno existente.
Llamada al sistema: shmget
int shmget( key_t key, size_t size, int shmflg);

2.- Mapeado del segmento de memoria compartida al espacio de

direcciones del proceso.
Llamada al sistema: shmat
char *shmat( int shmid, void *shmaddr, int shmflg );

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

17
COMUNICACIÓN ENTRE PROCESOS: SEGMENTO
DE MEMORIA
OPERACIONES
3.- Lectura o escritura. En esta zona se lee y se escribe como en cualquier
dirección de memoria del proceso. Por ser una zona de memoria
compartida, para realizar el acceso a esta zona hay que utilizar semáforos
para obtener acceso exclusivo.

4.- Desenlace del segmento de memoria compartida por parte del proceso.
Llamada al sistema: shmdt
int shmdt( void *shmaddr )

Librerías:
#include <sys/ipc.h>
#include <sys/shm.h>

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

COMUNICACIÓN ENTRE PROCESOS:

SEGMENTO DE MEMORIA: EJEMPLO
Proceso 1 Proceso 2
struct info *ctrl; struct info *ctrl;
struct info{
// obtener un identificador // crear la memoria compartida
id = shmget(KEY, SEGSIZE, 0); char mensaje[255];
id = shmget(KEY, SEGSIZE, IPC_CREAT |
if (id <0){ }; 0666);
printf(" FALLO EL shmget \n"); exit(1); if (id <0){
} #defineprintf("Error
KEY ((key_t)fallo(1243))
el shmget \n"); exit(1);
//asociar la memoria a la estructura local#define}SEGSIZE sizeof (struct info)
ctrl = (struct info*) shmat(id,0,0); //tamaño// asociar la memoria a la estructura ctrl
de la estructura
if (ctrl <= (struct info *) (0)){ ctrl = (struct info*) shmat(id,0,0);
printf(" Error en el shmat \n"); exit(2); if (ctrl <= (struct info *) (0)){
} printf(" Error fallo shmat \n"); exit(2);
// operar sobre memoria compartida }
if ( argc == 1 ) //valor inicial al segmento de memoria
strcpy( ctrl->mensaje, "\0" ); compartida
else strcpy(ctrl->mensaje, "Sistemas
strcpy( ctrl->mensaje, argv[1]); Operativos");

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

18
COMUNICACIÓN ENTRE PROCESOS: COLAS DE
MENSAJES
OPERACIONES
1.- Creación de la cola de mensajes. Librerías:
Llamada al sistema: msgget #include <sys/ipc.h>
#include <sys/msg.h>
int msgget( key_t key, int shmflg);
2.- Envío de un mensaje.
Llamada al sistema: msgsnd
int msgsnd( int msqid, const void *msgp, size_t msgsz, int msgflg);
3.- Recepción de un mensaje.
Llamada al sistema: msgrcv
int msgrcv( int msqid, const void *msgp, size_t msgsz, long msgtyp,
int msgflg);

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

COMUNICACIÓN ENTRE PROCESOS: COLAS DE

MENSAJES
FORMATO DEL MENSAJE

struct mensaje{
long tipo;
int dato_1; Primer campo del
mensaje. Define el
int dato_2; tipo de mensaje
};

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

19
COMUNICACIÓN ENTRE PROCESOS: COLAS
DE MENSAJES: EJEMPLO
Emisor Receptor
.... inicialización de la cola.... .... vinculación a la cola....
idmsg = msgget(key, IPC_CREAT|0666); idmsg = msgget(key, 0666);
mimensaje.tipo = 1;
mimensaje.dato_1 = 24; longitud = sizeof(struct mensaje) -
mimensaje.dato_2 = 4; sizeof(long);

longitud = sizeof(struct mensaje) - if (msgrcv(idmsg, &mimensaje, longitud,

sizeof(long); 0, 0) == -1)
{
if (msgsnd(idmsg, &mimensaje, longitud, printf(“Error en la lectura mensaje\n”);
0) == -1) exit(1); }
{
printf(“Error en la escritura mensaje\n”);
exit(1); }

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

Bibliografía:
- Silberschatz, A., Gagne G., y Galvin, P.B.; "Operating System
Concepts", 7ma Edición 2009, 9na Edición 2012, 10ma Edición 2018.
- Stallings, W. "Operating Systems: Internals and Design
Principles", Prentice Hall, 6ta Edición 2009, 7ma Edición 2011, 9na
Edición 2018.

KMC © 2019 SISTEMAS OPERATIVOS - INTERBLOQUEOS

20