Evasión: el algoritmo del banquero

1. Qué es la evasión

La evasión (avoidance) de interbloqueos consiste en tomar decisiones en tiempo de ejecución para evitar entrar en un estado inseguro. A diferencia de la prevención (que es estática), la evasión es dinámica: el sistema evalúa cada solicitud de recurso y la concede solo si el estado resultante es seguro.

La evasión requiere conocer de antemano la demanda máxima de cada proceso: cuántos recursos de cada tipo va a necesitar en el peor caso. Con esta información, el sistema puede calcular si conceder un recurso deja el sistema en un estado seguro.

2. Estados seguros e inseguros

Un estado seguro es un estado en el que existe al menos una secuencia de ejecución de los procesos que permite que todos terminen, concediendo los recursos en el orden adecuado. Un estado inseguro es un estado en el que no existe tal secuencia: puede haber deadlock.

La diferencia clave es que un estado inseguro no es necesariamente un deadlock: es un estado en el que el deadlock es posible, pero no inevitable. Si los procesos liberan los recursos en el orden correcto, puede que no haya deadlock. Pero el sistema no puede garantizarlo.

La evasión consiste en no conceder un recurso si el estado resultante sería inseguro. Esto garantiza que el sistema nunca entra en un estado inseguro, y por lo tanto nunca hay deadlock.

3. El algoritmo del banquero

