Um dos problemas clássicos de programação concorrente é o Barbeiro Dorminhoco. Esse problema é baseado no trabalho clássico primeiramente proposto por Edsger W. Dijkstra,
em 1968. (EW Dijkstra, "Co-operating Sequential Processes", in Programming Languages , Academic Press, 1968, pp. 43-112.). O trabalho dessa disciplina foi baseado na proposta da Professora Janet Davis da Universidade Grinnell
College. 
- Três barbeiros trabalham de forma independente em uma barbearia.
A barbearia tem 3 cadeiras de barbeiro, cada uma das quais é atribuída a um barbeiro. - Cada barbeiro segue o mesmo plano de trabalho:
- O barbeiro dorme na sua cadeira (ou lê Caras...), quando terminou de atender um cliente e não há nenhum cliente à espera.
-
Quando o barbeiro está dormindo, espera ser acordado por um novo cliente. Um sinal na barbearia indica o barbeiro com sono mais
longo para que o cliente saber qual barbeiro deve acordar primeiro se vários
barbeiros estão dormindo.
- Uma vez desperto, o barbeiro corta o cabelo do cliente na cadeira de barbeiro.
- Após o corte ser feito, o cliente paga ao barbeiro e, em seguida, está livre para sair.
- Depois de receber o pagamento, o barbeiro chama o próximo cliente na fila de espera (se houver).
- Se houver cliente na fila de espera, o cliente se senta na cadeira do barbeiro e o barbeiro começa o cortar o cabelo imediatamente.
- Se não houver cliente esperando, o barbeiro senta na cadeira e volta a dormir.
Cada cliente segue a seguinte sequência de eventos: - Quando o cliente entra na barbearia e há barbeiro disponível, ele é atendido imediatamente.
- Se não houver barbeiro disponível, o cliente espera na sala de espera em pé ou sentado. Na sala de espera da barbearia há lugar para 20 pessoas (10 em
pé e 10 sentados).
- Caso o cliente não encontre lugar na barbearia (em pé ou sentado) ele desiste e vai embora.
- Se pelo menos um barbeiro
estiver dormindo, o cliente olha para o sinal, acorda o barbeiro que está dormindo a mais tempo, e se senta na cadeira do barbeiro (após o
barbeiro se levantar, é claro...).
- Se todos os barbeiros estão ocupados, o cliente senta em uma cadeira da sala de espera, se estiver disponível. Caso contrário, o cliente permanece em pé até uma cadeira da sala de espera estiver disponível.
- Os clientes respeitam a ordem de chegada, portanto a pessoa sentada a mais tempo é sempre atendida primeiro.
- Da mesma
forma, os clientes em pé sempre lembram a sua ordem, então a pessoa em pé por
mais tempo sempre pegam a próxima cadeira disponível na sala de espera.
O trabalho prático consiste em escrever um programa em C, C++, Java ou Python para simular a atividade desta barbearia: - Simular cada barbeiro e cada cliente como um processo separado.
- Ao todo, 50 clientes devem tentar entrar na barbearia.
- Use um gerador de números aleatórios, para simular a chegada de um cliente a cada 1, 2, 3, 4, 5 ou 6 segundos. (Isto pode ser feito com uma função rand()).
- Da mesma forma, cada corte de cabelo dura entre 3 e 6 segundos.
- Cada barbeiro deve informar quando ele começa e quando ele termina cada corte de cabelo.
- Cada cliente deve informar quando ele entra na barbearia. O cliente também deve informar se ele decide ir embora imediatamente (sem lugar para esperar).
- Da mesma forma, se o cliente deve ficar de pé ou sentar-se na sala de
espera, o cliente deve informar quando começa cada atividade.
- Finalmente, o cliente deve informar quando o cabelo começa a ser cortado e quando o cliente finalmente sai da loja.
- Semáforos e memória compartilhada deve ser usado para sincronização.
- Deve ser implementada uma interface gráfica mostrando o funcionamento da barbearia (mostrar a ocupação das cadeiras).
- Ao final da execução do programa deve ser exibido um relatório contendo:
- Tempo médio de espera para cortar o cabelo (tempo de espera + corte).
- Taxa de ocupação de cada barbeiro.
|
|