Sistemas operativos modernos

Como ejemplo de un sistema más complejo que los estudiados hasta ahora, consideremos un sistema con siete procesos, A a G, y seis recursos, a ÍV. El estado actual del sistema en cuan­ to a posesión y solicitudes de recursos es el siguiente: 1. El proceso A tiene R y quiere S. 2. El proceso B no tiene nada pero quiere T. 3. El proceso C no tiene nada pero quiere 5. 4. El proceso D tiene U y quiere S y T. 5. El proceso E tiene T y quiere V. 6 . El proceso F tiene W y quiere 5. 7. El proceso G tiene V y quiere U. Las preguntas son: “¿Este sistema ha caído en un bloqueo irreversible? y, de ser así, ¿cuáles procesos participan en él?” Para contestar estas preguntas, podemos construir el grafo de recursos de la figura 3-5a. Es­ te grafo contiene un ciclo, que puede detectarse por inspección visual. Tal ciclo se muestra en la figura 3-5b. En él, vemos que los procesos D, E y G han caído en un bloqueo irreversible. Este no es el caso de los procesos A, C y F no porque S puede asignarse a cualquiera de ellos, y cuan­ do ése termine, lo devolverá. Luego los otros dos pueden turnarse para ocuparlo y así terminar. (a) (b) Figura 3-5. a) Grafo de recursos, b) Ciclo extraído de a. Aunque en un grafo simple es relativamente fácil ver cuáles procesos ha caído en un blo­ queo irreversible, en los sistemas reales necesitamos un algoritmo formal para detectar dichos bloqueos. Se conocen muchos algoritmos para detectar ciclos en grafos dirigidos. A continua­ ción presentaremos uno sencillo que inspecciona un grafo, y termina a! hallar un ciclo o al de­ mostrar que no los hay. Se utiliza la estructura de datos L, que es una lista de nodos. Durante el algoritmo, los arcos se marcan para indicar que ya se inspeccionaron, y así evitar inspeccio­ nes repetidas.