3_esperimenti.tex

%----------------------------------------------------------------------------------------
%	MODELLO
%----------------------------------------------------------------------------------------


\input{figure/test_protocolli.tex}
\input{figure/grafico1.tex}
\input{figure/grafico_sched.tex}
\input{figure/grafico_release.tex}
\input{figure/grafico_cxs.tex}
\input{figure/timeline.tex}
\input{figure/overheads_suffered.tex}
\input{figure/data_structure.tex}
\input{figure/overheads.tex}

\chapter{Esperimenti e valutazioni}
\label{sec:esperimenti}

Gli esperimenti eseguiti hanno lo scopo di valutare l'implementazione proposta di \emph{MrsP} da diversi punti di vista.\\

In un primo insieme di esperimenti il protocollo è messo a confronto con altri due protocolli che, come MrsP, sono sviluppati su sistemi partizionati con condivisione di risorse globali: il primo è basato su un approccio \textit{simple ceiling}, mentre il secondo utilizza inibizione di prerilascio. Questo esperimento conside le prestazioni dei protocolli nell'esecuzione di taskset creati su misura per confrontare i \textit{response time} dei vari task in specifiche circostanze. Infine i risultati delle elaborazioni sono confrontati con i dati ottenuti dalle simulazioni in Burns et al.~\cite{Burns:2013:SCM:2547348.2547350}.\\

In seguito, è discussa una valutazione di costi e prestazioni dell'implementazione: una serie di campionamenti permette di verificare il costo aggiunto da MrsP alle primitive dello scheduler, in particolare il tempo computazionale aggiunto per integrare il protocollo in P-FP.\\

Infine, risulta interessante il funzionamento dello scheduler in assenza di risorse, questo in quanto la presenza di risorse globali condivise in un sistema partizionato è un caso particolare di esecuzione, quindi un buon funzionamento in sua assenza risulterebbe positivo ai fini di una valutazione completa. A tal fine, il sistema è confrontato con P-FP, cioè il medesimo scheduler privo di integrazione con MrsP.\\

\section{Ambiente di esecuzione}
\label{sec:ambiente}

Gli esperimenti sono effettuati su una macchina fisica dotata di piattaforma i7-2670QM, architettura lanciata da Intel nell'ottobre del 2011.\\

\paragraph{Sandy Bridge} è l'architettura alla base del sistema. Esso consiste in un quad-core con frequenza di clock pari a 2.2 GHz, 3.1 GHz in \textit{Turbo mode}. Ogni core possiede due livelli di cache, L1 e L2 di dimensione rispettivamente pari a 64 KB e 256 KB, ed un terzo livello L3 condiviso tra i 4 core con dimensione di 6 MB. La memoria cache utilizza un metodo di gestione creato da Intel e chiamato "Smart cache": permette di diminuire il rapporto globale di \textit{cache miss} aumentando così l'efficienza del suo utilizzo. Questa tecnologia prevede che tutti i livelli di cache siano condivisi tra le CPU e gli accessi assegnati in base alle richieste piuttosto che essere dedicati; inoltre, applica la logica \textit{data-fetch} alle operazioni in modo da mettere a disposizione dei dati ancor prima che siano richiesti. La tecnologia \textbf{Simultaneous Multi-Threading} permette di raddoppiare il numero di core, trasformando i 4 fisici in 8 logici, tramite l'esecuzione di due thread sul medesimo core. Questa opzione è disabilitata in fase di test; allo stesso modo anche le funzioni di gestione della potenza sono disattivate. Il \textbf{bus} interno alla CPU ha una velocità pari a 100 MHz, mentre il bus seriale che permette le comunicazioni tra processori e con il chipset raggiunge i 5 GT/s. I bus per le connessioni tra processori e chipset utilizzano la tecnologia \textit{QuickPath Interconnect} (QPI), la cui caratteristica principale consiste nel permettere comunicazioni "point-to-point" tra le varie componenti; questo è indubbiamente un vantaggio rispetto all'utilizzo del bus come canale unico per tutte le comunicazioni, permettendo così più trasferimenti simultanei.\\
La piattaforma utilizzata supporta la \textbf{Vanderpool Technology}, una particolare tecnologia di virtualizzazione per piattaforme Intel che rende possibile l'esecuzione simultanea di più sistemi operativi ospiti contemporaneamente.\\

Gli esperimenti sono eseguiti con il supporto di macchina virtuale; l'infrastruttura di virtualizzazione è basata su \textit{Kernel-based Virtual Machine} (\textbf{KVM}) che è specifica per i sistemi Linux, mentre il software di emulazione QEMU permette di eseguire il sistema operativo, nel nostro caso l'estensione di Linux con LITMUS\textsuperscript{RT}, come ospite della macchina fisica. L'immagine virtuale utilizzata è in formato compatibile con QEMU ed esegue la bzImage generata tramite la compilazione del kernel.\\

Il comando di lancio della VM è il seguente:\\

\texttt{qemu-system-x86\_64 -enable-kvm -smp 4 -m 512 \\
-boot c -nographic -net nic -net user,hostfwd=tcp::10022-:22 \\
-kernel bzImage -append "console=ttyS0,115200 root=/dev/hda1" \\ 
-hda ubuntu.backing.qcow2.img}\\

Tramite i parametri specificati il sistema di virtualizzazione riconosce che viene lanciato un kernel a 64 bit utilizzando KVM; quest'ultimo supporta la tecnologia di virtualizzazione specifica di Intel denominata Vanderpool citata precedentemente: permette di dividere un sistema in macchine virtuali distinte nonostante condividano le stesse risorse di sistema; ne risultano quindi due macchine logiche, che operano in maniera totalmente indipendente grazie all'appoggio di specifiche funzionalità hardware che consentono di ottimizzare tale condivisione. In particolare, l'architettura hardware abbinata a questa configurazione permette un accesso diretto ai core fisici senza alcun livello di virtualizzazione intermedio.\\
Alla macchina virtuale vengono assegnati il kernel Linux \texttt{-hda}, 4 core fisici e 512 MB di memoria.\\

In fase di sviluppo sono stati utilizzati alcuni strumenti \textit{user-space} per interagire con LITMUS\textsuperscript{RT}:

\begin{itemize}
  \item \textit{liblitmus}, Appendice~\ref{sec:liblitmus}, è una libreria che permette la creazione ed il controllo di task set;
  \item \texttt{TRACE()} permette di ottenere informazioni dall'esecuzione, è il principale strumento per effettuare debugging.\\
\end{itemize}

I campionamenti sono effettuati tramite \textit{Feather-Trace}, il quale consiste in una serie di strumenti atti a calcolare gli overhead delle primitive e rilevare gli eventi di scheduling. Tramite i dati raccolti è stato possibile valutare l'implementazione e confrontare i vari protocolli.\\
Maggiori informazioni sui metodi di tracciamento e campionamento sono presentati in Appendice~\ref{sec:trace}.\\

\subsection{Generazione ed esecuzione degli esperimenti}

Per la creazione dei taskset sono stati usati tre differenti approcci:

\begin{itemize}
	\item generati manualmente per ottenere un determinato comportamento;
	\item tramite applicazione Java per taskset che richiedano l'utilizzo di risorse;
	\item \textit{experiment-scripts}, una suite di script in Python per la creazione di taskset.
