Server aperiodici a priorità dinamica
Introduzione
11
Verranno descritti alcuni algoritmi per il servizio di task aperiodici in un contesto in cui i task periodici vengono schedulati con EDF.
L'uso di algoritmi dinamici permette di raggiungere la piena utilizzazione del processore, permettendo di avere tempi di risposta migliori per i task aperiodici rispetto ai server a priorità statica.
Server a priorità dinamica
22
Verranno trattati i seguenti server a priorità dinamica:
- DSS: Dynamic Sporadic Server
- TBS: Total Bandwidth Server
- CBS: Constant Bandwidth Server
- EDL: Earliest Deadline Late - Cenni
Dynamic Sporadic Server
33
Il Dynamic Sporadic Server (DSS) rappresenta un'estensione dello Sporadic Server ai sistemi a priorità dinamiche.
Esso è caratterizzato da una capacità Cs e da un periodo T
s.
La sua capacità non viene ripristinata la valore iniziale di ogni periodo, ma solo quando viene consumata.
DSS - Replenishment rule - 1
44
Gli istanti di tempo in cui avviene il ripristino della capacità vengono calcolati in base ad una regola di riempimento che consente di raggiungere la piena utilizzazione del processore.
A differenza di SS, che ha una priorità statica fissata in base al periodo, DSS ha una priorità dinamica assegnata mediante una deadline opportuna.
DSS - Replenishment rule - 2
55
L'assegnamento della deadline e il riempimento della capacità sono definiti da particolari regole.
1) Alla creazione del server si pone Cs pari a C
S0, valore massimo della
capacità.
2) Se Cs > 0 e la coda aperiodica è vuota il successivo istante di
riempimento e la deadline del server vengono decisi al prossimo arrivo di una richiesta aperiodica.
DSS - Replenishment rule - 3
66
3) Se Cs = 0 e ci sono richieste aperiodiche pendenti, il successivo
istante di riempimento e la deadline del server vengono decisi appena C
s diventa maggiore di zero.
4) L'istante di riempimento RT e la deadline Ds vengono posti uguali a
RT = ds = t + T
s, con t istante corrente.
DSS – Esempio - 1
77
Si considerino i task Ta e T
b con le seguenti caratteristiche:
Ad essi aggiungiamo un DSS con le seguenti caratteristiche:
CS0
= 3 e Ts = 6
2 8
3 12
Ci
Ti
Τa
Τb
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
2
RT1 = d
s = t + T
S = 9
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
2
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
2
2
RA1 = 2
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2
RT2 = d
s = t + T
S = 12
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
RA2 = 1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
RT3 = d
s = t + T
S = 15
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
RA3 = 1
1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1 1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1 1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1 1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2
1
RT4 = d
s = t + T
S = 20
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1
RA4 = 3
3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 33
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Esempio - 2
77
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
22
2 1
2 1
1 3
DSS – Schedulabilità - 1
Si noti che, in un sistema basato su schedulazione dinamica con EDF la domanda di calcolo di un task aperiodico in un intervallo [t
1, t
2], dove t
1
coincide con un tempo di richiesta, si ha:
C p floor t 2−t1
T i
C i
t2t
188
DSS – Schedulabilità - 2
Visto che:
1) L'ammontare del riempimento è sempre minore o uguale a CS0
.2) La capacità non viene ripristinata prima di un intervallo T
s
dall'istante in cui è stato calcolato l'ammontare.
Nel caso peggiore DSS si comporta come un task aperiodico di periodo T
S e capacità C
S.
Cape floor t2−t1
T S
CS
99
DSS – Schedulabilità - 3
Pertanto, dato un insieme di task periodici con fattore di utilizzazione U
P ed un DSS con fattore di utilizzazione U
S si ha che l'insieme totale è
schedulabile con EDF se e solo se
U PU S1
1010
DSS - Conclusioni
Con DSS se il periodo del server è lungo l'esecuzione delle richieste aperiodiche può essere ritardato notevolmente.
Una soluzione potrebbe essere diminuire il periodo del DSS per migliorare il tempo di risposta.
Questo però comporta un overhead dovuto ai numerosi context switch che DSS causerebbe.
1111
Total Bandwidth Server
Migliorare il tempo di risposta ottenuto con DSS è possibile assegnando deadline più vicine alle richieste aperiodiche.
Ovviamente tale assegnamento deve essere fatto senza compromettere la schedulazione dei task periodici hard.
Il Total Bandwidth Server (TBS) si basa su questa idea.
1212
TBS - Definizione
Quando arriva la k-esima richiesta aperiodica al tempo t = rk, essa
riceve una deadline pari a
dove Ck è il tempo di esecuzione della richiesta aperiodica e U
S è il
fattore di utilizzazione del server.
Per definizione si ha d0 = 0.
US è detta banda del server.
1313
d k=max r k , d k−1C k
U S
TBS - Note
Una volta assegnata la deadline la richiesta aperiodica può essere schedulata con EDF insieme agli altri task periodici.
Si noti che basta considerare la deadline (dk-1
) dell'ultimo task aperiodico per calcolare la banda da assegnare.
1414
TBS – Esempio - 1
Si considerino i task Ta e T
b con le seguenti caratteristiche:
Ad essi aggiungamo un TBS con fattore di utilizzazione US = 1/4
3 6
2 8
Ci
Ti
Τa
Τb
1515
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
d1 = r
1 + C
1/U
S = 3 + 1/0.25 = 7
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
d2 = r
2 + C
2/U
S = 9 + 2/0.25 = 17
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
d3 = max (r
3, d
2) + C
3/U
S = 17 + 1/0.25 = 21
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Esempio - 2
Ta
Tb
Richieste aperiodiche
Ta
Tb
1616
0 2 4 6 8 10 12 14 16 18 20 22
1
d1
2
d2
1
d3
TBS – Schedulabilità
Il server TBS si comporta come un task periodico equivalente.
In qualunque intervallo [t1, t
2], dove t
1 coincide con l'arrivo di una
richiesta aperiodica, si ha
Sulla base di questo risultato un insieme di task periodici in presenza di un server TBS può essere schedulato se e solo se
Cape
t 2−t1
U S
1717
U PU S1
TBS – Considerazioni
L'algoritmo TBS è computazionalmente molto semplice, di conseguenza l'overhead introdotto è molto basso.
Inoltre, esso è in grado di ottenere ottime prestazioni in termini di tempo di risposta dei task aperiodici.
Purtroppo esso è condizionato dal fatto di “fidarsi” dei tempi di calcolo delle richieste aperiodiche, non avendo una capacità che limiti la loro richiesta di banda.
1818
Constant Bandwidth Server
Per far fronte alla limitazione del TBS è possibile modificarlo reintroducendo il concetto di budget.
Se una richiesta aperiodica consuma tutto il tempo assegnatole essa verrà rischedulata in maniera tale da non intaccare i task periodici.
Il Constant Bandwidth Server è simile al TBS, ma introduce un meccanismo di protezione che assicura che la banda U
S allocata al
server non venga superata.
1919
CBS - Definizioni
Il CBS viene definito attraverso due grandezze:
un periodo TS ed una capacità Q
S
Il rapporto QS/T
S viene detto banda del server.
Inoltre, il CBS gestisce due variabili interne che definiscono il suo stato:
cs – rappresenta il budget attuale al tempo t
ds – rapresenta la deadline attuale assegnata ad una richiesta
Entrambi sono inizializzati a zero.
2020
CBS - Funzionamento
Ad ogni richiesta viene assegnato un budget iniziale pari a QS e una
deadline iniziale pari a TS.
Se la richiesta termina entro il budget assegnato si passa alla eventuale richiesta aperiodica successiva.
Se la richiesta consuma tutto il budget, ne viene assegnato uno nuovo, spostando la deadline in avanti di un periodo T
S.
2121
CBS – Regole - 1
L'algoritmo del CBS funziona in base alle seguenti regole:
1) Se una richiesta arriva mentre l'attuale richieste è attiva, essa viene messa in coda (ad es. FIFO).
2) Quando il budget cs si esaurisce esso viene posto uguale al valore
massimo (cs = Q
S) e la deadline attuale posticipata a d
s_new = d
s + T
S.
2222
CBS – Regole - 2
3) Se una richiesta viene completata, il server preleva, se esiste, la succesiva richiesta in coda, schedulandola con il budget e la deadline attuali.
4) Se arriva una richiesta in un istante t nel quale il server è inattivo, si controlla se è possibile riciclare il budget e la deadline attuali del server. In particolare, se risulta che c
s ≤ (d
s - t) U
S la richiesta può essere
schedulata con i valori attuali del server, altrimenti il budget viene ricaricato al valore massimo(c
s = Q
S) e la deadline attuale posticipata a
ds_new
= t + TS.
2323
CBS – Esempio - 1
2424
Si considerino i task Ta e T
b con le seguenti caratteristiche:
Ad essi aggiungamo un CBS con banda US = 1/3, in modo da avere
US + U
p = 1
Scegliamo Qs = 2 e T
s = 6
2 6
3 9
Ci
Ti
Τa
Τb
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d1
R4: CBS idle, cs = Q
s e d
s = t + T
s = 8
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d1
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d1
R2: budget esaurito – cs = Q
s e d
s_new = d
s + T
s = 14
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d2
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d3
R4: CBS idle, cs > (t – d
s) U
s, c
s = Q
s e d
s = t + T
s = 18
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d3
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d3
R2: budget esaurito – cs = Q
s e d
s_new = d
s + T
s = 24
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d4
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d41
R4: CBS idle, cs < (t – d
s) U
s, si usano c
s e d
s attuali
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d41
R2: budget esaurito – cs = Q
s e d
s_new = d
s + T
s = 30
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d41
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d41
CBS – Esempio - 2
2525
Ta
Tb
Ta
Tb
Richieste aperiodiche
Cs
0 2 4 6 8 10 12 14 16 18 20 22
d0 3
d23
d41
Earliest Deadline Late
Come lo Slack Stealer per i server a schedulazione statica Earliest Deadline Late (EDL) utilizza il concetto di slack per gestire le richieste aperiodiche.
I task periodici vengono ordinati per deadline più imminente, ma vengono schedulati il più tardi possibile.
Lo slack ottenuto in tale maniera può essere utilizzato per gestire le richieste aperiodiche.
2626
Earliest Deadline Late
EDL è un algoritmo molto pesante, dovendo continuamente aggiornare una funzione di disponibilità che permette di calcolare l'idle time disponibile.
Esso è un punto di riferimento per tutti gli algoritmi, essendo ottimo dal punto di vista dei tempi di risposta dei task aperiodici in sistemi a priorità dinamiche.
2727