O Problema do Barbeiro Dorminhoco (com threads)

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_problem
Sistemas Operacionais Modernos, 2a ed - A.S.Tanenbaum