Sistemas Operativos (SO)

Grado en ingenierı́a de datos e inteligencia artificial

Ángel Manuel Guerrero Higueras

[email protected]

Área de Arquitectura y Tecnologı́a de Computadores

Universidad de León

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International

 Interbloqueos

Modelado
Definición y caracterización
Detección y recuperación
Predicción y prevención

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 2 de 22

 Modelado

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 3 de 22

 Entidades y relaciones

Entidades:
1 Un conjunto de procesos (o hilos).
2 Un conjunto de recursos reutilizables de uso exclusivo.
3 Un conjunto de unidades de cada recurso.

Relaciones −→ relación entre procesos y recursos para un instante t.

1 Asignaciones → ¿Cuántas?
2 Solicitudes no atendidas → ¿Cuántas?

Restricciones
Asignación → El número total de unidades asignadas tiene que ser menor que el
número unidades para un recurso.
Solicitudes→ El número de unidades solicitadas por un proceso tiene que ser menor
o igual que el número de unidades existentes de ese recurso.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 4 de 22

 Funciones

Solicitud −→ S(R1 [U1 ], R2 [U2 ], . . . , Rn [Un ])

Si todos los recursos solicitados en una solicitud S están libres se le asignan al
proceso que los solicita.
En caso contrario se genera un bloqueo (aunque haya algunos recursos libres), sin
reservar ninguno.
El proceso se desbloquea cuando todos estén disponibles.

Liberación:
Un proceso no bloqueado libera los recursos después de usarlos.
Una liberación puede desbloquear uno o más procesos.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 5 de 22

 Representación mediante grafos I

Grafo de asignación de recursos

Nodos Recurso −→ cuadrados.
Nodos Proceso −→ cı́rculos.
Arcos Asignación −→ orientado de recurso a proceso.
Arcos Solicitud −→ orientado de proceso a recurso.

Restricciones
El número de arcos que salen de un recurso debe ser menor que el inventario
(unidades) de ese recurso.
Por cada par Ri y Pj , la suma de arcos de solicitud y de asignación debe ser menor o
igual que el inventario.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 6 de 22

 Representación mediante grafos II

A S D

T U

R B C

(a) (b) (c)

(a) Asignación de recurso

(b) Solicitud
(c) Interbloqueo

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 7 de 22

 Representación mediante grafos III
A B C
Request R Request S Request T
Request S Request T Request R
Release R Release S Release T
Release S Release T Release R
(a) (b) (c)

1. A requests R
2. B requests S A B C A B C A B C
3. C requests T
4. A requests S
5. B requests T
6. C requests R
R S T R S T R S T
deadlock
(d) (e) (f) (g)

A B C A B C A B C

R S T R S T R S T

(h) (i)
(j)

1. A requests R
2. C requests T A B C A B C A B C
3. A requests S
4. C requests R
5. A releases R
6. A releases S R S T R S T R S T
no deadlock
(k) (l) (m) (n)

A B C A B C A B C

R S T R S T R S T

(o) (p) (q)

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 8 de 22

 Representación mediante matrices I

Si p es el número de procesos y r es de recursos, tenemos:

▶ Matriz de asignación (At ) p × r .
At [i, j] cuántas unidades de j están asignadas a i en el instante t.
▶ Matriz de solicitudes (St ) p × r .
St [i, j] cuántas unidades del recursos j está esperando el proceso i en el instante t.
▶ Vector de inventario E (dimensión r ).
E[i] indica cuantas unidades del recurso existen.
▶ Vector de recursos disponibles Dt (dimensión r ).
Dt [i] indica cuantas unidades hay disponibles del recurso en t.

Restricciones
De asignación → ∀ recurso i, la suma de la columna i de la matriz A sea menor o
igual que el número de recursos existentes E[i]
De solicitud → Para cada proceso i y recurso j se tiene que verificar:
A[i, j] + S[i, j] ≤ E[j]

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 9 de 22

 Representación mediante matrices II

   
2 0 0 0 0 0    
A = 0 1 0 S = 1 0 0 E = 2 3 2 D= 0 1 2
0 1 0 0 0 0

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 10 de 22

 Definición y caracterización

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 11 de 22

 Definición de interbloqueo

Definición
Un conjunto de procesos está en interbloqueo si cada proceso está esperando por
recursos que sólo puede liberar otro proceso del conjunto.

No confundir con inanición: un único recurso usado por sucesivos procesos (un
subconjunto puede sufrir inanición)
No confundir con falta de progreso: varios compiten por un recurso que no se
asigna a ninguno.
Condiciones necesarias:
▶ exclusión mutua,
▶ retención y espera,
▶ no expropiación y
▶ espera circular.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 12 de 22

 Caracterización

Reducción
El estado del sistema en un instante t se puede reducir por el proceso P, si se pueden
satisfacer las necesidades de P con los recursos disponibles.

