Versione finale relazione

[toni-reis.git] / doc / concorrenza.tex

\chapter{Concorrenza}

\begin{figure}
\centering
\includegraphics[width=14cm]{Attivita_Concorrenza_Circuito}
\caption{Protocollo di percorrenza del circuito.}
\label{fig:attivita}
\end{figure}
\section{Percorrenza del circuito: Sector e Lane}
%---------forse da mettere nella descrizione di track
\textit{Track} è un entità passiva, in particolare una \textit{RCI}. 
In \textit{Track} sono presenti le entità protette \textit{Sector} e \textit{Lane}, che rappresentano gli elementi della  pista.
La pista è divisa in settori, intesi come rettilinei, curve o box. Ogni settore può essere un intertempo, ovvero essere dotato degli strumenti per tenere traccia dei tempi di percorrenza.
La pista non è altro che un insieme ordinato (nello specifico un \textit{array}) di settori, a cui si aggiunge il settore dei box.
%----------------

\subsection{Sector}
\textit{Sector} è implementato come una risorsa protetta: viene ipotizzato quindi che le auto possano entrare (e uscire) una alla volta in un determinato settore.
Questa assunzione, anche se non rispecchia esattamente la realtà, consente una gestione più semplice e corretta della concorrenza, come si vedrà in seguito.
Ogni \textit{Sector} si compone di un certo numero di corsie parallele che possono essere percorse contemporaneamente da più autovetture, chiamate \textit{Lane}.
Segue lo pseudocodice della procedura di entrata in un settore.

\begin{lstlisting}[frame=trBL,columns=fixed,postbreak=\space,breaklines,caption={Procedura Enter di Sector.}]
entry Enter is
  begin
       
    n_lane := corsia da percorrere. Trovo quella meno trafficata.
    aggiorno variabili di Sector notificando l'ingresso nel settore n_lane

    requeue Corsie(Sector_Id)(n_lane).Demand;
         
end Enter;
\end{lstlisting}

Il compito principale della risorsa \textit{Sector} è quello di smistare le auto in ingresso nelle varie corsie secondo una logica predefinita.

\subsection{Lane}
\textit{Lane} è implementato anch'esso come una risorsa protetta. Esso calcola, a partire dal tempo di invocazione e dalle caratteristiche dell'auto in questione, il tempo di percorrenza del tratto. Vengono eseguiti controlli sul valore calcolato, in modo da evitare i sorpassi nello stesso \textit{Lane}.
Segue il codice semplificato della procedura di accesso alla corsia.

\begin{lstlisting}[frame=trBL,columns=fixed,postbreak=\space,breaklines,caption={Procedura principale di Lane.}]
entry Demand (time : Time) is
  -- ExitTime : variabile di Lane che salva il tempo d'uscita piu' alto tra le auto che precedono
  -- ExitSpeed : variabile di Lane che salva la velocita' d'uscita dell'auto con tempo d'uscita piu' alto.
  begin
    t, speed := CalculateDriveTime;
    -- la chiamata ritorna il tempo di percorrenza e la velocita' calcolati
      
    time := time + t;

    -- se non ci sono auto che precedono, salvo i valori nelle variabili di Lane
    if (time > exit_time) then
      exit_time := time;
      exit_speed := speed;
    elsif (time < exit_time) then
      -- se sono presenti altre auto nel Lane, vengono modificati tempo di uscita e velocita'
      time := exit_time;
      if (speed > exit_speed) then speed:=exit_speed;
      end if;
    end if;
end Demand;
\end{lstlisting}


Il trasferimento della chiamata da \textit{Sector} a \textit{Lane} verrà implementato con \textit{requeue}. Questo permette di liberare la risorsa \textit{Sector} durante il calcolo dei tempi di percorrenza, non pregiudicando la correttezza poichè il protocollo di accesso al circuito prevede di dover invocare \textit{Sector} e non \textit{Lane}. Il protocollo non presenta quindi situazioni di race condition non gestite.


Queste scelte architetturali consentono a più auto di percorrere contemporaneamente lo stesso settore, consentendo quindi anche il sorpasso. Inoltre più auto possono percorrere contemporaneamente lo stesso \textit{Lane}, ma in questo caso non è consentito alle auto di superarsi.

\subsection{Release\_and\_Enter}
Nella figura \ref{fig:attivita} è rappresentato il protocollo di percorrenza del circuito. Come si vede, la chiamata a \textit{Release\_and\_Enter}, che fa uscire un auto da un settore e la fa automaticamente entrare nel settore successivo, ritorna un valore \textit{Time}, che indica il tempo al quale l'auto avrà terminato di percorrere quel tratto. L'auto eseguirà quindi una chiamata \texttt{delay until Time;}, ma prima dovrà comunicare questo tempo di uscita al settore interessato attraverso la procedura \textit{BookExit} con parametro \textit{Time}. Scaduto questo tempo, l'auto è pronta per percorrere il settore successivo, seguendo la stessa procedura.


