Montanha Russa

Problema:

Questão retirada do livro Principle of Concurrent and Distributed Programming de M.Ben-Ari, segunda edição, pág, 332. Questão 10.

The roller-coaster problem.

There are n people at an amusement park who can decide they want to ride the roller-coaster, or they can be engaged in other activities and may never try to ride the roller-coaster. A single-car roller-coaster ride begins its run only when exactly r passengers are ready. Develop an algorithm to synchronize the actions of the roller-coaster and the passengers.

Generalize the program to multiple roller-coaster cars; however, the cars can not pass each other.

Solução 1:

Global{ Semáforo desce ← (R,ø) Semáforo sobe ← (0,ø) } Processo passageiro{ loop{ wait(desce) print id signal(sobe) } } Processo Carro{ loop{ for R: wait(sobe) print ‘carro’ for R:signal(desce) } }

Código-fonte em Python: montanha_russa_v1.py

Em q2, q3 um carro pega as R pessoas que sobem. Depois o carro sai e então o carro desce as R pessoas.

Cada pessoa espera alguem descer (ou ter descido) entra no carro. O importante aqui é que o carro que desça as pessoas e não as pessoas que desçam por conta própria.

Um exemplo de saída para 3 pessoas e um carro com 3 vagas, R=3:

1 2 3 carro 3 2 1 carro 2 1 3 carro 1 2 3 carro 3 2 1 carro …

Agora um exemplo com 3 pessoas e um carro com 2 vagas, R=2:

1 3 carro 3 1 carro 1 3 carro 1 3 carro …

Nesse exemplo todos queriam entrar no carro mas sempre só a pessoa 1 a pessoa 3 entravam. A pessoa 2 nunca conseguiu entrar. É um caso de inanição (starvation).

Solução 2:

O problema da solução anterior é que alguem que acabou de andar na montanha russa pode andar novamente, precisamos usar algum tipo de estutura FIFO (primeiro que entra é o primeiro que sai) para organizarmos quem pode entrar no carrinho.

A estrutura de monitores apresentada no capítulo 7 resolve bem esse problema.

monitor MR{ circunstância minha_vez operacação entra{ waitC(minha_vez) print id } operação anda{ for R: signalC(minha_vez) print ‘carro’ } } processo passageiro{ loop{ se quiser(): MR.entra() } } processo carro{ loop{ MR.anda() } }

Código-fonte em Python: montanha_russa_v2.py

Solução 3:

Foi também pedido na questão para generalizar o problema para vários carros, com a restrição que um carro não passe na frente do outro. Isso pode ser resolvido com mais uma fila.

monitor MR{ circunstância passageiro_vez circunstância carro_vez operacação entra{ waitC(passageiro_vez) print id } operação anda{ if empty(carro_vez){ carro_vez.append(id) for R: signal(passageiro_vez) print ‘carro’ id carro_vez.pop() }else{ waitC(carro_vez) } for R: signalC(passageiro_vez) print ‘carro’ id signalC(carro_vez) } }
Equipe: