Descrição do Trabalho Prático 2011.2: Babuinos atravessando o cânion

babuinos
O trabalho dessa disciplina 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.

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.

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).
O trabalho prático consiste em escrever um programa em C, C++, Java ou Python para simular a travessia dos babuinos através do cânion:
  1. Simular cada babuíno como um processo separado.
  2. 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).
  3. Use um gerador de números aleatórios, de modo que o tempo entre chegada de babuínos ao canion seja entre 1 e 8 segundos.
  4. Cada babuíno leva um segundo para chegar na corda (isto é, o espaçamento inter-babuíno mínimo é 1 segundo).
  5. Todos os babuínos atravessam na mesma velocidade. O percurso leva exatamente 4 segundos, após o babuíno chegar na corda.
  6. Use semáforos para sincronização. Você também pode usar memória compartilhada.
  7. Deve ser implementada uma interface gráfica mostrando a travessia (mostrar as filas para travessia).
  8. Ao final da execução do programa deve ser exibido um relatório contendo:
    • Quantidade de babuínos para cada sentido.
    • Tempo médio de espera para atravessar (tempo de espera + travessia).
    • Taxa de aproveitamento da corda (tempo em uso / tempo total).
Comments