Real-time EDF scheduling per il kernel FreeBSD:...

Real-time EDF scheduling per il kernel FreeBSD:analisi, implementazione e risultati sperimentali

Marco [email protected]

Relatore: Dott. Sergio RuoccoCorrelatore: Prof. Francesco Tisato

Facolta di Scienze Matematiche Fisiche e NaturaliCorso di Laurea Specialistica in Informatica

Sessione del 24 Novembre, 2011

[email protected]

Roadmap della presentazione

1 evoluzione dei sistemi operativi Unix-like

2 FreeBSD, Linux, e sue varianti real-time

3 lo scheduler real-time SCHED DEADLINE per Linux

4 porting di SCHED DEADLINE per FreeBSD

5 risultati sperimentali

6 conclusioni e sviluppi futuri

Real-time EDF scheduling per FreeBSD

Evoluzione dei sistemi operativi Unix-like


FreeBSD

Origini, impieghi e caratteristiche principali

FreeBSD nasce nel 1993 come derivazione di 386BSD – la versionenon commerciale di Unix sviluppata da UC-Berkeley

impiegato per server, workstation e – recentemente – in alcunisistemi embedded (TV Panasonic)

lo scheduler (ULE) non ha supporto per il real-time. . .

. . . e nella comunita non sono note iniziative in tal senso!

ha una licenza (BSD) tecnicamente e commercialmente moltomeno restrittiva di quella Linux (GPL)


Real-time Linux

Stato dell’arte

Linux viene oggi impiegato in svariati ambiti: multimedia, sistemi embedded e mobili,cellulari, smartphone (Android), consumer electronics (TV, navigatori), robotica. . .

dal 1999 si tiene il Real Time Linux Workshop, seminario internazionalededicato al supporto ed impiego di Linux in ambiti real-time.

varianti con supporto commerciale: Montavista, Windriver e Timesys;

varianti con supporto communita: OCERA, AQuoSA, Frescor, LITMUS-RT,RTLinux e Preempt-RT;

Variante scelta per questa tesi: SCHED DEADLINE

SCHED DEADLINE = EDF + isolamento temporale (Constant Bandwidth Server)

implementazione per Linux nel contesto del progetto europeo ACTOR guidatoda Ericsson Research con la partecipazione, tra gli altri, di Scuola S. Anna (PI)

incapsulata in un componente (modulo Linux) - lo scheduler e modulare dallaversione 2.6.23

licenza Gnu Public License (GPL) V2 “free software”


Modello dei task real-time in SCHED DEADLINE


FreeBSD (sched)ULE: strutture dati


(sched)ULE + SCHED DEADLINE = FreeBSD real-time!


Risultati sperimentali

Ambiente di test:

AMD Athlon(tm) 64bit X2 Dual Core Processor 5200+ (2700.27-MHz K8-classCPU);

FreeBSD 8.2.0 con patch deadline-bsd (HZ=10000)

Tool:

modifica di sched getparam ex e relativi parametri per portare in user spaceinformazioni di scheduling dei thread real-time;

KTR, sched switch e GtkWave per visualizzare gli eventi di scheduling informato grafico.

Misurazioni:

1 rispetto dei vincoli temporali di esecuzione;

2 confronto con le altre classi di scheduling.


Risultati sperimentali - (1) SCHED DEADLINE

Legenda:

sh tid 100063: task di classe real-time Posix (massima priorita, simula alto carico);

sh tid 100092/93/94: task di classe deadline con runtime 200/300/300(us) e deadline 1/2/3(ms);

colore linea: rosso per task ready; verde/azzurro per task running; giallo per task not ready;


Risultati sperimentali - (1) SCHED DEADLINE

Osservazioni:

rispetto priorita esecutiva;

rispetto di max runtime (isolamento temporale);

rispetto delle deadline (EDF);

preemption tra task real-time (EDF);


Risultati sperimentali - (2) classe standard di ULE

Legenda:

sh tid 100085: task di classe real-time Posix (massima priorita e in while(1), simula alto carico);

