13 Condiciones para el interbloqueo Enunciadas por Coffman Exclusión mutua: un recurso está asignado a un proceso o está disponible Retención y espera: Se pueden solicitar más recursos sin abandonar los ya obtenidos No expulsión: Los procesos tienen que dejar los recursos explícitamente Círculo de espera: Se produce un círculo de 2 o más procesos
14 Grafos para modelar interbloqueos Los grafos sirven para averiguar si una determinada secuencia produce interbloqueo R P R asignado a P R P P bloqueado esperando R R1 R2 D P Interbloqueo
15 Ejemplo 3 procesos Planificación por turno rotatorio ===== > El S.O puede suspender un proceso = > A Pedir R Pedir S Dejar R Dejar S C Pedir T Pedir R Dejar T Dejar R B Pedir S Pedir T Dejar S Dejar T 1. A pide R 2. B pide S 3. C pide T 4. A pide S 5. B pide T 6. C pide R R A S B T C 2 1 3 4 5 6 1. A pide R 2. C pide T 3. A pide S 4. C pide R 5. A deja R 6. A deja S
16 Formas de tratar el interbloqueo El algoritmo del avestruz Esconder la cabeza y desentenderse Unix Detección y eliminación de interbloqueos Controlar peticiones y liberaciones de recursos Actualizar el grafo de recursos y comprobar que no haya bucles Comprobar periódicamente si hay procesos que han estado bloqueados durante mucho tiempo Prevención de interbloqueos Predicción de interbloqueos
17 Prevención de interbloqueos Imponer restricciones a los procesos de forma que un interbloqueo no sea posible No habrá interbloqueo si no se cumple alguna de las 4 condiciones necesarias para el interbloqueo: Exclusión mutua No se puede eliminar, se puede llegar a condiciones de carrera Retención y espera Solicitar todos los recursos al principio No permite utilización óptima No se sabe a priori Antes de solicitar un recurso, los procesos están obligados a dejar temporalmente los que tienen retenidos No expulsión No aconsejable Círculos de espera
18 Círculos de espera Retener un recurso en cada momento No es adecuado Dar a los recursos una numeración general. Los recursos se solicitan en orden de numeración El grafo no puede tener bucles cerrados Puede ser difícil dar a los recursos una numeración adecuada A – 1 B – 2 C – 3 D – 4 E – 5 B y luego D pero no D y luego B
19 Predicción de interbloqueos Evitar los interbloqueos cuando se asignen los recursos Trayectorias de recursos Algoritmo del banquero para un recurso Algoritmo del banquero para múltiples recursos
20 Trayectorias de recursos Para 2 recursos y 2 procesos I1 I2 I3 I4 I5 I6 I7 I8 Impresora Trazador Impresora Trazador A B p q r s t Ejecución de A Ejecución de B
21 Algoritmo del banqueropara un recurso Estado del sistema con respecto a la asignación de recursos: lista de procesos, recursos usados y máximo No todos los procesos van a utilizar el máximo Estado seguro: si hay una secuencia que lleve a todos los procesos a obtener sus máximos p1 p2 p3 p4 0 0 0 0 6 5 4 7 Disponible=10 p1 p2 p3 p4 1 1 2 4 6 5 4 7 Disponible=2 p1 p2 p3 p4 1 2 2 4 6 5 4 7 Disponible=1 max max max usado usado usado
22 Algoritmo del banquero para múltiples recursos Ra: recursos asignados en ese momento Rn: recursos que se necesitan todavía E: recursos existentes P: recursos asignados a algún proceso D: recursos disponibles A B C D E Ra 3 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 R1 R2 R3 R4 A B C D E Rn 1 1 3 0 2 0 1 1 0 1 1 0 2 0 0 0 0 0 1 1 R1 R2 R3 R4 E=(6 3 4 2) P=(5 3 2 2) D=(1 0 2 0)
P+D=E
23 Algoritmo de comprobación de estado seguro Buscar fila F cuyas necesidades de recursos sean menores que D. Si no hay=> estado no seguro, el sistema se puede interbloquear, se necesitan más de los disponibles Suponer que el proceso de la fila F pide todos los recursos y termina. Marcar el proceso como terminado y añadir sus recursos a D Repetir los dos pasos anteriores hasta terminar todos los procesos. Si se puede terminar => estado seguro
24 Ejemplo Estado seguro D D=(2 1 2 1) A D=(5 1 3 2) o E E D=(5 1 3 2) o C C D=(6 2 4 2) B D=(6 3 4 2) A B C D E Ra 3 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 0 0 R1 R2 R3 R4 A B C D E Rn 1 1 3 0 2 0 1 1 0 1 1 0 2 0 0 0 0 0 1 1 R1 R2 R3 R4 E=(6 3 4 2) P=(5 3 2 2) D=(1 0 2 0)
P+D=E
25 Ejemplo B pide un R3 => ¿estado seguro? A B C D E Ra 3 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 R1 R2 R3 R4 A B C D E Rn 1 1 3 0 2 0 1 1 0 1 1 0 2 0 0 0 0 0 0 1 R1 R2 R3 R4 E=(6 3 4 2) P=(5 3 3 2) D=(1 0 1 0)
P+D=E
26 Ejemplo E pide un R3 => ¿estado seguro? A B C D E Ra 3 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 R1 R2 R3 R4 A B C D E Rn 1 1 3 0 2 0 1 1 0 1 0 0 2 0 0 0 0 0 0 1 R1 R2 R3 R4 E=(6 3 4 2) P=(5 3 4 2) D=(1 0 0 0)
P+D=E
27 Problemas Poca aplicación práctica: Los procesos raramente saben la cantidad máxima de recursos que van a utilizar El nº de procesos no es fijo Pueden desaparecer recursos con los que se contaba
| Página siguiente |