Appunti di Software Engineering For Embedded Systems

B

valori di ed Otteniamo quindi una nuova

∆ = 5 = 200.

H

soluzione che contiene sincronizzazioni per il ciclo maggiore e

40

quindi può risultare difficile da ridisegnare lo schedule per

questa soluzione.

CAPITOLO 2. SISTEMI REAL-TIME 17

Timer-driven timer-driven

L’algoritmo di scheduling è un algoritmo di scheduling in cui il dispat-

cher si avvia per istanti di tempo irregolari (in questo caso il timer necessita di essere

riprogrammato).

Definiamo i seguenti parametri che verificano la schedulabilità di un problema:

Fattore di utilizzo del processore,

• rappresenta la frazione di tempo entro la

quale il processore risulta occupato ad eseguire i task. Si definisce come la som-

ma su tutti i task del rapporto tra il tempo di computazione del task ed il suo

τ

i

n C

periodo, ovvero .

i

X

:=

U T

i

i=1

ES:

Consideriamo il seguente task set:

Allora il fattore di utilizzo del processore risulta essere 10 10

= + +

U 25 40

(indica che il processore viene impiegato all’85%).

20 34

= = 0.85

100 40

Upper bound

• (limite del fattore di utilizzo per un ta-

superiore) (Γ,

U A) U

ub

sk set che viene schedulato da un algoritmo di scheduling In particolare,

Γ A.

utilizza completamente

se allora si dice che il processore

= (Γ, Γ

U U A),

ub

(ovvero il task set sta utilizzando il processore al massimo delle sue capacità).

Osserviamo che ogni task può avere un differente upper bound (quindi non è

detto che tutti i task riescano ad utilizzare il processore al 100%).

N.B: non tutti gli algoritmi di scheduling utilizzano il processore al 100%.

ES:

Ipotizziamo che il processore venga assegnato ai task in ordine cre-

scente dei periodi (ovvero si esegue prima il task con periodo minore).

CAPITOLO 2. SISTEMI REAL-TIME 18

Consideriamo i due seguenti casi:

Un task set con Osserviamo che se

24 26 56 '

= + = 0.833.

U

• ub

aumentiamo i tempi di computazione di e di le deadline

τ τ

1 2

non vengono più rispettate perciò quello ottenuto è il risultato

migliore che possiamo avere e quindi '

= 0.833.

U U

ub

Un task set con Osserviamo che

24 25 9

= + = = 0.9.

U

• ub 10

diminuendo il periodo di si aumenta il fattore di utilizzo .

τ U

2

Ogni task set possiede quindi un diverso upper bound sull’utilizzo del

processore.

Least upper bound

• (limite del fattore di utilizzo

superiore minimo) (A)

U U

lub

su un algoritmo di scheduling Si definisce come il minimo dei fattori di utilizzo

A.

su tutti i task set che utilizzano completamente il processore, ovvero (A) :=

U

lub

min (Γ,

U A).

ub

Γ

N.B: un task set risulta schedulabile da un algoritmo di scheduling se ≤

A U

mentre non è schedulabile se Possiamo invece avere una situazio-

(A), 1.

U U >

lub

ne incerta nel caso in cui (ovvero in questo caso non possiamo

≤

(A) 1

U < U

lub

concludere niente riguardo alla schedulabilità del task set).

CAPITOLO 2. SISTEMI REAL-TIME 19

N.B: il caso ottimo si verifica quando poiché viene eliminata l’incertezza

= 1

U

lub

sulla schedulabilità del task set.

Teorema: Se il fattore di utilizzazione del processore di un task set è più gran-

Γ

de di allora non è feasible.

1 Γ

Dim (si dimostra per assurdo):

Supponiamo Allora moltiplicando per l’iperperiodo (con

1.

U > H

otteniamo

0)

H > U H > H.

Di conseguenza, per la definizione di otteniamo:

U

n n

C H

i

X X

⇒

H>H C > H

i

T T

i i

i=1 i=1

Osserviamo che rappresenta il numero (intero) di volte in cui il task

H

T

viene eseguite nell’ipereriodo

i

τ H.

i

Quindi rappresenta il tempo di computazione richiesto dal task

H C τ

i i

T

nell’iperperiodo (ovvero la quantità di tempo in cui il task occu-

i H τ i

pa il processore durante l’iperperiodo).

n H

Perciò rappresenta il tempo totale di computazione

X C > H

i

T

i

i=1

richiesto dall’intero task set nell’iperperiodo

Γ H.

Osserviamo quindi che, poiché il tempo di computazione del task set

supera il tempo disponibile del processore allora il task non è

Γ H,

feasible.

C.V.D.

N.B: questo risultato vale in generale per ogni algoritmo di scheduling.

2.2.2 Priority-driven

priority-driven

Lo scheduling di tipo comprende gli algoritmi di scheduling che as-

segnano la priorità ai task sulla base dei loro vincoli temporali. L’obiettivo di questi

algoritmi è quello di costruire uno schedule ottimale tenendo conto dell’utilizzo del

processore e calcolando il tempo di risposta di ogni task.

Tali algoritmi di scheduling sono algoritmi di tipo online, ovvero prendono decisioni nel

momento in cui un task viene attivato (questo implica che il dispatcher non possiede

una tabella che indica gli istanti di esecuzione dei vari task).

