Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | perlita-zani |
View: | 214 times |
Download: | 0 times |
Università degli Studi di Parma
Corso di laurea in Ingegneria Informatica
A.A. 2004 - 2005
Dario Lodi Rizzini
Sistemi in tempo reale
1
TODS: ANALISI ED ESTENSIONE DI UN FRAMEWORK ORIENTATO AGLI OGGETTI
PER APPLICAZIONI REAL-TIME
Docente:
Prof. Stefano Caselli
2Dario Lodi Rizzini
Sommario
• Introduzione a TODS• Estensioni a TODS: implementazione di Rate Monotonic• Valutazione delle prestazioni • Conclusioni
3Dario Lodi Rizzini
Introduzione
• TODS (Timed Object for Distributed Systems) è un framework orientato agli oggetti per le applicazioni real time.
• Consente la creazione di oggetti in tempo reale demandando le funzionalità di scheduling e della verifica dei vincoli temporali al framework.
• Semplifica l’introduzione di nuovi algoritmi di scheduling.
4Dario Lodi Rizzini
Struttura di TODS
TODS Layer
DisC++ Thread Layer
POSIX Thread
Glibc Linux
TODS Framework
OSLinux Thread
TODS è organizzato in due strati: • TODS layer: implementa le funzionalità real time in senso stretto• Thread layer: libreria ad oggetti per la programmazione concorrente basata su DisC++
Il Thread layer di TODS dovrebbe impiegare soltanto POSIX Thread.
In verità sfrutta direttamente funzionalità della libreria Linux Thread che gradualmente verrà sostituita dalla NPTL.
5Dario Lodi Rizzini
• Esempio di applicazione in tempo reale usando gli RTObject di TODS
#include <tods.H>
using namespace tods;
class myRTobj : public RTObject { protected: // the body of the RT method void body( /* void */){ ... // the code that performs task } public: RTMethod< myRTobj, void, void > method;
// ctor myRTobj( shared_ptr< RequestManager > rm ) : RTObject( rm ), method( this, &( myRTobj::body ) ) {}};
Livello utente (1)
RTMethod usa i template
Riferimento a body()
6Dario Lodi Rizzini
…
try { const string algo = "Edf_OnOff_Conf"; vector< string > par( 1 ); par[0] = string( "1.0" ); auto_ptr< RequestManager > tmprm = RTFactory::create( algo, par ); shared_ptr< RequestManager > rm( tmprm ); myRTobj rtObj( rm ); ... const TimeInterval t( 0, 100000000 );
// one-shot request rtObj.method( t );
// periodic request: PeriodicReqHandle< void > h1 = rtObj.method( t, callType::periodic ); … h1.terminate();}catch ( /* evcezione*/ ) { …}
Livello utente (2)
Algoritmo e parametri
Creazione dell’executive
dealine
Rilascio di task one shot e periodici (method è un oggetto funzione)
Terminazione task periodici
7Dario Lodi Rizzini
Livello utente (3)
• Gli oggetti in tempo reale sono istanze di classi che ereditano dalla classe RTObject e hanno un RTMethod, ossia un oggetto funzione che gestisce il rilascio, come membro pubblico.
• Gli algoritmi di scheduling supportati da TODS sono di tipo priority driven (solo EDF è stato implementato). La classe RTFactory ha in compito di caricare l’algoritmo da uno shared object e di fornire all’Executive i riferimenti di Accepter e Scheduler.
8Dario Lodi Rizzini
Livello utente (4)
• L’Executive eredita l’interfaccia RequestManager.• Il rilascio di un task può essere di tipo periodic o one
shot.• Nel caso di task one shot si possono specificare
deadline assolute con la classe TimeInstant o relative con la classe TimeInterval.
• L’utente non si occupa di parametri come il worst case execution time (WCET) o del test di acceptance: in caso di fallimento viene infatti lanciata una eccezione not_feasible_task.
9Dario Lodi Rizzini
Implementazione di RM (1)
• Lo sviluppo di TODS è orientato all’adozione di Earliest Deadline First (EDF) come algoritmo di scheduling.
• L’implementazione di Rate Monotonic (RM) evidenzia la semplicità con cui è possibile introdurre nuovi algoritmi di scheduling.
• Le modiche richieste sono state relativamente poche– estensione di alcune interfaccce (classi Job e derivate)
– alcune classi sono state reimplementate per supportare policies (es: JobQueue che gestisce la coda dei job)
10Dario Lodi Rizzini
Implementazione di RM (2)
• Sono state fatte alcune scelte di progetto che limitano l’uso di RM– Si è deciso di gestire solo task periodici; sono possibili
estensioni per gestire anche task one shot come il polling server o il deferrable server.
– Non è stato consentito il partizionamento dell’utilizazzione della CPU supportato dalla implementazione di EDF.
• il bound di Liu-Layland restringe molto l’ammissibilità di un nuovo task
11Dario Lodi Rizzini
Class Diagram
<<interface>>Scheduler <<Interface>>
Accepter<<interface>>ReqObserver
RMAccepter
eredita
RMScheduler
eredita
<<template>>
Servant
<<template>>JobQueue
<<interface>>Job
notify
<<interface>>RequestManager
Executive
eredita
RTObject
usa
usa
<<interface>>
Request
12Dario Lodi Rizzini
Le classi di RM (1)
• Rm_OnOff_Conf : classe di configurazione dell’algoritmo RM con il compito di fornire al RequestManager l’accepter e lo scheduler di RM– implementa l’interfaccia RTConfiguration
• RMAccepter : implementa le interfacce Accepter e ReqObserver– implementa una variazione del normale pattern Observer per consentire
allo Scheduler di notificare all’Accepter il rilascio o la terminazione di task
– verifica l’ammissibilità dei task rilasciati → metodo isFeasible()
– isFeasible() per i task one shot restituisce sempre il valore false
13Dario Lodi Rizzini
Le classi di RM (2)
• RMScheduler : implementa l’interfaccia Scheduler – presenta differenze rispetto a EDFSceduler che adotta soluzioni per
gestire il partizionamento dell’utilizzazione della CPU
– accoglie le richieste (precedentemente validate) attraverso il metodo addReq()
– usa istanze di JobQueue e Servant, le classi che di fatto realizzano l’algoritmo RM, specificando la policy RMCompareJob che ordina i job rispetto al periodo
• JobQueue : eredita dalla classe STL list <Job> – è una classe template per consentire di definire la politica di
ordinamento della coda
– riordina anche le priorità del thread pool sulla base dell’ordinamento dei Job
14Dario Lodi Rizzini
Le classi RM (3)
• Servant : è una classe di collegamento con il Thread Layer di TODS– possiede un thread a priorità massima che viene risvegliato quando un
nuovo job entra nella coda oppure è scaduta una deadline; per il tempo restante rimane in attesa su di una condition variable
– possiede un thread pool che vengono assgnati ai job della coda
– è una classe template per poter contenere un riferimento a JobQueue che è a sua volta template
15Dario Lodi Rizzini
Valutazione delle prestazioni
• Uno dei principali obiettivi del progetto è valutare le prestazioni del framework ed in particolare l’overhead introdotto da TODS
• I test effettuati prevedono tre tipi di stime:– valutazione dell’overhead complessivo al momento del rilascio di
un task
– valutazione dei contributi specifici di Executive e Accepter
– valutazione della latenza
• I test principalmente hanno interessato il consolidato algortimo EDF
16Dario Lodi Rizzini
Overhead complessivo
• Test: un task τ0 rilascia altri task con deadline successiva per ritardare la loro esecuzione.
• Risultati: – nei primi 20 rilasci il valore dell’overhead assume valori di
2-3 ms, particolarmente elevati rispetto alle dimensioni dei task
– le successive misure si assestano intorno ai 200-300 μs
…τ0
overhead overhead
17Dario Lodi Rizzini
Overhead di Accepter e Scheduler
• Nel codice dell’executive sono state inseriti dei timer per rilevare l’overhead di Accepter e Scheduler.
• I valori ottenuti sono significativamente molto ridotti, dell’ordine di delle decine di microsecondi
EDF RM
Accepter 24.1 μs 307.1 μs*
Scheduler 13.6 μs 27.8 μs*
18Dario Lodi Rizzini
Misure di latenza
• Output del test di latenza latency test n. 0 : measure 3.1585
latency test n. 1 : measure 0.222632latency test n. 2 : measure 0.172539latency test n. 3 : measure 0.178615latency test n. 4 : measure 0.171721latency test n. 5 : measure 0.179257latency test n. 6 : measure 0.179567latency test n. 7 : measure 0.17923latency test n. 8 : measure 0.172881latency test n. 9 : measure 0.179821…
• Il primo valore è normalmente di 3 ms, gli altri variano fra 170-180 μs.
Ck start() Ck.stop()
myRTObj.method()
19Dario Lodi Rizzini
Osservazioni
• I test mettono in evidenza la presenza di valori di overhead abbastanza elevati in relazione alle primi rilasci di job.
• L’ipotesi più ragionevole è che l’overhead iniziale dipenda dall’inizalizzazione del thread pool– il thread pool ha dimensione di default di 20 thread– nel test di latenza viene creato un unico thread ed il valore
elevato si presenta solo in un caso
20Dario Lodi Rizzini
Conclusioni
• È stata implementata una prima versione dell’algoritmo RM. – Sviluppi futuri possono prevedere l’introduzione di un server periodico
per la gestione di task one shot
• L’analisi delle prestazioni ha messo in evidenza ulteriori limiti del Thread layer di TODS– È incompatibile con la Native POSIX Threading Libary (NPTL)
– Bug nelle implementazioni di oggetti thread sono la probabile causa degli overhead segnalati
21Dario Lodi Rizzini
Bibliografia
• Pallastrelli D., Studio e realizzazione di un framework orientato agli oggetti per applicazioni Real-Time, tesi di laurea.
• Gamma, Helm et al., Design Pattern, Addison-Wesley• Alexandrescu A., Modern C++ Design
Per futuri sviluppi di RM:
• Strosnider, Lehoczky, Sha, The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Envirinments, IEEE Trans. on Computers, Jan. 1995