Sistemas Operativos I

Tema 5

Interbloqueos
Equipo de Sistemas Operativos DISCA / DSIC UPV

Tema 5: Interbloqueos
Contenido 1.- Concepto de interbloqueo. 2.- Caracterizacin formal.
Modelo de sistema. Representacin grfica. Condiciones de Coffman.

Bibliografa A. Silberschatz, P. Galvin. Sistemas Operativos. Conceptos Fundamentales (3 / 5 Ed.). Addison-Wesley

3.-Tcnicas de tratamiento de interbloqueos

Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

Tema 5: Interbloqueos
1.- Concepto de interbloqueo.
2.- Caracterizacin formal. Modelo de sistema. Representacin grfica. Condiciones de Coffman. 3.-Tcnicas de tratamiento de interbloqueos Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

1.- Concepto de interbloqueo.

Concepto
Dados: un conjunto de procesos ejecutndose 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 situacin: Ningn proceso eternamente). del grupo puede evolucionar (suspendido

Ningn otro proceso podr obtener los recursos retenidos, puesto que no pueden ser liberados. Los interbloqueos constituyen un grave problema para el que la mayora de sistemas operativos (como UNIX, por ejemplo) no contemplan ningn tratamiento en absoluto.
Sistemas Operativos I (00-01) Tema5: Interbloqueos 4

1.- Concepto de interbloqueo.

Ejemplos
El sistema tiene dos unidades de cinta, P1 y P2 tienen cada uno una unidad y necesitan la otra. Semforos SemA y SemB, inicializados a 1 Situacin de trfico en interbloqueo Proceso1 P(SemA) P(SemB) Proceso2 P(SemB) P(SemA)

...

...

...
...
Sistemas Operativos I (00-01)

Tema5: Interbloqueos

Tema 5: Interbloqueos
1.- Concepto de interbloqueo. 2.- Caracterizacin formal. Modelo de sistema. Representacin grfica. Condiciones de Coffman. 3.-Tcnicas de tratamiento de interbloqueos Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

2.- Caracterizacin 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 fsicos (discos, cintas, impresoras, etc.), o lgicos (monitores, semforos, etc.). De cada recurso puede haber una o ms 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: Peticin del recurso: Si no est disponible, el proceso queda suspendido hasta que lo est. Uso del recurso. Liberacin del recurso.
Sistemas Operativos I (00-01) Tema5: Interbloqueos 7

2.- Caracterizacin formal

Condiciones de Coffman:
Se ha demostrado que las siguientes cuatro condiciones son necesarias (aunque no suficientes) para que se produzca un interbloqueo: 1) Exclusin mutua: Al menos un recurso debe ser utilizado en exclusin 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 algn otro recurso que posea otro proceso, por lo que estar esperando. 3) No expulsin: 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 simultneamente, el sistema se encuentra en situacin de riesgo de sufrir un interbloqueo.
Sistemas Operativos I (00-01) Tema5: Interbloqueos 8

2.- Caracterizacin formal

Ejemplo
Situacin de trfico en interbloqueo:
Cada seccin de la calle se considera un recurso. Exclusin mutua: slo un vehculo puede ocupar una seccin de la calle. Retener y esperar: cada vehculo ocupa una seccin de la calle y est esperando para moverse a la siguiente seccin. No expulsin: no se puede quitar una seccin de la calle ocupada por un vehculo. El vehculo la liberar cuando se mueva a la siguiente seccin. Espera circular: cada vehculo est esperando a que mueva el vehculo de enfrente.

...

...

...
...
9

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

2.- Caracterizacin formal

