PDF de programación - Sistemas Operativos I - Tema 5 - Interbloqueos

Sistemas Operativos I

Tema 5

Interbloqueos

Equipo de Sistemas Operativos DISCA / DSIC

UPV

Tema 5: Interbloqueos

 Contenido

1.- Concepto de interbloqueo.
2.- Caracterización formal.


Modelo de sistema.

Representación gráfica.

Condiciones de Coffman.

3.-Técnicas de tratamiento de interbloqueos


Prevención.

Evitación: el algoritmo del banquero.

Detección y recuperación.

 Bibliografía

 A. Silberschatz, P. Galvin.
“Sistemas Operativos.

Conceptos Fundamentales”
(3ª / 5ª Ed.). Addison-Wesley

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

2

1

Tema 5: Interbloqueos

1.- Concepto de interbloqueo.
2.- Caracterización formal.

 Modelo de sistema.
 Representación gráfica.
 Condiciones de Coffman.

3.-Técnicas de tratamiento de interbloqueos

 Prevención.
 Evitación: el algoritmo del banquero.
 Detección y recuperación.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

3

1.- Concepto de interbloqueo.
Concepto

 Dados:


un conjunto de procesos ejecutándose en un sistema (computador),

un conjunto de recursos que son utilizados por dichos procesos,

se dice que el conjunto de procesos se encuentra en un estado de
interbloqueo cuando todos sus procesos se encuentran esperando un
recurso que mantiene retenido otro proceso del grupo.

 En esa situación:


Ningún proceso del grupo puede evolucionar

eternamente).

(suspendido


Ningún otro proceso podrá obtener los recursos retenidos, puesto que

no pueden ser liberados.

 Los interbloqueos constituyen un grave problema para el que la mayoría
de sistemas operativos (como UNIX, por ejemplo) no contemplan ningún
tratamiento en absoluto.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

4

2

1.- Concepto de interbloqueo.
 Ejemplos

 El sistema tiene dos unidades de cinta, P1 y P2 tienen cada uno una unidad y

necesitan la otra.

 Semáforos SemA y SemB, inicializados a 1

 Situación de tráfico en interbloqueo

Proceso1 Proceso2
P(SemB)
P(SemA)
P(SemB)
P(SemA)

.
.
.

...

...

.
.
.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

5

Tema 5: Interbloqueos

1.- Concepto de interbloqueo.
2.- Caracterización formal.

 Modelo de sistema.
 Representación gráfica.
 Condiciones de Coffman.

3.-Técnicas de tratamiento de interbloqueos

 Prevención.
 Evitación: el algoritmo del banquero.
 Detección y recuperación.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

6

3

2.- Caracterización formal
Modelo de sistema

 Conjunto de procesos, identificados por P1, P2, ..., Pi, ... Pn.
 Conjunto de recursos, identificados por R1, R2, ..., Rj, ... Rm. Estos
recursos pueden ser físicos (discos, cintas, impresoras, etc.), o lógicos
(monitores, semáforos, etc.).
De cada recurso puede haber una o más instancias. Dos recursos se
consideran en realidad instancias del mismo recurso si un proceso que
solicita dicho recurso considera que puede obtener cualquiera de ellas
indistintamente.
 El uso que un proceso hace de un recurso sigue este protocolo:


Petición del recurso: Si no está disponible, el proceso queda

suspendido hasta que lo esté.


Uso del recurso.

Liberación del recurso.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

7

2.- Caracterización formal
 Condiciones de Coffman:

 Se ha demostrado que las siguientes cuatro condiciones son necesarias (aunque

no suficientes) para que se produzca un interbloqueo:

1) Exclusión mutua: Al menos un recurso debe ser utilizado en exclusión

mutua, es decir, de modo no compartido.

2) Retener y esperar: Debe haber al menos un proceso que retenga un recurso
y que haya pedido algún otro recurso que posea otro proceso, por lo que
estará esperando.

3) No expulsión: El sistema no puede arrebatar los recursos que ha asignado
previamente a los procesos. En otras palabras, un proceso mantiene retenido
un recurso hasta que deja de utilizarlo y lo libera voluntariamente.

4) Espera circular: Debe existir un conjunto de procesos {P1, P2, ... Pn} tal que P1
se encuentra esperando un recurso que retiene P2, P2 espera un recurso que
retiene P3, ..., Pn-1 espera un recurso que mantiene Pn, y Pn espera un recurso
que mantiene P1.

 Si todas ellas se cumplen simultáneamente, el sistema se encuentra en situación

de riesgo de sufrir un interbloqueo.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

8

4

2.- Caracterización formal
 Ejemplo

 Situación de tráfico en interbloqueo:


Cada sección de la calle se considera

un recurso.


Exclusión mutua: sólo un vehículo

puede ocupar una sección de la calle.


Retener y esperar: cada vehículo
ocupa una sección de la calle y está
esperando para moverse a la siguiente
sección.


