Problema dos Babuínos atravessando o Cânion

O trabalho foi baseado na proposta da Professora Janet Davis da Universidade Grinnell College. Este exercício é uma versão ligeiramente modificada dos exercícios 2.35 e 2.36 do livro "Sistemas operacionais: Projeto e Implementação - 2 ed", de Tannenbaum e Woodhull.

Introdução

Um estudante graduando em antropologia e em ciência da computação embarcou em um projeto de pesquisa para ver se os babuínos africanos tem inteligência para superar impasses (deadlocks). Ele localiza um cânion profundo e prende uma corda através dele, assim os babuínos podem cruzá-lo utilizando a corda.

Descrição

A passagem ao longo da corda segue estas regras:
  • Vários babuínos podem atravessar o cânion ao mesmo tempo, desde que todos estejam indo no mesmo sentido.
  • Babuínos se movendo em sentidos contrários irão produzir um impasse (os babuínos ficarão presos no meio da corda), porque é impossível para um babuíno passar sobre o outro, enquanto estiver suspenso sobre o canyon. Estando no meio da corda os babuínos também não sabem voltar.
  • Quando um babuíno for atravessar o cânion, ele deve verificar se nenhum outro babuíno está atravessando no sentido oposto (deve esperar até a corda ficar livre).
Procure implementar uma solução que evite a fome (starvarion). Se um número grande de babuínos chegar em um lado do cânion, deve ser implementada uma política para permitir que os babuínos no sentido contrário possam atravessar. (alternar a oportunidade de travessia?)

A travessia também deve ser otimizada para evitar esperas muito longas (vários babuínos atravessando ao mesmo tempo).

Implementação

Simular cada babuíno como um processo separado.

Ao todo, 50 babuínos irão cruzar o cânion, com um gerador de números aleatórios especificando se estão se movendo para leste ou para oeste (com probabilidade igual).

Use um gerador de números aleatórios, de modo que o tempo entre chegada de babuínos ao cânion seja entre 1 e 8 segundos.

Cada babuíno leva um segundo para chegar na corda (isto é, o espaçamento inter-babuíno mínimo é 1 segundo).

Todos os babuínos atravessam na mesma velocidade. O percurso leva exatamente 4 segundos, após o babuíno chegar na corda.

Use semáforos ou monitor  para sincronização.

Durante a execução do programa  deve mostrar as filas para travessia.
 
Ao final da execução do programa deve ser exibido um relatório contendo:
  1. Quantidade de babuínos para cada sentido.
  2. Tempo médio de espera para atravessar (tempo de espera + travessia).
  3. Taxa de aproveitamento da corda (tempo em uso / tempo total).

Avaliação

A avaliação consiste em uma apresentação oral em sala com a execução do programa e um trabalho escrito. Na avaliação será considerado 50% para a apresentação oral em sala (incluindo a execução correta do programa) e 50% para o relatório escrito.

Apresentação Oral

Os alunos deverão fazer uma apresentação oral do trabalho realizado para os demais alunos. Na apresentação deverão mostrar a análise do problema, as formas de resolução, as decisões de implementação e a apresentação da execução do programa. 

Considera-se a execução correta se o programa cumprir o determinado sem a ocorrência de deadlocks ou starvation.

O calendário de apresentação será definido futuramente.

A apresentação oral é obrigatória. Caso o aluno não consiga apresentar na data marcada, haverá outra oportunidade, antes da NEF, para apresentar o trabalho.

Trabalho Escrito

O trabalho escrito é obrigatório.

Os alunos deverão entregar um relatório escrito com os seguintes tópicos:
  1. Formulação do problema
  2. Descrição dos algoritmos
  3. Descrição da Implementação (diagrama de classes)
  4. Resultados de, pelo menos, três execuções.
Para ajudar na preparação do relatório apresentamos um modelo de exemplo: Modelo de Relatório.

Comments