Corso di Sistemi RT

Prof. Davide Brugali

Università degli Studi di Bergamo

Algoritmi Priority-Driven RT

Algoritmi Real Time

2

Earliest Due Date (statico)

Seleziona il task con la deadline relativa più

imminente [Jackson’ 55].

Tutti i tasks arrivano simultaneamente

Le priorità sono fisse (Di è nota in anticipo)

La preemption non è un problema

Minimizza la massima lateness (Lmax)

3

EDD - Lateness

4

EDD – Maximum Lateness

5

EDD - Ottimalità

6

EDD - Ottimalità

7

EDD - Guarantee test (off line)

8

Earliest Deadline First (Dinamico)

9

Earliest Deadline First (EDF) - DINAMICO

10

Algoritmo EDF

11

Esempio - EDF

12

Limiti di EDF

13

EDF non è sempre ottimo

14

Non ottimalità di EDF

J1 J3 J2

15

Ottimalità di EDF

16

Ottimalità di EDF

17

EDF Guarantee test (on line)

18

Altri criteri di ordinamento delle priorità

Non è quindi un algoritmo priority-driven in senso stretto

19

Latest Release Time

20

Ottimalità LRT

21

Algoritmo LST / MLF

Least Slack Time First (LST), chiamato anche

Minimum Laxity First (MLF)

22

Modello per task periodici

Insieme di task : T1, T2, …, Tn

Ogni task consiste di job : Ti={Ji1, Ji2, … Jim}

Ogni task ha un execution time ei

Ogni task è caratterizzato da un periodo pi

Ogni task è caratterizzato da una relative deadline Di

Ogni task ha una phase i

Task T1 = {i, pi, ei, Di}

Task T1 = {pi, ei, Di} i = 0

Task T1 = {pi, ei} i = 0, Di = pi

L’insieme di task è caratterizzato dall’ Hyperperiod H

L’utilization di un task è : ui = ei / pi

Total utilization U = ui

23

Algoritmo Rate Monotonic (RM) - STATICO

È un fixed-priority algorithm.

Assegna le priorità ai task in base ai loro periodi. Più breve è il periodo, più alta è la priorità.

La rate (frequenza) dei tempi di rilascio dei job è pari all’inverso del periodo del task.

Consideriamo un sistema di tre task periodici

T1 = (4, 1); T2 = (5, 2); T3 = (20, 5)

P(T1) > P(T2) > P(T3)

T1 T2 T3

4 8 12 16 20

T1 T2

0

T1 T2 T3 T1 T2T3 T1 T3 T2 T1

24

Rate Monotonic (RM): Priority Assignment

Each process is assigned a (unique) priority based on its period; the

shorter the period (the higher the frequency), the higher the priority

These priorities do not change;

The tasks are scheduled according to their priorities, i.e. a ready

task with highest priority is executed until a higher priority task

becomes ready. Such higher priority task then pre-empts the lower

priority task.

This assignment is optimal in the sense that if any process set can

be scheduled (using pre-emptive priority-based scheduling) with a

fixed-priority assignment scheme, then the given process set can

also be scheduled with a rate monotonic assignment scheme

25

Rate Monotonic: schedulability testTheorem:

A set of independent periodic tasks scheduled by the rate monotonic

algorithm will always meet its deadlines , for all task, if

where

ci = worst-case task execution time of task i

fi = frequency of task i

m= number of tasks

ici1

m

i* f m(21/ m 1)

For D=T task sets only

A simple sufficient but not necessary schedulability test exists

26

Value of the threshold factor

m m*(21/m

-1)

1 1

2 0.828427125

3 0.77976315

4 0.75682846

5 0.743491775

6 0.73477229

12 0.713557132

24 0.703253679

48 0.698176077

96 0.695655573

200 0.694349702

0

0.5

1

1.5

1 3 512

48

200

m

m*(2

**(1

/m)-1

)

Reeks1

27

Example

name execution time

[msec]

period

[msec]

Deadline

[msec]

tsk 1 20 100 100

tsk 2 40 150 150

tsk 3 100 350 350

ici1

3

i* f 20

100

40

150

100

350 0753 3(21/3 1) 0.779

name priorities

tsk 1 high

tsk 2 middel

tsk 3 low

T1

T2

T3

100

150

350

200

28

Algoritmo Deadline Monotonic (DM) - STATICO

È un fixed-priority algorithm.

Assegna le priorità ai task in base alle loro relative deadline. Più breve è la relative deadline, più alta è la priorità.

La rate (frequenza) dei tempi di rilascio dei job è pari all’inverso del periodo del task.

Consideriamo un sistema di tre task periodici T1 = (50, 50, 25,100); T2 = (0,62.5,10,20); T3 = (0,125,25, 50)

P(T2) > P(T3) > P(T1) T = {i, pi, ei, Di}

T1

T2

T3

50 100 150 200 250

62.5 125 187.5 250

125

29

Deadline monotonic priority assignment Theorem: A deadline monotonic priority assignment is

optimal for set of independent events with responses

that execute at a constant priority and for deadlines that

are at or before the end of the period.

30

Confronto RM - DM

Quando la relative deadline di ogni task è proporzionale al suo periodo, gli algoritmi RM e DM sono identici

Quando la relative deadline è arbitraria, l’algoritmo DM è migliore, nel senso che può (a volte) produrre uno schedule feasible quando RM fallisce.

Quando invece l’algoritmo DM fallisce, di sicuro RM fallisce.

L’esempio in figura mostra che l’algoritmo RM fallisce perché non riesce a rispettare tutte le deadline.

T1

T2

T3

50 100 150 200 250

62.5 125 187.5 250

125Missed deadline

31

EDF per Task Periodici

32

Esempio RM

33

Esempio EDF

34

Vantaggi di EDF rispetto Fixed P.

35

Effetto domino

36

Effetto domino

37

Deadlines diverse dal periodo

38