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:

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

• (EN) The Little Book of Semaphores, su greenteapress.com. URL consultato il 7 marzo 2008 (archiviato dall'url originale il 14 giugno 2016).
• (EN) The Edinburgh Concurrency Workbench, su homepages.inf.ed.ac.uk.