La scelta di rendere atomiche l'uscita da un settore e l'entrata nel successivo è dovuta al fatto che, tenendo le procedure separate e ritornando il controllo al chiamante di \textit{PutOnPitLane}, non sarebbe stato possibile sempre prevedere l'ordine di esecuzione, cioè l'ordine di ingresso nel settore successivo. Inoltre piccole differenze nei tempi di risveglio dalla \textit{delay until} potrebbero portare a sorpassi indesiderati.

La scelta di tenere la procedura \textit{BookExit} esterna, invece che invocarla automaticamente dalla \textit{Release\_and\_Enter} è stata fatta per la maggior semplicità nel protocollo di ritiro delle auto.

Segue il codice semplificato del protocollo di riaccodamento.

\begin{lstlisting}[frame=trBL,columns=fixed,postbreak=\space,breaklines,caption={Procedura principale di Sector.}]


entry Release_and_Enter 
  --ExitArray e' una struttura dati che per ogni auto ha un flag booleano Arrived che ne segna l'arrivo
  begin
  if (ExitArray(1).CarId = my_properties.CarId) then
    -- l'auto e' la prima nella lista di uscita
    rimuovi l'auto da ExitArray
    if (sono presenti auto nella coda interna) then 
      apri la guardia 
    else
      chiudi la guardia
    end if;
  
  else
    -- l'auto NON e' la prima nella lista di uscita: la chiamata deve essere trasferita nella coda interna ExitLane      
    ExitArray(posizione auto) := True;
    chiudi la guardia di ExitLane
    -- trasferisco la chiamata in ExitLane
    requeue ExitLane;

  end if;
  next_sect := calcolo il settore successivo
  requeue Sectors(next_sect).Enter;
end Release_and_Enter;
\end{lstlisting}

\subsubsection{Uscita dal settore}
La procedura \textit{Release\_and\_Enter} utilizza il modello a guscio d'uovo per gestire l'ordine di uscita dal settore. Se infatti un'auto invoca \textit{Release\_and\_Enter} quando ancora non è il suo turno di uscita (l'ordine è conosciuto e mantenuto coerente in una struttura dati interna a \textit{Sector}), la chiamata viene trasferita in una coda interna, governata da una guardia di Dijkstra, fino a quando la procedura non verrà invocata da un'altra auto. Se è quest'ultima l'auto che deve uscire, viene aperta la guardia della coda interna e le auto in attesa vengono fatte uscire, sempre rispettando l'ordine. Altrimenti anche questa seconda auto viene accodata nella coda interna.
Di seguito vediamo il codice semplificato della entry ExitLane.

\begin{lstlisting}[frame=trBL,columns=fixed,postbreak=\space,breaklines,caption={Procedura ExitLane di Sector.}]
entry ExitLane when Changed = True is
  begin
    if (ExitArray(1).CarId = my_properties.CarId) then
      -- l'auto e' la prima nella lista di uscita
      rimuovi auto da ExitArray
      if (sono presenti auto nella coda interna) then
        apri la guardia
      else 
        chiudi la guardia
      end if;

      next_sect := calcolo il settore successivo
      requeue Sectors(next_sect).Enter;

    else
      -- l'auto NON e' la prima nella coda di uscita
      requeue ExitLane;
    end if;
end ExitLane;
\end{lstlisting}

In questo modo viene gestito algoritmicamente l'ordine di uscita dai settori.

\section{Race}

Il componente Race è implementato come un tipo task. Si tratta di un \textit{server}, cioè un tipo di entità reattiva. L'esecuzione delle varie chiamate avviene quindi in mutua esclusione. Questo permette di assegnare senza incorrere in \textit{race condition} gli \textit{ID} alle auto registrate. Inoltre l'esecuzione in mutua esclusione delle chiamate semplifica la gestione delle classifiche e dei monitor.

\textit{Race} infatti ha anche il ruolo di gestione delle statistiche. Logicamente è la gara che conosce la classifica ed i vari tempi di percorrenza sull'intermedio e sul giro dei singoli concorrenti. \textit{Race} si occupa quindi di ricevere informazioni sulle percorrenze da \textit{Track}, elaborare tali dati ottenendo informazioni derivate (ad esempio il tempo sul giro) e diffondere queste informazioni ai monitor tramite un protocollo di comunicazione che segue il modello della \textit{push notification}.
Tutte le chiamate relative alle statistiche sono implementate come asincrone.

\section{Monitor}

Monitor, per sua natura, è strettamente correlato alla propria GUI. Coerentemente con i messaggi ricevuti da gara, viene creata una struttura dati GTK che ne permette la visualizzazione. La concorrenza in questo componente si limita alla mutua esclusione nell'accesso alla struttura dati, che viene garantita da apposite chiamate GTK con cui racchiudere la sezione critica.

