Problema da Montanha Russa 2012.2

Introdução

O Problema da Montanha Russa (Roller Coaster) é um exemplo lúdico de um problema muito comum em controle de processos. Para resolvê-lo deve-se usar princípios básico de programação concorrente.

O problema da Montanha Russa usa apenas três processos: a montanha russa, os passageiros e o(s) carro(s).

Proposta do Problema

Caso carro único

Considere uma montanha russa com apenas 1 (um) carro com C lugares. Considere n passageiros, que chegam repetidamente e  esperam em uma fila na plataforma para entrar no carro, que podem acomodar C passageiros, C <n. O tempo de chegada dos n passageiros à montanha russa é Tp, que é aleatório. No entanto, o carro só pode começar o passeio pelo trilho quando estiver cheio. Considere um tempo Te como o tempo para os passageiros desembarcarem e embarcarem no carro. O carro então inicia o passeio que leva Tm minutos e quando chegar de volta, os passageiros saem e entra mais C passageiros.

Desenvolver um algoritmo concorrente e códigos para o carro e os passageiros. Desenvolver uma solução para sincronizá-los.

Considere n = 52, C = 4, Tm = 2 min, Te = 20 segTp = 10 a 30 seg.

Caso 2 carros

Considere agora que existem m carros na montanha russa, sendo m> 1. Uma vez que existe apenas um trilho, os carros não podem passar sobre os outros, isto é, eles devem percorrer o trilho na ordem em que começou. Por questão de segurança, apenas um carro pode circular na montanha russa em um determinado momento, um outro carro somente pode sair quando o carro que está circulando chegar. Mais uma vez, um carro só pode sair quando estiver cheio, mas nesse caso os passageiro podem sentar no carro e partir logo  que o outro carro chegar.

Considere n = 52, m = 2C = 4,  Te = 20 segTm = 2 minTp = 10 a 30 seg.

Caso 3 carros

Considere n = 100m = 3C = 4,  Te = 20 segTm = 2 minTp = 10 a 30 seg.

Implementação

O trabalho prático consiste em escrever um programa em CC++Java ou Python para simular os carros, passageiros e a montanha russa

Ao final da execução  deve ser calculado: tempo mínimo, máximo e médio de espera dos passageiros na fila. Tempo de utilização do(s) carros (tempo movimentando/tempo total)

Avaliação

A avaliação consiste em uma apresentação oral e um trabalho 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.

Trabalho Escrito

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
Comments