4_conclusioni.tex

\chapter{Conclusioni}
\label{sec:conclusione}

Questa tesi presenta l'implementazione e la valutazione empirica di un protocollo di accesso a risorsa disegnato a partire dalle linee guida fornite da Burns e Wellings in \textit{A Schedulability Compatible Multiprocessor Resource Sharing Protocol - MrsP} (~\cite{Burns:2009:RSP:1643588}). I due autori hanno dimostrato come il protocollo permetta l'utilizzo di tecniche di analisi di schedulabilità per sistemi single processor. In particolare, è presa in considerazione la \textit{response-time analysis} che bene si presta per l'analisi di un sistema basato su scheduler \textit{(Partitioned) Fixed Priority} aumentata dalla contesa per l'accesso alla risorsa globale. Di conseguenza, una volta calcolato il possibile numero di accessi in parallelo, questo parametro è utilizzato, in fase di analisi, per limitare l'impatto della loro serializzazione.\\

MrsP è un algoritmo basato su attesa attiva, cioè l'attesa effettuata dal job dopo la sua richiesta nel caso di risorsa occupata. In questo caso, infatti, la richiesta viene inserita in una coda con ordinamento FIFO fino a che non ottiene ed esegue la risorsa. Tale coda ha lunghezza massima pari al numero di processori in cui vi è allocato un task che la richiede. Come si è visto, la caratteristica che rende il protocollo innovativo consiste nel permettere a un qualsiasi job in attesa di accedere alla risorsa e di eseguire per conto del suo possessore. Nell'implementazione fornita, questo si traduce nel permettere al job, possessore della risorsa, di migrare, in caso di prerilascio, nella partizione di uno dei job in attesa.\\
MrsP definisce un protocollo con un basso impatto sulla schedulabilità di un taskset: la soluzione proposta è stata implementata per verificare se il protocollo comporta un alto costo in fase di esecuzione, andando quindi a penalizzare il basso impatto ottenuto dalle scelte algoritmiche.\\
`
Gli esperimenti sono stati realizzati per valutare il protocollo e la relativa implementazione da diversi punti di vista. Attraverso la comparazione con altri due protocolli: \textit{simple ceiling} e \textit{non preemption}, basati rispettivamente su utilizzo di ceiling e inibizione di prerilascio, i cui approcci sono alla base di molti dei protocolli precedentemente esistenti per la condivisione di risorse in sistemi multiprocessor. Dal confronto è emerso come MrsP garantisca un tempo di risposta inferiore rispetto agli altri due protocolli, sia per i job a bassa priorità che a priorità alta.\\
Inoltre, sono stati valutati i costi delle singoli primitive implementate, evidenziando così un limite entro il quale l'utilizzo del protocollo comporta beneficio; superato quel valore, invece, il costo aggiunto da MrsP diviene superiore rispetto alla durata della sezione critica della risorsa. I costi rilevati hanno dimostrato che le operazioni sulla coda, struttura su cui si basa il funzionamento del protocollo, comportano un costo ridotto rispetto al tempo complessivo necessario per l'esecuzione delle primitive di scheduling e di gestione della risorsa. Per esempio, la primitiva di acquisizione della risorsa ha un costo (nel caso pessimo) di circa 3k ns e solamente 200 ns circa sono riportabili alle operazioni sulla coda.\\
Infine, si è verificato come il protocollo non vada ad appesantire il sistema quando non vi sono risorse globali. Questo è un risultato importante in quanto, in un sistema reale, un task necessita della risorsa per un tempo breve rispetto alla lunghezza dell'esecuzione complessiva.\\

\section{Sviluppi futuri}
\label{sec:open_problem}

\paragraph{Limitazione delle migrazioni}

Gli esperimenti eseguiti hanno evidenziato come il costo principale del protocollo sia la migrazione. Un studio più approfondito potrebbe portare a un approccio in grado di limitarne il numero durante l'esecuzione. Una volta stimato il costo del protocollo su una determinata piattaforma e confrontato con la durata della sezione critica delle risorse, un approccio simile a FMLP (sezione~\ref{sec:lockProtocols.fmlp}) permette di dividerle tra "brevi" e "lunghe". Per le prime si potrebbe optare per una gestione che inibisce il prerilascio, in quanto, come discusso, comporta un basso costo durante l'esecuzione. MrsP sarebbe chiamata a gestire gli accessi alle risorse "lunghe", ma con un ulteriore accorgimento: quando un job a priorità superiore al ceiling richiede di prerilasciare il job in possesso della risorsa, si valuta di quanto tempo necessita quest'ultimo per portare a termine la sezione critica, se tale tempo è inferiore al tempo necessario per effettuare una migrazione viene ritardato il prerilascio, altrimenti vengono utilizzati i normali meccanismi del protocollo. Un approccio di questo tipo causerebbe blocco ai job a priorità superiore al ceiling, ma per un tempo limitato (minore al costo di una migrazione), per una volta soltanto e prima dell'inizio dell'effettiva esecuzione. Di conseguenza, è facilmente integrabile in fase di analisi di schedulabilità.

\paragraph{Confronto con OMIP}

La sezione~\ref{sec:lockProtocols.multi} ha analizzato il protocollo OMIP (\cite{6602109}), il quale rappresenta una valida alternativa a MrsP. Nonostante sia pensato per sistemi organizzati a cluster, se si pone la dimensione di ognuno pari a uno si ottiene un sistema partizionato, quindi è possibile e interessante un confronto tra MrsP e OMIP. Inoltre, è possible modificare OMIP per meglio adattarlo a un sistema partizionato, tuttociò sostituendo la coda FIFO per ogni processore (sezione~\ref{sec:lockProtocols.omip}) con un qualche meccanismo che vada a implementare il concetto di \textit{token} da acquisire in ogni cluster.

\paragraph{Risorse innestate}

Un possibile sviluppo futuro, per quanto riguardo il protocollo, è il supporto alle risorse innestate, cioè l'acquisizione di una risorsa quando si è già in possesso di un'altra.\\
La soluzione più semplice è quella di vincolare le risorse a un ordinamento, deciso in fase di progettazione, secondo il quale una risorsa può accedere solamente quelle che la precedono. In tal modo, si evitano le situazioni di deadlock a scapito di una minore espressività progettuale.\\
FMLP propone l'utilizzo dei "Group locks", già discussi nella sezione~\ref{sec:lockProtocols.fmlp}. Le risorse innestate vengono raggruppate in unico gruppo e per accedere a una risorsa bisogna acquisire il gruppo a cui appartiene, nonostante non necessiti di tutte le risorse. In questo caso, si previene il deadlock ma a scapito del parallelismo.\\
Infine, Ward et. al~\cite{DBLP:dblp_conf/ecrts/WardA12} propongo il protocollo RNLP (\textit{real-time nested locking protocol}). \`E basato su un sistema a k-lock, con il quale limita il numero di richieste di accesso alle risorse che possono essere in attesa in un determianto momento, e su un meccanismo che utilizza i timestamp delle richieste per ottenere un protocollo che permette risorse innestate a grana fine.