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:

  • Cassiano C. Rocha
  • Edilson Júnior
  • José M. Silveira Neto

Observação: as implementações que estão aqui, em Python, não são as implementações corretas. As implementações finais estão aqui.

Links Úteis: