Blame |
Last modification |
View Log
| RSS feed
\documentclass[12pt]{article}
\usepackage[italian]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{graphicx}
\author{Luigi Panzeri}
\title{Protocollo Highest Locker Priority per S.Ha.R.K.}
\begin{document}
\tableofcontents
\section{Introduzione}
L'implementazione per \emph{S.Ha.R.K.}, che realizza il protocollo di
accesso a risorse condivise \emph{Highest Locker Priority} \'e stata
realizzata come modulo di accesso alle risorse, partendo dal codice
del modulo del \emph{Stack Resource Policy}. Il lavoro prodotto ha
cercato, quindi, di non tradire la filosofia modulare con la quale \'e
stato scritto S.Ha.R.K, e le convenzioni usate nell'interfaccia verso
il codice utente e nello stile del codice stesso del modulo.
\newline
La seconda parte del lavoro ha prodotto una demo che disegna la
temporizzazione di $n$ task che condividono fino a 3 mutex utilizzando
HLP. Il task set e la sequenza di accesso \`e configurabile da
file. Con poche modifiche \'e possibile usare la demo anche per test o
simulazioni per altri protocolli.
\subsection{Logica di riferimento: HLP}
Il protocollo HLP stabilisce che la priorit\'a di esecuzione di un
processo $J_i$ che usa una risorsa $R$ viene innalzata ad un livello
$p_i$ tale che esso non possa subire preemption dai processi che
condividono quella stessa risorsa. Ovvero viene stabilito il Non
preemptive protocol solo tra i task che condividono una stessa
risorsa.
In S.Ha.R.K., per permettere indipendenza e separazione tra i vari
moduli, c\'e una netta separazione tra i moduli che gestiscono lo
scheduling (\emph{Scheduling Module}), e quelli che gestiscono
l'accesso alle risorse condivise (\emph{Resource Module}). Per questo
motivo, i moduli che gestiscono le risorse condivise (mutex, semafori,
etc.), non conoscono i dettagli algoritmici dei moduli di scheduling e
non possono quindi intervenire su parametri quali le priorit\'a dei
processi.
Per permettere ad un \emph{Resource Module} di modificare la
schedulazione dei task, si utilizza il meccanismo degli
\emph{shadows}. Ogni task ha associato un puntatore ad un altro task
(chiamato appunto shadow). Quando un task viene schedulato, viene
eseguito non il task stesso, ma il suo shadow. In una situazione
normale ogni task ha come shadow se stesso. Un Resource Module pu\'o
quindi intervenire sugli shadow per modificare,
\textbf{indipendentemente} dal modulo (o moduli) di scheduling
adottato, la schedulazione dei task.
\section{Interfaccia per l'utente}
L'interfaccia per l'utente segue la linea del SRP. Per creare un
mutex, in fase di inizializzazione esiste il tipo $HLP\_mutexattr\_t$ e
la macro $HLP\_mutexattr\_default$.
\newline
Per la creazione dei task e la registrazione dei mutex esistono le strutture $HLP\_RES\_MODEL$ e le macro $HLP\_res\_default\_model$ e $HLP\_usemutex$. La seconda accetta come secondo parametro il livello di preemption del task(nella demo impostato inversamente proporzionale al periodo). L'ultima si fa carico della registrazione del mutex nella $task\_createn$.
\section{Internals}
\subsection{La gestione degli shadow per l'HLP}
Le strutture dati usate per gestire gli shadow sono due liste,
rispettivamente, di task ($tasklist$) e di mutex($mutexlist$)
ortogonali. Ogni elemento della lista dei task(mutex) \`e una lista
dei mutex(task) che vengono utilizzati(utilizzano) dal task(mutex). Le
liste dei task sono ordinate per livelli di preemption (i quali
possono essere assegnati in maniera inversamente proporzionale al
periodo per avere un comportamento classico HLP+RM).
\subsubsection{Il lock}
Quando viene effettuato un lock (callback $HLP\_lock$), semplicemente
faccio puntare lo shadow dei processi che usano lo stesso lock e che
hanno preemption level maggiore al processo bloccante. In tal modo,
anche se scelti dallo scheduler, verr\'a eseguito il task che ha
bloccato la risorsa. L'effetto finale \`e che il task bloccante non
pu\'o subire preemption da task che usano la stessa risorsa. Nel
codice $current$ \`e il task che ha chiesto il lock. La lista su cui
si scorre \`e quella dei task che usano il mutex in questione.
\begin{verbatim}
for (taskscan = current->prev; taskscan != NULL; taskscan = taskscan->prev)
proc_table[taskscan->pid].shadow = exec_shadow;
\end{verbatim}
\subsubsection{L'unlock}
L'unlock \`e la fase meno semplice, in quanto in caso di accessi
annidati, perdiamo l'informazione dell'ultima shadow salvata. \`E
quindi indispensabile ricalcolare completamente lo shadow per i
tutti i processi che subiscono l'unshadowing.
\begin{verbatim}
/* ciclo sui processi a preemption level maggiore */
for (taskscan = current->prev; taskscan; taskscan = taskscan->prev) {
/* task influenzato, ha bisogno di un ricalcolo dello shadow */
if (proc_table[taskscan->pid].shadow == exec_shadow &&
taskscan->pid != current->pid) {
proc_table[taskscan->pid].shadow = taskscan->pid;
for (mutscan = taskscan->mutexlist; mutscan; mutscan = mutscan->next) {
if (mutscan->owner != NIL) {
taskowner = HLP_tasklist_with_pid(mutscan->tasklist, mutscan->owner);
if (taskowner->preempt <= taskscan->preempt)
proc_table[taskscan->pid].shadow = mutscan->owner;
}
}
}
}
\end{verbatim}
\subsection{Eccezioni}
Il modulo lavora sotto l'ipotesi che le risorse siano singole. \'E
possibile innestare i lock dei mutex (senza intersezioni), avere pi\'u
di una risorsa bloccata. In caso di comportamenti anomali (es. un task
termina prima di sbloccare tutti i suoi mutex, oppure un task cerca di
accedere ad una risorsa gi\'a occupata) viene sollevata un'eccezione.
\section{Demo}
La demo \`e fornita in versione testuale e versione grafica. La
configurazione del taskset viene specificata nel file hlp.cfg con la
sintassi:
\begin{verbatim}
task T1 every 10 runs 15
locks m1 runs 12 unlocks m1
runs 13
task T2 every 20 runs 20
etc...
\end{verbatim}
Dove T1, T2 e m2 sono nomi arbitrari da dare ai task ed alle risorse. Il numero di task
\`e limitato dall'altezza dello schermo. Il numero dei mutex utilizzati dai task \`e limitato a 3, a causa dei limiti della task\_createn.
Al termine della demo, viene salvato un file ppm rappresentante la temporizzazione. Es.:
\begin{figure}
\includegraphics[angle=90]{tutto}
\caption{Snapshot totale della temporizzazione}
\end{figure}
\begin{figure}
\includegraphics[scale=2]{hlp}
\caption{Zoom che evidenzia il funzionamento dell'Highest Locker Priority}
\end{figure}
\section{Files}
Per compilare il tutto bisogna tener presente che i file
\begin{enumerate}
\item hlpgraph.c
\item hlpparse.c
\item hlptext.c
\item hlpdemo.h
\item hlptxtin.c
\item hlpgrxin.c
\end{enumerate}
sono stati pensati per essere compilati nella directory demos/base, con i flag di compilazione per la gestione del Frame Buffer.
\end{document}