Representacin grfica: Grafo de asignacin de recursos.
Una asignacin concreta de recursos a procesos puede ser representada de forma grfica mediante un grafo en el que: Existen dos tipos de nodos: crculos (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 peticin, y si van de un recurso a un proceso, indican asignacin. En este ltimo caso, el arco va en realidad de una instancia concreta (punto) al proceso. Ejemplo:
R1 R3

P1

P2

P3

R2

R4

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

10

2.- Caracterizacin formal

Grafo de asignacin de recursos (2)
Interpretacin del grafo: Si no existen ciclos (dirigidos), entonces no hay interbloqueo. Si existe algn ciclo dirigido, entonces: Si hay slo una instancia de cada recurso, entonces hay un interbloqueo. Si hay ms de una instancia, entonces puede haber un interbloqueo. Ejemplo anterior: Ahora P3 solicita R2.
R1 R3 P1 est esperando un recurso que posee P2, que espera un recurso que posee P3, que espera un recurso que poseen P1 y P2. P3

P1

P2

R2

R4

INTERBLOQUEO !

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

11

2.- Caracterizacin formal

Grafo de asignacin de recursos (3)
Ejemplo de grafo de asignacin de recursos con un ciclo pero sin interbloqueo

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

12

Tema 5: Interbloqueos
1.- Concepto de interbloqueo. 2.- Caracterizacin formal. Modelo de sistema. Representacin grfica. Condiciones de Coffman. 3.-Tcnicas de tratamiento de interbloqueos Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

13

3.-Tcnicas de tratamiento de interbloqueos

Alternativas en el tratamiento de interbloqueos:
Ignorar el problema, asumiendo que dicha situacin nunca se dar en el sistema. Es la aproximacin que mantienen muchos sistemas operativos, incluido UNIX. Emplear algn algoritmo o protocolo que asegure que nunca se va a poder producir un interbloqueo. Esta solucin puede adoptar dos formas alternativas: Prevencin. Consiste en conseguir que no puedan darse simultneamente las cuatro condiciones de Coffman. De esta forma, el interbloqueo no puede llegar a producirse. Evitacin. 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 peticin de un recurso, el sistema analiza toda esa informacin para conceder (o denegar) dicho recurso. Utilizar un algoritmo que pueda detectar una situacin de interbloqueo (deteccin) y seguir alguna tcnica que permita deshacer dicha situacin (recuperacin).

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

14

Prevencin de interbloqueos
Veamos cules de las condiciones de Coffman son evitables, y cmo:
Exclusin mutua: No es posible eliminar esta condicin, pues la mayora de recursos son inherentemente no compartibles (i.e., reutilizables serie). Retener y esperar: Para deshacer esta condicin, se debe obligar a los procesos a: Solicitar todos sus recursos de una vez, al principio de su ejecucin, o bien... Utilizar los recursos de uno en uno, liberando cada recurso antes de solicitar el siguiente. En cualquier caso, si necesita ms de uno a la vez, debe entonces solicitar todos ellos al principio. Estas aproximaciones tienen dos problemas: Baja utilizacin de los recursos, puesto que estarn retenidos desde el principio de la ejecucin de los procesos, pero evidentemente no se estarn utilizando en todo momento. Inanicin de los procesos que necesiten muchos recursos solicitados muy frecuentemente por los dems procesos.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

15

Prevencin de interbloqueos (2)

No expulsin: Para eliminar esta restriccin, se puede aplicar el siguiente algoritmo: Cuando un proceso P solicita recursos que no estn libres, el sistema examina si los poseen procesos que a su vez estn 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 slo podrn continuar cuando obtengan de nuevo dichos recursos, ms los que estaban esperando. Espera circular: Esta condicin 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 funcin F: R N, que asocia a cada recurso un nmero natural. Un proceso que posee un recurso Ri puede solicitar otro recurso Rj si y slo si F(Ri) < F(Rj) (o bien ha liberado los recursos que no cumplen con la condicin).

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

16

Prevencin de interbloqueos (3)

Espera circular. Orden total:
En una hipottica cadena circular, cada proceso Pi (que posee Ri) espera el recurso Ri+1 (que posee Pi+1). Con eso tendramos que i F(Ri) < F(Ri+1). Pero entonces se cumplira que: F(R0) < F(R1) < ... < F(Rn) < F(R0), lo que es imposible por definicin del orden total.

..... 1 2 3 4 5 6 7 8 9

No est permitido, no se cumple F(Ri)

< F(Rj)
17

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

Tema 5: Interbloqueos
1.- Concepto de interbloqueo. 2.- Caracterizacin formal. Modelo de sistema. Representacin grfica. Condiciones de Coffman. 3.-Tcnicas de tratamiento de interbloqueos Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

18

Evitacin de interbloqueos. Generalidades

En este tipo de tcnicas, el sistema necesita conocer:
La necesidad mxima de recursos de los procesos que se estn ejecutando. La asignacin actual de recursos a procesos. La cantidad actual de instancias libres de cada recurso en el sistema.

A partir de dicha informacin, se determina:

Estado seguro: un estado (de asignacin de recursos) se considera seguro si en l no hay posibilidad de interbloqueo. Para que un estado sea seguro, es necesario que los procesos formen una secuencia segura. Una secuencia segura es una cierta ordenacin de los procesos que cumple que los recursos que an puede pedir cualquier Pi pueden ser satisfechos con los recursos libres ms los recursos retenidos por los Pj, j<i. Si dicha secuencia existe, como mucho cada proceso tendr que esperar a que liberen sus recursos los procesos que van antes que l en la secuencia.

En base a ello, cuando un proceso realice una peticin de recursos, el sistema se los conceder slo en el caso de que la peticin mantenga al sistema en un estado seguro.
Sistemas Operativos I (00-01) Tema5: Interbloqueos 19

Evitacin de interbloqueos. Generalidades

Espacios de estado seguro, inseguro e interbloqueo
interbloqueo inseguro

seguro

Secuencia segura
es una cierta ordenacin de los procesos que cumple que los recursos que an puede pedir cualquier Pi pueden ser satisfechos con los recursos libres ms los recursos retenidos por los Pj, j<i.
An puede solicitar

R1 P1 P2

Secuencias seguras: P2, P3 y P1 P3, P2 y P1

P1 P2 P3

1 3 2 R1

2 1 1 R2

R2

P3

Estado SEGURO
20

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

10

Evitacin de interbloqueos. Generalidades

Situacin 2

An puede solicitar

R1 No existe una Secuencia segura P1 P2

P1 P2 P3

0 2 2 R1

2 1 1 R2

R2

P3

Estado INSEGURO

Dependiendo de cundo se soliciten los recursos y cuando se liberen, podr darse un interbloqueo o no

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

21

Evitacin. El algoritmo del banquero

Suponemos:
n procesos m recursos

Estructuras de datos necesarias:

Disponible[m]

C antidad de instancias disponibles de cada recurso. M xim o n de instancias de cada recurso que cada proceso puede pedir N de instancias de cada recurso actualm ente asignadas a cada proceso. N de peticiones de instancias de cada recurso que cada proceso an no ha hecho.

Max[n,m]

Asignado[n,m]

Necesito[n,m]

NOTACION: En las matrices como Asignado denotaremos por Asignado[i] a la fila i-sima de dicha matriz.
Sistemas Operativos I (00-01) Tema5: Interbloqueos 22

11

Evitacin. El algoritmo del banquero

Un ejemplo:
A P3 B P0 P4 P0 C P1 P2 P3 P4 P1 P2 P0 Disponible 3 A 3 B 2 C P1 P2 P3 P4 Asignado 0 2 3 2 0 A
Sistemas Operativos I (00-01)

MAX 7 3 9 2 4 A Necesito 0 0 2 1 2 C P0 P1 P2 P3 P4 7 1 6 0 4 A 4 2 0 1 3 B 3 2 0 1 1 C
23

5 2 0 2 3 B

3 2 2 2 3 C

1 0 0 1 0 B

Tema5: Interbloqueos

Evitacin. El algoritmo del banquero

ALGORITMO 1: Algoritmo de seguridad.
Establece si el sistema se encuentra actualmente en un estado seguro. Estructuras de datos auxiliares:
Trabajo[m]: Acumula los recursos de los procesos que pueden evolucionar Acabado[n]: Booleano que indica cuando un proceso ha acabado

Algoritmo:

Funcion Seguridad retorna Boolean Funcion Seguridad retorna Boolean Trabajo := Disponible Trabajo := Disponible Para todo i Para todo i Acabado[i] := false Acabado[i] := false FinPara FinPara Mientras i tal que Acabado[i]=False AND Mientras i tal que Acabado[i]=False AND Necesito[i]<=Trabajo Necesito[i]<=Trabajo Trabajo := Trabajo + Asignado[i] Trabajo := Trabajo + Asignado[i] Acabado[i] := True Acabado[i] := True FinMientras FinMientras Si i Acabado[i]=True Entonces Si i Acabado[i]=True Entonces Seguridad := True Seguridad := True Sino Sino Seguridad := False Seguridad := False FinSi FinSi Fin Seguridad Fin Seguridad
Tema5: Interbloqueos 24

Sistemas Operativos I (00-01)

12

Evitacin. El algoritmo del banquero

Un ejemplo:
A P3 B P0 P4 C

Disponible 3 Necesito P0 P1 P2 P3 P4 7 1 6 0 4 A 4 2 0 1 3 B 3 2 0 1 1 C 0 2 3 2 0 A 3 Asignado 1 0 0 1 0 B 0 0 2 1 2 C 5 2 3

Trabajo 3 2
P1 P2

10 3 2 10 7 4 3 7 4 5 4 7

Estado seguro

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

25

Evitacin. El algoritmo del banquero

ALGORITMO 2: Algoritmo de peticin de recursos.
Lo utiliza el sistema para averiguar si puede satisfacer una peticin de recursos. Estructura de datos auxiliar:
Peticion[i]: Vector de tamao m que refleja los recursos que pide el proceso i.

Algoritmo:

Invocacin al algoritmo anterior

Procedimiento Peticion_Recursos( Peticion[i] ) Procedimiento Peticion_Recursos( Peticion[i] ) Si Peticion[i] > Necesito[i] Si Peticion[i] > Necesito[i] Entonces ERROR Entonces ERROR FinSi FinSi Si Peticion[i] > Disponible Si Peticion[i] > Disponible Entonces Suspender_Proceso(i) Entonces Suspender_Proceso(i) Sino Sino Disponible := Disponible - Peticion[i] Disponible := Disponible - Peticion[i] Asignado[i] := Asignado[i] + Peticion[i] Asignado[i] := Asignado[i] + Peticion[i] Necesito[i] := Necesito[i] - Peticion[i] Necesito[i] := Necesito[i] - Peticion[i] Si Seguridad Si Seguridad Entonces Dar_Recursos_A(i) Entonces Dar_Recursos_A(i) Sino Sino Recuperar_estado_previo() Recuperar_estado_previo() Suspender_Proceso(i) Suspender_Proceso(i) FinSi FinSi FinSi FinSi Fin Peticion_Recursos Fin Peticion_Recursos
Tema5: Interbloqueos 26

Sistemas Operativos I (00-01)

13

Evitacin. El algoritmo del banquero

Un ejemplo:
Peticin 1 0 2 Disponible 3 3 2
A P3 B C P4

OK
Trabajo

P0

Disponible P1 Necesito P0 P1 P2 P3 P4 7 0 6 0 4 A 4 2 0 1 3 B 3 0 0 1 1 C 0 3 3 2 0 A 2 3 Asignado 1 0 0 1 0 B 0 2 2 1 2 C 5 0 2

P1

0
P2

10 3 2 10 7 4 3 P0 7 4 5 P1 P2 P3 P4 7 3 9 2 4 A 4 7

MAX 5 2 0 2 3 B
27

3 2 2 2 3 C

Estado seguro. Se atiende la peticin de recursos.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

Evitacin. El algoritmo del banquero

Un ejemplo:
Peticin 0 2 0 Disponible 2 3 0
A P3 B C P4

OK
Trabajo

P0

Disponible P0 Necesito P0 P1 P2 P3 P4 7 0 6 0 4 A 2 2 0 1 3 B 3 0 0 1 1 C 0 3 3 2 0 A 2 1 Asignado 3 0 0 1 0 B 0 2 2 1 0 2

P1

0
P2

No se concede la peticin. No se concede la peticin. ESTADO INSEGURO ESTADO INSEGURO

MAX P0 7 3 9 2 4 A 5 2 0 2 3 B
28

3 2 2 2 3 C

2 C

P1

No puede acabar ningn proceso

P2 P3 P4

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

14

Tema 5: Interbloqueos
1.- Concepto de interbloqueo. 2.- Caracterizacin formal. Modelo de sistema. Representacin grfica. Condiciones de Coffman. 3.-Tcnicas de tratamiento de interbloqueos Prevencin. Evitacin: el algoritmo del banquero. Deteccin y recuperacin.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

29

Deteccin de interbloqueos
Algoritmos de deteccin. Casos:
1) Si slo hay recursos de instancia nica Grafo de espera-a (wait-for) Se basa en el grafo de asignacin de recursos. Se eliminan los nodos correspondientes a recursos, y se ajustan los arcos de forma que habr un arco del proceso Pi al proceso Pj si Pj posee un recurso que Pi ha solicitado. Existir un interbloqueo si y slo si hay un ciclo en el grafo.

