Algoritmi Priority-Driven
Corso di Sistemi RT
Prof. Davide Brugali
Università degli Studi di Bergamo
Classification of Tasks
 We associate a period pi with each task Ti.
 Periodic Tasks:
 pi is the exact time between job releases
 Sporadic Tasks:
 pi is the minimum time between job releases
 Aperiodic Tasks:
 Released at arbitrary times (no period)
 Tasks have no deadline or a soft deadline
2
Task aperiodici e sporadici
 In task aperiodici o sporadici i tempi di interarrivo tra
due job consecutivi non sono noti a priori e possono
essere arbitrariamente brevi.
 I job di un task sporadico hanno tempi di interarrivo
modellati da variabili stocastiche con identica
distribuzione A(x) e tempi di esecuzione modellati da
variabili stocastiche con identica distribuzione B(x). Ciò
significa che il sistema è stazionario (almeno in H). I job
di un task aperiodico hanno solo soft deadline.
 I job di un task aperiodico hanno release time casuali e
hard deadline.
3
Classification of Scheduling Algorithms
All scheduling algorithms
static scheduling
(or offline/clock-driven)
dynamic scheduling
(or online/priority-driven)
static-priority
scheduling
RM
4
dynamic-priority
scheduling
EDF
Scheduling prioritario
5
Approccio priority-driven
6
Approccio priority-driven
7
Approccio priority-driven
 Algoritmi priority-driven che assegnano le priorità in
base al release time
 FIFO (FCFS): First-In-First-Out (First Come First Served)
 LIFO : Last-In-First-Out
 Algoritmi priority-driven che assegnano le priorità in
base all’execution time
 SETF : Shortest-Execution-Time-First
 LETF : Longest-Execution-Time-First
8
First Come First Served (Non RT)
9
First Come First Served (Non RT)
10
Shortest Job First (SJF) (Non RT)
11
Ottimalità di SJF
12
Ottimalità di SJF
13
SJF è adatto per il Real-Time?
14
Scheduling prioritario
15
Esempio: priority-driven nonpreemptive
16
Esempio: priority-driven nonpreemptive
LET : Longest Execution Time First
17
Esempio: priority-driven nonpreemptive
18
Esempio: priority-driven (non)preemptive
J1:3
J2:1
J3:2
J5:2
J6:4
J7:4
J8:1
preemptive
nonpreemptive
19
{
{
P1
P2
(J1, J2, …, J8)
(J
1, J2, J3, J4, J7, J6, J5, J8)
J1
J2
P1
P2
J4:2
J4
J3
J1
J2
J7
J7
J5
J4
J3
J6
J8
J5
J7
J6
J8
Round Robin (Non RT)
20
Round Robin
21
Round Robin
22
Multi-level scheduling
23
Algoritmi Real Time
24
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)
25
EDD - Lateness
26
EDD – Maximum Lateness
27
EDD - Ottimalità
28
EDD - Ottimalità
29
EDD - Guarantee test (off line)
30
Earliest Deadline First (Dinamico)
31
EDF
32
Algoritmo EDF
33
Esempio - EDF
34
Limiti di EDF
35
EDF non è sempre ottimo
36
Non ottimalità di EDF
J1
37
J3
J2
Ottimalità di EDF
38
Ottimalità di EDF
39
EDF Guarantee test (on line)
40
Altri criteri di ordinamento delle priorità
Non è quindi un algoritmo priority-driven in senso stretto
41
Latest Release Time
42
Ottimalità LRT
43
Algoritmo LST / MLF
 Least Slack Time First (LST), chiamato anche
 Minimum Laxity First (MLF)
44
Anomalie di scheduling
 È difficile validare il rispetto delle deadline di tutti I job schedulati
secondo algoritmi priority-driven quando i parametri temporali dei job
variano.
 Si possono verificare delle anomalie di schedulazione.
 Esempio
 Il sistema comprende due processori.
 Un’unica coda di priorità.
 Il sistema comprende quattro job.
J1 (0, 10), 5
J2 (0, 10), [2,6]
J3 (4, 15), 8
J4 (0, 20), 10
 I job sono preemptable ma non possono migrare
 Il tempo di esecuzione di un job non è noto con esattezza ma è sicuramente
contenuto in un intervallo limitato.
 L’ordine di priorità è : J1 > J2 > J3 > J4
45
Anomalie di schedulazione
P1
J1
P2
J2:6
P1
J1
P2
J2:2
P2
46
J3
J4
P1
J1 (0, 10), 5
J2 (0, 10), [2,6]
J3 (4, 15), 8
J4 (0, 20), 10
J4
J3
J4
J1
J2:3
J4
P1
J1
P2
J2:5
J3
J4
J3
J4
Anomalie di scheduling : esempio
47
Anomalie di scheduling : esempio
48
Anomalie di scheduling : esempio
49
Anomalie di scheduling : esempio
50
Anomalie di scheduling : esempio
51
Anomalie di scheduling : esempio
52
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
53
Algoritmo Rate Monotonic (RM)
 È 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 T1 T2 T3 T1 T3 T2 T1 T3 T2 T1 T2
0
54
4
8
12
16
T1
20
Rate Monotonic: 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
55
Rate Monotonic: schedulability test
Theorem:
A set of independent periodic tasks scheduled by the rate monotonic
algorithm will always meet its deadlines , for all task, if
m
 ci * f i  m(2
 1)
where
i1
ci = worst-case task execution time of task i
fi = frequency of task i
m= number of tasks
1/ m
 For D=T task sets only
 A simple sufficient but not necessary schedulability test exists
56
Value of the threshold factor
57
1/m
1.5
1
Reeks1
0.5
m
0
20
48
12
5
3
0
1
m*(2 -1)
1
0.828427125
0.77976315
0.75682846
0.743491775
0.73477229
0.713557132
0.703253679
0.698176077
0.695655573
0.694349702
m*(2**(1/m)-1)
m
1
2
3
4
5
6
12
24
48
96
200
Example
name
tsk 1
tsk 2
tsk 3
3
execution time
[msec]
20
40
100
 ci * f i 
i1
name
tsk 1
tsk 2
tsk 3
period
[msec]
100
150
350
20 40 100


 0753  3(21/3 1)  0.779
100 150 350
priorities
high
middel
low
T1
T2
200
100
150
T3
58
Deadline
[msec]
100
150
350
350
Algoritmo Deadline Monotonic (DM)
 È 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
50
100
150
200
250
T2
62.5
125
T3
125
59
187.5
250
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.
60
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
50
100
150
200
250
T2
62.5
125
187.5
250
T3
125
61
Missed deadline
EDF per Task Periodici
62
Esempio RM
63
Esempio EDF
64
Vantaggi di EDF rispetto Fixed P.
65
Effetto domino
66
Effetto domino
67
Deadlines diverse dal periodo
68