Capitolo 2: Sviluppi attuali sui sistemi operativi real-time
2.1 FUNZIONALITA' E CARATTERISTICHE DEI SISTEMI REAL-TIME
2.1.1 I primi sistemi real-time.
2.1.2 Predicibilità nei sistemi real-time.
2.1.3 Sistemi complessi.
2.2.1 Algoritmi di scheduling tradizionali
2.2.2 Scheduler per Sistemi Real-Time Multiprocessore e Distribuiti
2.2.3 Prospettive future
2.3 SINCRONIZZAZIONE NEI SISTEMI REAL-TIME
In questa parte descriveremo alcuni degli attuali sviluppi nelle ricerche sui sistemi operativi real-time. Vedremo prima di tutto un sommario dei risultati più importanti per quanto riguarda lo scheduling e la sincronizzazione, due aspetti fondamentali in questi sistemi. Descriveremo i sistemi operativi real-time mediante le primitive e i costrutti offerti ai programmi applicativi. Inoltre parleremo anche degli effetti che la sottostante architettura del calcolatore ha sui sistemi operativi real-time.
2.1 FUNZIONALITA' E CARATTERISTICHE DEI SISTEMI REAL-TIME
L'hardware dei calcolatori embedded nei moderni sistemi di controllo industriali è diventato sempre più complesso. Esso tipicamente consiste di molti calcolatori interconnessi che operano a diversi livelli di controllo oppure supervisionano diversi sistemi periferici, meccanici o elettronici. L'esecuzione efficiente di una applicazione real-time richiede ai programmatori di affrontare problemi come la gestione efficiente delle risorse, lo scheduling e la comunicazione tra diversi task, il load balancing, ecc. Perciò, così come nei sistemi operativi paralleli e distribuiti, un sistema operativo real-time deve fornire ai programmatori delle primitive per il controllo dei task, la comunicazione fra i processi, la gestione delle periferiche, ecc.
Tuttavia, i sistemi operativi usati in questo contesto devono anche offrire un supporto specifico dei sistemi real-time . Naturalmente è su questo supporto che concentreremo le nostre attenzioni.
Vedremo quindi i principi fondamentali ed anche alcuni esempi concreti di sistemi operativi per applicazioni real-time, soprattutto con riferimento alla ricerca, più che ai sistemi industriali effettivamente utilizzati.
2.1.1 I primi sistemi real-time
.I primi lavori sui sistemi operativi real-time si focalizzarono sulle esigenze di singoli sistemi embedded, ad esempio nel controllo di volo o nei sistemi di produzione. Gran parte di tale lavoro riguardò la costruzione di kernel di sistemi operativi per specifiche applicazioni e piattaforme architetturali. Due esempi significativi delle funzionalità tipiche offerte da tali sistemi sono dati dagli sforzi di definire un sistema real-time standard basato sul sistema Unix negli Stati Uniti (lo standard POSIX 1003.4) e da un analogo tentativo in Giappone (TRON).
Le funzioni real-time in POSIX 1003.4 comprendono:
Altre caratteristiche generali di un kernel real-time includono una dimensione che può essere adeguata alle diverse esigenze dell'applicazione, multitasking con basso overhead dovuto ai cambiamenti di contesto, una veloce risposta agli interrupt esterni, un uso limitato o anche assenza di memoria virtuale, un supporto ai vincoli temporali sui task come ad esempio lo scheduling con priorità, un supporto ai real-time clock, gestione di speciali allarmi e time-out.
2.1.2 Predicibilità nei sistemi real-time
.La funzionalità real-time offerta da POSIX e TRON consiste nella capacità di gestire le risorse di sistema in un modo dipendente dal tempo. Ciò significa che mentre i sistemi operativi tradizionali tentano di assicurare una allocazione efficiente ed equa delle risorse a diversi programmi applicativi, i sistemi operativi real-time devono assicurare che una tale allocazione sia fatta tenendo conto dei vincoli temporali. Quindi ciò comporta due proprietà fondamentali per tali sistemi :
Il termine che sintetizza queste due esigenze è predicibilità.
La predicibilità implica anche che le metriche con le quali i sistemi real-time sono valutati differiscono da quelle usate per sistemi non-real-time.
Ad esempio per implementazioni Unix su workstation si fa riferimento alle performance medie delle sue primitive di sistema, mentre un'importante metrica in una versione real-time di Unix è che la performance di una primitiva non degrada al di sotto di una certa soglia accettabile.
Bisogna anche dire che la predicibilità desiderata di un sistema non è facile da misurare e da valutare, anche perché le richieste temporali dei programmi applicativi possono essere molto diverse (deadline garantite o hard che non possono essere superate, se non con danni catastrofici al sistema; soft deadline che possono essere occasionalmente superate; deadline recuperabili che, se superate, forzano azioni di recupero programmate; deadline deboli, che specificano che risultati parziali o incompleti sono comunque accettabili, quando la deadline è superata. Perciò, in questo caso, spendere più tempo su certe computazioni può essere utile perché fornisce risultati migliori anche se con il rischio di possibili violazioni temporali.).
I sistemi real-time possono essere classificati usando i seguenti parametri:
La granularità e la laxity determinano congiuntamente le lunghezze dei task e la quantità di tempo disponibile per prendere decisioni di scheduling.
Per un sistema con basse granularità dei task ( che spesso coincidono con basse laxity dei task) decisioni di scheduling veloci ed efficienti possono essere più appropriate rispetto ad altre ottime ma più lente.
Con il termine strictness delle deadline si fa riferimento alle semantiche temporali, come ad esempio hard vs. soft deadline, e il termine determina l'utilità di continuare ad eseguire un task anche dopo che si è superata la sua deadline. Chiaramente, le definizioni di predicibilità di un sistema devono tener presenti queste semantiche, e varieranno con le specifiche del particolare sistema. In questo contesto, l'affidabilità ( reliability ) di un sistema può essere definita come la capacità del sistema di eseguire task critici all'interno dei loro vincoli temporali. L'ambiente operativo del sistema determina il grado con cui il sistema si confronta con fenomeni dinamici, come ad esempio cambiamenti nella modalità di funzionamento in risposta a drastici cambiamenti ambientali ( per esempio dalla modalità walking alla modalità running in un robot).
.
Mentre buona parte dei primi lavori nei sistemi operativi real-time si focalizzarono su architetture e applicazioni embedded, i sistemi e le applicazioni attuali stanno diventando sempre più ampie e complesse. Esempi possono essere sistemi di controllo di tutto il traffico aereo, sistemi di gestione di teatri di guerra single-site o multi-site, sistemi di diversi robot autonomi e cooperanti, simulazioni distribuite e real-time, e comunicazioni real-time in sistemi informativi su larga scala e distribuiti.
La complessità di tali sistemi richiede diverse caratteristiche essenziali e nuove dai moderni sistemi real-time:
Vediamo ora alcuni risultati nel real-time scheduling. Questa è un'area dall'importanza critica nei sistemi operativi real-time. Vedremo successivamente la sincronizzazione nei sistemi real-time e poi descriveremo le caratteristiche salienti di sistemi operativi real-time sperimentali costruiti negli ultimi anni.
Un grande passo in avanti fatto negli ultimi anni è stato il passaggio da uno scheduling statico (off-line) ad uno scheduling dinamico (on-line). Vedremo solo una breve panoramica dei più conosciuti metodi di scheduling statico, seguita da una discussione più estesa sullo scheduling dinamico.
Tutto il lavoro presentato usa le stesse misure di "successo" e "qualità" degli algoritmi di real-time scheduling:
2.2.1 Algoritmi di scheduling tradizionali
Algoritmi. I primi lavori si sono focalizzati su sistemi real-time relativamente di piccola scala o statici, dove i tempi di esecuzione del task possono essere stimati prima dell'esecuzione del task (cioè le dipendenze dai dati sono limitate), e dove lo scheduler lavora off-line. Gli algoritmi riguardano sia task periodici che task sporadici; i task periodici sorgono tipicamente da dati provenienti da sensori e cicli di controllo, e i task sporadici possono sorgere da eventi inaspettati causati dall'ambiente o da azioni dell'operatore. Un algoritmo di scheduling opera congiuntamente su tutti i task periodici e sporadici in modo tale che le loro richieste temporali siano soddisfatte.
I metodi statici più comunemente usati sono schedulers ciclici e gli algoritmi di scheduling Rate Monotonic (RM), in parte perché essi sono facilmente mappati su scheduler di basso livello priority-based. L'idea base dell'algoritmo rate monotonic è di assegnare diverse e fisse priorità a task con tassi di esecuzione diversi, assegnando la priorità più alta ai task con le frequenze più alte, la priorità più bassa ai task con le frequenze più basse.
Ad ogni modo, lo scheduler di basso livello semplicemente sceglie di eseguire il task con priorità più alta. Specificando il periodo e il massimo tempo di computazione di ciascun task, il comportamento del sistema può essere definito a priori.
Gli algoritmi RM (e gli algoritmi a priorità statica) possono schedulare un insieme di task in modo tale da rispettare le loro deadline se il fattore di utilizzazione totale è minore di un certo schedulable bound.
Questo bound può essere minore del 100%. Esso vale 0.693 per gli algoritmi RM in generale (con dimensione dell'insieme dei task tendente all'infinito), 0.88 quando i periodi sono uniformemente distribuiti e 1.0 solo quando i periodi sono multipli del periodo più piccolo.
L'algoritmo Extended Priority Exchange utilizza il tempo inutilizzato concesso ai task periodici per una migliore risposta aperiodica, e l'algoritmo Sporadic Server crea un "server" task con un dato periodo e utilizzazione. Tutti gli aperiodici soft-deadline usano un singolo server sporadico, mentre ogni aperiodico hard-deadline usa un server distinto. Questo approccio raggiunge lo scopo di rispettare le deadline dei periodici e degli aperiodici hard-deadline, minimizzando il tempo di risposta per gli aperiodici soft-deadline.
Oltre al fatto che gli schedulable bounds sono minori di 1.0, ci sono altri due problemi per gli algoritmi RM:
Il primo problema è stato studiato considerando uno scheduling a priorità fissa dei task periodici con priorità di esecuzione dei task variabile. Specificamente, i task possono avere sottotask di varie priorità. Il metodo presentato per determinare la schedulabilità dei task richiede di identificare un istante critico per il task periodico analizzando il suo sfasamento peggiore rispetto agli altri task, la priorità di ciascun task rispetto alle priorità dei sottotask degli altri task (per trovare il numero di sottotask la cui schedulabilità deve essere controllata), e controllare il completamento di ciascuno di tali sottotask. Un istante critico per un task è l'istante di attivazione del task che comporta il tempo di completamento maggiore.
L'inversione della priorità nasce quando un job ad alta priorità deve aspettare che venga eseguito un job a priorità più bassa, tipicamente dovuto al fatto che altre risorse sono usate da task in esecuzione. Alcuni autori hanno considerato la natura delle regioni critiche non interrompibili che originano tali inversioni di priorità nel contesto di un sistema operativo soft real-time, dove il tempo di risposta medio per differenti classi di priorità è la metrica primaria della performance. Viene usato un modello analitico per illustrare come le regioni critiche non interrompibili possono influenzare i job temporalmente vincolati in un insieme di task multi-media (soft real-time).
Gli algoritmi di scheduling Earliest Deadline First (EDF) possono essere usati per un real-time scheduling sia dinamico che statico. Questi algoritmi usano la deadline di un task come sua priorità. Dal momento che il task con la deadline più vicina ha la priorità più alta, le priorità risultanti sono naturalmente dinamiche e i periodi dei task (rappresentati dalle loro deadline) possono essere cambiati in ogni istante. Una variante dello scheduling EDF è lo scheduling Minimum Laxity First (MLF), dove una laxity è assegnata a ciascun task nel sistema, e i task con la laxity minima sono eseguiti per primi.
La laxity misura l'ammontare del tempo rimanente prima della deadline del task se il task usa il tempo di esecuzione massimo assegnatogli. Essenzialmente, la laxity è una misura della flessibilità disponibile per schedulare un task. La principale differenza tra MLF e EDF è che, a differenza di EDF, MLF tiene conto del tempo di esecuzione di un task.
Mentre EDF è superiore a RM nel senso che il suo schedulable bound è pari al 100% per tutti gli insiemi di task, un problema dell'EDF è che non c'è modo di garantire quali task falliranno in situazioni transitorie di overload. Per risolvere questo problema è stata introdotta un'altra variante dell'EDF, l'algoritmo di scheduling Maximum Urgency First (MUF), in cui ad ogni task è assegnata un'esplicita descrizione di urgenza. Questa urgenza è definita come la combinazione di due priorità fisse e una priorità dinamica, che è inversamente proporzionale alla laxity del task. Una delle priorità fisse, chiamata "criticità del task", ha la precedenza sulla priorità dinamica del task. L'altra priorità fissa, chiamata "priorità d'utente", ha minor precedenza rispetto alla priorità dinamica del task. L'idea è quella di usare nozioni di priorità specificate dagli utenti per aiutare gli algoritmi on-line a distinguere i task più importanti da quelli meno importanti.
Gli algoritmi EDF sono stati anche estesi per risorse diverse dalla CPU. E' stato proposto un algoritmo ottimo per schedulare un insieme di task sporadici che condividono un insieme di risorse riusabili serialmente in modo tale che i task completino la loro esecuzione prima di una deadline, e che alle risorse si faccia accesso sequenzialmente. L'algoritmo combina lo scheduling EDF con uno schema di sincronizzazione per accedere a risorse condivise.
Effetti del Cycle-Stealing e degli Overload sugli algoritmi di scheduling. Sono stati studiati gli effetti del cycle-stealing sugli algoritmi di scheduling in un ambiente hard real-time. Specificatamente, dal momento che un dispositivo di input/output può trasferire dati attraverso accesso diretto alla memoria (DMA) e quindi rubare cicli al processore e al task correntemente in esecuzione, tale fenomeno di cycle-stealing può causare ritardi impredicibili e portare a superare le deadline dei task (anche per bassi gradi di utilizzazione del processore). Inoltre i dispositivi di input/output sono spesso progettati in modo tale che il solo modo possibile di schedulare le attività di input/output è quello FIFO. Di conseguenza i benefici di un real-time CPU-scheduling "intelligente" possono essere compromessi da un inappropriato I/O scheduling. E' stato proposto un rimedio che consiste di due passi:
Sono stati ottenuti dei risultati di schedulabilità teorica in condizioni di overload del sistema, ed è stato presentato un algoritmo di scheduling on-line ottimo capace di operare in sistemi overloaded. Inoltre è stato trovato un bound intrinseco alle prestazioni che uno scheduler on-line multiprocessore è in grado di fornire, e presentato un algoritmo che raggiunge nel caso peggiore delle prestazioni che si distanziano di un piccolo fattore da questo bound.
Altri autori hanno studiato le semantiche di applicazioni real-time data-intensive. Esaminando le semantiche di queste applicazioni, è stato introdotto il concetto di "similarità", che è stato utilizzato dai progettisti delle applicazioni per ottenere più flessibilità nel controllo di concorrenza. E' stato proposto un efficiente algoritmo di real-time scheduling sfruttando tale similarità.
Infine altri autori hanno mostrato che nessun algoritmo di scheduling on-line può garantire una performance maggiore di un quarto di quella di uno scheduler off-line, ed hanno presentato un algoritmo monoprocessore che lavora con questa performance. Generalizzando al caso con due processori, gli autori hanno dimostrato che nessun algoritmo on-line può garantire una performance migliore della metà di quella di un algoritmo off-line.
Valutazione degli algoritmi. Sono stati molto studiati gli algoritmi di scheduling real-time sia preemptive sia non-preemptive. E' stato dimostrato che gli algoritmi di scheduling rate-monotonic e earliest deadline sono algoritmi ottimi in un ambiente monoprocessore. Anche l'algoritmo slack-time è ottimo.
Uno scheduler runtime per ambienti hard real-time viene definito ottimo se è in grado di rispettare tutte le deadline dei task, posto che un tale algoritmo esista. E' stato mostrato che non può essere trovato uno scheduler ottimo per multiprocessori senza una conoscenza a priori delle deadline, tempi di computazione e tempi di arrivo di tutti i task. A dire il vero, è stato mostrato che anche per un processore singolo costruire uno schedule ottimo per task con tempi di arrivo e di computazione arbitrari e laxity arbitraria è un problema NP-completo.
Sono stati fatti studi di performance di vari classici algoritmi di scheduling considerando situazioni in cui i tempi di computazione non sono esattamente noti al tempo di arrivo del task, ma hanno una data e nota distribuzione. Tali studi introducono la nozione di value function che specifica il valore del completamento di un task ad ogni istante dopo l'arrivo, tentando di unificare il trattamento di ambienti hard e soft real-time. L'idea è quella che i task con value function che diventano negative mentre sono in attesa o durante l'esecuzione sono abortiti o scaricati dalla coda dei task. I migliori algoritmi in termini di massimizzazione del valore dei task per multiprocessore completati prendono in considerazione il valore atteso di un task al suo completamento. Questo valore è la probabilità che un task sia completato prima del suo tempo critico o deadline. Tali studi però non indicano in che modo possano essere trovate opportune value function per problemi di scheduling pratici.
Computazioni imprecise. Recenti lavori nello scheduling real-time hanno cominciato a considerare la possibilità di usare nei sistemi attuali dei cambiamenti nelle semantiche dei vincoli temporali. Sono state avanzate diverse formulazioni specifiche riguardo alle "computazioni imprecise".
L'idea base è che ci sono alcuni algoritmi (ad esempio quelli iterativi), che possono fornire dei risultati in quasi ogni istante della loro esecuzione. Più a lungo vengono eseguiti, più precisi sono i loro risultati. Idealmente, un processo dovrebbe essere eseguito fino a che non é prodotto un risultato con una tolleranza piccola a piacere. Tuttavia, quando il tempo a disposizione è limitato, il processo può essere terminato prematuramente, fornendo un risultato che può essere accettabile ma non preciso quanto desiderato.
Alcuni autori hanno discusso una formulazione di questo problema ed alcuni algoritmi che tengono in considerazione la qualità del risultato complessivo. In un altro lavoro sono stati descritti tre algoritmi per il preemptive scheduling di task imprecisi su un processore in modo tale da minimizzare l'errore totale. Ciascun task impreciso è costituito da una mandatory seguita da una porzione opzionale, e alcuni dei task possono arrivare dopo che il processore ha cominciato l'esecuzione. Gli algoritmi assumono che quando ciascun nuovo on-line task arriva, la sua porzione mandatory e tutte le porzioni mandatory di tutti i task che devono essere ancora completati al momento possono essere schedulati prima delle loro deadline. Gli algoritmi producono per tali task degli schedule i cui errori totali sono minimizzati. Sono presentati tre algoritmi per tre tipi di sistemi di task:
Recenti ricerche su algoritmi anytime, applicate alla robotica real-time, non assumono porzioni di task mandatory. Come altre ricerche nei robot autonomi, i ricercatori assumono invece l'esistenza di task o insiemi di task alternativi (per esempio task gestori delle eccezioni) da usare quando le deadline dei task originali non possono essere rispettate.
2.2.2 Scheduler per Sistemi Real-Time Multiprocessore e Distribuiti
Scheduling multiprocessore. Dal momento che i progettisti di sistemi embedded si stanno sempre più orientando verso architetture multiprocessore (per ragioni di affidabilità e/o performance), gli algoritmi di scheduling e i progetti degli scheduler hanno cominciato ad indirizzarsi verso piattaforme di esecuzione parallele, tipicamente assumendo arrivi dei task dinamici e scheduling on-line sia per task sporadici sia per task periodici. Un efficiente algoritmo on-line multiprocessore è l'algoritmo proposto da Blake e Schwan, che offre un'implementazione di uno scheduler distribuito che consiste di scheduler globali che realizzano l'assegnamento dei task ai processori in cooperazione con scheduler locali che eseguono il deadline scheduling.
La qualità dello scheduling on-line è determinata non solo dagli algoritmi implementati dagli scheduler, ma anche dall'efficienza dello scheduler parallelo ( e le sue strutture dati) che implementa quegli algoritmi. Vi sono due problemi che riguardano la performance degli scheduler multiprocessore:
E' stato presentato un algoritmo di scheduling real-time per multiprocessori che è scalabile nel numero di task che realizzano lo scheduling e nell'ammontare massimo del tempo di computazione consumato da quei task. In più, una rappresentazione flessibile per le informazioni condivise all'interno dello scheduler distribuito facilità le variazioni nel grado di completezza e consistenza delle informazioni condivise. Si può mostrare che la condivisione di informazione incompleta (vs. completa) può portare ad un aumentata performance nella latenza con poche o nessuna perdita nella qualità dello scheduling.
Un secondo argomento che sta ricevendo sempre più attenzione è la costruzione di hardware special-purpose per l'esecuzione di scheduler o per l'assistenza nella gestione della memoria nelle applicazioni real-time. Tale lavoro è cominciato semplicemente dedicando un singolo processore in un sistema multiprocessore ad eseguire lo scheduler e contenere le informazioni di scheduling, ma i lavori recenti riguardano il supporto hardware per lo scheduling ( scheduling co-processors) e analogamente per la gestione dinamica della memoria.
Vediamo ora alcuni dettagli sullo scheduling real-time distribuito, dando maggior attenzione alle performance e alla struttura dello scheduler piuttosto che agli algoritmi di scheduling.
Scheduling real-time distribuito. Un'importante questione nello scheduling real-time è come far valere globalmente importanti proprietà di performance nei sistemi distribuiti. Verso questa finalità, la gran parte degli algoritmi di scheduling distribuito hanno due caratteristiche comuni:
La politica di scheduling locale è spesso basata su euristiche che determinano efficientemente quali task accettare o respingere.
E' stata proposta un'euristica, chiamata "guarantee routine", per lo scheduling locale in un sistema distribuito. Qui un task in arrivo è inserito nella coda se è possibile garantire che sia il task in arrivo sia tutti gli altri task correntemente nella coda non falliscono le loro deadline. I task rifiutati sono quindi passati all'algoritmo di distribuzione dei task per la distribuzione ad altri processori.
La performance degli algoritmi di scheduling locali per sistemi distribuiti hard real-time è determinata non solo dalla frazione di task respinti ma anche dal numero di task che possono essere condivisi. Questo in sostanza dipende dal fatto che il task respinto abbia una sufficiente laxity rimanente al momento della rejection, così che possa essere spedito ad altri processori. Per task con deadline hard real-time i risultati sono limitati al servizio FCFS.
Inizialmente sono stati presentati risultati analitici per la frazione di task respinti in arrivo ad un sistema multiprocessore, assumendo arrivi di Poisson e task con richieste di computazione e laxity note ed esponenziali.
Poi sono stati presentati risultati per task con computazione, laxity e distribuzione degli arrivi arbitrarie, dove è usato il servizio FCFS e tutti i parametri dei task sono noti all'arrivo in coda. Poi i risultati analitici sono stati estesi per un algoritmo elementare di distribuzione del carico con task di laxity fissa e un ritardo fisso nella distribuzione del carico, sempre assumendo un algoritmo di scheduling locale FCFS.
Infine sono stati esaminati gli algoritmi locali non-preemptive comunemente usati, e sono state confrontate le loro performance rispetto al tasso di scarto e alla laxity attesa al momento dello scarto. Le politiche confrontate sono FCFS, SJF, LLF, EDD, GM, e un algoritmo di selezione run-time (chiamato algoritmo MM) basato sulla regola di ordinamento di Moore.
I criteri considerati per la selezione di un algoritmo di scheduling locale per sistemi hard real-time sono quelli della minima frazione di scarto, massimo numero di task scartati con laxity positiva e della maggiore laxity al momento dello scarto per i task con laxity positiva. I risultati della simulazione mostrano che gli algoritmi MM forniscono la miglior performance nella frazione di scarto per un dato esempio di computazione e laxity del task. Per gli altri criteri, l'algoritmo FCFS mostra il maggior numero di task scartati con laxity positiva, mentre l'algoritmo LLF mostra la maggiore laxity allo scarto. L'utilizzazione della CPU è simile per gli algoritmi LLF, EDD, GM e MM e per gli algoritmi FCFS e SJF.
Hou, Shin ed altri hanno proposto un algoritmo di distribuzione del carico per applicazioni real-time che tiene conto dell'effetto degli arrivi di task futuri nel localizzare il miglior ricevente per ogni task in un ambiente eterogeneo distribuito.
Questo lavoro è stato poi esteso affrontando il problema di allocare moduli di task periodici a nodi di processing in sistemi real-time distribuiti soggetti a vincoli di precedenza di task ed a vincoli temporali. Viene proposto un algoritmo di allocazione del modulo (MAA) per trovare un'allocazione "ottima" che massimizza la probabilità di rispettare le deadline dei task usando la tecnica branch-and-bound.
Il sistema dei task all'interno di un ciclo di pianificazione è prima modellato con un grafo di flusso dei task (TG) che descrive i moduli di computazione e comunicazione così come i vincoli di precedenza tra di essi.
Per incorporare sia la correttezza temporale che quella logica nell'allocazione del modulo, viene usata come funzione obiettivo la probabilità di rispettare le deadline.
Il MAA viene quindi applicato per trovare un'allocazione ottima dei moduli in un sistema distribuito. Gli aspetti temporali incorporati nella funzione obiettivo guidano il MAA non solo ad assegnare i moduli ai nodi di processing, ma anche ad usare un algoritmo di scheduling del modulo (con complessità temporale polinomiale) per schedulare tutti i moduli assegnati ad ogni nodo in modo tale che tutti i task possano essere completati in tempo. Sono stati presentati diversi esempi numerici per dimostrare la praticabilità degli algoritmi proposti.
Figura 2.1. Una semplice tassonomia di alcuni degli algoritmi di scheduling discussi.
La figura 2.1 presenta una classificazione di alcuni degli algoritmi di scheduling presentati. Gli approcci allo scheduling possono per prima cosa essere divisi tra algoritmi di scheduling monoprocessore e multiprocessore, in cui gli approcci multiprocessore sono spesso usati nello scheduling real-time distribuito. L'approccio Rate Monotonic è stato il solo algoritmo monoprocessore statico che abbiamo discusso. Tra gli approcci dinamici, abbiamo menzionato Earliest-Deadline-First e sue varianti: Minimum Laxity First e Maximum Urgency First. Abbiamo anche discusso i lavori su computazione imprecisa/algoritmi anytime nel dominio monoprocessore.
Nello scheduling multiprocessore, abbiamo menzionato alcuni approcci che si confrontano con gli overload (alcuni di questi approcci sono anche applicabili in sistemi monoprocessore), e poi abbiamo discusso alcune strategie di scheduling real-time distribuito, e la struttura degli scheduler distribuiti. Gli scheduler real-time multiprocessore dinamici sono per loro natura sub-ottimi.
Sistemi dinamici. Il lavoro futuro nello scheduling real-time deve affrontare gli ambienti altamente dinamici e complessi dei sistemi real-time su larga scala, come le reti nazionali che trasportano comunicazioni con vincoli temporali (ad esempio applicazioni multimediali come la video compressione e trasmissione real-time), o il sistema di gestione di un teatro di guerra, o le simulazioni real-time distribuite.
Le nuove caratteristiche di tali applicazioni real-time includono:
Di conseguenza, i ricercatori si stanno occupando primariamente dello scheduling on-line, dello scheduling per sistemi paralleli e distribuiti, e delle semantiche dei vincoli temporali da utilizzare in tali sistemi (ad esempio le hard deadline non sono utilizzabili per formulare vincoli temporali in applicazioni multimediali).
On-line scheduling. I ricercatori stanno studiando gli overhead sperimentati dagli algoritmi di scheduling on-line, ed anche il modo di realizzare lo scheduling in hardware. Ciò significa che si sta dedicando maggiore attenzione agli algoritmi di scheduling ed alla implementazione dello scheduler piuttosto che a considerazioni sulla ottimalità e complessità degli algoritmi (quest'ultima riguarda solo il caso peggiore, mentre noi siamo spesso interessati, nei sistemi attuali, al caso medio). Inoltre nuove questioni come l'affidabilità combinata con la tempestività devono essere esplorate per sistemi su larga scala. Anche l'argomento delle soft deadline e delle nozioni alternative di deadline richiede ulteriori studi.
Implementazione dello scheduler. Un altro importante argomento è quello della integrazione e configurazione dello scheduler in sistemi operativi che offrono un supporto multi-utente e le facilities di protezione richieste. Mentre del lavoro è stato fatto sulle interfacce utente/sistema operativo per scheduler threads-based in sistemi non-real-time, solo ricerche recenti stanno studiando come le richieste del livello utente possano influire sullo scheduler o gli algoritmi di scheduling integrati in un sistema operativo real-time. Tipicamente, tale ricerca sta assumendo interfacce utente/sistema operativo object-oriented, dove l'informazione di scheduling addizionale è condivisa come attributi passati al tempo della creazione del thread o dello scheduling del thread per un'analisi di schedulabilità dinamica, o dove tali attributi sono passati prima per lo scheduling statico. Inoltre la configurabilità del sistema operativo o, più specificamente, dello scheduler può concernere la definizione di "metodi di configurazione" addizionali sugli oggetti dello scheduler o "attributi di configurazione" definiti con l'invocazione di oggetti e processati da politiche associate con gli oggetti del sistema operativo.
La ricerca sta anche cominciando ad interessarsi della struttura di scheduler flessibili per macchine su larga scala parallele o distribuite. Tali scheduler devono provvedere all'uso di diversi algoritmi di scheduling, rappresentazioni alternative della informazione di scheduling (per raggiungere vari trade-off costo/performance e scalabilità), e permettere l'uso di semantiche temporali differenti. Il lavoro recente ha tentato di definire strutture flessibili all'interno delle quali possono essere realizzate implementazioni alternative dello scheduler e degli algoritmi di scheduling.
Il sistema operativo ad oggetti Chaos offre anche agli utenti la possibilità di implementare e usare real-time threads scheduler di basso livello alternativi. Inoltre, Stankovic e Ramamrithan hanno identificato un insieme di problemi che ogni esauriente approccio di scheduling dovrebbe essere in grado di affrontare. Questi includono la capacità di gestire task sia preemptable sia non-preemptable, sia periodici sia non periodici, multiple criticità dei task, gruppi di task con una singola deadline condivisa (co-scheduling), vincoli di precedenza, esigenze di gestione delle risorse e di comunicazione, migrazione e posizionamento dei task, esigenze di tolleranza ai guasti, deadline soft e hard, e condizioni normali e overloaded.
2.3 SINCRONIZZAZIONE NEI SISTEMI REAL-TIME
La sincronizzazione è importante nei sistemi real-time per due ragioni:
2.3.1 Sistemi monoprocessore.
Per sistemi monoprocessore che fanno girare task periodici, due recenti protocolli forniscono soluzioni efficaci al problema dello scheduling con risorse condivise. Essi sono il protocollo kernelized monitor e il protocollo priority ceiling.
Nel primo, viene usata per il task scheduling la politica earliest deadline first. Tutte le esecuzioni nelle sezioni critiche non sono interrompibili. Tuttavia, l'analisi di schedulabilità fatta in questo protocollo richiede l'uso di upper bounds sui tempi di esecuzione di tutte le sezioni critiche che compaiono nei task. Dal momento che tali upper bounds possono essere troppo pessimistici, usare il protocollo kernelized monitor può portare ad una bassa utilizzazione del processore.
Il protocollo priority ceiling è progettato per sistemi in cui ogni task ha una priorità fissa e viene usato l'algoritmo di scheduling rate monotonic. Con questo protocollo nel caso peggiore, ogni task deve solo aspettare che al più un task a priorità più bassa in una sezione critica termini, e non possono esserci deadlock. Supponendo che il tempo di attesa più lungo possibile sia noto per ogni task nel sistema, possono anche essere derivate delle condizioni sufficienti per schedulare insiemi di task periodici. Tuttavia, il protocollo priority ceiling non può essere direttamente usato quando le priorità sono dinamiche.
Per sistemi monoprocessore, Jeffay ha sviluppato delle condizioni di schedulabilità per un insieme di task sporadici ciascuno di quali consiste di una sequenza di fasi, dove al più ad una risorsa condivisa si può fare accesso in ogni fase. Nella sua analisi, i vincoli temporali dei task così come le richieste di risorse sono ipotizzate note a priori. Viene dimostrato che le discipline di sincronizzazione e di scheduling ottime esistono per pattern ristretti di utilizzo delle risorse.
2.3.2 Sistemi multiprocessore
.Sono stati descritti degli algoritmi per semafori con attesa lineare. Sebbene gli algoritmi proposti sono prevedibili, essi non tengono in considerazione le priorità dei processi che desiderano acquisire il semaforo.
E' stata presentata anche un'estensione multiprocessore del protocollo priority ceiling. Il protocollo priority ceiling minimizza l'inversione di priorità per un insieme di processi periodici real-time che accedono in modo esclusivo ad alcuni dati condivisi.
Il protocollo priority ceiling multiprocessore generalizza il protocollo monoprocessore eseguendo tutte le regioni critiche associate ad un semaforo su un particolare processore chiamato processore di sincronizzazione. Di conseguenza, le regioni critiche in un programma sono sostituite da un'invocazione di un server remoto di sincronizzazione. Sfortunatamente, la descrizione di un singolo server di sincronizzazione centralizzato limita la scalabilità della soluzione, e può aumentare il costo di esecuzione di applicazioni real-time a grana fine.
Sono state discusse anche la sincronizzazione e la mutua esclusione per applicazioni multiprocessore hard real-time dinamiche.
Così come ogni programma parallelo dinamico, l'esecuzione di un'applicazione real-time dinamica può significare la creazione on-line di task addizionali, e la creazione di tali task vincolati temporalmente non può essere prevista prima dell'esecuzione del programma.
I risultati presentati riguardano la sincronizzazione di task tale che possano essere fatte delle garanzie sui vincoli temporali dei task sincronizzati. Tali garanzie non possono essere fatte senza effettuare un'analisi di schedulabilità on-line e un'analisi on-line riguardante il tempo massimo che un task aspetterà per acquisire certe risorse con una primitiva di sincronizzazione. Viene presentato un nuovo schema di locking real-time per evitare deadlock ed assicurare la mutua esclusione time-bounded. Il massimo tempo di attesa per un task che tenta di acquisire una risorsa è calcolato con un algoritmo O(1). Due attributi dell'algoritmo sono:
Dalle ricerche sulla sincronizzazione nei sistemi non-real-time derivano efficienti implementazioni spin-lock sui sistemi multiprocessore.
Siccome queste implementazioni servono le richieste di lock in ordine FIFO, possono essere utilmente impiegate nei sistemi real-time che vogliono soltanto limitare (non minimizzare) l'inversione di priorità.
Markatos ha migliorato algoritmi esistenti (Burns e Mellor-Crummey-Scott) per definire uno spin lock con priorità con implementazioni che coinvolgono solo spinning locale. Ogni processore che compete per uno spin lock con priorità ha un'unica priorità dinamica che riflette l'importanza del processo che fa girare. I processi che richiedono, detengono o rilasciano tali lock non sono interrompibili durante le operazioni di lock.