Schedulazione real-time di task PERIODICI

Sono la maggioranza delle attività 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 è costante La deadline coincide con la fine del periodo corrente Tutti i task sono indipendenti

Quindi, un processo periodico è 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 più lungo

tempo di risposta Zona critica: intervallo tra istante critico e istante di

completamento dell’istanza. Equivale al tempo di risposta più lungo.

Schedulazione di task periodici

Fattore di utilizzazione del processore U è la frazione di tempo utilizzata dalla CPU per eseguire l’insieme

di task (è una misura della occupazione del tempo di CPU per eseguire un insieme di task periodici)‏

In un insieme di n task:

Il processore è “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. è il carico massimo gestibile da un algoritmo di schedulazione.

Schedulazione di task periodici

Zona di schedulabilità per qualsiasi insieme

Ulsm1

Ulsm2

Ulsm3

Ulsm4

Ulsm1Ulsm

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

Schedulazione di task periodici Teorema di schedulabilità generaleCondizione 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 τi viene eseguito in T, mentre (T/Ti)Ci rappresenta il tempo di calcolo richiesto dal task τi 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

R ≤ D

volte

Schedulazione di task periodici

Solve by forming a recurrence relationship:

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 priorità

direttamente proporzionale alla propria frequenza di richiesta (task con periodo breve priorità elevata)‏

Chiamato anche Shortest Period First (SPF)‏ Pre-emptive, statico Proprietà: RM è ottimo, nel senso che se un insieme di task NON è

schedulabile con RM, allora non è schedulabile con nessun altra regola di assegnazione a priorità fisse

Schedulazione di task periodici a priorità fissa: Rate Monotonic

•Altro esempio:

Schedulazione di task periodici: Rate Monotonic

Teorema della ottimalità di RM Se un insieme di task periodici NON è schedulabile con RM,

allora non esiste un algoritmo di schedulazione a priorità fissa per quell’insieme di task.

Dim. Si afferma che: se un insieme di task non è schedulabile con RM

non esiste altra schedulazione.

Cioè: se esiste una schedulazione è 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, cioè facciamo prima τ2 poi τ1. Affinché sia fattibile:

(1) C1+C2 <= T1

Supponiamo ora di usare RM. Ci sono due possibili casi:Caso a)‏

Cioè tutte le richieste di t1 vengono completate entro T2. Cioè C1<=Δ

Affinchè RM sia fattibile, deve essere Mostriamo che, se vale (1), allora RM è fattibile. Moltiplicando (1) per F:

CVD

Schedulazione di task periodici: Rate Monotonic

τ2

τ1

Δ=T2-F.T1

Schedulazione di task periodici: Rate MonotonicCaso b)

L’ultima esecuzione di τ1 si sovrappone con τ2. Cioè: In questo caso, RM è fattibile se:

CVD

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

T2-T1F

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è

T2-T1F

Calcolo di Ulsm per RM

Qual’è il valore minimo di U? Prendiamo il caso a). Sostituendo

Chiamando per semplicità a=T2/T1 si scrive:

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è

Il valore di U nel punto di minimo è:

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

Calcolo di Ulsm per RM

Earliest Deadline First (EDF)‏

94τ3

72τ2

51τ1

TiCi

U=1/5+2/7+4/9=0.93

Uno dei più usati, Complessità O(n) (lista ordinata)‏ Si seleziona dalla lista dei processi pronti quello la cui deadline è più imminente Pre-emptive: se arriva un task con deadline minore sospensione Utilizzabile nei SO a base prioritaria (priorità alta=deadline vicina)‏ La coda dei processi pronti ordinata (velocizzare)‏ Teorema di schedulabilità: Condizione necessaria e sufficiente per la

schedulabilità è ΣCi/Ti ≤ 1 Ulsm=1

Esempio:

Semplice dimostrazione della schedulabilità: Condizione necessaria e sufficiente per la schedulabilità è

Σ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 τ1 2 4 τ2 2 5 τ3 2 6

Calcolo di U: U=2/4+2/5+2/6=1,23 I task non sono schedulabili

τ2

τ3

50 10

τ1

EDF

?

τ2

τ3

50 10

τ1

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;

w53=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 più corta

Nei sistemi a base prioritaria, Pi = 1/Di

Test di schedulabilità ( condizione sufficiente):

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