\section{Protocollo di partenza}
\label{Protocollo_Partenza}
Il protocollo di partenza emula quello che accade nel mondo reale. Si fissa un ordine di partenza, che può dipendere dall'\textit{ID} delle auto o essere randomizzato.
Quando arriva il segnale di inizio gara, la prima auto inizia a percorrere il primo settore; in particolare, effettua una chiamata \textit{Enter}. Solo a questo punto, l'auto notifica alla successiva che può partire. 
Il protocollo di partenza ``simula'' l'idea di una fila, in cui ogni auto può partire solo dopo che l'auto precedente è partita.
Come tempo di inizio della competizione viene inteso il tempo di partenza della prima auto in griglia. \\
Questa soluzione sembra un giusto compromesso tra semplicità e realismo nella simulazione.


\section{Correttezza temporale}
\label{Correttezza_Temporale}
Si può assumere che il protocollo di percorrenza del circuito è corretto dal punto di vista temporale sulla base delle seguenti considerazioni:
\begin{itemize}
        \item La simulazione avviene interamente nel componente \textit{Track}. I tempi necessari alla simulazione (tempo di avvio della gara) sono riferiti solo all'orologio locale del nodo in cui esegue questa componente. Non si presentano quindi problemi legati alla sincronizzazione degli orologi. Inoltre i tempi di percorrenza sono tutti relativi (\textit{Duration}), quindi completamente indipendenti dall'orologio di sistema.

        \item L'ordine di ingresso in un settore è controllato da una risorsa protetta (il settore precedente) che ne assicura la correttezza a prescindere dall'ordine di esecuzione.

        \item I tempi di percorrenza si basano solo sui tempi calcolati, quindi il protocollo è corretto indipendentemente dall'ordine e dal tempo di esecuzione.

        \item Il tempo di percorrenza di un settore dipende esclusivamente dalle caratteristiche dell'auto e quindi ancora indipendente dall'esecuzione concorrente.

        \item L'unico caso in cui il tempo calcolato viene modificato è quando la corsia di percorrenza è affollata. In questo condizione il tempo di percorrenza dell'auto viene aumentato in modo che il tempo d'uscita dal settore non sia inferiore di quelli delle auto che precedono, quindi concettualmente corretto.

        \item L'accodamento nelle varie corsie è controllato algoritmicamente: viene scelta la corsia meno affollata. E' quindi decidibile e non dipende dall'ambiente di esecuzione.
\end{itemize}

I problemi maggiori dipendono dal fatto che i task possono alternarsi nell'esecuzione in modo (per noi) non predicibile. Si sono presentati diverse situazioni che riguardo questa tematica. Di seguito ne elenchiamo alcune, con le relative soluzioni.

\begin{itemize}
\item il risveglio delle auto dalla \textit{delay} può non avvenire in ordine: la soluzione è stata l'introduzione di un protocollo di \textit{booking}: le auto comunicano ai settori quale sarà il loro tempo di uscita. La procedura che implementa questa idea è chiamata \textit{BookExit}. Sostanzialmente si tratta di una soluzione algoritmica ad un ordine di esecuzione dei processi non corretto.
 I processi vengono accodati in una coda interna di una risorsa protetta (\textit{Sector}). 
Le auto riescono ad uscire dal settore solo rispettando l'ordine di uscita calcolato sui tempi comunicati in precedenza. 
Un task che esegue in un momento non previsto, non ha la possibilità di uscire, viene riaccodato nella coda interna, e deve attendere l'esecuzione degli altri task. Questi task eseguiranno sicuramente, poichè se un'auto intende ritirarsi, non effettuerà la chiamata a \textit{BookExit},  quindi non risulterà presente nella lista dei tempi di uscita (esclusa \textit{starvation}). Questo protocollo non compromette i tempi di percorrenza.

\item Tra l'uscita da un settore e l'entrata nel successivo, l'ordine di esecuzione dei task potrebbe cambiare (prerilascio). La soluzione è stata rendere atomiche l'uscita da un settore e l'entrata nel successivo. L'implementazione prevede una \textit{requeue} dal metodo \textit{Release} di un settore, al metodo \textit{Enter} del settore successivo.

\item Coerenza dei tempi: il tempo di calcolo che intercorre tra il risveglio dalla \textit{delay until} al calcolo del tempo di risveglio nel settore successivo, non viene tenuto in considerazione.
 Il tempo di calcolo è quindi irrilevante. Questo tempo di calcolo, anche se fosse molto grande e diverso per ogni auto, non potrebbe in alcun modo influire sull'ordine di percorrenza, sui distacchi o sui tempi sul giro.
  I tempi sul giro ed i distacchi sono infatti calcolati come somma dei tempi dei singoli settori.
\end{itemize}

La gestione dei tempi di gara sembra risultare corretta e coerente. Auto con le stesse caratteristiche hanno identici tempi di percorrenza (a parte nel primo giro per i tempi di partenza diversi).