Descrição do Trabalho Prático 2011.1: Barbeiro Dorminhoco Extendido

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.

Diagrama da Barbearia

  • 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:

  1. Simular cada barbeiro e cada cliente como um processo separado.
  2. Ao todo, 50 clientes devem tentar entrar na barbearia.
  3. 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()).
  4. Da mesma forma, cada corte de cabelo dura entre 3 e 6 segundos.
  5. Cada barbeiro deve informar quando ele começa e quando ele termina cada corte de cabelo.
  6. 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).
  7. 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.
  8. Finalmente, o cliente deve informar quando o cabelo começa a ser cortado e quando o cliente finalmente sai da loja.
  9. Semáforos e memória compartilhada deve ser usado para sincronização.
  10. Deve ser implementada uma interface gráfica mostrando o funcionamento da barbearia (mostrar a ocupação das cadeiras).
  11. 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.
Comments