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: boarders = 0 unboarders = 0 mutex1 = Semaphore(1) mutex2 = Semaphore(1) boardQueue = Semaphore(0) unboardQueue = Semaphore(0) allAboard = Semaphore(0) allAshore = Semaphore(0) 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: load() boardQueue.signal(C) allAboard.wait() run() unload() unboardQueue.signal(C) allAshore.wait() 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() board() mutex1.wait() boarders += 1 if boarders == C: allAboard.signal() boarders = 0 mutex1.signal() unboardQueue.wait() unboard() mutex2.wait() unboarders += 1 if unboarders == C: allAshore.signal() unboarders = 0 mutex2.signal() 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.

/************************************************************* * Per compilare con gcc su Linux: * * gcc file.c -lpthread * *************************************************************/

#include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <semaphore.h>

#define NUM_PASS 200

typedef struct { int boarders, unboarders; Semaphore *mutex1, *mutex2; Semaphore *boardQueue, *unboardQueue; Semaphore *allAboard, *allAshore; } Shared;

// Some utility functions //

void error (char *msg) { perror (msg); exit (1); }

void * check_malloc (int size) { void *p = malloc (size); if (p == NULL) error ("malloc failed\n"); return p; }

Semaphore * new_semaphore (int n) { Semaphore *sem = check_malloc (sizeof (Semaphore)); int ret = sem_init (sem, 0, n); if (ret == -1) error ("sem_init failed\n"); return sem; }

void join_thread (pthread_t thread) { int ret = pthread_join (thread, NULL); if (ret == -1) error ("pthread_join failed\n"); }

// Roller coaster problem //

void * rollercoaster (void *arg) { int id = id_counter++; int i, turn = 1; Shared *shared = (Shared *) arg;

for (turn = 1; turn <= TURN; turn++)

printf ("\nR: This is turn number %d\n", turn); printf ("R: Loading passengers...\n"); for (i = 0; i < SEATS; i++) sem_post (shared->boardQueue); sem_wait (shared->allAboard);

printf ("R: Roller coaster start\n"); sleep (1); printf ("R: Roller coaster stop\n");

printf ("R: Unloading passengers...\n"); for (i = 0; i < SEATS; i++) sem_post (shared->unboardQueue); sem_wait (shared->allAshore);

printf ("\nR: It's 6PM, service is close!\n"); pthread_exit (NULL); }

void * passenger (void *arg) { int id = id_counter++; Shared *shared = (Shared *) arg;

sem_wait (shared->boardQueue); printf ("P: Passenger %d is boarding\n", id);

sem_wait (shared->mutex1); shared->boarders++; if (shared->boarders == SEATS)

sem_post (shared->allAboard); shared->boarders = 0;

sem_post (shared->mutex1);

sem_wait (shared->unboardQueue); printf ("P: Passenger %d is unboarding\n", id);

sem_wait (shared->mutex2); shared->unboarders++; if (shared->unboarders == SEATS)

sem_post (shared->allAshore); shared->unboarders = 0;

sem_post (shared->mutex2);

pthread_exit (NULL); }

int main () { int i; pthread_t passengers[NUM_PASS]; pthread_t roller_coaster;

id_counter = 0; Shared *shared = new_shared ();

roller_coaster = new_thread (rollercoaster, shared);

for (i = 0; i < NUM_PASS; i++) new_thread (passenger, shared);

join_thread (roller_coaster);

return 0; }

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): agent P = 'board.'unboard.P; agent BOARDQUEUE = board.board.'allAboard.0; agent UNBOARDQUEUE = unboard.unboard.'allAshore.0; agent RC = 'load.allAboard.RC1 | load.BOARDQUEUE; agent RC1 = run.RC2; agent RC2 = 'unload.allAshore.RC | unload.UNBOARDQUEUE; set L = {load, unload, board, unboard,allAboard,allAshore}; agent SYS = (RC|P|P|P|P)\L;

Voci correlate Problema del produttore/consumatore Problema dei filosofi a cena

Collegamenti esterni

Categoria:Controllo della concorrenza Categoria:Algoritmi