\end{itemize}

La libreria \textit{experiment-scripts} definisce un formato di file con il quale è possibile avviare, con un unico comando, un intero taskset:

\begin{itemize}
  \item \texttt{sched.py} consiste in una lista di task con relativi parametri (WCET, periodo, risorse, etc.);
  \item \texttt{params.py} contiene informazioni che specificano il plugin utilizzato ed informazioni riguardanti il taskset.
\end{itemize}

Una volta deciso lo scheduler da utilizzare, il file che specifica il taskset è generato manualmente o tramite script . Maggiori informazioni riguardanti \textit{experiment-scripts} sono riportate in Appendice~\ref{sec:exp-script}.\\

\section{Confronto tra protocolli}
\label{sec:confronto_protocolli}

Nei protocolli \textit{lock-based} l'accesso è gestito, in caso di risorsa occupata, tramite sospensione oppure attesa attiva. Nel primo caso, se la risorsa è occupata, il task richiedente si sospende e viene inserito in una coda in attesa del suo rilascio. Al contrario, in presenza di un protocollo \textit{spin-based}, il richiedente effettua attesa attiva fino al momento di accesso alla risorsa. Tale argomento viene discusso approfonditamente in Brandenburg et al.~\cite{Brandenburg:2008:RSM:1440456.1440601}. MrsP si basa su approccio spin-based, in quanto tale scelta permette di limitare il tempo di blocco subito, ma risulta cruciale come ed in quali circostanze effettuare attesa attiva.\\

Questo esperimento si sofferma su questo aspetto, cioè in che modo effettuare attesa attiva e a quali condizioni: a seconda del valore di priorità scelto per proseguire l'attesa si ottengono comportamenti differenti che influenzano in modo diverso il sistema.\\