No expulsión: no se puede quitar una
sección de la calle ocupada por un
vehículo. El vehículo la liberará cuando
se mueva a la siguiente sección.


Espera circular: cada vehículo está
esperando a que mueva el vehículo de
enfrente.

.
.
.

...

...

.
.
.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

9

2.- Caracterización formal
 Representación gráfica: Grafo de asignación de recursos.

 Una asignación concreta de recursos a procesos puede ser representada de

forma gráfica mediante un grafo en el que:


Existen dos tipos de nodos: círculos (procesos) y cuadrados (recursos). Los
cuadrados poseen tantos puntos en su interior como instancias haya de dicho
recurso.


Los arcos son dirigidos. Si van de un proceso a un recurso, indican petición,
y si van de un recurso a un proceso, indican asignación. En este último caso,
el arco va en realidad de una instancia concreta (punto) al proceso.

 Ejemplo:

P1

R1

R2

R3

P2

P3

R4

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

10

5

2.- Caracterización formal
 Grafo de asignación de recursos (2)

 Interpretación del grafo:


Si no existen ciclos (dirigidos), entonces no hay interbloqueo.

Si existe algún ciclo dirigido, entonces:

– Si hay sólo una instancia de cada recurso, entonces hay un interbloqueo.
– Si hay más de una instancia, entonces puede haber un interbloqueo.

 Ejemplo anterior: Ahora P3 solicita R2.

P1

R1

R2

R3

P2

P3

R4

P1 está esperando un recurso
que posee P2, que espera un

recurso que posee P3, que espera
un recurso que poseen P1 y P2.

¡ INTERBLOQUEO !

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

11

2.- Caracterización formal
 Grafo de asignación de recursos (3)

 Ejemplo de grafo de asignación de recursos con un ciclo pero sin interbloqueo

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

12

6

Tema 5: Interbloqueos

1.- Concepto de interbloqueo.
2.- Caracterización formal.

 Modelo de sistema.
 Representación gráfica.
 Condiciones de Coffman.

3.-Técnicas de tratamiento de interbloqueos

 Prevención.
 Evitación: el algoritmo del banquero.
 Detección y recuperación.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

13

3.-Técnicas de tratamiento de interbloqueos
 Alternativas en el tratamiento de interbloqueos:

 Ignorar el problema, asumiendo que dicha situación nunca se dará en el sistema.

Es la aproximación que mantienen muchos sistemas operativos, incluido UNIX.

 Emplear algún algoritmo o protocolo que asegure que nunca se va a poder

producir un interbloqueo. Esta solución puede adoptar dos formas alternativas:


Prevención. Consiste en conseguir que no puedan darse simultáneamente las
cuatro condiciones de Coffman. De esta forma, el interbloqueo no puede llegar
a producirse.


Evitación. Consiste en llevar la cuenta de los recursos disponibles en el
sistema, los recursos que poseen los procesos y los que pueden llegar a
solicitar. Cada vez que un proceso hace una petición de un recurso, el sistema
analiza toda esa información para conceder (o denegar) dicho recurso.

 Utilizar un algoritmo que pueda detectar una situación de interbloqueo (detección)

y seguir alguna técnica que permita deshacer dicha situación (recuperación).

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

14

7

Prevención de interbloqueos
 Veamos cuáles de las condiciones de Coffman son evitables, y cómo:

 Exclusión mutua:

No es posible eliminar esta condición, pues la mayoría de recursos son
inherentemente no compartibles (i.e., reutilizables serie).

 Retener y esperar:

Para deshacer esta condición, se debe obligar a los procesos a:


Solicitar todos sus recursos de una vez, al principio de su ejecución, o bien...

Utilizar los recursos de uno en uno, liberando cada recurso antes de solicitar el
siguiente. En cualquier caso, si necesita más de uno a la vez, debe entonces
solicitar todos ellos al principio.

Estas aproximaciones tienen dos problemas:


Baja utilización de los recursos, puesto que estarán retenidos desde el
principio de la ejecución de los procesos, pero evidentemente no se estarán
utilizando en todo momento.


Inanición de los procesos que necesiten muchos recursos solicitados muy

frecuentemente por los demás procesos.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

15

Prevención de interbloqueos (2)
 No expulsión:

Para eliminar esta restricción, se puede aplicar el siguiente algoritmo: Cuando un
proceso P solicita recursos que no están libres, el sistema examina si los poseen
procesos que a su vez están esperando. En ese caso, el sistema se apropia de
dichos recursos y se los ofrece a P.
Los procesos a los que se les ha arrebatado recursos sólo podrán continuar
cuando obtengan de nuevo dichos recursos, más los que estaban esperando.

 Espera circular:

Esta condición se puede romper si imponemos un orden total a los recursos, y se
obliga a que los procesos soliciten siempre los recursos siguiendo dicho orden.
Es decir:


Definimos la función F: R → N, que asocia a cada recurso