sh tid 100069-72: task di classe real-time Posix (massima priorita e in while(1));

colore linea: rosso per task ready; verde/azzurro per task running; giallo per task not ready;


Risultati sperimentali - (2) classe standard di ULE

Osservazioni:

max runtime dipende dalla time slice (default a 100ms per tutti i task);

periodo di esecuzione dipende dal numero di task in stato di pronto (in Round Robin);


Conclusioni e direzioni future

Risultati ottenuti:

il porting di SCHED DEADLINE in FreeBSD e stato effettuatocon successo;

FreeBSD puo essere impiegato in ambiti applicativi conrequisiti real-time.

Lavori futuri:

vincolo deadline diverso dal periodo;

integrare altri algoritmi di scheduling real-time (come moduli);


(Extra) Cosa e stato fatto - Teoria e pratica

Parte teorica:

studio sulla teoria dello scheduling di processi nei sistemioperativi;

scheduling in Linux e FreeBSD con ricerca di propostereal-time.

Parte pratica:

implementazione/trapianto di SCHED DEADLINE nelloscheduler di FreeBSD con risultati sperimentali.


(Extra) FreeBSD - Scheduling di processi

Due scheduler:

4BSD, ereditato da 4.3BSD (obsoleto);

il piu recente ULE (da schedULE), scheduler di default per la maggior partedelle architetture supportate;

Obiettivi

massima priorita esecutiva ai task kernel;

minimizzare i tempi di risposta per i task utente interattivi;

supporto per architetture multicore (SMP).


(Extra) FreeBSD - Scheduling di processi

Caratteristiche di ULE:

classi di priorita: in una decisione di scheduling si manda in esecuzione il taskcon priorita maggiore;

classi kernel con priorita statiche e senza time slice;

classi utente con time slice e calcolo delle priorita dinamiche con lo scopo difavorire i task interattivi;

complessita temporale di O(1) (in 4BSD era O(n));

tecnica a priorita ereditata per il problema di priorita inversa;

supporto alle classi di scheduling real-time POSIX sched fifo e sched rr;

bilanciamento di carico statico e periodico basato su affinity e distanza dicache, per architetture multicore (SMP).


(Extra) FreeBSD - Scheduling real-time (?!)

FreeBSD manca di:

scheduling che tenga conto di vincoli temporali;

kernel preemptive a grana piu fine;

timer ad alta risoluzione [1ms ... 10us];

Cosa risolve l’implementazione di SCHED DEADLINE inFreeBSD?


(Extra) Deadline-BSD - classe di scheduling

Nuova classe di scheduling deadline.

Precedenza di esecuzione:

minore rispetto alle classi kernel;

maggiore rispetto a tutte le classi utente;

Motivazioni:

evitare di ritardare l’esecuzione dei gestori degli interrupt;

rispetto dei vincoli temporali richide la precedenza su altri taskutente;

gestione della capacita di calcolo per allocare banda di utilizzoper altre classi.


(Extra) Deadline-BSD - Gestione dei task

Strutture dati:

modifica struttura informativa dei thread;

albero binario red-black (per-CPU);

banda di utilizzo disponibile ed effettiva (per-CPU);

Albero red-black

ogni nodo rappresenta/punta ad un task;

ordinato sulla base delle deadline assolute dei task;

il nodo piu a sinistra e quello con il minor valore;

complessita temporale di gestione dell’albero di O(log n).


(Extra) Deadline-BSD - Isolamento temporale

EDF non garantisce il rispetto del budget di esecuzione dei task.

Controllo del budget:

agganciato alla gestione dei tick del clock di sistema;

quando un task esaurisce il suo budget viene stoppato eri-attivato (tramite un timer) sulla base del periodo.

Cosa otteniamo?

l’istanza del task puo restare in esecuzione per al massimo ilsuo budget;

un task non puo monopolizzare la CPU, influenzandol’esecuzione di altri task.