\subsection{Esperimento \#1}
\label{sec:confronto_protocolli_exp}

Il seguente esperimento mette a confronto tre protocolli differenti costruiti su sistema partizionato con dispatching basato su priorità e accesso alla risorsa globale gestito tramite accodamento FIFO. In tutti e tre i casi i protocolli sono basati su SRP: un job inizia a eseguire solamente quando le risorse di cui necessita sono libere, innalza la propria priorità al momento della richiesta ed effettua attesa attiva fino a quando ne ottiene l'accesso esclusivo.\\

Il protocollo basato su \textit{simple ceiling} prevede che il job innalzi la propria priorità al valore della priorità più alta tra tutti i task allocati nella stessa CPU che la richiedono, esattamente come MrsP. Il suo comportamento è analogo a quello di MrsP, salvo il fatto che non vi è nessun meccanismo di migrazione.\\

Il terzo protocollo prevede che al momento della richiesta venga inibito il prerilascio localmente alla CPU del richiedente. Questo effetto in fase di implementazione è stato ottenuto innalzando la priorità al valore massimo, non permettendo a nessun job di causare prerilascio.\\

L'esperimento prevede di mettere a confronto i response time dei task che compongono il sistema, analizzando quali vengano maggiormente penalizzati dall'attesa attiva nei tre protocolli al variare di parametri come la lunghezza della sezione critica o del WCET di determinati task.\\

\subsection{Configurazione}
\label{sec:confronto_protocolli_conf}

Il taskset prevede 3 task ($\tau_1, \tau_2, \tau_3$) allocati su due CPU: sulla prima CPU viene allocato un task a priorità maggiore e uno a priorità inferiore, quest'ultimo condivide la risorsa globale con un task allocato nella seconda CPU.\\

L'esecuzione è impostata in modo tale che il primo job a essere rilasciato ed eseguire sia quello a priorità inferiore allocato nella prima CPU ($L_1$), poi il job della seconda CPU ($L_3$) e infine quello a priorità più alta ($H_2$. L'esecuzione voluta è rappresentata nella figura \ref{fig:test_protocols}: 

\begin{itemize}
  \item punto {\color{red} 1}, il job a priorità più bassa è rilasciato e ottiene la risorsa in quanto libera;
  \item punto {\color{red} 2}, il secondo job a bassa priorità si accoda ed effettua attesa attiva nella seconda CPU;
  \item punto {\color{red} 3}, Il job a priorità più alta tenta di eseguire causando prerilascio del primo job; quest'ultimo passaggio viene gestito in modo differente dai tre protocolli.\\
\end{itemize}

\begin{figure}
\centering
\exampleTest{1.5}{1.5}
\caption{Configurazione del test tra protocolli.}
\label{fig:test_protocols}
\end{figure}

\subsection{Obiettivo}
\label{sec:confronto_protocolli_ob}

Variando il tempo di esecuzione del job a priorità più alta e la lunghezza della sezione critica della risorsa globale il comportamento atteso è che in ogni protocollo sia differente il job che soffre maggiormente tale cambiamento.\\

Nei capitoli precedenti è stato chiarito come la condivisione della risorsa tra più CPU in un sistema partizionato vada ad aumentare il costo pagato da alcuni job. In MrsP, tale condivisione influenza solamente i job che la vogliono ottenere e coloro che subiscono blocco da essi, cioè non la richiedono, ma un job a priorità più bassa la contende ad uno a priorità superiore alla propria tra quelli della medesima CPU.\\

Privando MrsP dei meccanismi per gestire i prerilasci si ottiene un comportamento simile a quello del protocollo basato su \textit{simple ceiling}: i job a priorità maggiore non verranno influenzati, ma al tempo stesso aumenta il tempo di blocco subito dai job a priorità inferiore al ceiling e i tempi di attesa dei job accodati sulla risorsa allocati in altre CPU. Tale aumento di blocco e attesa è determinato dal fatto che il proprietario della risorsa non può proseguire l'esecuzione della sezione critica in quanto prerilasciato. Il risultato è un sistema in cui l'interferenza subita dal lock holder si ripercuote anche sugli altri processori.\\

Il comportamento atteso dal protocollo che inibisce il prerilascio è che il job a soffrire maggiormente della condivisione sia quello localmente ready a priorità più alta: esso subisce un ritardo pari all'esecuzione della sezione critica nonostante non necessiti della risorsa globale. Il risultato è quindi che soffrano blocco anche i job che non rispecchiano la condizioni fornite in precedenza, la loro esecuzione di conseguenza viene ritardata fino a che il job non ripristina la proprio priorità al momento del rilascio della risorsa.\\

Un altro aspetto che si vuole studiare è come le migrazioni vadano a influenzare le prestazioni di MrsP: un ultimo taskset è configurato in modo tale che le circostanze che forzano il job dalla prima CPU alla seconda a migrare si ripresentino anche in quest'ultima, obbligando a una seconda migrazione nella terza CPU in cui eseguire la sezione critica.

\subsection{Risultati esperimento \#1}
\label{sec:confronto_protocolli_ris}

La tabella~\ref{tab:test_protocols_Taskset1} rappresenta il primo task set. In esso i job hanno i medesimi tempi di esecuzione (pari a un millisecondo). La durata della sezione critica è compresa nell'esecuzione del WCET; nel caso abbiano lo stesso valore si intende che il job effettui la richiesta di accesso come prima azione e completi al momento del rilascio la propria esecuzione. Ne consegue che l'evento di rilascio della risorsa e quello di completamento del task non coincidono. Questo particolare è importante in quanto, in alcuni casi, nelle tempistiche riportate si considera il momento di rilascio della risorsa.\\

\begin{table}
  \centering
  \begin{tabular}{ccccc}
	\hline\hline
	    Task & Partition & priority & Critical section & WCET  \\ \hline
	    $L_1$ & $P_1$  & 20 & 1 & 1 \\
	    $H_2$ & $P_1$  & 10 & 0 & 1 \\
    	$L_3$ & $P_2$  & 20 & 1 & 1 \\
  	\hline
  	\end{tabular}
  \caption{Confronto tra protocolli: primo task set.}
  \label{tab:test_protocols_Taskset1}
\end{table}

La tabella~\ref{tab:test_protocols_Taskset1_ris} riporta i tempi di completamento di ogni job per i tre protocolli. I valori sottolineati indicano l'istante di rilascio della risorsa piuttosto che il completamento, questo in quanto il resto esecuzione subisce interferenza da parte del job a priorità superiore ed esula dai compiti dei protocolli di accesso a risorsa.\\

\begin{table}
  \centering
  \begin{tabular}{cccc}
  \hline\hline
    Task & MrsP & Ceiling & Non preemption \\ \hline
    $L_1$ & \underline{1.206.362} & 2.194.042 & \underline{1.111.517} \\
    $H_2$ & 1.098.587 & 1.068.602 & 1.977.039 \\
    $L_3$ & 2.351.562 & 3.168.240 & 1.911.890 \\
    \hline
    \end{tabular}
  \caption{Confronto tra protocolli: risultato primo task set, tempi espressi in nano secondi. I valori sottolineati si riferiscono al rilascio della risorsa e non al completamento del job.}
  \label{tab:test_protocols_Taskset1_ris}
\end{table}

    \begin{figure}
      \centering
      \RisultatoUnoMrsP
      \caption{\textit{MrsP}.}
      \label{fig:test_protocols_mrsp}
    \end{figure}

    \begin{figure}
      \centering
      \RisultatoUnoCeiling
      \caption{\textit{Simple ceiling}.}
      \label{fig:test_protocols_sc}
    \end{figure}
    
    \begin{figure}
      \centering
      \RisultatoUnoNoPreempion
      \caption{\textit{non preemption}.}
      \label{fig:test_protocols_np}
    \end{figure}

L'esecuzione del taskset è rappresentato graficamente in \ref{fig:test_protocols_mrsp}, \ref{fig:test_protocols_sc} e \ref{fig:test_protocols_np}. Analizzando i dati, si nota come in MrsP la migrazione renda minimo il tempo di attesa subito da $L_3$ e nullo il blocco subito da $H_2$. I valori di esecuzione rappresentati subiscono degli overhead dati dal sistema, in particolare il costo della migrazione. Questo comportamento viene messo in risalto nella figura~\ref{fig:test_protocols_mrsp}; le due linee rosse tratteggiate evidenziano l'overhead dato dal cambio di processore. Tale lasco di tempo consiste nel tempo che impiega il job a migrare, per cui $L_3$ continua a effettuare attesa attiva e lo smaltimento della coda FIFO viene rallentato in quanto $L_1$ non sta progredendo nell'esecuzione della sezione critica.\\
Con l'approccio basato su simple ceiling il tempo di attesa di $H_2$ non dipende più solamente dalla lunghezza della coda della risorsa, ma anche dall'interferenza che il lock holder subisce. La figura~\ref{fig:test_protocols_sc} mostra come l'interferenza penalizzi ogni processore in cui vi sia un job in attesa della risorsa. Modificando il tempo di esecuzione di $H_2$ ci si aspetta che tale costo aumenti o diminuisca di conseguenza.\\
Al contrario dei casi precedenti, inibendo il prerilascio il job a soffrire maggiormente la condivisione della risorsa è $H_2$ in quanto non riesce ad eseguire nonostante non la richieda. L'inizio dell'esecuzione del job a priorità maggiore viene quindi ritardata; in figura~\ref{fig:test_protocols_np} è evidenziato questo comportamento. Pertanto, $H_2$ subisce un maggiore blocco all'aumentare della sezione critica.\\

Nei taskset~\ref{tab:test_protocols_Taskset2} e \ref{tab:test_protocols_Taskset3} sono state apportate modifiche rispettivamente alla lunghezza della sezione critica e al tempo di esecuzione del job a priorità maggiore.\\

\begin{table}
  \centering
  \begin{tabular}{ccccc}
  \hline\hline
    Task & Partition     & priority & Critical section & WCET  \\ \hline
    $L_1$ & $P_1$  & 20 & 3 & 3 \\
    $H_2$ & $P_1$  & 10 & 0 & 1 \\
    $L_3$ & $P_2$  & 20 & 3 & 3 \\
    \hline
    \end{tabular}
  \caption{Confronto tra protocolli: aumento della sezione critica.}
  \label{tab:test_protocols_Taskset2}
  \end{table}

  \begin{table}
  \centering
  \begin{tabular}{ccccc}
  \hline\hline
    Task & Partition     & priority & Critical section & WCET  \\ \hline
    $L_1$ & $P_1$  & 20 & 1 & 1 \\
    $H_2$ & $P_1$  & 10 & 0 & 3 \\
    $L_3$ & $P_2$  & 20 & 1 & 1 \\
    \hline
    \end{tabular}
    \caption{Confronto tra protocolli: aumento dell'interferenza.}
  \label{tab:test_protocols_Taskset3}
  \end{table}

Nel primo caso il comportamento è quello che ci si aspetta: la figura~\ref{tab:test_protocols_Taskset2_ris} mostra come un aumento della sezione critica con MrsP dilunghi il tempo di attesa di $L_3$, che viene utilizzato come nel caso precedente per far proseguire $L_1$ al momento del prerilascio, mentre $H_2$ resta inalterato. Al contrario, con simple ceiling sia $L_1$ che $L_3$ subiscono l'interferenza da parte di $H_2$. Infine, inibendo il prerilascio il job di $L_3$ subisce ulteriormente l'inversione di priorità.\\

\begin{table}
  \centering
  \begin{tabular}{cccc}
  \hline\hline
    Task & MrsP & Ceiling & Non preemption \\ \hline
    $L_1$ & \underline{3.066.828} & 4.242.092 & \underline{3.177.307} \\
    $H_2$ & 1.035.721 & 1.141.324 & 3.956.506 \\
    $L_3$ & 6.099.752 & 7.209.873 & 6.024.691 \\
    \hline
    \end{tabular}
    \caption{Confronto tra protocolli: aumento della sezione critica, tempi espressi in nano secondi. I valori sottolineati si riferiscono al rilascio della risorsa e non al completamento del job.}
  \label{tab:test_protocols_Taskset2_ris}
  \end{table}

Agendo sul WCET di $H_2$ (tabella~\ref{tab:test_protocols_Taskset3_ris}) si dimostra come MrsP sia più performante al netto dei costi della migrazione, mentre con simple ceiling la maggiore interferenza subita da $L_1$ rende maggiore il tempo di attesa di $L_3$. Inibendo il prerilascio il maggior tempo di esecuzione non influisce sui job che vogliono accedere la risorsa e l'inizio dell'esecuzione di $H_2$ è posticipato allungando così il tempo di completamento.\\

\begin{table}
  \centering
  \begin{tabular}{cccc}
  \hline\hline
    Task & MrsP & Ceiling & Non preemption \\ \hline
    $L_1$ & \underline{1.053.232} & 4.215.599 & \underline{1.113.397} \\
    $H_2$ & 3.018.344 & 3.071.190 & 4.006.309 \\
    $L_3$ & 2.042.122 & 5.169.139 & 2.068.905 \\
    \hline
    \end{tabular}
    \caption{Confronto tra protocolli: aumento dell'interferenza, tempi espressi in nano secondi. I valori sottolineati si riferiscono al rilascio della risorsa e non al completamento del job.}
  \label{tab:test_protocols_Taskset3_ris}
  \end{table}

Con il taskset illustrato nella tabella~\ref{tab:test_protocols_Taskset4} si intende ripercorrere il funzionamento del primo esempio forzando in questo caso il job che detiene la risorsa ad affrontare 2 migrazioni. Inoltre il fatto che vi siano 3 CPU a contendere per l'accesso della risorsa triplica il fattore per cui la sezione critica viene moltiplicata. A seconda del protocollo utilizzato aumenta l'attesa dei job accodati o il blocco subito dai job a priorità più alta.\\

\begin{table}
  \centering
  \begin{tabular}{ccccc}
  \hline\hline
    Task & Partition     & priority & Critical section & WCET  \\ \hline
    $L_1$ & $P_1$  & 20 & 1 & 1 \\
    $H_2$ & $P_1$  & 10 & 0 & 3 \\
    $L_3$ & $P_2$  & 20 & 1 & 1 \\
    $H_4$ & $P_2$  & 10 & 0 & 3 \\
    $L_5$ & $P_3$  & 20 & 1 & 1 \\
    \hline
    \end{tabular}
    \caption{Confronto tra protocolli: doppia migrazione.}
  \label{tab:test_protocols_Taskset4}
  \end{table}

  \begin{table}
  \centering
  \begin{tabular}{cccc}
  \hline\hline
    Task & MrsP & Ceiling & Non preemption \\ \hline
    $L_1$ & \underline{1.111.410} & 4.312.490 & \underline{1.173.600} \\
    $H_2$ & 3.029.214 & 3.131.630 & 4.205.578 \\
    $L_3$ & \underline{2.062.770} & 5.301.240 & \underline{2.211.347} \\
    $H_4$ & 3.022.036 & 3.099.090 & 5.078.436 \\
    $L_5$ & 3.030.634 & 6.309.370 & 3.184.333 \\
    \hline
    \end{tabular}
    \caption{Confronto tra protocolli: doppia migrazione, tempi espressi in millisecondi. I valori sottolineati si riferiscono al rilascio della risorsa e non al completamento del job.}
  \label{tab:test_protocols_Taskset4_ris}
  \end{table}

Nella tabella~\ref{tab:test_protocols_Taskset4_ris} il comportamento è quello atteso e discusso finora, l'aspetto interessante è vedere come l'esecuzione di circa 1 ms di $L_1$ sia aumentato ulteriormente da 1.05 ms a 1.1 ms a causa della doppia migrazione.

\subsection{Considerazioni}
\label{sec:confronto_protocolli_cons}

I risultati esaminati mettono in risalto le differenze tra i vari protocolli nella gestione della risorsa globale. Si nota come MrsP sia migliore rispetto alle alternative qui studiate: simple ceiling è inadatto a gestire la condivisione di risorse in ogni caso analizzato, mentre l'inibizione del prerilascio risulterebbe migliore in uno scenario in cui la lunghezza della sezione critica fosse inferiore rispetto agli overhead dati da MrsP, in particolare il costo della migrazione.\\

Quest'ultimo aspetto è discusso da Burns et al.~\cite{Burns:2013:SCM:2547348.2547350}: se i costi aggiunti dal sistema sono superiori rispetto alla lunghezza della sezione critica allora il protocollo non è più utile. Tale affermazione è confermata a seguito dell'implementazione e dei test, essi mettono in risalto come la presenza di costi aggiuntivi vada a penalizzarne le prestazioni.\\

Nei grafici \ref{fig:test_protocols_L1}, \ref{fig:test_protocols_H2} e \ref{fig:test_protocols_L3} sono riassunti i risultati ottenuti nell'esperimento, mettendo a confronto i tempi raccolti per ogni task nelle diverse configurazioni del sistema.\\

\begin{figure}
  \centering
  \confrontoProtocolliLUno
  \caption{Response time di $L_1$}
  \label{fig:test_protocols_L1}
\end{figure}

In figura~\ref{fig:test_protocols_L1} è preso in considerazione $L_1$, cioè il task a bassa priorità che richiede e accede la risorsa per primo. Il grafico evidenzia come MrsP e l'inibizione del prerilascio abbiano prestazioni molto simili, salvo il costo della migrazione nel primo caso; al contrario simple ceiling porta a risultati peggiori in ogni configurazione del sistema.\\

\begin{figure}
  \centering
  \confrontoProtocolliHDue
  \caption{Response time di $H_2$}
  \label{fig:test_protocols_H2}
\end{figure}

Il grafico~\ref{fig:test_protocols_H2} rappresenta le prestazioni raccolte di $H_2$: nei sistemi gestiti tramite utilizzo di ceiling i task a priorità superiore non risentono della presenza di risorse, mentre l'inibizione del prerilascio causa notevoli ritardi nei tempi di completamento dei job in quanto subisce blocco dall'esecuzione della sezione critica.\\

\begin{figure}
  \centering
  \confrontoProtocolliLTre
  \caption{Response time di $L_3$}
  \label{fig:test_protocols_L3}
\end{figure}

Infine il grafico~\ref{fig:test_protocols_L3} evidenzia come il job $L_3$ subisca l'interferenza a cui è soggetto $L_1$: MrsP e non preemption tentano di minimizzare tale interferenza, di conseguenza anche $L_3$ giova di questi meccanismi anche se con il primo protocollo si notano i costi dovuti dalla migrazione. Nel caso di simple ceiling il job in questione incorre nell'interferenza che avviene nella prima CPU oltre che nei tempi di attesa dovuti dallo smaltimento della FIFO.\\

L'esperimento illustrato in questa sezione è tratto dai test simulati da Burns e Wellings in ~\cite{Burns:2013:SCM:2547348.2547350}. L'implementazione sviluppata e valutata in questo lavoro di tesi rispecchia ciò che gli autori affermano. In particolare si evidenzia come MrsP sia una buona combinazione dei vantaggi degli altri approcci esaminati in questo esperimento. Inoltre, una reale implementazione, al contrario della simulazione, permette di ottenere un migliore riscontro dei costi aggiuntivi dati dalle primitive e, soprattutto, dalle migrazioni.\\

\section{Calcolo degli overhead}
\label{sec:overhead}

MrsP combina approcci differenti in parte tratti da protocolli esistenti, i quali, nonostante alcuni aspetti positivi, hanno un funzionamento inapplicabile ad un sistema real-time oppure hanno una complessità che a livello teorico sembra ragionevole ma che in un ambiente reale non è sostenibile. Uno degli obiettivi di questo lavoro di tesi è dimostrare che è possibile implementare il protocollo di Burns et al.~\cite{Burns:2013:SCM:2547348.2547350} a partire da uno scheduler P-FP con un sovraccarico ragionevole del sistema.

\subsection{Esperimento \#2}
\label{sec:overhead_exp}

Gli esperimenti esposti in questa sezione mirano a valutare l'implementazione e le scelte algoritmiche, i relativi overhead vengono studiati per capire quali task ne risentano e in quali circostanze.\\

Lo sviluppo del protocollo a partire dall'implementazione fornita da LITMUS\textsuperscript{RT} di P-FP ha reso necessario modificare alcune primitive per integrare il protocollo di accesso. Quelle prese in considerazioni sono le seguenti:

\begin{itemize}
	\item creazione della risorsa;
	\item richiesta di accesso;
	\item rilascio della risorsa;
	\item chiusura della risorsa;
	\item operazione di schedule;
	\item \textit{finish-switch}.
\end{itemize}

\subsection{Configurazione}
\label{sec:overhead_conf}

Il sistema non permette di avere un release time unico per tutti i job a meno di creare un taskset caratterizzato da periodi armonici, ma in questo caso risulterebbe difficile riuscire a testare alcuni meccanismi che solamente in casi particolari entrano in gioco. In un sistema privo di periodi armonici i task sono soggetti a \textit{release latency}, di conseguenza non è possibile forzare determinate dinamiche con precisione. Per ottenere campionamenti per ogni meccanismo che caratterizza MrsP è necessario creare un taskset sufficientemente grande in modo che si vengano a creare naturalmente le circostanze per poterne usufruire.\\
Il taskset è generato randomicamente con 25 job suddivisi su 4 CPU in modo il più possibile bilanciato. Per ogni CPU sono selezionati alcuni job ai quali è aggiunta la richiesta alla risorsa condivisa. Ogni taskset, prima di essere eseguito, è analizzato con uno script creato per verificare che sia \textit{feasible} andando ad applicare la \textit{response time analysis} aumentata con il protocollo MrsP.\\

\subsection{Obiettivo}
\label{sec:overhead_ob}

Lo scopo di questo esperimento è valutare l'impatto del protocollo in termini di overhead; i campionamenti sono messi in relazione con i tempi di esecuzione ed i costi aggiunti dal sistema.\\

Non tutte le primitive sono interessanti per lo studio dei costi che il protocollo aggiunge a \textit{runtime}: la creazione e la chiusura non sono presi in considerazione in quanto eseguite in fase di inizializzazione e finalizzazione della risorsa.\\

L'operazione di scheduling subisce un'unica modifica che permette di bloccare la coda dei job ready quando la richiesta in testa a tale coda ha priorità inferiore rispetto al ceiling locale. Ne consegue che il costo della primitiva risulta uguale o minore rispetto alla versione originale, di conseguenza, è poco interessante per i campionamenti.\\

Più complesse sono le primitive inerenti a \textbf{lock} e \textbf{release} della risorsa e l'operazione di \textbf{finish-switch}; quello che ci si aspetta è che l'overhead aggiunto in caso di esecuzioni nella norma non sia elevato e che vada ad aumentare a seconda dei meccanismi attivati. Per esecuzione "normale" si intende quei casi in cui non vi sono interferenze al lock holder da parte di job a priorità superiore al ceiling locale, pertanto i job che contendono per il possesso della risorsa effettuano la richiesta, se occupata attendono fino ad ottenerla, eseguono la sezione critica e la rilasciano.\\

I costi rilevati durante i campionamenti possono influenzare il sistema a tre differenti livelli (figura \ref{fig:overheads_suffered}):\\

\begin{itemize}
	\item {\color{red} (i)} il solo job che esegue la primitiva: questo accade se non si va a modificare il ceiling locale, di conseguenza non si causa blocco ai job a priorità inferiore a tale valore;
	\item {\color{red} (ii)} la sola CPU in cui è allocato il job corrente: questo succede nei casi in cui i costi vengano generati in circostanze di ceiling innalzato ma non si è in possesso della risorsa;
	\item {\color{red} (iii)} l'intero sistema, inteso come le CPU in cui stanno eseguendo job che attendono di accedere la risorsa.
\end{itemize}

\begin{figure}
\centering
\overheadsSuffered{1.4}{1.4}
\caption{Overhead e relativa influenza sul sistema.}
\label{fig:overheads_suffered}
\end{figure}

\subsection{Risultati esperimento \#2}
\label{sec:overhead_ris}

I dati del sistema sono organizzati secondo la figura \ref{fig:datas}: per ogni CPU è presente una struttura dati che tiene traccia del task attualmente in esecuzione, il numero della CPU, la coda dei task ready in attesa di eseguire ed il ceiling locale; la risorsa invece è composta dal task che la detiene, la coda di task in attesa di ottenerla e la lista dei ceiling calcolati in fase di inizializzazione. L'accesso alle strutture dati da parte dei processi viene reso sequenziale ed in mutua esclusione tramite l'uso dei \textbf{spinlock}. Quest'ultimo consiste in un particolare tipo di lock del kernel Linux, lo si acquisisce tramite l'operazione \texttt{spin\_lock(lock)} e lo si rilascia con \texttt{spin\_unlock(lock)}. Di conseguenza le primitive che prevedono l'utilizzo delle strutture dati prima di eseguire la sezione critica devono ottenere lo spinlock, tale operazione aggiunge ulteriori overhead oltre a quelli dettati dal protocollo in sé.\\

\begin{figure}
\centering
\data{1.3}{1.3}
\caption{Strutture dati.}
\label{fig:datas}
\end{figure}

Di seguito, sono prese in considerazione le primitive, per ognuna si indicando gli overhead campionati; i valori rilevati sono espressi in nanosecondi.

\paragraph{Lock}  L'operazione di richiesta della risorsa consiste nei tre passaggi elencati di seguito e raffigurati in figura \ref{fig:mrsplock}:

\begin{enumerate}
	\item innalzamento della priorità del job e del ceiling locale al valore calcolato in fase di inizializzazione, cioè la priorità più alta tra tutti i job allocati in quella CPU che accedono la risorsa, accodamento della richiesta nella FIFO ed infine determina la stato corrente della risorsa ed eventuale proprietario;
	\item in base alle informazioni ottenute al passo precedente, se il proprietario non è in esecuzione, cioè è accodato nella coda dei job ready di un altro processore, gli viene concesso di eseguire nella CPU corrente, viene perciò effettuata una migrazione;
	\item se il job che ha inoltrato la richiesta non ha ottenuto la risorsa effettua attesa attiva fino ad arrivare in testa alla coda FIFO.
\end{enumerate}

\begin{figure}
\includegraphics[width=\linewidth]{images/mrsp_lock.jpeg}
\caption{Lock: diagramma di flusso.}
\label{fig:mrsplock}
\end{figure}

La prima fase causa un overhead pari a circa \textbf{800 ns} e costituisce il costo principale riguarda le operazioni sulla coda di richieste. Questo costo è intrinseco alla risorsa e viene pagato dal job stesso e da quelli della stessa CPU. Tale influenza è motivata dal fatto che la prima operazione che viene effettuata è l'innalzamento di priorità e del ceiling, di conseguenza il tempo di blocco oltre alla sezione critica comprende anche questo overhead.\\

I dati utili a questa operazione sono condivisi con altri processi, di conseguenza l'accesso deve essere gestito tramite il sistema di spinlock in modo da garantire mutua esclusione ed evitare stati inconsistenti causati da accessi in parallelo da distinte CPU. Per eseguire i passaggi indicati in questa fase è necessario quindi aver acquisito lo spinlock della risorsa, aumentando il tempo necessario per effettuare la richiesta di accesso. Il suo costo va ad influire solamente sul job in questione ed il suo ammontare dipende dal numero di processori che contendono: un maggior numero di richieste in parallelo significa maggior interferenza, quindi un incremento dell'attesa.\\

La seconda fase consiste nel togliere il job dalla coda ready della CPU in cui si trova per modificarne la priorità ed accodarlo in quella corrente. In questo modo è possibile selezionarlo per l'esecuzione alla successiva operazione di scheduling. Le due singole operazioni sulle code richiedono in media un tempo pari a \textbf{500 ns}. Anche in questo caso il sistema è dotato di un sistema di lock che mirano a serializzare le operazioni, quindi è necessario ottenere lo spinlock prima di una CPU e poi, dopo aver rilasciato il precedente, di quella corrente. Le misurazioni del tempo complessivo della seconda fase indicano che le tempistiche medie sono vicine ai \textbf{2k ns}, e rispecchiano la contesa per ottenere il lock sulle CPU.\\

Il costo della migrazione è in media pari a \textbf{6k ns}, esso consiste nel tempo che impiega la CPU corrente ad effettuare il context switch tra il job che richiede la risorsa e quello che la detiene. Tale cambio di job in esecuzione viene effettuato tramite un'operazione di scheduling; i strumenti di misurazione delle primitive di sistema confermano che il costo complessivo della migrazione è composta dai singoli costi delle primitive richiamate per togliere il job dall'esecuzione in un processore e trasferirla sul processore di destinazione.\\

Gli overhead identificati influiscono sull'intero sistema in quanto l'esecuzione della sezione critica da parte del job che detiene la risorsa non riprende immediatamente non appena vi è una nuova CPU disponibile, bensì dopo una quantità di tempo determinata principalmente dalla migrazione.\\

La terza ed ultima fase della primitiva di richiesta della risorsa consiste nell'eseguire attesa attiva. Essa consiste nell'eseguire ciclicamente un controllo alla testa della coda FIFO, e nel caso sia il turno del job corrente acquisisce la risorsa. Ogni ciclo ha un costo di \textbf{500 ns}, anche in questo caso dettato dalle operazioni sulla coda; questo dato non tiene conto dell'overhead per ottenere lo spinlock della risorsa.\\

Quest'ultimo caso è un costo intrinseco del protocollo e dell'approccio spin-based, di conseguenza non aggiunge alcun costo, salvo un eventuale offset dato dal tempo che il job impiega ad accorgersi che è il suo turno. In tale circostanza si va ad allungare i tempi di attesa degli altri job contendenti, quindi anche il tempo di blocco subito nelle CPU.\\

\paragraph{Relsease} Al momento del rilascio della risorsa vengono effettuate le seguenti operazioni:

\begin{enumerate}
	\item il job rilascia la risorsa, ripristina la propria priorità ed il ceiling della CPU in cui è allocato e toglie la richiesta dalla testa della coda;
	\item se la FIFO non è vuota, viene controllato lo stato del job in testa, se non sta eseguendo si cerca una CPU in cui farlo eseguire;
	\item il job rilascia la CPU in cui sta eseguendo se non si trova nella propria di origine.
\end{enumerate}

\begin{figure}
\includegraphics[width=\linewidth]{images/mrsp_unlock.jpeg}
\caption{Lock: diagramma di flusso.}
\label{fig:mrsplock}
\end{figure}

Le operazioni della prima fase causano un overhead di \textbf{500 ns}; come nelle circostanze precedenti ad influire sono le manipolazioni della FIFO. In questo modo si posticipa l'esecuzione del prossimo job in testa alla coda, di conseguenza influenza ogni CPU in attesa di accesso.\\

Come nel caso dell'acquisizione della risorsa, in alcune circostanze è necessario forzare il prossimo lock holder a migrare in un'altra CPU per proseguire nell'esecuzione e limitare i tempi di attesa della coda FIFO. I campionamenti hanno evidenziato le medesime tempistiche: \textbf{2k ns} per le operazioni eseguite tenendo in considerazione i tempi causati dai spinlock sulle CPU e \textbf{6k ns} per effettuare la migrazione vera e propria. L'overhead viene pagato dall'intero sistema.\\

Nell'ultima fase il job che ha rilasciato la risorsa, se necessario, ritorna alla propria CPU di origine. Questo viene effettuato andando ad abbassare la priorità del job al di sotto del ceiling e forzando lo scheduler a selezionare la testa della coda ready.\\

Tale operazione raccoglie gli overhead delle seguenti operazioni:

\begin{enumerate}
	\item parte della chiamata di sistema per rilasciare la risorsa;
	\item schedule nella CPU attuale;
	\item operazione di post-schedule, la quale riaccoda il task nella propria CPU;
	\item schedule nella CPU di origine.
\end{enumerate}

Questa operazione di conseguenza risulta molto costosa, circa \textbf{65k ns}, è pagata solamente dal job che ha effettuato il rilascio. Tale attribuzione consegue dal fatto che la risorsa già nella prima fase è stata rilasciata, quindi potenzialmente il prossimo job può eseguire la propria sezione critica, ed il valore di ceiling della CPU di origine è stato ripristinato, permettendo ai job a priorità inferiore di eseguire nuovamente.\\

\paragraph{Finish-switch} Al contrario delle altre primitive, non vi è una sequenza di fasi, bensì, se necessario, si aziona solamente un meccanismo tra quelli implementati nella primitiva:

\begin{itemize}
	\item meccanismo base di migrazione di MrsP in caso di prerilascio;
	\item meccanismo di notifica di CPU di nuovo disponibile
  \item meccanismo di migrazione di LITMUS\textsuperscript{RT} 
\end{itemize}

Il primo prevede di cercare una CPU disponibile per la migrazione, il suo costo dipendente principalmente dalla lunghezza della coda. In caso di successo, il job modifica la propria CPU di riferimento e la priorità in base al nuovo ceiling, infine viene accodato nella CPU disponibile, forzando su di essa un'operazione di scheduling. Questo insieme di operazioni risulta onerosa in quanto opera sulla coda e necessita dello spinlock della risorsa e della coda ready. Il campionamento ha evidenziato un caso medio di circa \textbf{24k ns}.\\

Inoltre tali operazioni generano una migrazione: al contrario dei casi precedenti il job non è accodato, bensì è in uno stato di prerilascio. Il costo campionato è pari a \textbf{37k ns}.\\

Nel secondo caso viene inizialmente elaborato lo stato della CPU e del lock holder, se quest'ultimo non è in esecuzione e la CPU corrente è tra quelle accodate nella FIFO della risorsa si ricorre alla migrazione per cedere l'esecuzione. I campionamenti indicano che la prima parte ha un costo di \textbf{3k ns}. Questo in quanto si necessita di mutua esclusione durante la manipolazione della coda, quindi di acquisire lo spinlock. II costo della migrazione è in linea con gli altri casi in cui il job preso in considerazione è accodato: circa \textbf{6k ns}.\\

Gli overhead campionati che caratterizzano la primitiva di finish-switch affliggono il job mentre detiene la risorsa, quindi i ritardi provocati penalizzano l'intero sistema.

\subsection{Considerazioni}
\label{sec:overhead_cons}

Questo esperimento e gli overhead riportati evidenziano come MrsP abbia un costo relativamente basso nella maggior parte dei casi, cioè quando non vi sono circostanze in cui i vari meccanismi di migrazione entrano in gioco.\\

I strumenti di misurazione permettono di avere un campionamento delle operazioni nella loro interezza, cioè da quando viene effettuata la \textit{system call} a quando si è conclusa. Tali misurazioni hanno evidenziato come le primitive di LOCK e UNLOCK della risorsa comportino un overhead di circa \textbf{2k ns}, di cui solamente \textbf{500 / 800 ns} sono riportabili all'implementazione di MrsP. Questo permette di affermare nuovamente che se non vi sono prerilasci il protocollo ha un impatto relativamente basso sul sistema.\\

% \begin{figure}
% \centering
% \overheadsLock{0.9}{0.9}
% \caption{Lock: overhead.}
% \label{fig:overheadsLock}
% \end{figure}

% \begin{figure}
% \centering
% \overheadsRelease{0.9}{0.9}
% \caption{Release: overhead.}
% \label{fig:overheadsUnlock}
% \end{figure}

% \begin{figure}
% \centering
% \overheadsFS{0.9}{0.9}
% \caption{Finish-switch: overhead.}
% \label{fig:overheadsFS}
% \end{figure}

Considerazioni differenti vanno fatte in caso di prerilascio: l'operazione più onerosa è data dalla migrazione al momento del rilascio della risorsa, essa accade solamente una volta ed il suo overhead rispecchia come si vadano ad accumulare una serie di costi di sistema e relative primitive prima che il job riprenda ad eseguire nella propria CPU.\\

Gli altri meccanismi di migrazione al contrario sono meno onerosi, hanno però lo svantaggio che non si può stimare quante volte verranno innescate nell'arco di una sezione critica dato che dipendono dalle dinamiche del sistema durante l'esecuzione della sezione critica.\\

Le tempistiche campionate sono rappresentate graficamente nel grafico \ref{fig:overheads}, in esso viene tralasciata la migrazione al momento del rilascio in quanto affligge solamente il job che la deve effettuare senza influenzare altri task.\\

  \begin{figure}
    \centering
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\overheadsLock
        \caption{Lock: overhead.}
        \label{fig:overheadsLock}
      \end{subfigure}
      \begin{subfigure}[b]{0.36\textwidth}
        \centering
        \resizebox{\linewidth}{!}\overheadsRelease
        \caption{Release: overhead.}
        \label{fig:overheadsUnlock}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\overheadsFS
        \caption{Finish-switch: overhead.}
        \label{fig:overheadsFS}
      \end{subfigure}
    \caption{Overhead di sistema delle primitive.}
    \label{fig:overheads}
  \end{figure}

Alla luce di queste considerazioni, come accennato in precedenza, MrsP risulta utile in quelle situazioni in cui la somma degli overhead hanno un valore inferiore rispetto all'interferenza che viene causata dai job a priorità superiore, di conseguenza dipende dalla lunghezza della sezione critica. Se tali costi fossero superiori è conveniente un approccio basato sull'inibizione del prerilascio in quanto gli overhead pagati dal sistema sarebbero superiori ai benefici tratti dai job a priorità più alta del ceiling. La tabella~\ref{fig:overheads_riassunto} riassume i costi: il funzionamento di base ha un costo totale di circa 1300 ns (lock e release della risorsa), che quindi indica un tempo sotto il quale non è conveniente l'utilizzo del protocollo; nel caso in cui entrino in gioco i meccanismi descritti (per esempio, operazioni sulle CPU e migrazioni), il costo del protocollo aumenta, ma non è possibile calcolare valore preciso in quanto non abbiamo controllo sulle esecuzioni dei job e, quindi, sul numero di migrazioni necessarie.\\

\begin{table}
  \centering
\begin{tabular}{|l|c|l|}
  \hline
    & 800 ns & operazioni base\\ \cline{2-3}
  Lock & 2k ns & operazioni sulle CPU\\ \cline{2-3}
    & 6k ns & migrazione del job\\
  \hline\hline
    & 500 ns & operazioni base\\ \cline{2-3}
  Release & 2k ns &operazioni sulle CPU\\ \cline{2-3}
    & 6k ns & migrazione del prossimo \textit{lock holder}\\ \cline{2-3}
    & 65k ns & migrazione del job\\
  \hline\hline
    & 24k ns & operazioni sullo stato\\
  Finish-switch & 37k ns & migrazione\\ \cline{2-3}
    & 6k ns & notifica e migrazione \textit{lock holder}\\
  \hline
\end{tabular}
\caption{Riassutno overhead di sistema delle primitive.}
    \label{fig:overheads_riassunto}
\end{table}


\section{Impatto in assenza di risorsa globale}
\label{sec:confronto_norisorsa}

In un sistema real-time la condivisione di risorse globali tra task allocati su differenti CPU è un caso particolare, di conseguenza risulta interessante un confronto tra l'implementazione del protocollo con uno scheduler che non le prevede nell'esecuzione di un taskset in cui i task sono indipendenti.

\subsection{Esperimento \#3}
\label{sec:confronto_norisorsa_exp}

Gli esperimenti discussi in questa sezione pongono a confronto l'implementazione di partenza di \textit{partitioned fixed priority} fornita da LITMUS\textsuperscript{RT} con la versione modificata per integrare MrsP.

\subsection{Configurazione}
\label{sec:confronto_norisorsa_conf}

I taskset sono generati casualmente con alcuni accorgimenti: i periodi sono armonici e variano tra i 25ms ed i 200ms, i tempi di esecuzione sono calcolati con distribuzione di probabilità uniforme tra 0.1 e 0.4 in relazione al periodo, l'esecuzione dell'ultimo task creato viene ridimensionata in base alle esigenze per ottenere un utilizzazione dell'intero taskset pari al valore richiesto. Il problema del \textit{bin-packing} per allocare i task nei processori segue l'euristica \textit{worst-fit}. Infine, ogni esecuzione osservata ha una durata di 15 secondi.\\

Il valore di utilizzazione del taskset è pari alla somma del rapporto tra WCET e periodo di ogni task ed il carico di lavoro di sistema. L'esperimento prevede che i taskset siano creati in modo tale da rispettare una soglia di utilizzazione che varia dal 50\% del carico totale fino al 100\%, nel caso di un sistema composto da 4 processori le soglie saranno 2.0, 2.4, 2.8, 3.0, 3.2, 3.4, 3.6, 4.0.

\subsection{Obiettivo}
\label{sec:confronto_norisorsa_ob}

L'obiettivo è studiare le esecuzioni dei taskset e il comportamento degli scheduler all'aumentare del fattore di utilizzazione. Quello che ci si aspetta è che l'overhead aggiunto dall'integrazione di MrsP non vada ad intaccare il normale svolgimento di \textit{partitioned fixed priority}, ma ad alti livelli di carico del sistema anche i minimi costi possono causare deadline miss che altrimenti non avverrebbero, questo considerando che già il sistema di per sé aggiunge dei ritardi dati dalle singole primitive.\\

%La scelta di incrementare il livello campionamento per carichi vicini all'80\% è data dal comportamento atteso: l'assegnamento della priorità di ogni singolo task è stato effettuato utilizzato la tecnica di \textit{rate monotonic assignment}, di conseguenza possiamo far uso della \textit{utilization-based analysis}, secondo cui un valore di utilizzazione inferiore al 0.69 è condizione sufficiente ma non necessaria per ottenere un taskset schedulabile (Liu et al.~\cite{Liu:1973:SAM:321738.321743}). Di conseguenza se il protocollo aggiunge elevati costi rispetto ad un'implementazione che non lo supporta, ci si aspetta che sia nell'intorno di questa soglia che i due scheduler abbiano comportamenti diversi per quanto riguarda il numero di \textit{deadline miss}.\\

La fase di valutazione rileva un aumento nel numero di \textit{deadline miss} a partire da un rapporto di utilizzazione vicino al 70\%, abbiamo quindi aumentato la frequenza di campionamento per carichi vicini all'80\%. L'obiettivo è di evidenziare un valore di utilizzazione in cui alcuni taskset schedulabili, o con un limitato numero di \textit{deadlin miss}, non lo siano nella versione che prevede task non indipendenti.

\subsection{Risultati esperimento \#3}
\label{sec:confronto_norisorsa_ris}

Dalle esecuzioni sono stati estrapolati diverse informazioni: il numero di deadline miss rappresentato nel grafico \ref{fig:DLM} indica come il comportamento delle due implementazioni sia il medesimo. Nel grafico non sono riportati i dati relativi a workload pari al 90\% ed al 100\% in quanto già al 90\% sei taskset su dieci producono deadline miss su entrambi; essendo i periodi armonici, a ogni "iper-periodo" le stesse "dinamiche" sono ripetute fino alla fine dell'esecuzione, pertanto ci si aspetta un numero molto alto. Di conseguenza, gli overhead degli scheduler non influiscono sui dati rilevati.\\

  \begin{figure}
    \graficoUno
    \caption{Numero di \textit{deadline miss}.} %%Average job release overhead.
    \label{fig:DLM}
  \end{figure}

Le primitive principali utilizzate dal protocollo di accesso sono state discusse in precedenza; l'implementazione di \textit{fixed priority scheduler} in assenza di risorsa condivisa non richiede le operazioni di accesso e rilascio, ergo sono state prese in considerazione l'evento di dispatching, di \textit{context switch} e di \textit{job release}.\\

L'operazione di dispatching ha il compito di decidere a quale job assegnare l'esecuzione nel processore, consiste quindi nel determinare lo stato del job corrente e se necessario prerilasciarlo a favore di quello in testa alla coda dei job pronti all'esecuzione. Tale primitiva è richiamata in molteplici circostanze e il job in coda acquisisce la CPU quando è inutilizzata o ha priorità superiore rispetto a quello in esecuzione. Le figure \ref{fig:schedMin}, \ref{fig:schedMax} e \ref{fig:schedAvg} rappresentano e confrontano rispettivamente costo minimo, massimo e medio della primitiva di dispatching. In tutti e tre i grafici si nota come le due implementazioni abbiano lo stesso comportamento e la differenza tra i valori ottenuti è bassa, soprattutto per quanto riguarda il costo massimo.\\

  \begin{figure}[htb]
    \centering
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoSchedMIN  
        \caption{Costo minimo.}
        \label{fig:schedMin}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoSchedMAX
        \caption{Costo massimo.}
        \label{fig:schedMax}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoSchedAVG
        \caption{Costo medio.}
        \label{fig:schedAvg}
      \end{subfigure}

    \caption{Confronto tra implementazioni: \textit{schedule}.}
    \label{fig:sched}
  \end{figure}

Nei grafici \ref{fig:releaseMin}, \ref{fig:releaseMax} e \ref{fig:releaseAvg} i rilevamenti dell'operazione di release mostrano nuovamente un andamento molto simile tra i due scheduler anche se con valori leggermente differenti. Tali divergenze non sono comunque riportabili all'implementazione in quando tale primitiva non viene modificata, inoltre le normali dinamiche di \textit{partitioned fixed priority} non sono alterate. All'evento di release lo scheduler ha il compito di inserire il job nella coda ready, in questo caso mantenendo l'ordinamento in base alla priorità.\\

  \begin{figure}[htb]
    \centering
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoReleaseMIN  
        \caption{Costo minimo.}
        \label{fig:releaseMin}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoReleaseMAX
        \caption{Costo massimo.}
        \label{fig:releaseMax}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoReleaseAVG
        \caption{Costo medio.}
        \label{fig:releaseAvg}
      \end{subfigure}

    \caption{Confronto tra implementazioni: \textit{job release}.}
    \label{fig:release}
  \end{figure}
        
L'operazione di post-schedule è fondamentale nell'integrazione di MrsP, in essa vengono attuati meccanismi che permettono al job che detiene la risorsa di migrare quando necessario, al contrario in assenza di risorsa essa non ha alcun particolare utilizzo. Il costo minimo, massimo e medio risulta in linea con l'implementazione che non prevede condivisione di risorse: figure \ref{fig:cxsMin}, \ref{fig:cxsMax} e \ref{fig:cxsAvg}.\\

  \begin{figure}[htb]
    \centering
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoCxsMIN  
        \caption{Costo minimo.}
        \label{fig:cxsMin}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoCxsMAX
        \caption{Costo massimo.}
        \label{fig:cxsMax}
      \end{subfigure}
      \begin{subfigure}[b]{0.49\textwidth}
        \centering
        \resizebox{\linewidth}{!}\graficoCxsAVG
        \caption{Costo medio.}
        \label{fig:cxsAvg}
      \end{subfigure}

    \caption{Confronto tra implementazioni: \textit{context switch}.}
    \label{fig:cxs}
  \end{figure}

\subsection{Considerazioni}
\label{sec:confronto_norisorsa_cons}

L'esperimento ha lo scopo di mettere a confronto il medesimo \textit{scheduler} con e senza l'integrazione con \textit{MrsP}.\\

I dati raccolti mostrano come nel caso di assenza di risorse globali non vi sia differenza tra le due, questo è un risultato importante in quanto la condivisione di risorse tra job allocati in diversi processori è un caso particolare e non quello normale. Di conseguenza, possiamo affermare che gli overhead del protocollo di accesso non hanno un impatto sul sistema quando non viene utilizzato.\\