El algoritmo del banquero (banker's algorithm) es el algoritmo clásico de evasión. Fue propuesto por Edsger Dijkstra en 1965. La analogía es un banquero que presta dinero: solo presta si, después del préstamo, puede satisfacer a todos los clientes (incluso si todos piden su máximo).

El algoritmo tiene dos partes:

• Prueba de seguridad: dado un estado, determinar si es seguro.
• Asignación de recursos: dado una solicitud, determinar si se puede conceder sin entrar en un estado inseguro.

4. El modelo de recursos

El algoritmo del banquero usa estos datos para cada proceso P_i:

La relación invariante es: Available + Σ Allocation_i = total de recursos.

5. La prueba de seguridad

La prueba de seguridad determina si un estado es seguro. El algoritmo es:

1. Inicializar: Work = Available. Finish[i] = false para todos. init
2. Buscar un proceso i tal que Finish[i] = false y Need[i] ≤ Work. buscar
3. Si existe: Work = Work + Allocation[i]. Finish[i] = true. Volver al paso 2. simular
4. Si no existe: si todos los Finish[i] son true, el estado es seguro. Si no, es inseguro. resultado

La idea es simular que los procesos terminan en algún orden, liberando sus recursos. Si se puede encontrar un orden en el que todos terminen, el estado es seguro.

6. Un ejemplo desarrollado

Un sistema con 3 procesos y 3 tipos de recursos (A, B, C) con 10, 5, 7 instancias respectivamente:

Available = (10-0-2-3, 5-1-0-0, 7-0-0-2) = (5, 4, 5).

Prueba de seguridad:

1. Work = (5,4,5). Buscar proceso con Need ≤ Work. init
2. P1: Need = (1,2,2) ≤ (5,4,5). ✓. Work = (5,4,5) + (2,0,0) = (7,4,5). Finish[1] = true. P1
3. P0: Need = (7,4,3) ≤ (7,4,5). ✓. Work = (7,4,5) + (0,1,0) = (7,5,5). Finish[0] = true. P0
4. P2: Need = (6,0,0) ≤ (7,5,5). ✓. Work = (7,5,5) + (3,0,2) = (10,5,7). Finish[2] = true. P2
5. Todos terminaron. El estado es seguro. Secuencia segura: P1, P0, P2. seguro

7. Asignación de recursos

Cuando un proceso solicita recursos, el sistema:

1. Verifica que la solicitud sea válida: Request ≤ Need (el proceso no pide más de lo que declaró). validar
2. Verifica que haya suficientes recursos: Request ≤ Available. disponibilidad
3. Simula la asignación: Available -= Request, Allocation += Request, Need -= Request. simular
4. Verifica la seguridad: ejecuta la prueba de seguridad. seguridad
5. Si es seguro: la asignación se confirma. Si es inseguro, se revierte. decidir

Si la asignación deja el sistema en un estado inseguro, se deniega (el proceso espera).

8. Implementación paso a paso

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>

#define N 5       /* número de procesos */
#define M 3       /* número de tipos de recurso */

int available[M];       /* recursos disponibles */
int allocation[N][M];    /* asignación actual */
int max_need[N][M];     /* demanda máxima */
int need[N][M];         /* necesidad (max - allocation) */

/* Calcular need = max - allocation. */
void calcular_need(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            need[i][j] = max_need[i][j] - allocation[i][j];
}

/* Prueba de seguridad. Retorna 1 si es seguro. */
int es_seguro(int *secuencia) {
    int work[M];
    int finish[N];
    for (int j = 0; j < M; j++) work[j] = available[j];
    for (int i = 0; i < N; i++) finish[i] = 0;

    int count = 0;
    while (count < N) {
        int found = 0;
        for (int i = 0; i < N; i++) {
            if (!finish[i]) {
                int ok = 1;
                for (int j = 0; j < M; j++) {
                    if (need[i][j] > work[j]) { ok = 0; break; }
                }
                if (ok) {
                    for (int j = 0; j < M; j++)
                        work[j] += allocation[i][j];
                    finish[i] = 1;
                    secuencia[count++] = i;
                    found = 1;
                }
            }
        }
        if (!found) break;  /* no se encontró proceso: inseguro */
    }
    return (count == N);
}

/* Solicitar recursos. Retorna 1 si se conceden. */
int solicitar(int pid, int request[]) {
    /* Verificar que request <= need. */
    for (int j = 0; j < M; j++) {
        if (request[j] > need[pid][j]) return 0;  /* solicitud inválida */
    }
    /* Verificar que request <= available. */
    for (int j = 0; j < M; j++) {
        if (request[j] > available[j]) return 0;  /* no hay suficientes */
    }
    /* Simular la asignación. */
    for (int j = 0; j < M; j++) {
        available[j] -= request[j];
        allocation[pid][j] += request[j];
        need[pid][j] -= request[j];
    }
    /* Verificar seguridad. */
    int secuencia[N];
    if (es_seguro(secuencia)) {
        return 1;  /* conceder */
    }
    /* Revertir. */
    for (int j = 0; j < M; j++) {
        available[j] += request[j];
        allocation[pid][j] -= request[j];
        need[pid][j] += request[j];
    }
    return 0;  /* denegar */
}

9. Limitaciones

• Requiere conocer la demanda máxima: en la práctica, los procesos no conocen su demanda máxima de antemano.
• Número fijo de procesos: el algoritmo asume que el número de procesos es fijo.
• Recursos fijos: asume que el número de recursos no cambia.
• Overhead: la prueba de seguridad es O(n²·m), donde n es el número de procesos y m el número de tipos de recurso.
• Poco usado en la práctica: la mayoría de los sistemas usan prevención o detección, no evasión.

10. Simulador interactivo

Este simulador ejecuta el algoritmo del banquero y muestra si el estado es seguro:

11. Resumen

• La evasión toma decisiones en tiempo de ejecución para evitar estados inseguros.
• El algoritmo del banquero es el algoritmo clásico de evasión.
• Un estado seguro tiene una secuencia en la que todos los procesos terminan.
• La prueba de seguridad simula que los procesos terminan y liberan recursos.
• La asignación de recursos se concede solo si el estado resultante es seguro.
• Requiere conocer la demanda máxima de cada proceso.
• Es poco usado en la práctica por su overhead y requisitos.

12. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Ejecuta la prueba de seguridad para el ejemplo del tema.
2. Diseña un conjunto de procesos y recursos y determina si es seguro.
3. Implementa el algoritmo del banquero en C.
4. Explica por qué un estado inseguro no es necesariamente un deadlock.
5. Investiga cómo se implementa la evasión en sistemas reales.
6. Compara la evasión con la prevención y la detección.