Em ciência da computação, o problema do barbeiro dorminhoco é um problema clássico de comunicação inter-processo e sincronização entre múltiplos processos.
O problema é análogo a manter o barbeiro ocupado enquanto há clientes, e descansando quando não há nenhum (fazendo isso de uma maneira ordenada).
O barbeiro e seus clientes correspondem aos processos mencionados acima.
O problema:
Na barbearia há um barbeiro, uma cadeira de barbeiro e
n cadeiras para eventuais clientes esperarem a vez. Quando não há clientes, o barbeiro senta-se na cadeira de barbeiro e cai no sono. Quando chega um cliente, ele precisa acordar o barbeiro. Se outros clientes chegarem enquanto o barbeiro estiver cortando o cabelo de um cliente, eles se sentarão (se houver cadeiras vazias) ou sairão da barbearia (se todas as cadeiras estiverem ocupadas). O problema é programar o barbeiro e os clientes sem cair em condições de disputa. Esse problema é semelhante a situações com várias filas, como uma mesa de atendimento de telemarketing com diversos atendentes e com um sistema computadorizado de chamadas em espera, atendendo a um número limitado de chamadas que chegam.
A solução aqui apresentada usa três semáforos:
customers, que conta os clientes à espera de atendimento (exceto o cliente que está na cadeira de barbeiro, que não está esperando);
barbers, o número de barbeiros (0 ou 1) que estão ociosos à espera de clientes, e
mutex, que é usado para exclusão mútua. Precisamos ainda de uma variável,
waiting, que também conta os clientes à espera de atendimento. É essencialmente uma cópia de
customers. A razão de se ter
waiting é que não há uma maneira de ler o valor atual do semáforo. Nessa solução, um cliente que entra na barbearia deve contar o número de clientes à espera de atendimento. Se este for menor que o número de cadeiras, ele ficará; do contrário, ele sairá.
Na solução, quando chega de manhã para trabalhar, o barbeiro executa o método
barber, que o leva a bloquear sobre o semáforo
customers, que inicialmente está em 0. O barbeiro então vai dormir, e permanece dormindo até que o primeiro cliente apareça.
Quando chega, o cliente executa
customer e inicia obtendo
mutex para entrar em uma região crítica. Se um outro cliente chega logo em seguida, o segundo nada pode fazer até que o primeiro libere o
mutex. O cliente então verifica se o número de clientes à espera é menor que o número de cadeiras. Se não for, ele liberará o
mutex e sairá sem cortar o cabelo.
Se houver uma cadeira disponível, o cliente incrementará a variável inteira
waiting. Ele faz então um up no semáforo
customers, que acorda o barbeiro. Nesse ponto, o cliente e o barbeiro estão ambos acordados. Quando o cliente libera
mutex, o barbeiro o pega, faz alguma limpeza e começa a cortar o cabelo.
Quando termina o corte de cabelo, o cliente sai do procedimento e deixa a barbearia. Diferente de nossos exemplos anteriores, não há um laço para o cliente porque para cada um deles terá apenas um corte de cabelo. O barbeiro, contudo, contém um laço para tentar obter o próximo cliente. Se houver algum outro cliente, um novo corte de cabelo será iniciado. Do contrário, o barbeiro cairá no sono.
Abaixo está a implementação do problema, com os resultados obtidos:
Figura1: Saída do Programa
(clique na figura para melhor visualização)Código:
#include "stdio.h"
#include "unistd.h"
#include "stdlib.h"
#include "pthread.h"
#include "semaphore.h"
#define CHAIRS 5 /* número de cadeiras para os clientes à espera */
#define TRUE 1
sem_t customers; /* número de cliente à espera de atendimento */
sem_t barbers; /* número de barbeiros à espera de clientes */
sem_t mutex; /* para exclusão mútua */
int waiting = 0; /* clientes que estão esperando (não estão cortando) */
/* protótipos */
void* barber(void *arg);
void* customer(void *arg);
void cut_hair();
void customer_arrived();
void get_haircut();
void giveup_haircut();
int main() {
sem_init(&customers, TRUE, 0);
sem_init(&barbers, TRUE, 0);
sem_init(&mutex, TRUE, 1);
pthread_t b, c;
/* criando único barbeiro */
pthread_create(&b, NULL, (void *) barber, NULL);
/* criação indefinida de clientes */
while(TRUE) {
pthread_create(&c, NULL, (void *) customer, NULL);
sleep(1);
}
return 0;
}
void* barber(void *arg) {
while(TRUE) {
sem_wait(&customers); /* vai dormir se o número de clientes for 0 */
sem_wait(&mutex); /* obtém acesso a 'waiting' */
waiting = waiting - 1; /*descresce de um o contador de clientes à espera */
sem_post(&barbers); /* um barbeiro está agora pronto para cortar cabelo */
sem_post(&mutex); /* libera 'waiting' */
cut_hair(); /* corta o cabelo (fora da região crítica) */
}
pthread_exit(NULL);
}
void* customer(void *arg) {
sem_wait(&mutex); /* entra na região crítica */
if(waiting < CHAIRS) { /* se não houver cadeiras vazias, saia */
customer_arrived();
waiting = waiting + 1; /* incrementa o contador de clientes à espera */
sem_post(&customers); /* acorda o barbeiro se necessário */
sem_post(&mutex); /* libera o acesso a 'waiting' */
sem_wait(&barbers); /* vai dormir se o número de barbeiros livres for 0 */
get_haircut(); /* sentado e sendo servido */
} else {
sem_post(&mutex); /* a barbearia está cheia; não espera */
giveup_haircut();
}
pthread_exit(NULL);
}
void cut_hair() {
printf("Barbeiro estah cortando o cabelo de alguem!\n");
sleep(3);
}
void customer_arrived() {
printf("Cliente chegou para cortar cabelo!\n");
}
void get_haircut() {
printf("Cliente estah tendo o cabelo cortado!\n");
}
void giveup_haircut() {
printf("Cliente desistiu! (O salao estah muito cheio!)\n");
}
Fontes:
http://en.wikipedia.org/wiki/Sleeping_barber_problemSistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum
