Problema del Barbero Dormilón: Soluciones con Monitores en Concurrencia

Problema del Barbero Dormilón con Monitores

A continuación se presentan tres variantes de solución al clásico problema del barbero dormilón, implementadas mediante monitores con variables de condición. Cada variante corresponde a una configuración distinta de la barbería.

Variante 1: k barberos, sin prioridad, con sillón y sala de espera

Parámetros: k barberos, sin prioridad, con sillón y sala de espera.

Procedimiento del barbero

void barbero(int barbero) {
    barberia.esperar_cliente(barbero);
    do {
        afeitar();
        barberia.avisar_sgte(barbero);
    } while (1);
}

void cliente() {
    barberia.solicitar_barbero();
}

Monitor de la barbería

condition barberos, clientes, afeitando[k];
int mi_barbero = -1;

entry void solicitar_barbero() {
    int barbero;
    if (empty(barberos))
        wait(clientes);
    else {
        mi_barbero = buscar_barbero_libre();
        remove_barberos_libres(mi_barbero);
        signal(barberos);
    }
    wait(afeitando[mi_barbero]);
    if (!empty(clientes))
        signal(clientes);
}

entry void esperar_cliente(int barbero) {
    if (empty(clientes)) {
        insert_barberos_libres(barbero);
        wait(barberos);
    } else {
        remove_barberos_libres(barbero);
        mi_barbero = barbero;
        signal(clientes);
    }
}

entry void avisar_sgte(int barbero) {
    if (empty(clientes)) {
        insert_barberos_libres(barbero);
        signal(afeitando[barbero]);
        wait(barberos);
    } else {
        mi_barbero = barbero;
        signal(afeitando[barbero]);
    }
}

Variante 2: k barberos, sin prioridad, con sala y sillón (orden alternativo)

Parámetros: k barberos, sin prioridad, con sala y sillón (orden invertido en la comunicación).

condition barberos, clientes, afeitando[k];
int mi_barbero = -1;

entry void solicitar_barbero() {
    if (empty(barberos))
        wait(clientes);
    else {
        mi_barbero = buscar_barbero_libre();
        remove_barberos_libres(mi_barbero);
        signal(barberos);
    }
    if (!empty(afeitando[mi_barbero]))
        signal(afeitando[mi_barbero]);
    wait(afeitando[mi_barbero]);
}

entry void esperar_cliente(int barbero) {
    if (empty(clientes)) {
        insert_barberos_libres(barbero);
        wait(barberos);
    } else {
        remove_barberos_libres(barbero);
        signal(clientes);
    }
}

entry void avisar_sgte(int barbero) {
    if (!empty(clientes)) {
        mi_barbero = barbero;
        signal(clientes);
    } else {
        insert_barberos_libres(barbero);
        signal(afeitando[barbero]);
        wait(barberos);
    }
}

Variante 3: 1 barbero, 2 tipos de clientes (VIP y no VIP), con sala

Parámetros: 1 barbero, dos tipos de clientes: VIP y no VIP, con sala de espera. Los clientes VIP tienen prioridad sobre los no VIP.

condition VIP, noVIP, barbero_dormido;
bool afeitando_VIP = false;
int VIP_espera = 0, noVIP_espera = 0;

entry void solicitar_barbero(string tipo) {
    if (tipo == VIP) {
        VIP_espera++;
        if (!empty(barbero_dormido))
            signal(barbero_dormido);
        wait(VIP);
        VIP_espera--;
    } else {
        noVIP_espera++;
        if (!empty(barbero_dormido))
            signal(barbero_dormido);
        wait(noVIP);
        noVIP_espera--;
    }
}

entry void esperar_cliente(void) {
    if ((VIP_espera == 0) && (noVIP_espera == 0))
        wait(barbero_dormido);
    else if (VIP_espera > 0)
        afeitando_VIP = true;
    else
        afeitando_VIP = false;
}

entry void avisar_sgte(void) {
    if (afeitando_VIP) {
        if (VIP_espera > 1)
            signal(VIP);
        else if (noVIP_espera > 0) {
            afeitando_VIP = false;
            signal(VIP);
        } else {
            afeitando_VIP = false;
            signal(VIP);
            wait(barbero_dormido);
        }
    } else {
        if (VIP_espera > 0) {
            afeitando_VIP = true;
            signal(noVIP);
        } else if (noVIP_espera > 1)
            signal(noVIP);
        else {
            signal(noVIP);
            wait(barbero_dormido);
        }
    }
}

Observaciones

Las tres variantes utilizan monitores para garantizar la exclusión mutua sobre el estado compartido de la barbería, mientras que las variables de condición permiten a barberos y clientes suspenderse y reanudarse de forma coordinada, evitando condiciones de carrera y espera activa.