El Barbero Durmiente: Clásicos de la Programación

Uno de los problemas clásicos para el cómputo paralelo es el barbero durmiente. Según narra la historia, tenemos una barbería, con una única silla y un único barbero, el cuál debe atender a todos los clientes que llegan.

El problema consiste en un barbero durmiente, que siempre se duerme cuando no existen clientes en espera, los cuáles al llegar se sientan en una fila de sillas.

Si un cliente llega y el barbero está durmiendo, éste lo despierta y lo comienza a afeitar, pero si se encuentra atendiendo a otro cliente, se queda esperando en la silla hasta que el barbero se desocupe.

En programación paralela, la zona crítica es aquel recurso compartido que sólo debe ser accedido por un solo hilo a la vez, para evitar la competencia por el recurso, y para ello el barbero durmiente ha sido uno de los problemas clásicos que utiliza mecanismos de exclusión mutua para resolver el problema de competencia por un recurso dentro de la región crítica.

Para ello se utilizan semáforos para proteger la variable compartida y así evitar que se sobreescriba, produciendo resultados no deseados en el resto de hilos.

Código en C para el barbero durmiente

A continuación se muestra el código de cómo se podría resolver un problema de concurrencia a través del método del barbero durmiente. Para éste ejemplo de concurrencia hacemos uso del lenguaje C y de la biblioteca de manejo de hilos pthreads, además de la biblioteca semaphore. Se ha procurado mostrar la documentación adecuada al código para ayudar al lector a entender cada una de las partes del código.

 // Importar bibliotecas
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
// Número de clientes
#define MAX_CLIENTES 25
void *cliente(void *num);
void *barbero(void *num);
// Limitar acceso a las sillas de espera al mismo tiempo
sem_t SillaEspera;
// Acceso a la silla del barbero
sem_t barberosilla;
// barbero duerme mientras no hay cliente
sem_t barberodormir;
// El cliente debe esperar hasta que el barbero termine de cortar su cabello
sem_t CorteCabello;
// Bandera para detener el hilo del barbero cuando todos los hilos han sido atendidos
int TodosAtendidos = 0;
int main(int argc, char *argv[]) {
    pthread_t btid;
    pthread_t tid[MAX_CLIENTES];
    //long RandSeed;
    int i, numclientes, numsillas;
    int Number[MAX_CLIENTES];
    
    if (argc != 3) {
        printf("Use: barbero <Num clientes> <Num sillas>\n");
        exit(-1);
    }
    
    //Toma los argumentos
    numclientes = atoi(argv[1]);
    numsillas = atoi(argv[2]);
    
    // El número de threads es menor al número de clientes que soporta
    if (numclientes > MAX_CLIENTES) {
        printf("El número máximo de clientes es %d.\n", MAX_CLIENTES);
        exit(-1);
    }
    // Inicializar el arreglo
    for (i=0; i<MAX_CLIENTES; i++) {
        Number[i] = i;
    }
    
    // Valores iniciales de semáforos
    sem_init(&SillaEspera, 0, numsillas);
    sem_init(&barberosilla, 0, 1);
    sem_init(&barberodormir, 0, 0);
    sem_init(&CorteCabello, 0, 0);
    
    // Crear thread del barbero
    pthread_create(&btid, NULL, barbero, NULL);
    
    // Crear thread de los clientes
    for (i=0; i<numclientes; i++) {
        pthread_create(&tid[i], NULL, cliente, (void *)&Number[i]);
    }
    
    // Une los threads al finalizar
    for (i=0; i<numclientes; i++) {
        pthread_join(tid[i],NULL);
    }
    
    // Al finalizar todos los clientes
    TodosAtendidos = 1;
    sem_post(&barberodormir);  // Despierta el barbero para cerrar la barbería
    pthread_join(btid,NULL);
}
void *cliente(void *number) {
    int num = *(int *)number;
    
    //randwait(5);
    printf("El cliente %d llegó a la barbería\n", num+1);
    
    // Espera para sentarse
    sem_wait(&SillaEspera);
    printf("El cliente %d se sienta en la sala de espera\n", num+1);
    
    // Espera que se levante el barbero de su silla
    sem_wait(&barberosilla);
    
    // El cliente desocupa su silla de la sala de espera
    sem_post(&SillaEspera);
    
    // Se levanta el barbero
    printf("El cliente %d levanta al barbero\n", num+1);
    sem_post(&barberodormir);
    
    // Espera que el barbero le corte su cabello
    sem_wait(&CorteCabello);
    
    // Deja su silla del barbero
    sem_post(&barberosilla);
    printf("El cliente %d se fué\n", num+1);
    return 0;
}
void *barbero(void *num) {
    while (!TodosAtendidos) {
        printf("El barbero está durmiendo\n");
        sem_wait(&barberodormir);
        if (!TodosAtendidos) {
            printf("El barbero está cortando cabello\n");
            // Terminó de hacer el corte
            sem_post(&CorteCabello);
            printf("Ya terminó\n");
        }
    }
    printf("El barbero salió de la barbería\n");
    return 0;
}

Compilación y ejecución del código

Debido a que hacemos uso de la biblioteca pthread, utilizamos GCC con las opciones para tal compilación, como se muestra en el siguiente comando:

gcc barbero.c -o barbero -lpthread -lm

Al final la ejecución del programa se da al incluir el número de clientes que van a entrar a la barbería y el número de sillas existentes, el código emulará el problema del barbero durmiente.

./barbero [número de clientes] [número de sillas]

Otros ejemplos clásicos de programación paralela

Otro ejemplo clásico de concurrencia es el de productores y consumidores, el cuál maneja el consumo de un recurso compartido y limitante.