Después de una reducción el proceso devuelve los recursos asignados.

Condición necesaria y suficiente −→ si una secuencia de reducciones desde el
estado actual incluye a todos los procesos, el sistema está libre de interbloqueos.
Si desde un estado concreto se puede reducir por muchos procesos −→ alta
complejidad del algoritmo.
Estrategias de tratamiento:
▶ Avestruz −→ suponer que no va a pasar.
▶ Detección y recuperación −→ costes de rendimiento (parada).
▶ Prevención −→ implica infrautilización.
▶ Predicción −→ necesita análisis teórico.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 13 de 22

 Detección y recuperación

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 14 de 22

 Algoritmo de detección en grafos

S←∅ ▷ Secuencia de reducción. Inicialmente vacı́a

D ▷ Conjunto de procesos desbloqueados y no incluidos en S
while D ̸= ∅ do
Pi ← Primer elemento de D ▷ Se puede reducir por cualquier proceso de D
Reducir grafo por Pi
Añadir Pi a S y eliminarlo de D
Determinar que procesos se debloquean por la reducción (sus solicitudes
pueden satisfacerse en el nuevo grafo) y añadirlos a D
end while
if S = P then ▷ Si la secuencia contiene todos los procesos (P)
No hay interbloqueo
else
Lo procesos del conjunto P-S están en interbloqueo
end if

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 15 de 22

 Algoritmo de detección en matrices

S←∅ ▷ Secuencia de reducción. Inicialmente vacı́a

while True do
if ∃Pi tal que S[i] ≤ D then ▷ Equivale a S[i, j] ≤ D[j] para j = 1, . . . , n
Reducir grafo por Pi : D = D + A[i]
Añadir Pi a S
else
break
end if
end while
if S = P then ▷ Si la secuencia contiene todos los procesos (P)
No hay interbloqueo
else
Lo procesos del conjunto P-S están en interbloqueo
end if

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 16 de 22

 Recuperación

Estrategias:
1 Recuperación por apropiación.
▶ Quitar temporalmente un recurso asignado a un proceso. Puede ser:
manual −→ lotes en mainframes, gestión de impresoras, etc.
Automática −→ en base a prioridades.
2 Recuperación por retroceso.
▶ Hacer que los procesos retrocedan en su tiempo de ejecución.
Incluir “puntos de recuperación” en los procesos (que periódicamente guarden su estado en un
archivo p.e.) .
Útil en sistemas de bases de datos −→ Transacciones.
Retroceso total −→ abortar procesos.
3 Recuperación por eliminación.
▶ Eliminar uno o más procesos.
Después de abortar un proceso habrı́a que ejecutar el algoritmo de detección.
Opción uno −→ eliminar un proceso del ciclo.
Opción dos −→ eliminar uno de fuera (eligiendo uno que tenga recursos reclamados).

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 17 de 22

 Predicción y prevención

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 18 de 22

 Prevención

Estrategias:
Métodos Indirectos:
▶ Prevenir la aparición de las causas.
Exclusión mutua −→ evitar la asignación exclusiva. e.g. impresora y spool.
Retención y espera −→ hacer que todos los recursos se soliciten a la vez. Ineficiente.
No apropiación −→ si se le niega un recurso, que suelte los que tenı́a. Ineficiente.
Métodos Directos:
▶ Impedir el ciclo vicioso de espera.
▶ Una solución es la ordenación lineal de los recursos y exigir que los procesos los soliciten
en ese orden.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 19 de 22

 Predicción

La predicción necesita conocer el futuro −→ saber que recursos necesitará un

proceso.

Estado Seguro
Un estado es seguro si el estado de asignación de recursos que resulta al considerar que
todos los procesos realizan en ese instante todas sus posibles peticiones, no tiene
interbloqueos.

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 20 de 22

 Algoritmo del banquero

Es necesario una matriz de necesidad N (dimensión (p × r ))

N[i, j] especifica cuantas unidades del recurso j puede necesitar el proceso i.

S←∅ ▷ Secuencia de reducción. Inicialmente vacı́a

while True do
if ∃Pi tal que N[i] ≤ D then ▷ Equivale a N[i, j] ≤ D[j] para j = 1, . . . , n
Reducir grafo por Pi : D = D + A[i]
Añadir Pi a S
else
break
end if
end while
if S = P then ▷ Si la secuencia contiene todos los procesos (P)
El estado es seguro
else
El estado NO es seguro
end if

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International 21 de 22

 Sistemas Operativos (SO)
Grado en ingenierı́a de datos e inteligencia artificial

Ángel Manuel Guerrero Higueras

[email protected]

Área de Arquitectura y Tecnologı́a de Computadores

Universidad de León

Distributed under: Creative Commons Attribution-ShareAlike 4.0 International