Sistemi Real-Time
Ing. Rigutini Leonardo
Dipartimento di Ingegneria dell’informazione
Università di Siena
Sistema Real-Time
• Sistema in cui la correttezza non dipende solamente
dai valori di output ma anche dal tempo con cui tali
risultati sono prodotti
• REAL TIME significa che il tempo di sistema deve
essere sincronizzato con il tempo dell’ambiente
Input x(t)
RT
System
t
Ambiente
Output y(t+Δt)
Rigutini Leonardo – Sistemi Real-Time
t
Slide n° 2
Tipiche applicazioni Real-Time
• Sistemi militari per la difesa
• Controllo di impianti nucleari o chimici
• Robotica
• Sistemi di gestione scambi ferroviari
• Sistemi di monitoraggio (aereo, ferroviario …)
• Sistemi di telecomunicazioni
Rigutini Leonardo – Sistemi Real-Time
Slide n° 3
Approccio tradizionale
Molte applicazioni RT sono sviluppate con metodi empirici:
• Programmazione assembler
• Temporizzazione tramite timer dedicati
• Controllo attraverso programmazione dei driver
• Manipolazione delle priorità
Svantaggi:
• Programmazione noiosa e dipendente dalle capacità
umane
• Codice poco leggibile
• Difficile manutenzione
• Difficile verifica dei vincoli temporali
Rigutini Leonardo – Sistemi Real-Time
Slide n° 4
Progetto di un sistema RT
• La fase di test, anche se necessaria, non permette una
verifica completa del sistema
• La predicibilità deve essere migliorata a livello di
kernel
• Gestione dei sovraccarichi (Overload handling)
• Tolleranza ai guasti (Fault-Tolerance)
• I sistemi critici devono essere progettati con
assunzioni pessimistiche (legge di Murphy)
Rigutini Leonardo – Sistemi Real-Time
Slide n° 5
Real-Time ≠ Veloce
Real-Time non è un sistema veloce:
• La velocità è relativa all’ ambiente
– Es. tartaruga e topolino
• Essere più veloce è un vantaggio ma non garantisce
la correttezza
• Un sistema RT deve garantire il comportamento
temporale di ogni task
• Un sistema veloce deve minimizzare il tempo di
risposta medio di un insieme di task
Rigutini Leonardo – Sistemi Real-Time
Slide n° 6
Fondamenti di S.O
Stati di un task:
BLOCKED
signal
activation
wait
preemption
READY
termination
RUNNING
dispatching
Scheduler:
Task
from blocked
Ready queque
Scheduler
CPU
New task
Rigutini Leonardo – Sistemi Real-Time
Slide n° 7
Schedule
Uno schedule è una particolare assegnazione di task al
processore:
• sia Γ={τ1, τ2, … , τn } l’insieme dei task,
uno schedule è un mapping σ : R+  N tale che
t R+, t1 ,t2 : t  [t1 ,t2) e t’ [t1 ,t2): σ(t)= σ(t’)
K>0 se τn è in esecuzione
σ(t)=
0
altrimenti
τ1
idle
τ2
τ3
τ2
idle
3
2
1
0
preemption
t1
t2
t3
Rigutini Leonardo – Sistemi Real-Time
t4
t5
Slide n° 8
Real-Time Task
Di
Ci
τi
ri
si
fi
ri request time (arrival time ai)
si start time
Ci tempo di esecuzione
nel caso peggiore (wcet)
di absolute deadline
Di relative deadline
fi finishing time
slack
ci(t)
τi
ri
si
t
di
fi
di
ci(t)
Residual wcet ci(ri)=Ci
Li = fi – di
Margine
di – t – ci(t)
laxity o slack
Max(0,Li)
Ritardo
Rigutini Leonardo – Sistemi Real-Time
Slide n° 9
HARD e SOFT task
HARD task
• Mancare la deadline può causare effetti catastrofici
– Acquisizione di dati da sensori
– Controllo a basso livello
SOFT task
• Mancare la deadline causa solamente un degrado di
prestazioni
– Visualizzazione di messaggi
– Interpretazione di comandi utente
Un sistema capace di gestire HARD task è detto
hard real-time
Rigutini Leonardo – Sistemi Real-Time
Slide n° 10
Modi di attivazione
Time Driven (task periodici)
• Il task è attivato automaticamente dal kernel ad intervalli regolari
Event Driven (task aperiodici)
• Il task è attivato al verificarsi di un evento o attraverso una
esplicita invocazione della primitiva di attivazione
Aperiodico:
Sporadico:
Rigutini Leonardo – Sistemi Real-Time
Slide n° 11
Vincoli
• Temporali
– Es. Attivazione, completamento, …
– Possono essere:
 Espliciti – inclusi nelle specifiche
 Impliciti – derivano da specifiche che sembrano non
