Post on 01-May-2015
transcript
Sistemi e schedulazione in tempo reale E.Mumolo
mumolo@units.it
Sistemi in tempo reale Sistemi di calcolo in cui la correttezza del funzionamento dipende
criticamente dal tempo dal tempo in cui i risultati sono prodotti. Possibili campi applicativi:
regolazione di impianti industriali (chimici, nucleari etc.) controllo di processi controllo di volo, di traffico etc. sistemi di telecomunicazioni sistemi militari sistemi spaziali realta’ virtuale Robotica Sistemi di monitoraggio medico Sistemi di controllo nell’auto: sistema ABS e controllo elettronico del motore
…
Come assicurare che il sw sia corretto?1° problema: test del SW !2° problema: progetto del sistema assunzioni pessimistiche3° problema: empiricita’4° problema: codice molto spesso Assembly
Sistemi in tempo reale
Perche’ Tempo Reale? Tempo: la validita’ dei risultati dipende dal tempo di servizio Reale: la risposta agli eventi esterni deve avvenire durante l’evolversi
dell’evento stesso Il tempo di sistema deve essere misurato secondo un riferimento
temporale che dipende dall’ambiente Esempio: sistemi biologici. Introducendo eventi con costante di
tempo piu’ bassa pericolo! Ogni sistema RT deve essere studiato nell’ambiente effettivo di
lavoro La caratteristica piu’ importante di un sistema RT non e’ la velocita’,
ma la prevedibilita’! La differenza principale tra un processo RT ed un processo NON
RT e’ la Deadline (= tempo massimo di fine processo) In un sistema RT, un risultato prodotto oltre la deadline e’ dannoso
Sistemi in tempo reale
Esempi:
Sistemi in tempo reale TIPI DI PROCESSI RT
Hard RT: se il superamento della deadline e’ catastrofico. Es.: acquisizione dati asservimento pianificazione azioni controllo automatico
Soft RT: se il superamento della deadline non e’ catastrofico ma sopportabile. Es.: Interpretazione comandi utente Visualizzazione messaggi
ASPETTI FONDAMENTALI: SCHEDULING ACCESSO A RISORSE GESTIONE SOVRACCARICHI COMUNICAZIONE TRA PROCESSI
Sistemi in tempo reale
• Riassumendo:
• TR vs NTR: vincoli temporali, ambiente dinamico.
• Un sistema in tempo reale è quindi:
• stimolo esterno elabora entro un tempo finito e specificato
• ogni sistema nel quale è importante il tempo di term.
• movimento nel mondo fisico l’uscita è relativa allo stesso movimento.
• La differenza tra l’istante dell’evento di ingresso e l’istante dell’evento d’uscita è la prontezza del sistema.
Sistemi Soft Real time e Hard Real Time
Deadline: l’istante nel quale deve essere terminata l’esecuzione.
distinzione a seconda del risultato della risposta Può essere accettata una risposta oltre la deadline. Il tempo di risposta è importante ma non cruciale.
Hard deadline: se i dati arrivano tardi rispetto alla deadline sono sbagliati e come tali non possono essere accettati.
Soft deadline: se i dati arrivano tardi rispetto alla deadline possono essere ancora utilizzati
Sistemi Soft Real time e Hard Real Time
Sistemi Hard Real-Time: i processi hanno delle deadline assolutamente rigorose;
Sistemi Soft real-time: i processi hanno delle deadline non rigorose;
Alcuni sistemi hanno sia deadline soft che hard: una deadline può non essere soddisfatta se Le prestazioni medie sono sufficienti in ogni istante Ogni deadline viene comunque sodddisfatta entro un certo
intervallo temporale. Un sistema si dice schedulabile se tutte le richieste di
schedulazione sono soddisfacibili
Sistemi Soft Real time e Hard Real Time
Rispettare le deadline:
SoftReal-time
NonReal-time
HardReal-time
Simulazionisoftware
Interfacciautente
Video suinternet
Telecom appl. Controllo elettronicodi un motore
Sistema dicontrollodi un missile
Streaming
Sistemi Soft Real time e Hard Real Time
Esempi: Sistema di controllo di un aereo da combattimento
Le informazioni ambientali devono essere fornite al pilota immediatamente.
I comandi dati dal pilota devono essere eseguiti immediatamente
Sistema di monitoraggio di un paziente Per esempio una macchina che monitorizza il battito cardiaco: è
sufficiente conoscere la frequenza del battito entro un secondo e non entro un millisecondo dalla misura
Sistema di presentazione multimediale Questo sistema può essere considerato un sistema in tempo reale.
Tuttavia non è necessario che tutte le deadline siano assolutamente soddisfatte, ma è sufficiente che la maggior parte sia soddisfatta
Sistemi Soft Real time e Hard Real Time
Proprietà Non R T Soft R T Hard R T
Deterministico No Possibilmente Sì
Predicibile No Possibilmente Sì
Effetto del non Non ha Degrado FallimentoSoddisfacimento effetto prestazionidelle deadline
Affidabilità neicompiti critici No Sì Sì
Proprietà dei sistemi in tempo reale Controllano e monitorizzano processi fisici entro limiti
temporali. Sono affidabili per lunghi periodi. Non richiedono intervento umano diretto. Operano sotto vincoli più severi dei sistemi normali, di
uso generale.
Devono operare con la minima memoria ed il minimo supporto hardware.
Più difficili da sviluppare e correggere.
Non usano memoria di massa.
Non hanno il display o la tastiera tradizionali.
Caratteristiche dei sistemi in tempo reale
Tipicamente possono essere
Sistemi ‘embedded’: un componente di un sistema hardware/software più ampio
Sistemi concorrenti: il sistema controlla simultaneamente e/o reagisce ad aspetti differenti dell’ambiente.
Sistemi sicuri: non sono solo affidabili ma anche sicuri se il fallimento della esecuzione non provoca danni a persone o cose. Tipicamente lo sviluppo di sistemi sicuri richiede la ridondanza.
Sistemi reattivi: c’è una continua interazione con l’ambiente, che fornisce eventi ai quali il sistema reagisce. La risposta del sistema è tipicamente dipemdemte dallo stato.
Caratteristiche dei sistemi in tempo reale
Prontezza del sistema: descrive come il sistema soddisfa i vincoli temporali
Risposta agli eventi esterni: un sistema in tempo reale ha lo scopo principale di rispondere agli eventi esterni, che sono tipicamente non predicibili
Correttezza e robustezza Concorrenza: capacità di eseguire simultaneamente
diverse azioni. Problemi coinvolti: schedulazione modalità di arrivo sincronizzazione accesso alle risorse condivise
Modalità dell’arrivo dei processi
Gli arrivi possono essere periodici o aperiodici. Un arrivo periodico implica che il thread viene re-inizializzato a
periodi fissi (più o meno piccole variazioni (jitter)) task periodici
Un arrivo aperiodico non avviene a periodi fissi ma in istanti casuali. La temporizzazione può essere: Irregolare – gli interarrivi sono variabili e non predicibili. Impulsivo – gli interarrivi sono costituiti da gruppi dove un arrivo
è vicino all’altro. Ad intervallo limitato – esiste un intervallo minimo tra gli eventi. Raggruppati intorno ad una media. casuale – gli interarrivi possono essere previsti su base statistica
Le differenti modalità di arrivo devono essere trattate con diversi meccanismi.
Comunicazione tra thread e modalità di chiamata dei metodi
Comunicazione mediante messaggi. Durante la loro esecuzione i thread possono chiamare metodi
in diversi modi: Chiamate sincrone: gli oggetti chiamano direttamente i metodi di altri
oggetti entro lo stesso thread. Chiamate asincrone: gli oggetti di un thread inviano un messaggio di
chiamata ad un altro thread e continuano senza aspettare. Il thread chiamato gestisce il messaggio quando può farlo.
Chiamate bloccanti: il thread chiamante aspetta che il thread chiamato risponda.
Chiamate a tempo: il thread chiamante aspetta la risposta del thread chiamato per un tempo specificato.
Chiamata a polling: se il thread chiamato non è immediatamente disponibile, il thread chiamante non aspetta la risposta e fa’ altre cose.
È importante identificare la modalità di chiamata per soddisfare le deadline.
Prevedibilità
La prevedibilità di un sistema rappresenta la bontà con la quale si possono conoscere le sue risposte in anticipo.
È cruciale per i sistemi altamente affidabili e per i sistemi critici per quanto riguarda la sicurezza.
Per determinare la prevedibilità si possono usare: Tecniche di analisi statica, Algoritmi semplici di controllo dei task, per esempio mediante la
disabilitazione della concorrenza, Mediante l’uso di oggetti che rappresentano i task e identificano le
prestazioni dei task.
Ci sono due aspetti della prevedibilità: schedulabilità e memoria.
Prevedibilità
Memoria statica
Memoria Stack – le variabili locali e gli indirizzi di ritorno.
Memoria Heap – La maggior parte dei getsori della memoria heap non hanno un tempo di allocazione costante o conosciuto, perchè devono analizzare la memoria disponibile. L’allocazione non è predicibile e qualche deadline può essere superata.
La frammentazione della memoria peggiora le cose.
Soluzione comune – strutturare la memoria heap per blocchi di memoria di dimensione fissa.
Qualche possibilità: memoria stack stabile e scrivibile memoria heap volatile memoria stack stabile a sola lettura
Prevedibilità
La prevedibilià della memoria rappresenta la memoria utilizzata e la sua persistenza
Memoria utilizzata: Memoria usata per il codice eseguibile Memoria usata per i dati: stack, heap, variabili statiche.
Persistenza della memoria: Memoria stabile a sola lettura Memoria stabile riscrivibile Memoria volatile
Sistemi distribuiti
Sistemi in tempo reale di ampie dimensioni possono essere distribuiti su diversi processori.
Qualche volta nello stesso calcolatore e qualche volta in calcolatori diversi.
Questi sistemi hanno diversi problemi, quali ad esempio: coordinazione e sincronizzazione di processi su diversi processori processo di bootstrap comunicazione tra processi sincronizzazione della base dei tempi
Tolleranza ai guasti e sicurezza
Spesso i sistemi in tempo reale devono essere affidabili. Deve essere assicurata non solo l’affidabilità ma anche
la sicurezza Lo sviluppo di sistemi sicuri coinvolge la ridondanza
architetturale
Interfacciamento hardware a basso livello
Sviluppo di sistemi real-time: necessità di gestione delle interfacce hardware a basso livello, cioè la generazione di driver
Le componenti hardware e i dispositivi richiedono spesso di sviluppare dei driver opportuni.
Questi driver devono interfacciarsi con il sistema operativo in tempo reale.
Qualche volta l’efficienza della modalità di gestione dei dispositivi è cruciale per le prestazioni del sistema.
Sviluppo dei sistemi embedded
Di solito i sistemi embedded vengono svliluppati usando strumenti software che girano su calcolatori separati.
L’applicazione eseguibile verrà quindi eseguita su un differente calcolatore. Lo sviluppatore deve usare cross-compilatori, simulatori e srumenti simili.
Qualche volta l’ambiente di esecuzione non ha strumenti sofisticati di debug.
L’ambiente di sviluppo d’altra parte non è in grado d’altra parte di gestire tutti gli strumenti nell’ambiente di esecuzione.
Qualche volta l’ambiente di esecuzione è composto da hardware speciale che non è presente nel calcolatore di sviluppo e deve quindi essere simulato.
Sviluppo dei sistemi embedded
Qualche volta il sistema finale non ha un display sul quale visualizzare gli errori del programma o i messaggi diagnostici.
Qualche volta il sistema finale usa un Sistema Operativo diversi dal calcolatore di sviluppo.
Di solito il sistema finale è prodotto in piccola quantità ed è usato sia per lo sviluppo hardware che per lo sviluppo del software.
Questo sviluppo concorrente aggiunge alla difficoltà dello sviluppo software la difficoltà della integrazione hardware e software.
Le differenze tra lo l’ambiente di sviluppo e l’ambiente di esecuzione aggiunge quindi tempo, difficoltà e rischi nello sviluppo.
Spesso lo sviluppatore deve progettare e scrivere software per un hardware che ancora non esiste.
Principi di Schedulazione in tempo reale
Task in tempo reale
Un task ti è una sequenza di processi in tempo reale ik ciascuno caratterizzato da un tempo d’arrivo rik
un tempo di inizio esecuzione sik
un tempo di fine esecuzione fik
una deadline assoluta dik,
una deadline relativa Dik,
da un tempo di esecuzione Cik
k
k
sikfik
Task periodici
Task periodico i
Triggerati a periodi fissi da un timer
Consistono in una sequenza infinita di attività identiche, chiamate istanze.
Ciascuna istanza è caratterizzata da un periodo T e da un tempo di calcolo C
Task aperiodici
Task aperiodici:
Task sporadici:
Triggerati da interrupt esterni
I task sporadici sono triggerati da interrupt esterni con un minimo tempo di interarrivo tra gli interrupt
Parametri descrittivi dei processi in tempo reale
Lateness: L=f-d
Exceeding time: E=max(0,L) tempo in cui un processo e’ rimasto attivo oltre la propria deadline
Slack time (o LAXITY): LX=d-a-C ritardo di attivazione max consentita
Metriche di valutazione: basate sulla funzione di costo che dipende dal tempo di terminazione del task. La funzione di costo rappresenta l’importanza relativa del task.
Parametri descrittivi dei processi in tempo reale
Qualche esempio di funzioni di costo:
n
iii af
nrispostadimedioTempo
1)(
1
)(min)(maxom ii
ii
aftotalepletamentocdiTempo
i
ii fwpletamentocditempideipesatamaS omom
i
ii fmissdeadlinela
oraggiungonnonchetardivitaskdeimassimoNumero
)()
(
ii
iiii dfse
dfsefmissdove
1
0)(
Esempi di funzioni di costo
Andamento della importanza dei task:
f
f
f
f
v(f)
v(f)v(f)
v(f)
Non real time
hard real time
soft real time
critico
Sistemi operativi in tempo reale
FATTI DEI SISTEMI OPERATIVI RT In un sistema di controllo RT ogni processo e’ ben noto! Nessun
task del sistema e’ un processo casuale E’ importante assicurare che tutti i task critici completino la loro
attivita’ entro la deadline in una applicazione RT, i vari processi sono cooperanti: non e’
necessario usare spazi di indirizzamento separati PRESUPPOSTI DESIDERATI DAL S.O.
Scheduling ottimo per rispettare i vincoli temporali Condivisione risorse condivisione spazio indirizzamento Garanzia di esecuzione i task critici vengono attivati solo se
possono essere completati in tempo Prevedibilita’ del meccanismo dello scheduling tutte le
primitive devono avere un tempo di esecuzione massimo definito Flessibilita’ struttura modulare per adattarsi alla applicazione
CARATTERISTICHE REALI (Ereditate dalle implementazioni classiche) Multitasking Schedulazione prioritaria (non adatta ai sistemi RT) Risposta alle interruzioni (una rapida risposta puo’ rallentare
l’esecuzione dei processi) Sincronizzazione e cooperazione dei processi (indesiderato nei
SORT) Piccolo nucleo e veloce T.S. (Ma: il veloce T.S. non garantisce la
terminazione dei task) Clock RT per la generazione di un riferimento temporale. I
sistemi commerciali non forniscono primitive per i vincoli temporali l’utente deve trasformare i vincoli temporali in priorita’
PREVEDIBILITA’ DEL SISTEMA Devo sapere se i processi possono essere completati in tempo
determinismo dei processi
Sistemi operativi in tempo reale
Sistemi operativi in tempo reale
Cause di aleatorieta’: DMA CACHE (cache fault) Interrupts (un processo puo’ essere piu’ urgente di un interrupt).
Approcci: Disabilitazione delle interruzioni (polling) Disabilit. Interruz. Tranne il Timer che interroga periodicamente
l’I/O Mantenere gli interrupts ma schedulare un task come un altro Primitive del nucleo (devono avere durata max) Mutua esclusione (soluzioni ad hoc) Gestione della memoria (page fault! partizioni statiche) Linguaggio di programmazione (deve trattare i vincoli temporali)
SCHEDULAZIONE Def.: schedulazione fattibile se esiste un
assegnamento ai task tale che i task vengono completati rispettando i vincoli
Def.: un insieme di task e’ schedulabile se esiste una schedulazione fattibile
Def.: vincoli sui processi: temporali, di precedenza, su risorse condivise
Sistemi operativi in tempo reale
Scheduling Real Time per Processi Aperiodici Ottimizzare una funzione di costo definita sui parametri temporali
Notazione di Graham: (||)dove:
: macchina fisica (monoprocessore, multiprocessore etc) : tipo di vincoli ai processi (precedenza, preemption etc.) : funzione di costo minimizzata
Esempio:
(1|prec|LMAX), (3|nopreempt.|fi), (2| |fi)
Algoritmo di Jackson
Algoritmo (1|a0|Lmax) per un sistema di n tasks Consideriamo un insieme di task J={Ji(ai, Ci, di), i=1…n}, dove ai=a0 per
ogni i=1…n Algoritmo: la massima lateness Lmax e’ minimizzata se i processi sono
schedulati in ordine di deadline crescenti La complessita’ di calcolo dipende principalmente dalla procedura di
ordinamento dell’insieme di task O(nlogn)
46783di
21111Ci
J5J4J3J2J1
0 1 2 3 4 5 6 7 8 9
J1 J5 J4 J3 J2
1 5 4 3 2
Lmax = -1
Algoritmo di Jackson
Test di schedulabilità: i
i=1..n; Ck di
k=1
Esempio di schedulazione Non Fattibile
57463di
22112Ci
J5J4J3J2J1
0 1 2 3 4 5 6 7 8 9
J1 J3 J4J5 J2
1 5 43 2
Lmax = 1
Algoritmo di Jackson Ottimalità dell’algoritmo di Jackson Per una schedulazione generica, esisteranno almeno due task Ja e
Jb con da db tali che Jb precede Ja:
Se si invertono i due task, la lateness massima diminuisce:
dbda
JaJb
La=fa-da
Lb=fb-db
Lmax=fa-da
fb fa
JbJa
L’a=f’a-da
L’b=f’b-db
f’bf’adb
da
Se (L’a> L’b) L’max = f’a-da < fa-da L’max < Lmax
Se (L’b> L’a) L’max = f’b-db = fa-db < fa-da L’max < Lmax
Eseguendo un numero finito di scambi di questo tipo si ottiene la schedulazioneottima
Algoritmo di Horn Algoritmo (1|preemp|Lmax) Rimuove l’ipotesi di attivazioni simultanee: attivazione dinamica e pre-emption Estensione dell’algoritmo di Jackson Algoritmo: La massima lateness Lmax di un insieme di n task con attivazione
dinamica e’ minimizzata se, ogni volta che un nuovo task entra nel sistema la coda dei processi pronti viene riordinata per deadline crescente e la CPU viene assegnata al processo con deadline piu’ imminente.
Chiamata anche Earliest Deadline First (EDF)
Ottimalita’ nel senso che minimizza Lmax e nel senso della schedulazione.
0 5 10
J1
J2
J3
J4
J5
Algoritmo di Horn Complessita’ O(n2), dove n è il numero di processi che possono essere
attivati dinamicamente. Test di garanzia di schedulabilità: derivato dal test di Jackson:
i
i=1..n; ck(t) di k=1
dove ck(t) sono i tempi residui istantanei di esecuzione e di sono le deadline riscalate rispetto ai tempi di arrivo.
Minimizzazione di Lmax: deriva da Jackson Teorema:Se un insieme di task aperiodici non è schedulabile con l’algoritmo di
Horn, allora non è schedulabile con nessun altro algoritmoDim.In altre parole, l’enunciato del teorema afferma che: se un insieme di task è schedulabile con un qualche algoritmo A, allora
sicuramente è schedulabile con l’algoritmo di Horn.
Algoritmo di Horn (cont.) Si divida la scala temporale in quanti pari all’unità di tempo del sistema Sia t=0 il primo istante di attivazione dei processi Sia D=max(di) la deadline più lontana Sia A una qualsiasi schedulazione fattibile Sia (t) il task in esecuzione al tempo t nella schedulazione corrente Sia E(t) il task con deadline più imminente Sia tE l’istante di tempo in cui inizia E(t) nella schedulazione correnteAllora: la schedulazione può essere trasformata in una schedulazione di Horn
con il seguente algoritmo:
Trasforma(){
= A;for (t=0; t<D; t++)
if( (t) E(t)){ (tE) = (t); (t) = E(t);}
}
Algoritmo di Horn (cont.) Ciascuna trasformazione preserva il tempo di calcolo dei task (i quanti
possono essere solo traslati, non accorciati o allungati) Tutti i tempi possono al più essere ritardati di tE
Se la schedulazione A è fattibile, allora prima della trasformazione
(tE+1) dE, ma dE di per ogni i, quindi dopo la trasformazione (tE+1) di
quindi tutti i task terminano entro le deadline Horn è fattibile Esempio di una trasformazione:
5
J1
J2
J3
J4
5
J1
J2
J3
J40 10 13 D
50 10 13 D
Algoritmo di Horn (cont.)
Analisi della schedulabilità: deve essere fatta ad ogni arrivo
le deadline devono essere riscalate ad ogni arrivo del tempo dell’arrivo Istante 0: sono presenti in coda J1 e J2 (nell’ordine). Tempo residuo per J1: 1; per J2: 2.
1 <= d1= 2 1+2 <= d2=5 Istante 2: sono presenti in coda J3 e J2 (nell’ordine). Tempo residuo per J3: 2; per J2: 1
2 <= d3=2 2+1 <= d2= 3 Istante 3: sono presenti in coda J3, J2, J4 (nell’ordine). Tempo residuo per J3: 1; per J1: 1;
per J4: 2
1 <= d3=1 1+1 <= d1= 2 1+1+2 <= d4=7 Istante 6: sono presenti in coda J5, J4 (nell’ordine). Tempo residuo per J5: 2; per J4: 1
2 <= d5=3 2+1 <= d4=4
0 5 10
J1
J2
J3
J4
J5
Schedulazione senza pre-emption
algoritmo di Horn Se si esclude l’ipotesi di preemption, con attivazione dinamica l’algoritmo EDF non e’ piu’ ottimo
Esempio:
521J2
740J1
DiCiai 5 10
5 10
J1
J2
J1
J2
Schedulazioneottima
SchedulazioneEDF
Schedulazione senza pre-emption:
Algoritmo di Bratley Schedulazione senza pre-emption di un insieme di task attivati dinamicamente
Ricerca su un albero con pruning Complessita’ O(nn!) Algoritmo off-line. Esempio:
420J4
621J3
511J2
724J1
diCiai Numero nel nodo task che viene schedulato
Numero accanto al nodo tempo in cui il task termina
J+ task che supera la deadline schedulazione fattibile
Schedulazione senza pre-emption:
Algoritmo Spring Sistema Hard real-time Garantisce dinamicamente (on-line) l’esecuzione dei processi
attivati tenendo conto dei vincoli (temporali, di precedenza, sulle risorse, no pre-emption, esecuzione su multiprocessore, fault tolerance …)
Usa una funzione di costo H euristica Ogni volta che si estende una schedulazione parziale, si valuta H
per i task non ancora schedulati e si sceglie quello che minimizza H Albero delle schedulazioni con pruning. Alcune funzioni euristiche:
H=1 FCFS H=C SJF H=d EDF H=Test ESTF (Earliest Start Time First) H=d+W*C EDF+SJF
Algoritmi di Scheduling con Vincoli di Precedenza
Puo’ essere risolta con algoritmi polinomiali solo se si impongono ipotesi semplificative
Algoritmo Latest Deadline First (LDF). Algoritmo (1|prec, a0| Lmax) Algoritmo: Dato un insieme J di n task con grafo di precedenza, si costruisce la
lista di scheduling a partire dal fondo. Fra tutti i task che non hanno successori nel grafo, si seleziona il processo con la deadline piu’ lunga.
Schedulato l’ultimo task, la lista viene eseguita in ordine inverso. Esempio:
61JF
51JE
31JD
41JC
51JB
21JA
diiCi
A
B C
D E F
2
5 4
3 5 65
50
0
8
8
A B D C E F
FEDBCA
LDF
EDF
Lmax=0
Lmax=LD=1
A D C B E F
A D C B E F
Algoritmo EDF con vincoli di precedenza
Algoritmo (1|prec,pre-empt|Lmax) Modifica i tempi di arrivo e le deadline di tutti i processi in modo da
trasformare i vincoli di precedenza in vincoli temporali. Dopo le trasformazioni, i processi sono schedulati con EDF
Modifica dei tempi di arrivo: per ogni nodo iniziale del grafo di precedenza, ai*=ai si seleziona un task Jk non ancora modificato, tale che tutti i suoi
predecessori siano stati modificati. Se Jk non esiste, termina. Modifica il tempo di arrivo di Jk: ak*=max(ak, max(ai*+Ci:JiJk)] Vai al punto 2)
Modifica i tempi di deadline: per ogni nodo terminale, di*=di seleziona un task Jk non ancora modificato tale che tutti i suoi successori
siano stati modificati. Se Jk non esiste, si termina modifica la deadline di Jk: dk*=min[dk, min(di*-Ci:JkJi)] vai al 2)
Complessita’ O(n2)
Schedulazione di task periodici Sono la maggioranza delle attivita’ di elaborazione. Es. regolazione,
acquisizione, filtraggio, monitoraggio, comando di attuatori etc. Ipotesi:
Tutte le richieste di esecuzione sono inoltrate ad intervalli regolari (periodo)
Il tempo di eseuzione di un task e’ costante La deadline coincide con la fine del periodo corrente Tutti i task sono indipendenti
Quindi, un processo periodico e’ caratterizzato da due parametri: Periodo Ti
Tempo di esecuzione Ci
Schedulazione di task periodici
Ulteriori definizioni: Istante di richiesta: istante in cui una istanza periodica
diventa pronta per l’esecuzione Frequenza di richiesta: inverso del periodo di un task Tempo di risposta: tempo che intercorre tra istante di
richiesta e istante di completamento Istante critico: istante di richiesta che genera il piu’ lungo
tempo di risposta Zona critica: intervallo tra istante critico e istante di
completamento dell’istanza. Equivale al tempo di risposta piu’ lungo.
Schedulazione di task periodici
Fattore di utilizzazione del processore U E’ la frazione di tempo utilizzata dalla CPU per eseguire l’insieme
di task (e’ una misura della occupazione del tempo di CPU per eseguire un insieme di task periodici)
In un insieme di n task:
Il processore e’ “completamente utilizzato” dall’insieme di task se un piccolo aumento di un Ci rende la schedulazione non fattibile
“Limite superiore minimo” Ulsm del fattore di utilizzazione: minimo tra i fattori di utilizzazione calcolati su tutti gli insiemi di task che utilizzano completamente il processore. Parametro caratteristico di scheduling. E’ il carico massimo gestibile da un algoritmo di schedulazione.
n
i
i
T
C
1
U
Schedulazione di task periodici Se un insieme di task periodici ha un fattore di utilizzazione
del processore U minore di Ulsm l’insieme di task è sicuramente schedulabile
Se un insieme di task periodici ha un fattore di utilizzazione
del processore U maggiore o uguale a Ulsm l’insieme di task potrebbe essere schedulabile
Zona di schedulabilità per qualsiasi insieme
Ulsm1
Ulsm2
Ulsm3
Ulsm4
Ulsm1Ulsm
Schedulazione di task periodici Teorema di schedulabilità generale
Condizione sufficiente per la schedulabilità di un insieme di task periodici con un algoritmo A è U Ulsm(A)
Dim. Direttamente dalla definizione di Ulsm
Teorema della non schedulabilitàCondizione sufficiente per la non schedulabilità è U > 1.Dim.
Sia T=T1T2…Tn=Ti. Se U>1 UT>T. Quindi: (T/Ti)Ci > T
La quantità (T/Ti) rappresenta il nr. di volte che il task ti viene eseguito in T, mentre (T/Ti)Ci rappresenta il tempo di calcolo richiesto dal task ti nel tempo T. Quindi la domanda totale in [0,T] è superiore al tempo disponibile T, quindi la schedulazione non è fattibile con nessun algoritmo.
Schedulazione di task periodici Analisi del tempo di risposta per valutare la schedulabilità:
Valutazione del tempo di risposta nel caso peggiore, R, e controllo della deadline:
Valutazione del tempo di risposta nel caso peggiore: è dato dal tempo di calcolo più interferenze dei task a più alta priorità:
Durante Ri, ogni task a più alta priorità esegue
L’interferenza totale è data da
Quindi il tempo di risposta nel caso peggiore Ri può essere descritto con
dove la sommatoria è estesa a tutti i task di priorità maggiore del task i
iii ICR
R D
j
i
T
R
jj
i CT
R
jj
iii C
T
RCR
volte
Schedulazione di task periodici
Solve by forming a recurrence relationship:
jihpj
j
n
ii
n
i CT
wCw
)(
1
jihpj
j
iii C
TR
CR
)(
La soluzione della equazione
dove hp(i) è l’insieme dei task a priorità maggiore di i, è ottenuta per ricorrenza:
Quando la ricorrenza converge, cioè i valori restano costanti, si ottiene il termine Ri
Schedulazione di task periodici a priorità fissa
Priorità stabilite a priori Come stabilire le priorità dei task?
Sulla base dei tempi di esecuzione Priorità maggiore ai task con maggiore/minore tempo di esecuzione
Sulla base dei periodi Priorità maggiore ai task con maggiore/minore periodo di esecuzione
Sulla base della utilizzazione Priorità maggiore ai task con maggiore/minore coefficiente di utilizzazione
Sulla base delle deadline Priorità maggiore ai task con maggiore/minore tempo di deadline
…
Schedulazione di task periodici a priorità fissa: Rate Monotonic
Supponiamo di ordinare i task secondo periodi crescenti Algoritmo Rate Monotonic: assegna ad ogni processo una priorita’
direttamente proporzionale alla propria frequenza di richiesta (task con periodo breve priorita’ elevata)
Chiamato anche Shortest Period First (SPF) Pre-emptive, statico Proprieta’: RM e’ ottimo, nel senso che se un insieme di task NON e’
schedulabile con RM, allora non e’ schedulabile con nessun altra regola di assegnazione a priorita’ fisse
Schedulazione di task periodici a priorità fissa: Rate Monotonic
•Altro esempio:
Schedulazione di task periodici: Rate Monotonic
Teorema della ottimalita’ di RMSe un insieme di task periodici NON e’ schedulabile con RM, allora non esiste un algoritmo di schedulazione a priorita’ fissa per quell’insieme di task.
Dim.Si afferma che: se un insieme di task non e’ schedulabile con RM non esiste altra schedulazione.
Cioe’: se esiste una schedulazione e’ schedulabile con RM.
Supponiamo di avere due task periodici 1 e 2, con T1<T2. Secondo RM, dovrebbe essere schedulato prima 1 e poi 2. Prendiamo una schedulazione non RM, cioe’ facciamo prima 2 poi 1. Affinche’ sia fattibile:
(1) C1+C2 <= T1
Schedulazione di task periodici: Rate MonotonicSupponiamo ora di usare RM. Ci sono due possibili casi:Caso a)
Cioè tutte le richieste di t1 vengono completate entro T2. Cioe’
Affinchè RM sia fattibile, deve essere Mostriamo che, se vale (1), allora RM è fattibile. Moltiplicando (1) per F:
CVD
1
2121 T
TF dove TF - T C
.T C1)(F C 212
.T TF-TFT CFT CF)(1C TF-T C che Dato
CFT CF)(1C Abbiamo membri. i entrambi a C Sommiamo
F.TFCFC CFC 1,F che Dato F.T FCFC
221211121121
11211
12121121
T
Schedulazione di task periodici: Rate MonotonicCaso b)
L’ultima esecuzione di 1 si sovrappone con 2. Cioe’:
In questo caso, RM e’ fattibile se:
CVD
121 TF-TC
F.T FC FC :(1) Dalla .TF CCF 121121 FT CF C 1F che Dato 121
Calcolo di Ulsm per RM Consideriamo due processi periodici 1 e 2 con tempi di esecuzione C1 e
C2 e periodi tali che T1 < T2. L’algoritmo RM assegna a 2 la priorità maggiore.
Def:
Aumentiamo il tempo di esecuzione C2 fino a che sia possibile schedulare.
Consideriamo i casi di prima, a) e b):
Caso a)
In questo caso, Allora, il fattore di utilizzazione è:
Dato che [.] è negativa, il minimo valore di U di ha per
1
2
T
TF
T2-T1F
FT - T 121 C 1)(FC - T 122 C
)1(
T
T
T
C1)1(
T
C
T
C1
T
)1(C - T
T
C
T
C
T
C U
1
2
2
1
2
1
1
1
2
12
1
1
2
2
1
1 FFF
FT - T 121 C
e il max valore ammissibile di C2 è
F è il numero di periodi completi di t1 all’interno di T2.
Calcolo di Ulsm per RM Caso b)
In questo caso
Quindi il max valore ammissibile per C2 è
Il fattore di utilzzazione è in questo caso:
In questo caso la quantità tra parentesi [.] è positiva e U descresce al diminuire di C1. Il minimo di U si ha per il minimo di C1, cioè
FT - T 121 C
T2-T1F
)FC - (T 112 C
FF
T
TF
T
TF
F
1
2
2
1
2
1
2
1
2
1
1
1
2
11
1
1
2
2
1
1
T
T
T
C
T
C
T
C
T
)C - (T
T
C
T
C
T
C U
FT - T 121 C
Calcolo di Ulsm per RM
Qual’è il valore minimo di U? Prendiamo il caso a). Sostituendo FT - T 121 C
1
21
2
1111
1
2
2
111)1(
T
T
2
121)1(
T
T
T
C1 U
1
2
1
2
2
1
T
TFF
T
TF
T
TF
T
TF
T
FTTF
Chiamando per semplicità a=T2/T1 si scrive:
Fa
FFa
a
F
a
FaFF
a
F
a
FaFaF
a
F2
)1(2121)1(1111 U
2
Questa funzione tende a per a 0, e per a . In
mezzo raggiunge un minimo. Il minimo si può valutare con dU/da=0 cioè 1-
F(1+F)/a2 =0 cioè
)1( FFa Il valore di U nel punto di minimo è:
FFFFFF
FF
FF
FFFFFFF
a
FaFFa2)1(22
)1(
)1(2
)1(
)1(2)1()1(2)1( U
2
nella espressione di U:
Calcolo di Ulsm per RM
Ricordiamo che cioè F è un numero intero: 1, 2, 3… perché T2>T1
U è crescente con F. Il minimo di F corrisponde al minimo di U, Ulsm, e vale
Ulsm = 2(21/2 – 1)
Si dimostra che la stessa relazione vale per numero di task maggiore di 2. Cioè il limite superiore minimo del fattore di utilizzazione del processore per la schedulazione Rate Monotonic vale, in generale per n task:
Ulsm = n(21/n – 1)Il valore decresce con n:
per n=2 Ulsm = 0.83
per n=3 Ulsm = 0.78
per n=4 Ulsm = 0.76
Per n tendente a l’espressione converge verso 0.69
1
2
T
TF
Calcolo di Ulsm per RM
Earliest Deadline First (EDF)
94
722
511
TiCi
U=1/5+2/7+4/9=0.93
Uno dei piu’ usati, Complessita’ O(n) (lista ordinata) Si seleziona dalla lista dei processi pronti quello la cui deadline e’ piu’ imminente Pre-emptive: se arriva un task con deadline minore sospensione Utilizzabile nei SO a base prioritaria (priorita’ alta=deadline vicina) La coda dei processi pronti ordinata (velocizzare) Teorema di schedulabilità: Condizione necessaria e sufficiente per la
schedulabilità e’ Ci/Ti 1 Ulsm=1
Esempio:
Semplice dimostrazione della schedulabilità: Condizione necessaria e sufficiente per la schedulabilità e’
Ci/Ti 1
Necessarietà: schedulabilità Ci/Ti 1 Per assurdo: supponiamo che sched U > 1. Per il teorema della non
schedulabilità si ha che se U>1 allora è non schedulabile. Questo contraddice l’ipotesi.
Sufficienza: Ci/Ti 1 schedulabilità Per assurdo: suffoniamo che Ci/Ti 1 NON schedulabile. Se è Non
schedulabile si può dimostrare che U > 1 cosa che contraddice l’ipotesi.
Earliest Deadline First (EDF)
Esempio Si considerino i seguenti 3 task periodici: C T
t1 2 4
t2 2 5
t3 2 6
Calcolo di U: U=2/4+2/5+2/6=1,23 I task non sono schedulabili
t2
t3
50 10
t1
EDF
?
t2
t3
50 10
t1
RM?
Esempio (cont.)
Facendo riferimento all’esempio della slide precedente: C T
t1 2 4
t2 2 5
t3 2 6 Vogliamo qui calcolare i tempi massimi di risposta usando la ricorrenza
Per RM le priorità decrescono da t1 a t3. Risulta quindi che t1 non può essere interrotto da nessun task, t2 può essere interrotto da t1 e t3 può essere interrotto da t1 e t2. Quindi (senza fare tutti i conti):
w1=C1=2<d1=T1=4
w02=C2=2; w1
2= C2 + ceil(w02/T1) C1 = 4; w1
3=4 < d2=T2=5
w03=C3=2; w1
3= C3 + ceil(w03/T1) C1+ceil(w0
3/T2) C2 =6; w23=10; w3
3=12; w43=14; w5
3=16; w6
3=18; w73=20; w7
3=20 che non è minore di d3!!
Esempio 1
Verificare la schedulabilità dei seguenti due task periodici con Rate Monotonic:
1o: calcolo del coefficiente di utilizzazione:
2o: calcolo del limite superiore:
Risposta: i due task periodici sono schedulabili con Rate Monotonic:
Esempio 2 Verificare la schedulabilità con RM dei seguenti tre task periodici:
Calcolo del coeff. di utilizzazione CPU e limite superiore:
I task periodici potrebbero essere schedulabili. Analisi del tempo di risposta nel caso peggiore:
Esempio 2 - cont
Analisi del tempo di risposta nel caso peggiore:
L’insieme di task è schedulabile con RM!
Esempio 3
Verificare la schedulabilità con RM dei seguenti task periodici:
Calcolo della utilizzazione del processore e del limite superiore
L’insieme di task non è schedulabile con RM
Esempio 4
Verificare la schedulabilità con EDF dei seguenti task periodici:
Test di schedulabilità: (Di=Ti)
L’insieme dei task è schedulabile con EDF
Esempio 4 - cont
Schedulazione:
Deadline Monotonic
Estensione del RM: schedulazione di processi periodici con deadline indipendenti dal periodo
Parametri: Ci = tempo massimo di esecuzione
Ti = periodo
Di = deadline relativa all’istante della richiesta
Di = di – ri
Ci <= Di <= Ti
Algoritmo: Viene schedulato il processo con la deadline relativa piu’ corta
Nei sistemi a base prioritaria, Pi = 1/Di
Test di schedulabilita’ ( condizione sufficiente): i
nii n
D
C)12( /1
Ti
Di
Ci di
RM vs EDF: Ottimalità
Rate Monotonic è ottimo per gli algoritmi a priorità fissa: priorità inversamente proporzionale al periodo
EDF è ottimo per gli algoritmi a priorità dinamica: priorità inversamente proporzionale alla deadline
Tutti i task schedulabili con RM sono anche schedulabili con EDF Ma: per n-> inf. RM può schedulare sicuramente con una
occupazione massima di 0.69 Mentre EDF può schedulare anche con una occupazione al
100%
RM vs EDF: Overhead Overhead di Calcolo
EDF deve ricalcolare le priorità ad ogni arrivo RM calcola le priorità una sola volta
Overhead di Context-switch Dovuto alla pre-emption EDF deve fare molte interruzioni per rispettare le priorità
Esempio di due task periodici (c, p): 1 (2,5), 2(4,7) U=0.97
t2
t3
50 10
t2
t3
50 10
RM
EDF
15Deadline mancata!
RM vs EDF: Overhead Numero di interruzioni: risultati di simulazione Valori medi, 1000 simulazioni, periodi random da 10 a 100, U=0.9 Per pochi task, il num di interruzioni cresce Per molti task, la durata scende (U=0.9!) e quindi scende il numero di interr.
Numero di task
Num
ero
di in
terr
uzio
ni
Server aperiodici a priorità fissa
Finora, schedulazione di processi omogenei: processi unicamente aperiodici processi unicamente periodici
Problema generale: schedulazione di task misti, cioe’ insiemi di task periodici e aperiodici
Ipotesi: tutti i processi periodici siano gestiti da algoritmi a priorita’
fissa tutti i processi periodici siano attivati simultaneamente tutti i processi aperiodici siano attivati dinamicamente
Problema maggiore: come garantire la ciclicita’ dei processi periodici senza ritardare troppo l’esecuzione dei processi aperiodici
Schedulazione in background
104J2
62J1
Ciai
aperiodici
I task aperiodici sono schedulati solo quando il processore e’ libero. Cioe’ quando non ci sono task periodici in esecuzione.
Starvation: tempo residuo insufficiente per i task aperiodici Inefficiente per i processi aperiodici, ma di facile realizzazione Possibile realizzazione: due code a priorita’ diversa. La coda a bassa priorita’ e’
servita solo quando la prima e’ vuota; un task periodico causa la pre-emption dei task aperiodici
Esempio in cui i task periodici sono schedulati con RM
104B
62A
TiCi
periodici
Schedulazione in background Garanzia task periodici: garantita indipendentemente dai task aperiodici
Garanzia task aperiodici di tipo hard real time:
- Identificare gli intervalli di tempo in cui il processore è libero.
- Sia H il MCM dei periodi (iperperiodo); la schedulazione periodica si ripete ogni H.
- Sia U il fattore di utilizzazione dell’insieme periodico.
- Il tempo disponibile per gli aperiodici è: = (1-U)H
Teorema
Condizione sufficiente per la schedulabilità in background di un task aperiodico con durata C e deadline D è data da:
C ---
H D
Polling Server (PS)
Processo periodico da dedicare ai processi aperiodici. Tempo di calcolo Cs ( Capacita’ del server)
PS serve le richieste aperiodiche in attesa (pendenti) Se non ci sono richieste in attesa, PS si sospende fino al periodo seguente;
la sua capacita’ e’ usata per l’esecuzione periodica Schedulazione dei processi periodici: RM o EDF
Esempio con EDFTask Ci Ti serverPeriodici a 2 6 Cs=2
b 3 8 Ts=7
Esempio con RMTask Ci Ti serverPeriodici a 1 4 Cs=2
b 2 6 Ts=5
Deferrable Server (DS) - Lehoczky et al., ‘87
Simile al PS: un server periodico serve le richieste aperiodiche MA: il DS conserva la propria capacita’ per tutto il periodo anche se
non ci sono richieste aperiodiche pendenti Migliora il tempo di risposta delle richieste aperiodiche (fornisce un
servizio immediato) Esempio: con RM le priorità sono a – DS – b, quindi DS si trova a
priorità media
Deferrable Server (DS) - Lehoczky et al., ‘87
Confronto con PS
0
PS
5 10 15 20 25
0 (2)
0 5
Ci Ti1 2 82 3 10PS 2 6
0 5
ape
Capacità PS Priorità alta
0
DS
5 10 15 20 25
0 5
0 5
Ci Ti1 2 82 3 10DS 2 6
ape
Capacità DS
Priorità alta
(1) (2) (1)
Deferrable Server (DS) - Lehoczky et al., ‘87
DS può migliorare il tempo di risposta degli aperiodici. Ma: il guadagno in termini di tempo di risposta si paga in termini di
schedulabilità. Esempio:
0 5 10 15 20 25
0 5
0 5
RM
0 miss
DS
Capacità DS
Deferrable Server (DS) - Lehoczky et al., ‘87
Limite Superiore Minimo con RM
Per n infinito
Dove Us è in fattore di utilizzazione di DS e Up dei periodici
1
12
2/1 n
s
slsm U
UnU
12
2ln
s
slsm U
UU
Priority Exchange - Lehoczky et al ‘87
Crea un server periodico per servire i task aperiodici MA: preserva la capacita’ del server scambiandola con il tempo di
esecuzione di un task periodico a priorita’ piu’ bassa Esempio:
Sporadic Server (SS) - Sprunt et al., ‘89
Non e’ un task periodico, ma un gestore di capacita’ La capacita’ viene consumata e ripristinata dinamicamente in funzione delle
richieste aperiodiche SS conserva la sua capacita’ fino all’arrivo di una richiesta aperiodica La capacita’ viene ripristinata solo dopo che essa sia stata consumata da una
richiesta aperiodica; riempimento agli istanti t+Ts Regole di ripristino: Se Cs > 0 il tempo di ripristino viene calcolato appena SS diventa attivo, e posto
uguale a tattuale + TSS Se Cs = 0 il tempo di riempimento viene valutato quando SS e’ attivo e Cs
diventa > 0 Il riempimento viene effettuato all’istante calcolato quando SS diventa disattivo
(idle) oppure se Cs e’ stata consumata L’ammontare del riempimento e’ uguale al tempo consumato nell’ultimo
intervallo di attivita’ Migliora il tempo di risposta delle richieste periodiche senza degradare il fattore
di utilizzazione
Sporadic Server (SS) - Sprunt et al., ‘89
Esempio di Sporadic Server:
Slack Stealer (SSt) - ‘92
Migliora i tempi di risposta delle richieste aperiodiche soft in presenza di attivita’ periodiche hard RT
SSt e’ un gestore della risorsa tempo Il tempo di esecuzione assegnato alle richieste aperiodiche viene
rubato ai task periodici Esempio:
Confronto prestazioni
Mediante simulazione discreta Insieme di 10 task periodici con periodi da 54 a 1200 e fattore di
utilizzazione complessivo pari a 69%. Task aperiodici variabili dal 5 al 30%. Tempi di interarrivo esponenziali
Un risultato rappresentativo:
Server Aperiodici a Priorità dinamica
I processi periodici sono schedulati mediante algoritmi a priorita’ dinamica (es. EDF).
Gli algoritmi dnamici permettono di raggiungere la piena utilizzazione del processore
Alcuni algoritmi: Earliest Deadline as Late as Possible (EDL) - ‘94
Algoritmo ottimo. I task attivi ordinati per deadline sono schedulati il piu’ tardi possibile
Earliest Deadline as Soon as Possible (EDS) - ‘95 I task attivi sono schedulati appena possibile secondo EDF
Dynamic Priority Exchange (DPE) - ‘95 In assenza di richieste aperiodiche la capacita’ del server non viene persa ma
viene scambiata con il tempo di esecuzione delle richieste periodiche a priorita’ piu’ bassa (cioe’ deadline piu’ alta)
Server Aperiodici a Priorità dinamica
Esempio di EDL e DPE:
Server Aperiodici a Priorità dinamicaTotal Bandwidth Server (TBS)
Spuri-Buttazzo 1996
Assegna una deadline più vicina ad ogni richiesta aperiodica – senza superare il limite di schedulabilità
Banda del server = fattore di utilizzazione del server Us
TBS assegna tutta la banda al momento disponibile disponibile alle richieste aperiodiche
Quando la k-esima richiesta aperiodica arriva al tempo t=rk, riceve una deadline
dk = max(rk, dk-1)+ Ck/Us d0=0
La richiesta aperiodica viene quindi schedulata con gli altri task periodici con EDF
Teorema di schedulabilitàCondizione necessaria e sufficiente per la schedulabilità di un insieme di task
periodici con fattore di utilizzazione Up con un TBS con fattore di utilizzazione Us è che Up + Us 1
Server Aperiodici a Priorità dinamica
Total Bandwidth Server (TBS) Esempio: Up=3/6 + 2/8 = ¾ Us=1/4 (Up+Us=1)
d1=r1+C1/Us=3+1/0.25=7 d2=r2+C2/Us=17 d3=17+C3/Us=21
50 10 15 2320
50 10 15 2320
50 10 15 2320
r1 d1 r2 r3 d2 d3
Altre problematiche dei sistemi operativi RT
Protocolli di accesso a risorse condivise bloccaggio che i processi possono subire durante l’accesso a
risorse comuni meccanismi classici non possibili: inversione di priorita’ Gestione dei sovraccarichi la richiesta di calcolo eccede la disponibilita’, e quindi non tutti
i processi possono terminare entro i vincoli temporali specificati uso di algoritmi di schedulazione “robusti” che usano un altro
parametro per decidere la schedulazione (l’importanza del task) Meccanismi di comunicazione tra processi dove possibile, semafori e memoria condivisa nei sistemi distribuiti, scambio di messaggi