N.B: lo stato di un sistema è l’insieme minimo di variabili che permettono di caratte-

rizzare la storia passata del sistema e di determinarne la storia futura.

Esistono diversi algoritmi di scheduling di questo tipo elencati di seguito.

Rate Monotonic

L’algoritmo di scheduling (RM) è un algoritmo di scheduling a priorità

rate monotonic

statica (ovvero una volta assegnata la priorità ad un task questa non cambia duran-

CAPITOLO 2. SISTEMI REAL-TIME 20

te l’esecuzione del task). Inoltre RM permette la preemption tra i task (ovvero è un

algoritmo di tipo preemptive).

L’algoritmo RM si applica a task periodici puri (cioè ). In particolare RM

∀τ

=

D T

i i i

assegna le priorità in modo inversamente proporzionale ai periodi dei task, ovvero si

assegna priorità maggiore ai task che hanno periodo minore.

ES:

Consideriamo il seguente esempio in cui priorità priorità

τ > τ >

A B

priorità :

τ C

Teorema (proprietà ): RM è ottimo rispetto alla feasibility tra

dell’ottimalità di RM

tutti gli algoritmi a priorità fissa (ovvero per algoritmi di scheduling applicati a task

periodici che hanno le deadline uguale ai periodi).

Tale teorema comporta due affermazioni equivalenti:

• Se uno schedule a priorità fissa è feasible per un task set allora anche lo sche-

Γ,

dule RM è feasible per Γ.

• Se lo schedule RM non è feasible per un task set allora nessuno schedule a

Γ,

priorità fissa è feasible per Γ.

Da queste affermazioni consegue che, poiché ogni task raggiunge il suo tempo di rispo-

sta peggiore nel suo istante critico, allora è sufficiente verificare l’ottimalità agli istanti

critici. Quindi possiamo riformulare il teorema precedente nel seguente modo:

Teorema: se uno schedule a priorità fissa è feasible per un task set agli istanti criti-

Γ

ci, allora anche lo schedule RM è feasible per agli istanti critici.

Γ

Dim:

Consideriamo per semplicità un task set che possiede due task e con

Γ τ τ

1 2

(tale dimostrazione può essere facilmente estesa ad un task set con

T < T

1 2

task).

n

N.B: da questa ipotesi possiamo facilmente osservare che priorità τ >

1

priorità .

τ 2

Se consideriamo un algoritmo a priorità fissa che non sia RM, allora asse-

gneremo priorità maggiore a (ovvero priorità priorità ). Perciò in

τ τ > τ

2 2 1

questo caso caso lo schedule risulta feasible per il task set agli istanti cri-

Γ

CAPITOLO 2. SISTEMI REAL-TIME 21

tici se .

≤

+

C C T

1 2 1

Quindi per dimostrare il teorema è sufficiente dimostrare che se ≤

+

C C

1 2

, allora lo schedule RM è feasible per agli istanti critici

Γ

T

1

Definiamo il numero di periodi di interamente contenuti in .

T

b c

:=

F τ T

2 1 2

T

Per ipotesi, se le priorità vengono assegnate secondo l’algoritmo di schedu-

1

ling RM, allora priorità priorità .

τ > τ

1 2

Si distinguono quindi 2 casi:

• Caso 1: (ad esempio tutti i job di rilasciati entro

−

C < T F T τ

1 2 1 1

l’intervallo vengono completati prima che il secondo job di

[0, )

T τ

2 2

venga rilasciato).

In questo caso il task risulta schedulabile se .

≤

(F + 1)C + C T

1 2 2

Si dimostra che e quindi .

≤ ≤

+ (F + 1)C +

C C T C T

1 2 1 1 2 2

In particolare , poiché

≤ ⇒ ≤ ≥

+ + 1.

C C T F C F C F T F

1 2 1 1 2 1

Quindi , poiché

≤ ≤ ≥

+ + 1.

F C F C F C F C F T F

1 2 1 2 1

Di conseguenza , poiché

≤

(F + 1)C + +

C F T C < T

1 2 1 1 2

.

−

C < T F T

1 2 1

In conclusione .

(F + 1)C + C < T

1 2 2

• Caso 2: (ad esempio alcuni job di rilasciati entro

≥ −

C T F T τ

1 2 1 1

l’intervallo non vengono completati prima che il secondo job di

[0, )

T 2

venga rilasciato).

τ

2

In questo caso il task risulta schedulabile se .

≤

+

F C C F T

1 2 1

Si dimostra che e quindi , poiché

≤ ≤

+ +

C C T F C F C F T

1 2 1 1 2 1

≥ 1.

F

Quindi , poiché

≤ ≤ ≥

+ + 1.

F C F C F C F C F T F

1 2 1 2 1

Di conseguenza .

≤

+

F C C F T

1 2 1

CAPITOLO 2. SISTEMI REAL-TIME 22

C.V.D.

Teorema (test o

di garanzia di Liu & Layland limite di Liu & Layland):

se per un tasket di task periodici puri, allora risulta essere

1/n

≤ − 1) Γ Γ

U n(2 n

schedulabile con RM.

N.B: il teorema è solo sufficiente, ovvero un insieme di task risulta essere schedulabi-

le con RM se vale la relazione definita per il test, altrimenti non possiamo concludere

niente (cioè ci troviamo nella regione di indecisione).

N.B: il test ha complessità polinomiale rispetto