Ejemplo:
P2 R1 P1 R5 R4 P5
Sistemas Operativos I (00-01)

P2

R2 P3 R3 P1 P3

INTERBLOQUEO !
P4
Tema5: Interbloqueos

P5

P4
30

15

Deteccin de interbloqueos (2)

2) Si hay recursos de mltiples instancias Estructuras de datos:
Disponible[m]: Nmero de instancias disponibles de cada recurso. Asignado[n,m]: Cantidad de instancias asignadas a los procesos. Peticion[n,m]: Cantidad de peticiones de instancias de recursos actualmente.

Algoritmo de deteccin

Algoritmo:

Aquellos procesos para los que Acabado[i] sea falso, forman parte de un interbloqueo.

Funcion Detecccion retorna Boolean Funcion Detecccion retorna Boolean Trabajo := Disponible Trabajo := Disponible Para todo i Para todo i Si Asignado[i] <> 0 Si Asignado[i] <> 0 Entonces Acabado[i] := False Entonces Acabado[i] := False Sino Acabado[i] := True Sino Acabado[i] := True FinSi FinSi FinPara FinPara Mientras i tal que Acabado[i]=False AND Mientras i tal que Acabado[i]=False AND Peticion[i]<=Trabajo Peticion[i]<=Trabajo Trabajo := Trabajo + Asignado[i] Trabajo := Trabajo + Asignado[i] Acabado[i] := True Acabado[i] := True FinMientras FinMientras Si i Acabado[i]=True Si i Acabado[i]=True Entonces Deteccion := False Entonces Deteccion := False Sino Detecion := True Sino Detecion := True FinSi FinSi Fin Deteccion Fin Deteccion
Tema5: Interbloqueos 31