(Extra) Deadline-BSD - Gestione banda di utilizzo

Gestione della banda di utilizzo (per-CPU) dei task di classedeadline regolata da due parametri di sistema:

Sysctl:

kern.sched.dl period us (default a 1s);

kern.sched.dl runtime us (default a 600ms);


(Extra) Deadline-BSD - Test di ammissione

Test di ammissione:n∑

i=0

dl bw <= C ∗ (dl runtime us/dl period us)

con C numero di CPU del sistema e n numero di task di classedeadline in stato di pronto.

Cosa garantisce?

sufficiente banda di CPU per rispettare i vincoli temporali diesecuzione dei task.

Cosa non garantisce?

l’effettivo rispetto dei vincoli temporali.


(Extra) - Deadline-BSD - Granularita

Uso dei timer in Deadline-BSD:

per attivare nuove istanze di task;

per controllare il budget di esecuzione dei task;

I timer in FreeBSD sono legati alla frequenza del clock principale disistema (parametro di configurazione del kernel, HZ).

Cosa implica?

non e possibile armare timer con una risoluzione inferiore alperiodo di clock di sistema;

diminuisce la precisione nel rispetto dei vincoli;

frequenze troppo alte del clock di sistema comportanoinstabilita (es. a 1us).


(Extra) - Deadline-BSD - SMP

Gestione del bilanciamento di carico per i task di classe deadlineseparata da quella standard di ULE.

Scelta della CPU per i nuovi task:

banda di utilizzo sufficiente;

minir carico di task di classe deadline;

la banda rimane allocata fino al’uscita (exit/kill) del task.


(Extra) Deadline-BSD - Integrazione in ULE

Innesto di Deadline-BSD in ULE:

nuove strutture dati e relative inizializzazioni;

scelta del task da mandare in esecuzione;

switch di contesto;

fork di thread;

tick di stathz;

tick di hz;

passaggio del thread in stato di pronto;

yielding;

uscita di un thread.


(Extra) Deadline-BSD - Chiamate di sistema

syscall:

int sched_getparam_ex(pid_t, struct sched_param_ex *);

int sched_getscheduler_ex(pid_t);

int sched_setparam_ex(pid_t, const struct sched_param_ex *);

int sched_setscheduler_ex(pid_t, int, const struct sched_param_ex *);

struct sched_param_ex {

int sched_priority;

struct timespec sched_runtime;

struct timespec sched_deadline;

struct timespec sched_period;

unsigned int sched_flags;

struct timespec curr_runtime;

struct timespec used_runtime;

struct timespec curr_deadline;

};


(Extra) Deadline-BSD - Risultati sperimentali - (1)

Statistiche di scheduling: while(1) per 3 secondi con diversi vincoli temporali

200us/1ms 300us/2ms 300us/3ms (runtime/deadline)

tot rtime usec 600289 450430 300306 (runtime totale)

rtime over usec 289 430 306 (runtime totale in eccesso)

last rorun usec 1 73 9 (ultimo runtime in eccesso)

rorun max usec 99 99 99 (massimo runtime in eccesso)

cnt dmiss 0 0 0 (nbr deadline mancate)

cnt rorun 3000 1502 1001 (nbr runtime in eccesso)

cnt timerfire 3000 1502 1001 (nbr attivazione timer)

cnt resched 3000 1502 1001 (nbr rischedulazione)

cnt updatecurr 6166 4600 3576 (nbr update runtime)


(Extra) Deadline-BSD - Risultati sperimentali - (1)

Osservazioni:

rispetto della banda di utilizzo grazie all’isolamento temporale,(valori di tot rtime usec e figura);

rispetto della deadline (cnt dmiss a 0);

preemption tra task di classe deadline con EDF (preemptiondel task 94);

rorun max use non va mai oltre la “risoluzione” del tick diclock di sistema (in questo caso pari a 100us);


Real-time EDF scheduling per il kernel FreeBSD:...

Documents

Transcript of Real-time EDF scheduling per il kernel FreeBSD:...