Progetto Taxicab

Info

Documento di Presentazione del Progetto svolto per il corso di Sistemi Operativi A 2020/2021 ad UniTo - _Link Repository Github_

Opzioni di compilazione

gcc -D_GNU_SOURCE -std=c89 -pedantic -DDEBUG=0

• utilizzo di make
• flag di debug DDEBUG=0
  • attivabile con 1

Compilazione con

• make taxicab

Struttura della Simulazione

La simulazione e’ strutturata in diversi processi.

Master

Si occupa della raccolta e stampa dei dati durante l’esecuzione del programma.

• Crea la coda di messaggi dedicata ai processi che lo seguiranno
• Crea la memoria condivisa puntata da mapptr
  • Una matrice dimensionata SO_WIDTH*SO_HEIGHT di Cell
• Esegue Generator
• Attende il messaggio da parte di Generator
  • Alloca con una malloc() lo spazio per l’array simData.topCells
• Stampa ogni secondo lo stato della Mappa
  • in particolare l’attributo traffic dalle Cells
• Al termine della simulazione stampa i dati finali richiesti dal progetto.
  • Numero di viaggi effettuati:
    • Con successo
    • Inevasi
    • Abortiti
  • I processi taxi che hanno:
    • Attraversato piu’ strada
    • Viaggiato piu’ a lungo nel servire una richiesta
    • Servito il maggior numero di richieste/clienti
  • La mappa dove saranno evidenziati:
    • Punti sulla mappa di origine dei clienti (SO_SOURCE)
    • Punti inaccessibili ai taxi sulla mappa (SO_HOLES)
    • Le celle maggiormente attraversate dai taxi che non sono appartenti a SO_SOURCE (SO_TOP_CELLS)
• Una volta terminata la stampa disalloca le sue risorse e conclude.

Funzioni

void cellsData(Cell (*map)[][SO_HEIGHT], Point mostUsedCell_ptr[])

• Si occupa della raccolta dei dati delle celle che sono state maggiormente attraversate dai taxi durante la simulazione.

void printMap(Cell (*map)[][SO_HEIGHT])