Sistemas Operativos I (00-01)

Deteccin de interbloqueos (3)

Cundo se invoca este algoritmo? Alternativas:
Cada vez que una peticin de recursos no puede ser concedida inmediatamente. Cada cierto intervalo de tiempo.

Comparacin:
La primera alternativa produce ms sobrecarga, pero es ms fcil detectar qu procesos provocan el interbloqueo (pues como mucho habr un interbloqueo). Con la segunda alternativa podemos medir la sobrecarga, pero si existen varios ciclos ser difcil determinar qu procesos estn involucrados en cada uno de los interbloqueos. Peticin

Ejemplo:
A P3 B P0 P4

P0 P1 P2
C

0 2 0 1 0 A

0 0 0 0 0 B

0 2 0 0 2 C

La secuencia <P0, P2, P3, P1, P4> finaliza con Acabado[i] = true para todo i. P2 pide una instancia adicional del recurso C : Peticin[P2] = 0 0 1 Cul es el estado del sistema? Existe un interbloqueo, en el que intervienen los procesos P1,P2, P3, y P4.

P3 P4

P1 P2
Sistemas Operativos I (00-01)

Tema5: Interbloqueos

32

16

Recuperacin de interbloqueos
Alternativas: Terminacin de procesos.
Terminacin de todos los procesos interbloqueados. Terminacin iterativa de procesos, hasta que el interbloqueo desaparezca.