temporali (es. spazio di frenata dipende
dalla velocità)
• Precedenza
– Impongono un ordine nell’esecuzione dei task
• Risorse
– Forzano una sincronizzazione negli accessi a risorse
mutuamente esclusive
Rigutini Leonardo – Sistemi Real-Time
Slide n° 12
Anomalie di scheduling -1
Aumento del numero di
processori:
3 processori
4 processori
Task più brevi:
Rigutini Leonardo – Sistemi Real-Time
Slide n° 13
Anomalie di scheduling -2
Rimuovendo i vincoli di precedenza:
Processore 2 volte più veloce:
Rigutini Leonardo – Sistemi Real-Time
Slide n° 14
Scheduling
Uno schedule è detto ammissibile se ogni task termina
rispettando un insieme di vincoli
Uno scheduling può essere:
• Preemptive / Non Preemptive
– Possibilità di sospensione di un task
• Statico / Dinamico
– Decisioni prese in base a parametri fissi / variabili con il tempo
• On line / Off Line
– Decisioni prese prima dell’attivazione del task / a run time
• Best Effort / Ottimo
– Fa del suo meglio per trovare uno scheduling ammissibile /
trova sempre uno scheduling se ne esiste uno
Rigutini Leonardo – Sistemi Real-Time
Slide n° 15
Scheduling classici
• FCFS (First Come First Served)
– CPU assegnata in base ai tempi di arrivo
– Non Preemptive, Dinamico, OnLine, BestEffort
– Altamente impredicibile
• SJF (Shortest Job First)
– CPU assegnata al task con C minore
– Non preemptive o preemptive, statico (Ci fissati), on-line od off-line
– Minimizza il tempo di risposta medio
• PS (Priority scheduling)
– Viene eseguito il task con P maggiore
– Preemptive,Statico o Dinamico, on-line
– Problema: starvation  soluzione: aging
• RR (Round Robin)
– FCFS con time sharing
– Ogni task ha a disposizione
un lasso di tempo Q, altrimenti viene
sospeso e riattivato nQ dopo
– Ogni task viene eseguito come se
fosse su un processore n volte più lento
Rigutini Leonardo – Sistemi Real-Time
Slide n° 16
Scheduling Real-Time: Task Aperiodici
Per semplicità non consideriamo i vincoli di precedenza
I task possono essere schedulati in base:
• Deadline relativa (Di)  Earliest Due Date (EDD)
– Statico (Di fissati)
– Preemptive o meno
– Tutti i task arrivano simultaneamente
– Minimizza il massimo margine (Lmax)
• Deadline assoluta (di)  Earliest Deadline First (EDF)
– Dinamico (di dipende dal tempo di arrivo)
– Preemptive
– Task possono arrivare in qualsiasi istante
– Minimizza il massimo margine (Lmax)
Rigutini Leonardo – Sistemi Real-Time
Slide n° 17
Earliest Due Date (EDD)
• Seleziona il task con la deadline relativa (Di) minore
• Minimizza il massimo margine (Lmax)
If Lmax <0 then nessun task manca la sua deadline
• Test di garanzia off-line (istante di arrivo noto):
i k=0..i Ck  Di
Rigutini Leonardo – Sistemi Real-Time
Slide n° 18
Earliest Deadline First (EDF)
• Seleziona il task con la deadline assoluta (di) minore [Horn 74]
Es.
• Minimizza il massimo margine (Lmax)
• Test di garanzia on-line (i task possono arrivare in qualsiasi istante):
i fi = k=0..i ck(t)  di - t
Notare che fi = fi-1 + ci(t)
t
Rigutini Leonardo – Sistemi Real-Time
Slide n° 19
Scheduling Real-Time: Task Periodici
Task Periodico:
Per ogni task periodico garantire:
• ogni job ik sia attivato all’istante rik=(K-1)Ti
• ogni job ik termini entro dik= rik + Di
Due tassonomie di algoritmi:
• Timeline scheduling
– Utilizzato per 30 anni in tutti i sistemi RT (militare, navigazione, …)
– Asse dei tempi suddivisa in intervalli allocati staticamente ai vari task
• Priority Scheduling
– Priorità assegnate in base ai vincoli temporali di ogni task
– Vari tipi di algoritmi a seconda del modo di fissare le priorità
Rigutini Leonardo – Sistemi Real-Time
Slide n° 20
Timeline Scheduling
•
Deadline relativa uguale al periodo: Di = Ti
Vincoli:
Ca + Cb ≤ Δ
Ca + Cc ≤ Δ
Vantaggi:
1. Implementazione semplice
2. Basso overhead
Svantaggi:
1. Poco robusto durante sovraccarichi: cosa fare se un task sfora la
deadline?
–
–
Lasciare finire il task  effetto domino
Abortire il task  pericolo di stati inconsistenti
–
Modifica di uno o più task  riprogettare tutto, compreso T e ∆
2. Bassa espandibilità
3. Difficile da gestire la presenza di task aperiodici
Rigutini Leonardo – Sistemi Real-Time
Slide n° 21
Priority Scheduling: Rate Monotonic (RM)
• Priorità inversamente proporzionale alla frequenza del task
[Liu e Layland ‘73]
• Deadline relativa uguale al periodo:
Di = Ti
Es.
• Fattibilità:
• Ogni task utilizza la CPU per una frazione di tempo pari a:
• Quindi l’utizzazione del processore è:
Up misura il carico del processore
• Se Up > 1 il processore è sovraccaricato  T non schedulabile
• Ci sono casi di non schedulabilità anche con Up < 1
Rigutini Leonardo – Sistemi Real-Time
Slide n° 22
Utilization Upper Bound
• L’Utilization Upper Bound Uub dipende dall’insieme dei task:
Ulub = Least Upper Bound
Up = 3/6 + 3/9 = 0.833
Up = 2/4 + 4/8 = 1
se Up ≤ Ulub certamente schedulabile
se Ulub ≤ Up ≤ 1 non possiamo dire niente
• Nel 1973 Liu e Layland provarono che per un insieme di n task
periodici:
RM
U lub
 n(21 n  1)
