Corso di Sistemi RT
Prof. Davide Brugali
Università degli Studi di Bergamo
Algoritmi Priority-Driven RT
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
Altri criteri di ordinamento delle priorità
Non è quindi un algoritmo priority-driven in senso stretto
19
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