1. Qué es un RAG
Un grafo de asignación de recursos (Resource Allocation Graph, RAG) es un grafo dirigido que representa el estado de asignación de recursos en un sistema. Los nodos son procesos y recursos; las aristas representan solicitudes y asignaciones. Es una herramienta visual para detectar interbloqueos.
El RAG fue propuesto por Coffman et al. en 1971 como parte de su análisis de los interbloqueos. Es la base de los algoritmos de detección de deadlocks.
El RAG tiene dos tipos de nodos y dos tipos de aristas:
- Nodos de proceso: representan los procesos (o hilos) del sistema.
- Nodos de recurso: representan los recursos (mutexes, semáforos, archivos, etc.).
- Arista de solicitud (request edge): de un proceso a un recurso. Indica que el proceso está esperando el recurso.
- Arista de asignación (assignment edge): de un recurso a un proceso. Indica que el recurso está asignado al proceso.
2. Los nodos: procesos y recursos
Los nodos se representan gráficamente de forma distinta:
| Tipo de nodo | Representación | Ejemplo |
|---|---|---|
| Proceso | Círculo | P1, P2, P3 |
| Recurso (instancia única) | Cuadrado | R1, R2 |
| Recurso (múltiples instancias) | Cuadrado con puntos | R1 (3 instancias) |
Los procesos se representan como círculos y los recursos como cuadrados. Si un recurso tiene múltiples instancias, se representan como puntos dentro del cuadrado.
3. Las aristas: asignación y solicitud
Las aristas se representan como flechas:
| Tipo de arista | Representación | Significado |
|---|---|---|
| Solicitud (request) | Flecha de proceso a recurso | El proceso está esperando el recurso. |
| Asignación (assignment) | Flecha de recurso a proceso | El recurso está asignado al proceso. |
La dirección de la flecha indica la relación: de proceso a recurso = solicitud; de recurso a proceso = asignación.
4. Cómo se construye un RAG
Para construir un RAG:
- Crear un nodo por proceso. Un círculo por cada proceso del sistema. procesos
- Crear un nodo por recurso. Un cuadrado por cada tipo de recurso. recursos
- Añadir aristas de asignación. Para cada recurso asignado a un proceso, una flecha del recurso al proceso. asignación
- Añadir aristas de solicitud. Para cada recurso solicitado por un proceso, una flecha del proceso al recurso. solicitud
El RAG resultante muestra el estado completo del sistema: quién tiene qué y quién espera qué.
5. Un ejemplo desarrollado
El ejemplo del tema 35 (dos hilos, dos mutexes, orden inverso):
El RAG muestra un ciclo: P1 → R2 → P2 → R1 → P1. Este ciclo indica que hay un interbloqueo.
6. Los ciclos y el deadlock
La regla fundamental del RAG es:
| Tipo de recurso | Ciclo en el RAG | Deadlock |
|---|---|---|
| Todos los recursos tienen una sola instancia | Si hay un ciclo, hay deadlock. | Sí |
| Algunos recursos tienen múltiples instancias | Si hay un ciclo, puede haber deadlock (hay que verificar). | Posiblemente |
Con recursos de instancia única, un ciclo en el RAG es suficiente y necesario para indicar deadlock. Con recursos de múltiples instancias, un ciclo es necesario pero no suficiente: hay que verificar si hay un deadlock real.
7. Recursos con una sola instancia
Si todos los recursos tienen una sola instancia, la regla es simple: si hay un ciclo, hay deadlock. No hay excepciones.
Esto es porque, con una sola instancia, cada recurso solo puede estar asignado a un proceso. Si hay un ciclo, cada proceso en el ciclo está esperando un recurso que tiene otro proceso del ciclo, y ninguno puede liberarlo.
8. Recursos con múltiples instancias
Si algunos recursos tienen múltiples instancias, un ciclo no garantiza deadlock. Por ejemplo, si un recurso tiene 2 instancias y solo una está asignada, el proceso que solicita el recurso puede obtener la otra instancia, rompiendo el ciclo.
Para verificar si hay deadlock con recursos de múltiples instancias, se usa el algoritmo del banquero (tema 38) o la detección de deadlocks (tema 39).
9. Limitaciones del RAG
El RAG tiene estas limitaciones:
- No detecta deadlocks con recursos de múltiples instancias: un ciclo no garantiza deadlock.
- No previene deadlocks: solo detecta, no previene.
- No maneja la evasión: no dice cómo evitar el deadlock, solo lo detecta.
- Escala mal: con muchos procesos y recursos, el grafo es difícil de analizar.
Por eso, el RAG se usa principalmente como herramienta de visualización y análisis, no como algoritmo de detección en sistemas reales.
10. Simulador interactivo
Este simulador construye un RAG y detecta ciclos:
Simulador · grafo de asignación de recursos
11. Resumen
- El RAG es un grafo dirigido con nodos de proceso (círculos) y recurso (cuadrados).
- Las aristas de asignación van de recurso a proceso; las de solicitud de proceso a recurso.
- Con recursos de instancia única, un ciclo indica deadlock.
- Con recursos de múltiples instancias, un ciclo puede o no indicar deadlock.
- El RAG es una herramienta de visualización y análisis.
- No previene deadlocks, solo los detecta (y no siempre).
12. Preguntas de repaso
Intenta responder cada una antes de abrir la respuesta.
1. ¿Qué es un RAG?
Un grafo dirigido que muestra la asignación de recursos a procesos y las solicitudes pendientes.
2. ¿Cómo se representan los procesos y recursos?
Procesos como círculos, recursos como cuadrados.
3. ¿Qué es una arista de asignación?
Una flecha de recurso a proceso, indicando que el recurso está asignado al proceso.
4. ¿Qué es una arista de solicitud?
Una flecha de proceso a recurso, indicando que el proceso está esperando el recurso.
5. ¿Qué indica un ciclo en el RAG con recursos de instancia única?
Deadlock.
6. ¿Qué indica un ciclo con recursos de múltiples instancias?
Posiblemente deadlock (hay que verificar).
7. ¿El RAG previene deadlocks?
No. Solo los detecta.
8. ¿Cuál es la limitación principal del RAG?
No detecta deadlocks con recursos de múltiples instancias de forma concluyente.
9. ¿Para qué se usa el RAG?
Para visualizar y analizar el estado de asignación de recursos.
10. ¿Qué algoritmo se usa para verificar deadlocks con recursos de múltiples instancias?
El algoritmo del banquero (tema 38) o la detección de deadlocks (tema 39).
Para practicar
- Dibuja el RAG para el ejemplo de deadlock del tema 35.
- Dibuja el RAG para un sistema sin deadlock.
- Explica por qué un ciclo con recursos de múltiples instancias no garantiza deadlock.
- Diseña un RAG con 3 procesos y 3 recursos que tenga un ciclo.
- Investiga cómo se implementa la detección de deadlocks en el núcleo de Linux.
- Explica la diferencia entre detección y prevención de deadlocks.