Rigutini Leonardo – Sistemi Real-Time
RM
per n   , U lub
 ln 2
Slide n° 23
Priority Scheduling: Earliest Deadline First (EDF)
• Deadline relativa uguale al periodo:
Di = Ti
• Ogni task riceve una assoluta deadline
di,k =ri,k + Di con ri,k= ri,1 + (k-1)Ti
• Il processore è assegnato al task con di,k minore
• Utilizzo del processore fino al 100%
• Schedulabilità:
• Nel 1973 Liu e Layland provarono che per un set di n task
periodici
EDF
U lub
1
• Un insieme di task è schedulabile EDF se e solo se Up≤ 1
Rigutini Leonardo – Sistemi Real-Time
Slide n° 24
RM vs EDF
RM:
• Semplice da implementare su S.O. commerciali
• Più predicibile durante i sovraccarichi
EDF
• Più efficiente
• Riduzione dei content switch
Rigutini Leonardo – Sistemi Real-Time
Slide n° 25
Task Periodici con D < T
1. Deadline Monotonic (DM)
• Priorità inversamente proporsionale a D  pi  1/Di
2. Earliest Deadline First (EDF)
• Priorità inversamente proporsionale a d  pi  1/di
Rigutini Leonardo – Sistemi Real-Time
Slide n° 26
Task Aperiodici + Task Periodici
• Scheduling globale periodico
• Si utilizza un task periodico (server) che gestisce i task aperiodici
• Servers:
Priorità fissa:
• Polling server (PS)
• Deferrable server (DS)
Rigutini Leonardo – Sistemi Real-Time
Priorità dinamica:
• Dynamic Polling server (DPS)
• Dynamic Deferrable server (DDS)
Slide n° 27
Sommario
• Argomenti trattati in questo seminario:
1.Introduzione ai S.O.
2.Scheduling RT di Task Aperiodici
3.Scheduling RT di Task Periodici
4.Task Aperiodici + Task Periodici
Rigutini Leonardo – Sistemi Real-Time
Slide n° 28