Sistemas operativos modernos

El algoritmo opera llevando a cabo los siguientes pasos: 1. Para cada nodo N del grafo, realizar los cinco pasos siguientes con N como nodo inicial. 2. Asignar al principio una lista vacía a L, y designar a todos los arcos como no marcados. 3. Añadir el nodo actual al final de L y ver si ahora el nodo aparece en L dos veces. En tal caso, el grafo contiene un ciclo (que está en L) y el algoritmo termina. 4. A partir del nodo dado, ver si salen de él arcos no marcados. Si es así, ir al paso 5; de lo contrario, ir al paso 6 . 5. Escoger al azar un arco de salida no marcado y marcarlo. Luego seguirlo hasta el nue­ vo nodo actual e ir al paso 3. 6 . Hemos llegado a un callejón sin salida. Lo eliminamos y retrocedemos al nodo ante­ rior, es decir, al que era el actual inmediatamente antes de éste. Hacemos que ése sea el nodo actual y seguimos con el paso 3. Si este nodo es el inicial, significa que el grafo no contiene ciclos y el algoritmo termina. Lo que el algoritmo hace es tomar cada nodo, por tumo, como raíz de lo que espera será un árbol, y realiza en él una búsqueda de primero en profundidad. Si regresa a un nodo que ya visitó, habrá encontrado un ciclo. Si agota todos los arcos que salen de un nodo dado, retro­ cede al nodo anterior. Si retrocede hasta la raíz y no puede llegar más lejos, quiere decir que el subgrafo accesible desde el nodo actual no contiene ciclos. Si se cumple esta propiedad para todos los nodos, todo el grafo carecerá de ciclos y el sistema no caerá en un bloqueo irreversible. Para ver cómo funciona el algoritmo en la práctica, apliquémoslo al grafo de la figura 3-5a. El orden en que se procesan los nodos es arbitrario, así que simplemente inspeccionémoslos de izquierda a derecha y de arriba hacia abajo, ejecutando el algoritmo primero a partir de R, y luego sucesivamente a partir de A, B, C, 5, D, T, E, F, etc. Si encontramos un ciclo, el algo­ ritmo parará. Partimos de ^ y asignamos a L la lista vacía. Luego añadimos /? a la lista y pasamos a la única posibilidad, A, que añadimos a L, lo que nos da L = [R, A]. De A pasamos a S, con lo que obtenemos L = [R, A, 5]. De S no salen arcos, así que tenemos que retroceder a A. Puesto que de A no salen arcos que no estén ya marcados, retrocedemos a R, con lo que termina nues­ tra inspección de R. Ahora reiniciamos el algoritmo partiendo de A y asignando otra vez a ¿ la lista vacía. Es­ ta búsqueda también se detiene pronto, por lo que volvemos a comenzar en B. Desde B, y hasta llegar a D, seguimos los arcos que salen. Cuando llegamos n D , L - [fi, T, £, V, G, U, D]. Aho­ ra debemos tomar una decisión (al azar). Si escogemos S, llegamos a un callejón sin salida y retrocedemos a D. En la segunda ocasión escogemos T y actualizamos L a [fi, T, £, V, G, U, Dy T\. En ese momento descubrimos el ciclo y paramos el algoritmo. Este algoritmo dista mucho de ser óptimo. Hay uno mejor en Even (1979). No obstante, sirve para demostrar que existe un algoritmo para detectar bloqueos irreversibles.