IntroduçãoEsquiar é uma atividade muito praticada em países de clima frio durante o inverno. Um dos locais mais apreciados é a estação de esqui de Gornergrat nos Alpes, localizada na cidade de Zermatt na Suiça. Gornergrat é famosa pelo Matterhorn, pico que ilustra as embalagens do famoso chocolate Toblerone..... Abaixo uma foto do professor com o Matterhorn ao fundo.  Em uma estação de esqui existem elevadores que levam as pessoas para o alto da pista de onde elas vão iniciar o sua descida com ski até a base da pista. Em Gomergrat existe um elevados de esqui aberto, também conhecido como chairlift,com capacidade para quatro pessoas mostrado na figura abaixo. Lá existe elevadores maiores, para seis pessoas, mas para nosso problema, quatro está bom.  Um dos momentos mais críticos é entrada dos usuários no elevado aberto. O elevador funciona continuamente e as pessoas precisam entrar e sair com ele em movimento. As pessoas completamente equipadas ficam de costas esperando a cadeira se aproximar e se sentam assim que passa por elas, conforme figura abaixo.  Como podemos notar, o equilíbrio do elevador é essencial para uma viagem segura (já pensou se todo mundo senta de um lado só) então as pessoas tem que se organizar para sentar no elevador de forma segura e eficiente. Lembramos que na Suíça as pessoas são disciplinadas e não há necessidade de um fiscal para organizar as filas. Ainda bem que não existe estações de esqui no Brasil, pois teria acidente toda hora..... O problema do trabalho prático proposto consiste em implementar o controle de entrada em um elevador de esqui. Descrição do ProblemaA nossa pista de ski tem uma cadeira quadrupla, com capacidade de quatro pessoas por vez. Para isso são organizadas quatro filas de carregamento distintas:LS (Left Single): Fila de uma pessoa no lado esquerdo LT (Left Triple): Fila de uma tripla no lado esquerdo RT (Right Triple): Fila de uma tripla no lado direito RS (Right Single): Fila de uma pessoa no lado direito Sabemos que, na realidade, as pessoas não se alinham apenas em triplas e individuais, elas se alinham às vezes em duplas, às vezes em triplas, e às vezes em quadrupla. Isso, no entanto, aumenta a complexidade do nosso problema, então vamos considerar apenas triplas e individuais. Abaixo um diagrama do esquema proposto.  Nas filas triplas, 3 pessoas dessa fila se senta no elevador, que pode ser completado com pessoas das filas individuais. A seguir a explicação do algoritmo. Procedimento para o esquiador selecionar a fila de carregamentoUm esquiador (isto é, um processo concorrente), ao chegar ao elevador de esqui, olha para o comprimento de cada fila (isto é, conta o número de pessoas) e escolhe a fila a entrar conforme o seguinte algoritmo:(a) Escolhe a fila LS se o tamanho da fila LS for:
(b) Escolhe a fila RS se o tamanho da fila RS for:
(c) Escolhe a fila LT se o comprimento da fila LT for menor ou igual ao tamanho da fila RT, senão, (d) Escolhe a fila RT Procedimento para carregar o elevador:Considere que existe um processo Elevador que retira os esquiadores das filas conforme o procedimento abaixo. Como a cadeira tem quatro lugares, a quarta posição será ocupada por um esquiador das filas LS ou RS alternadamente. Novamente, se uma fila estiver vazia, a outra fila é servida continuamente. Se as filas LT e RT estiverem vazias é permitido atender as filas LS e RS até preencher todos as quatro posições. Caso as filas LS e RS estejam vazias é permitido que a cadeira viaje com apenas três pessoas sentadas. Regras GeraisEsse problema é basicamente um produtos-consumidor com quatro filas. para simplificar nosso problema vamos considerar uma fila bem grande para não ocorrer transbordamento (consideramos filas com tamanho 20) Cada esquiador deverá chegar no elevador com intervalo de 1 segundo. Fazer um daemon que cria um esquiador por segundo. Executar o programa com 120 (cento e vinte) esquiadores. O tempo total de execução do programa deve ser de aproximadamente 2 minutos. O elevador deverá funcionar a cada 4 segundos, isto é, a cada 4 seg o processo Elevador vai retirar até 4 esquiadores das filas. Ao final da execução deve exibir os seguintes resultados:
ImplementaçãoO trabalho prático consiste em escrever um programa em C, C++, Java ou Python para simular o jogo. Não precisa fazer interface gráfica.Não poderá haver deadlock nem starvation. AvaliaçãoA avaliação consiste em uma apresentação oral em sala com a execução do programa e um trabalho escrito.Apresentação OralOs 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 EscritoOs alunos deverão entregar um relatório escrito com os seguintes tópicos:
|
|
|