Apropiacin de recursos. El sistema se apropia de recursos de los procesos interbloqueados, hasta que desaparece el interbloqueo. Problemas a resolver:
Seleccin de una vctima: A quin se elige para apropiarse de sus recursos. Vuelta atrs: El proceso a quien se le quitan los recursos debe ser vuelto a un estado seguro. La solucin trivial es abortar dicho proceso. Inanicin. Hay que considerar que no se debera quitar siempre los recursos al mismo proceso, sobre todo si la vuelta atrs supone abortarlo y obligarle a empezar desde el principio.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

33

Ejemplo: El problema de los 5 filsofos

Enunciado :
En una mesa hay 5 filsofos. Cada uno puede comer y pensar. Protocolo para comer: Coger tenedor derecho. Coger tenedor izquierdo. Comer. Dejar tenedor derecho. Dejar tenedor izquierdo. Cada tenedor es un recurso reutilizable serie. Hay slo 5 tenedores para los 5 filsofos.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

17

Ejemplo: El problema de los 5 filsofos

Solucin con semforos: Cada tenedor es un semforo, inicializado a uno. Para que un filsofo pueda comer tiene que cerrar el semforo de su derecha y el de su izquierda. Cuando deja de comer, abre ambos semforos. Implementacin:
var tenedor :: array[0..4] of Semaforo := 1; var tenedor array[0..4] of Semaforo := 1; task Filosofo( i:0..4 )) task Filosofo( i:0..4 repeat repeat P( tenedor[i] ); P( tenedor[i] ); P( tenedor[(i+1) mod 5] ); P( tenedor[(i+1) mod 5] ); comer(); comer(); V( tenedor[i] ); V( tenedor[i] ); V( tenedor[(i+1) mod 5] ); V( tenedor[(i+1) mod 5] ); pensar(); pensar(); until false; until false; end Filosofo; end Filosofo;

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

Ejemplo: El problema de los 5 filsofos

Problema: Qu ocurre si cada uno coge el tenedor derecho (i) e intenta coger el izquierdo (i+1)?
Los 5 procesos han ejecutado

? ?

P( tenedor[i] );

y se quedan esperando en
P( tenedor[(i+1) mod 5] );

INTERBLOQUEO !

? ? ?

Soluciones triviales:
Permitir que slo 4 filsofos se sienten a la mesa. Cada filsofo coge ambos tenedores a la vez, o ninguno. Los filsofos pares cogen primero el tenedor derecho y los impares el izquierdo.

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

18

Ejemplo: El problema de los 5 filsofos

Caracterizacin formal: Grafo de asignacin de recursos
5 procesos (filsofos). 5 recursos (tenedor) de instancia nica. NOTA: Los tenedores no son todos iguales, puesto que cada proceso solicita un tenedor en concreto (el de su izquierda o el de su derecha).

P2 R1 P1 R5 R4 P5 P4 R3 R2 P3

CICLO

INTERBLOQUEO !

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

37

Deteccin de interbloqueos
Ejemplo: 5 filsofos. Supongamos que se ha producido el interbloqueo: Cuando se invoque Deteccion():
Estado inicial:
Trabajo 0 0 0 0 0 F Acabado F F F F

No hay iteraciones posibles.

I Acabado[i] = False I Acabado[i] = False Los cinco procesos estn Los cinco procesos estn interbloqueados interbloqueados

Sistemas Operativos I (00-01)

Tema5: Interbloqueos

38

19