Problema del Barbero durmiente

En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. 

Cuando llega un nuevo cliente, éste o bien despierta al barbero o si el barbero está afeitando a otro cliente se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). 

El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos y objetos de exclusión mutua para proteger la sección crítica.

Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS.

En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos.

El problema del peluquero dormilón (originalmente, el barbero dormilón) es un clásico de la Programación Concurrente. En él se propone la discusión sobre cómo gestionar el “transito” por una pequeña peluquería (recurso compartido), por parte de dos tipos de procesos: el peluquero y los clientes. El enunciado sugiere que durante la ejecución la interacción entre el peluquero y un cliente se puede producir muy a menudo y que, por tanto, deben establecerse los mecanismos de sincronización adecuados para evitar que los dos “colisionen” dentro la peluquería; es decir, asegurar uno sólo es el que se mueve en cada momento.

DIAGRAMA DE FLUJO

A continuacion les dejo el codigo en C para que puedan observar el funcionamiento del Algoritmo.

#include <stdlib.h>

#include <stdio.h>

#include <semaphore.h>

#include <pthread.h>

#include <math.h>

typedef enum {LLENO, CORTADO} respuesta;

#define NUM_CLIENTES 6 // Numero de clientes

#define N 3 // Numero max de clientes en la barberia

int clientes = 0; // Numero de clientes en la barberia

int quien = -1; // Cliente que esta siendo atendido

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; //para excl mutua ops monitor

pthread_cond_t silla, sillon, sube_sillon, dormir;

void pcliente(int i, char *s) {printf(“Cliente: %d -> %s\n”, i,s);}

void pbarbero (char *s) {printf(“Barbero: -> %s\n”, s);}

//———————————– inicio monitor

int entra_barberia(int i) {

pcliente(i,”ENTRO en la barberia”);

pthread_mutex_lock( &m );

if (clientes >= N) {pthread_mutex_unlock(&m ); return LLENO;} // No cabe

else {

clientes++;

if (clientes==1) {

pcliente(i,”DESPIERTO al barbero”);

pthread_cond_signal(&dormir);

}

else {

pcliente(i,”ESPERO mi turno”);

pthread_cond_wait(&silla, &m );

pthread_cond_signal(&sube_sillon);

}

quien = i;

pthread_cond_wait (&sillon, &m ); /* Esperar a que acabe el corte.*/

pcliente(i,”MI PELO TAN LINDAMENTE CORTADO!!!! ADIEU! \n”);

pthread_mutex_unlock(&m );

return CORTADO;

}

}

void espera_cliente() {

pthread_mutex_lock( &m );

if (!clientes) {

pbarbero(“ME VOY A DORMIR”);

pthread_cond_wait(&dormir,&m);

pbarbero(“YA VOYYYY!!!”);

}

else {

pbarbero(“QUE PASE EL SIGUIENTE!!!!”);

pthread_cond_signal(&silla );

pthread_cond_wait(&sube_sillon,&m);

}

pthread_mutex_unlock( &m);

}

void fin_corte() {

pthread_mutex_lock(&m);

pthread_cond_signal(&sillon); clientes–; pbarbero(“FIN CORTE”);

pthread_mutex_unlock(&m);

}

void corta_pelo() {

int r=rand()%10000;

//usleep(10); (con sube_sillon, ya no es necesario)

pthread_mutex_lock(&m ); // Protege el acceso a la variable “quien”

pbarbero(“CORTANDO EL PELO (Chis, Chas, Chis, Chas)”);

printf(” A %d (%d useg.)\n”,quien,r);

pthread_mutex_unlock(&m );

usleep(r);

}

void da_una_vuelta(int i, int t) {

pcliente(i,”VOY a dar una vuelta”); printf(” durante (%d useg.)\n”,t);

usleep(t);

pcliente(i,”VENGO de dar una vuelta”);

}

// ——————————- fin monitor

void *cliente(void *arg) {

long int i=(long int) arg;

do {da_una_vuelta(i,rand()%10000);} while (entra_barberia(i)==LLENO);

}

void *barbero(void *arg) {

while (1) {espera_cliente(); corta_pelo(); fin_corte();}

}

int main(void) {

long int i;

pthread_t id_clientes[NUM_CLIENTES], id_barbero;

srand( (unsigned)time( NULL ) );

pthread_cond_init(&silla, 0);

pthread_cond_init(&sillon, 0);

pthread_cond_init(&sube_sillon, 0);

pthread_cond_init(&dormir, 0);

pthread_create(&id_barbero, NULL, barbero, NULL); sleep(1);

for (i=0; i<NUM_CLIENTES; i++) pthread_create(&id_clientes[i], NULL, cliente, (void *) i);

for (i=0; i<NUM_CLIENTES; i++) pthread_join(id_clientes[i], NULL);

}