Sistemi e schedulazione in tempo reale E.Mumolo [email protected].

Sistemi e schedulazione in tempo reale E.Mumolo

[email protected]

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


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


• 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 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


Rispettare le deadline:

SoftReal-time

NonReal-time

HardReal-time

Simulazionisoftware

Interfacciautente

Video suinternet

Telecom appl. Controllo elettronicodi un motore

Sistema dicontrollodi un missile

Streaming


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


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



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


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.


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


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:


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

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


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)


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


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)


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


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

Sistemi e schedulazione in tempo reale E.Mumolo [email protected].

Documents

Transcript of Sistemi e schedulazione in tempo reale E.Mumolo [email protected].