• Si occupa della stampa della mappa nel seguente formato leggibile:
  • Celle FREE sono stampate come [ ]
  • Celle SOURCE sono stampate come [S]
  • Celle HOLE sono stampate come [#]

void handler(int sig)

• Gestisce i segnali
• Imposta la flag di esecuzione a 0 quando necessario

void logmsg(char *message, enum Level l)

• Si occupa stampa dei messaggi

void updateData(long pid, taxiData *data)

• Si occupa di aggiornare la propria struttura dati (simData) alla ricezione di messaggi da parte dei processi

void printReport(Cell (*map)[][SO_HEIGHT], Point mostUsedCell_ptr[])

• Si occupa della stampa dei dati raccolti durante la simulazione, mostrando le varie statistiche richieste dal progetto (Viaggi, Mappa e Taxi)

Generator

Si occupa della configurazione ed esecuzione complessiva della simulazione.

• Crea
  • Coda di messaggi dedicata a comunicazione Source-Taxi
  • Array condiviso contenente le coordinate delle Sources
  • Semafori
    • mutex
    • writers (SO_WIDTH * SO_HEIGHT)
    • sem
      • utilizzato per sincronizzare i taxi alla partenza
• Genera la mappa popolando la memoria condivisa (SO_WIDTH * SO_HEIGHT * sizeof(Cell)) puntata da mapptr
• Esegue la prima stampa della mappa, in forma di matrice, il quale sarà composto da:
  • Cell costituiti da variabili
    • capacity
    • traffic
    • visits
    • state
      • FREE, dove i taxi possono muoversi liberamente all’interno della mappa
      • SOURCE, dove le richieste dei clienti sono originate (SO_SOURCES)
      • HOLE, inaccessibili ai taxi (SO_HOLE).
    • Point, la posizione all’interno della mappa, costituito dalle variabili x e y
• Esegue SO_SOURCES processi source
  • li inserisce in un array di Point per semplificare ai Taxi lo spostamesto alla Source piu’ vicina
• Esegue SO_TAXI processi taxi, i quali si occuperanno di soddisfare le richieste dei clienti.
• Invia a Master su Message Queue il valore SO_TOP_CELLS, permettendogli a questo punto di continuare l’esecuzione
• Avvia il timer di SO_DURATION secondi
• Rilancia il processo taxi se riceve il segnale SIGUSR1
• Una volta terminati i figli disalloca le sue risorse e invia il segnale SIGUSR2 al Master, notificando la terminazione della simulazione

Funzioni

void unblock(int sem)

• Diminuisce il valore del semaforo di sincronizzazione, portandolo a 0.

void parseConf(Config *conf)

• Analizza il file taxicab.conf nella source directory ed popola il Config struct con i paramentri in taxicab.conf.

int checkNoAdiacentHoles(Cell (*matrix)[][SO_HEIGHT], int x, int y)

• Controlla le celle adiacenti nella matrice [x] [y] contrassegnati come HOLE, restituendo 0 se ha avuto successo.

void generateMap(Cell (*matrix)[][SO_HEIGHT], Config *conf)

• Popola la matrice[x][y] segnando lo stato delle celle se sono FREE, SOURCE oppure HOLE.

void printMap(Cell (*map)[][SO_HEIGHT])

• Si occupa della stampa della mappa nel seguente formato leggibile:
  • Celle FREE sono stampate come [ ]
  • Celle SOURCE sono stampate come [S]
  • Celle HOLE sono stampate come [#]

void logmsg(char *message, enum Level l)

• Si occupa della trasmissione dei messaggi fra tutte le funzioni all’interno del processo durante la simulazione.

void execTaxi()

• Invoca taxi per generare i taxi che verranno inseriti nella mappa.

void execSource(int arg)

• Invoca source per generare le richieste all’interno della mappa.

void handler(int sig)

• Si occupa della gestione dei segnali.

Source

Si occupa della generazione delle richieste all’interno nella mappa.

• Una volta inizializzata aspetta che il valore di sem sia 0
• Avvia il ciclo d’esecuzione, nel quale scegliera’ casualmente le celle che diventeranno le destinazioni dei clienti durante la simulazione e inviera’ la richiesta sulla Coda di Messaggi destinata ai Taxi.
• In caso l’utente invii SIGTSTP con la combinazione di tasti CTRL+Z generera’ una richiesta.
• Una volta ricevuto SIGALRM o SIGINT rilascia le risorse e chiude.

Funzioni

void logmsg(char *message, enum Level l)

• Si occupa delle stampe su stdout.

Void handler(int sig)

• Si occupa della gestione dei segnali.

int semSyncSource(int sem)

• Si occupa di sincronizzare i semafori alla partenza della simulazione.

void userRequest()

• Si occupa delle richieste che il processo riceve dal terminale con la combinazione di tasti CTRL+Z (SIGTSTP).

Taxi

Si occupa dei taxi e di configurare il loro comportamento durante l’esecuzione della simulazione.

• Una volta inizializzato aspetta che il valore di sem sia 0
• si sposta alla sorgente piu’ vicina, ovvero al punto d’origine del cliente
• una volta alla sorgente raccoglie le richieste di quella specifica Source sulla coda di messaggi
• si sposta alla Cella indicata dalla richiesta
• rimane fermo nella cella corrente per un tempo compreso tra SO_TIMENSEC_MIN e SO_TIMENSEC_MAX
• Il processo continuera’ a ripetersi fino al termine del tempo a disposizione alla simulazione, o nel caso il Taxi raggiunga il tempo di SO_TIMEOUT tra uno spostamento e l’altro (nel caso non riesca a prendere in carico una richiesta in tempo)
• Una volta ricevuto SIGALRM o SIGINT rilascia le risorse e chiude.

Funzioni

void moveTo(Point dest)

• Si occupa dello spostamento dei taxi fra le varie celle della mappa durante la compilazione.

int canTransist(Point p)

• Verifica se sia possibile per il taxi di spostarsi alla cella seguente.

void incTrafficAt(Point p)

• Aumenta il traffico all’interno della cella.

void decTrafficAt(Point p)

• Diminuisce il traffico all’interno della cella.

void logmsg(char *message, enum Level l)

• Si occupa della trasmissione dei messaggi fra tutte le funzioni all’interno del processo durante la simulazione.

Point getNearSource(int *source_id)

• Si occupa della selezione del punto d’origine dei clienti più vicino.

void checkTimeout()

• Verifica se il tempo a disposizione sia scaduto.

void printRep();

• Stampa (se DEBUG=1) lo stato dal Taxi

void handler(int sig)

• Si occupa della trasmissione dei messaggi fra tutte le funzioni all’interno del processo durante la simulazione.

general.h

Imposta le strutture principali che tutti altri processi utilizzeranno durante la simulazione e effettua gli import delle librerie comuni.

• Cell, le celle che formano la mappa durante la compilazione.
• Config, i parametri stabiliti dalla simulazione.
• Point, i punti cardinali che rappresentano le posizioni sulla mappa.
• Message, i messaggi che i processi Source e Taxi utilizzano per comunicare, contiene Point.
• MasterMessage, i messaggi riservati per il master, contiene int.

functions.c

Funzioni condivise dai moduli.

int isFree(Cell (*map)[][SO_HEIGHT], Point p)

• Verifica se il Point all’interno della cella sia libero.

void semWait(Point p, int sem)

• Wait sul sem[SO_WIDTH*p.y + p.x] semaforo del set.

void semSignal(Point p, int sem)

• Signal sul sem[SO_WIDTH*p.y + p.x] semaforo del set.

void semSync(int sem)

• Wait for Zero sul semaforo.

void lock(int sem)

• Incrementa il valore del semaforo mutex, portandolo a 1.

void unlock(int sem)

• Diminuisce il valore del semaforo mutex, portandolo a -1.

Configurazione

Il programma utilizza dieci parametri letti a tempo di esecuzione, da file taxicab.con, e due a tempo di compilazione, da general.h

In taxicab.conf

• SO_TAXI
  • Numero di taxi presenti.
• SO_SOURCES
  • Numero di punti sulla mappa di origine dei clienti.
• SO_HOLES
  • Numero di celle della mappa inaccessibili.
• SO_TOP_CELL
  • Numero di celle maggiormente attraversate dai taxi.
• SO_CAP_MIN
  • Capacita’ minima di ogni cella.
• SO_CAP_MAX
  • Capacita’ massima di ogni cella.
• SO_TIMENSEC_MIN
  • Tempo minimo necessario per l’attraversamento di ogni cella (in nanosecondi).
• SO_TIMENSEC_MAX
  • Tempo massimo necessario per l’attraversamento di ogni cella (in nanosecondi).
• SO_TIMEOUT
  • Tempo di inattivita’ massima di ogni taxi, dopo il quale il taxi chiude inviando SIGUSR1 a generator.
• SO_DURATION
  • Durata della simulazione. Dopo questo tempo i processi ricevono SIGALRM.

In general.h

• SO_WIDTH
  • Larghezza della mappa.
• SO_HEIGHT
  • Altezza della mappa.

Sincronizzazione

Per assicurarsi che il programma esegua correttamente sono stati necessari diversi accorgimenti riguardo la sincronizzazione di tutti i moduli.

Partenza

Una volta inizializzate tutte le strutture dati ed eseguiti le Source e i Taxi la sincronizzazione e’ implementata:

• con un semaforo sem inizializzato a 1
  • i Taxi e le Source aspettano lo 0
  • Generator lo azzera subito prima di far partire il timer SO_TIMEOUT
• con il primo messaggio a Master da parte di Generator (contenente SO_TOP_CELLS) Master rientra in esecuzione

Concorrenza di Source e Taxi

I processi Source e Taxi accedono concorrentemente alla memoria condivisa puntata da mapptr. L’accesso viene ordinato utilizzando uno schema di sincronizzazione Lettori-Scrittori a favore dei lettori:

• writer e’ un set di SO_WIDTH*SO_HEIGHT semafori
• mutex e’ un semaforo utilizzato per la mutua esclusione nella modifica di readers
• readers e’ un intero inizializzato a 0 in memoria condivisa
• Writer

wait(p, writer);
// Perform write operation
signal(p, writer);

• Reader

wait(mutex);
readers++;
if(readers == 1) {
    wait(p, writer);
}
signal(mutex);
// Perform read operation
wait(mutex);
readcount--;
if(readcount == 0) {
    signal(p, writer);
}
signal(mutex);

Conclusione

Nella fase di chiusura i processi ricevono SIGALRM da generator, che si mette in attesa dei figli. Una volta conclusi i figli e disallocate le risorse condivise Generator invia SIGUSR2 a Master e conclude. Master, ricevuto il segnale, imposta la propria flag di esecuzione a 0 e attende eventuali figli. Procede allora con la raccolta dei messaggi a lui inviati dai processi alla loro uscita, con questi messaggi popolera’ le sue aree dati per la stampa finale delle statistiche.

IPC

Le IPC utilizzate in questo progetto sono:

Code di Messaggi

• Tra Master e Generator/Source
  • creato da Master
• Tra Source e Taxi
  • creato da Generator

Semafori

Creati da Generator Per la sincronizzazione iniziale

• sem

Per la sincronizzazione durante l’esecuzione

• mutex
• writer

Memoria Condivisa

• La mappa di SO_WIDTH*SO_HEIGHT Cells
  • creato da Master
• Un array di SO_SOURCES Point
  • creato da Generator
• Un intero readers
  • creato da Generator