Interbloqueo (deadlock)
Páginas: 17 (4249 palabras)
Publicado: 30 de agosto de 2010
CAPITULO 8: DEADLOCKS
En un ambiente de multiprogramación, varios procesos pueden competir por un numero finito de recursos. Un proceso solicita recursos y si estos no están disponibles en ese momento, el proceso entra en estado de espera.
Puede ocurrir que procesos en espera nunca cambien de estado, pues los recursos que han solicitado han sido tomados por otros procesos en espera. Porejemplo, en un sistema con 4 unidades de cinta y 2 procesos, cada uno de los cuales ha tomado 2 unidades de cinta pero necesitan 3, cada uno de ellos esperara que el otro libere las cintas. Esta situación se conoce como deadlock (abrazo mortal).
Un sistema debe tomar acciones extremas para provenir un deadlock o recuperarse si ello sucede, tales como liberación de todos los recursos de uno o masprocesos que han entrado en deadlock. En este Capitulo se describen algunos de los varios métodos que los S.O. pueden usar para manejar el problema de los deadlocks.
8.1. EL PROBLEMA DEL DEADLOCK (ABRAZO MORTAL)
Este problema no es único de los S.O. Generalizando la interpretación de recursos y procesos, tenemos situaciones de deadlock en nuestra vida diaria. Por ejemplo, consideremos elcruce de un río a través de piedras. Para cruzarlo, una persona (en nuestro ejemplo un proceso) debe pisar una a una las piedras (recursos). Si dos personas de ambos lados del río comienzan el cruce, al llegar a la mitad se produce el
deadlock.
Una solución seria que una de ellas retroceda. Esto, en el ambiente de S.O. se denomina rollback. Si varias personas son las que cruzan, para solucionar elproblema, puede que sea necesario que mas de una de ellas retrocedan. La única manera de asegurar que el deadlock no ocurra, es poniéndose de acuerdo en un protocolo. Por ejemplo para iniciar el cruce se vea que de la otra orilla nadie ya lo ha iniciado. Debemos hacer algunas observaciones a este protocolo:
* Se debe determinar un mecanismo para saber si alguien este cruzando, el río. Si esposible saber el estado de todas las piedras, esta sola condición es suficiente, pero si no (por ejemplo que el río sea muy ancho o no se divise la otra orilla) debo implementar otro mecanismo.
* Supongamos que simultáneamente 2 personas de orillas opuestas quieran cruzar el río. Nuestro protocolo no especifica que se debe hacer. Si ambos cruzan, tengo deadlock. Si cada una espera por la otra acomenzar, estamos también en otra forma de deadlock. Una solución seria asignar a una de las orillas mayor prioridad: por ejemplo la persona de la costa Este cruzara primero, mientras la otra deberá esperar.
* Si aplicamos lo anterior, una o mas personas pueden esperar indefinidamente para cruzar. Esta situación se conoce como inanición. Sería el caso que una fila continua de gente cruce delEste (de mayor prioridad). Para evitar esto debo extender mi protocolo. Por ejemplo, definiendo un algoritmo que alterne la dirección de cruce.
8.1.1. MODELO DE UN SISTEMA
Un sistema consiste en un numero finito de recursos a ser distribuidos entre un numero de procesos en competencia. Los recursos se particionan en distintos tipos, cada uno de los cuales se llaman "Instancias".
Como ejemplode tipos de recursos tengo ciclos de CPU, espacio de memoria, archivos, dispositivos de E/S (impresoras, unidades de cintas etc.).
Si el sistema tiene 2 CPU, entonces este tipo de recurso tiene 2 instancias. Si un proceso solicita una instancia de algún tipo de recurso, la asignación de cualquier instancia satisface el pedido. Sí no sucede así, entonces las instancias no son idénticas, y por lotanto no han sido definidas correctamente las clases de tipo de recursos. Por ejemplo, si un sistema tiene 2 impresoras, estas pueden definirse dentro del mismo tipo de recurso, si es indiferente por donde se imprima una salida. Sin embargo, si una impresora esta en el piso 9 y la otra en el sótano de un edificio, evidentemente los usuarios del piso 9 no verán ambas impresoras como equivalentes...
En un ambiente de multiprogramación, varios procesos pueden competir por un numero finito de recursos. Un proceso solicita recursos y si estos no están disponibles en ese momento, el proceso entra en estado de espera.
Puede ocurrir que procesos en espera nunca cambien de estado, pues los recursos que han solicitado han sido tomados por otros procesos en espera. Porejemplo, en un sistema con 4 unidades de cinta y 2 procesos, cada uno de los cuales ha tomado 2 unidades de cinta pero necesitan 3, cada uno de ellos esperara que el otro libere las cintas. Esta situación se conoce como deadlock (abrazo mortal).
Un sistema debe tomar acciones extremas para provenir un deadlock o recuperarse si ello sucede, tales como liberación de todos los recursos de uno o masprocesos que han entrado en deadlock. En este Capitulo se describen algunos de los varios métodos que los S.O. pueden usar para manejar el problema de los deadlocks.
8.1. EL PROBLEMA DEL DEADLOCK (ABRAZO MORTAL)
Este problema no es único de los S.O. Generalizando la interpretación de recursos y procesos, tenemos situaciones de deadlock en nuestra vida diaria. Por ejemplo, consideremos elcruce de un río a través de piedras. Para cruzarlo, una persona (en nuestro ejemplo un proceso) debe pisar una a una las piedras (recursos). Si dos personas de ambos lados del río comienzan el cruce, al llegar a la mitad se produce el
deadlock.
Una solución seria que una de ellas retroceda. Esto, en el ambiente de S.O. se denomina rollback. Si varias personas son las que cruzan, para solucionar elproblema, puede que sea necesario que mas de una de ellas retrocedan. La única manera de asegurar que el deadlock no ocurra, es poniéndose de acuerdo en un protocolo. Por ejemplo para iniciar el cruce se vea que de la otra orilla nadie ya lo ha iniciado. Debemos hacer algunas observaciones a este protocolo:
* Se debe determinar un mecanismo para saber si alguien este cruzando, el río. Si esposible saber el estado de todas las piedras, esta sola condición es suficiente, pero si no (por ejemplo que el río sea muy ancho o no se divise la otra orilla) debo implementar otro mecanismo.
* Supongamos que simultáneamente 2 personas de orillas opuestas quieran cruzar el río. Nuestro protocolo no especifica que se debe hacer. Si ambos cruzan, tengo deadlock. Si cada una espera por la otra acomenzar, estamos también en otra forma de deadlock. Una solución seria asignar a una de las orillas mayor prioridad: por ejemplo la persona de la costa Este cruzara primero, mientras la otra deberá esperar.
* Si aplicamos lo anterior, una o mas personas pueden esperar indefinidamente para cruzar. Esta situación se conoce como inanición. Sería el caso que una fila continua de gente cruce delEste (de mayor prioridad). Para evitar esto debo extender mi protocolo. Por ejemplo, definiendo un algoritmo que alterne la dirección de cruce.
8.1.1. MODELO DE UN SISTEMA
Un sistema consiste en un numero finito de recursos a ser distribuidos entre un numero de procesos en competencia. Los recursos se particionan en distintos tipos, cada uno de los cuales se llaman "Instancias".
Como ejemplode tipos de recursos tengo ciclos de CPU, espacio de memoria, archivos, dispositivos de E/S (impresoras, unidades de cintas etc.).
Si el sistema tiene 2 CPU, entonces este tipo de recurso tiene 2 instancias. Si un proceso solicita una instancia de algún tipo de recurso, la asignación de cualquier instancia satisface el pedido. Sí no sucede así, entonces las instancias no son idénticas, y por lotanto no han sido definidas correctamente las clases de tipo de recursos. Por ejemplo, si un sistema tiene 2 impresoras, estas pueden definirse dentro del mismo tipo de recurso, si es indiferente por donde se imprima una salida. Sin embargo, si una impresora esta en el piso 9 y la otra en el sótano de un edificio, evidentemente los usuarios del piso 9 no verán ambas impresoras como equivalentes...
Leer documento completo
Regístrate para leer el documento completo.