Problema delle montagne russe
# Problema delle montagne russe

Il problema delle montagne russe (meglio conosciuto con il nome inglese Roller coaster problem) è un problema di sincronizzazione tra processi.

## Descrizione del problema

Supponiamo che ci siano n passeggeri (threads) e un carrello delle montagne russe (altro thread). I passeggeri arrivano alla giostra e si mettono in attesa che arrivi il carrello che può trasportare C passeggeri con C < n. Il carrello parte solo quando è pieno.

Dettagli restrittivi:

* i passeggeri invocano board e unboard
* il carrello invoca load, run e unload
* i passeggeri non possono montare finché il carrello non ha invocato load
* il carrello non può partire finché C passeggeri non sono montati a bordo
* i passeggeri non possono smontare finché il carrello non ha invocato unload

È ovvio che questo problema può essere causa di deadlock.

## Soluzione con i semafori

Per risolvere tale problema facciamo uso dei semafori. Utilizzeremo le seguenti variabili condivise tra tutti i processi in gioco così inizializzate:

Dove mutex protegge i passeggeri che contano il numero di passeggeri che hanno invocato board. I passeggeri attendono nella boardQueue prima di montare nel carrello e nella unboardQueue prima di smontare. allAboard indica che il carrello è pieno e allAshore che tutti i passeggeri sono smontati.

In questo pseudo-codice wait equivale alla classica P e signal alla V di Dijkstra. Lo pseudo-codice per il carrello può essere strutturato nel seguente modo:

Quando il carrello arriva, segnala C passeggeri, poi aspetta che l'ultimo abbia segnalato allAboard. Inizia il suo giro e quando arriva permette ai C passeggeri a boardo di smontare aspettando il segnale per allAshore.

Lo pseudo-codice per i passeggeri invece può essere strutturato nel seguente modo: boardQueue.wait

I passeggeri aspettano il carrello prima di montare. L'ultimo passeggero che monta segnala il carrello che può partire e resetta il contatore boarders.

Questa soluzione non va bene nel caso ci siano in gioco più carrelli.

## Implementazione in C

Qui di seguito il codice in C che risolve il problema col metodo dei semafori. Si sono utilizzati i pthread ed i semafori POSIX.

## Modellazione in CCS

Il Calculus of Communicating Systems (CCS) è un linguaggio teorico che permette di studiare i sistemi reattivi. Di seguito è riportato la modellazione in CCS del nostro problema (sintassi del Concurrency WorkBench) per un carrello con capienza 2 (C = 2):

