Risorse condivise e sovraccarichi nei sistemi in tempo reale E.Mumolo [email protected].

Risorse condivise e sovraccarichi nei sistemi in tempo reale

E.Mumolo

[email protected]

Sistemi in tempo reale TIPI DI PROCESSI RT

Hard RT: se il superamento della deadline e’ catastrofico. Es.: acquisizione dati asservimento pianificazione azioni controllo automatico

Soft RT: se il superamento della deadline non e’ catastrofico ma sopportabile. Es.: Interpretazione comandi utente Visualizzazione messaggi

ASPETTI FONDAMENTALI: SCHEDULING ACCESSO A RISORSE GESTIONE SOVRACCARICHI COMUNICAZIONE TRA PROCESSI

Ricorda: risorse condivise e concorrenza

Esempio di programmazione nello stesso spazio di indirizzamento:produttore-consumatore

prod() cons()

{ { while(true) while(true) { { el=produci(); while(in==out){}; while((IN+1)%N==out)){}; el=buf[out]; buf[in]=el; out=(out+1)%N; in=(in+1)%N; consuma(el); } }}

buf, N elementi Due puntatori: in, out. Buffer vuoto: in==out; Buffer pieno: (in+1)%N==out

Ricorda: mutua esclusione Caso due consumatori:

cons()

{

while(true)

{

while(in==out){};

el=buf(out);

out=(out+1)%N;

consuma(el);

}

}

cons1()

{

while(true)

{

while(in==out){};

el=buf(out);

out=(out+1)%N;

consuma(el);

}

}

Problema di mutua esclusione!

context switch!

Mutua esclusione

Uso di un ‘ARBITRO’ per decidere se posso continuare l’esecuzione

Arbitro Arbitro

cons()

{

while(true)

{

while(in==out){};

el=buf(out);

out=(out+1)%N;

consuma(el);

}

}

cons1()

{

while(true)

{

while(in==out){};

el=buf(out);

out=(out+1)%N;

consuma(el);

}

}

Sincronizzazione di processi concorrenti per accesso a

risorse condiviseArbitro sw: alternanza stretta Arbitro sw: algor. Peterson

Arbitro semaforico

Protocolli di accesso a risorse condivise in RT

Sezioni Critiche: parti del codice alle quali si deve garantire l‘uso esclusivo di alcune risorse. Protezione mediante il semaforo S primitive wait(S) e signal(S), o down(S) e up(S) o P(S) e V(S)

P(S)

V(S)

P(S)

V(S)

Accesso in mutua esclusionedi una risorsa non condivisibile

Thread 1 Thread 2

Protocolli di accesso a risorse condivise in RT

Il problema dell’inversione di priorità Un processo ad alta priorità viene bloccato da un processo a

più bassa priorità per un tempo indefinito Esempio (T1 a più alta priorità rispetto a T2):

normale critico

BloccoT1

Protocolli di accesso a risorse condivise

Altro esempio di inversione di priorità (J1>J2>J3)

J1

J2

J3

normale critico

P

PBlocco di J1 dovuto a J2:imprevedibile


Protocollo ‘priority enheritance’ (ereditarietà della priorità) Sha 1990 Risolve l’inversione di priorità

ipotesi: priorità J1> priorità J2 >… >priorità Jn Schedulazione FIFO Semafori binari Le sezioni critiche possono essere annidate

Protocollo: Quando un thread si blocca su un semaforo, trasmette la sua priorità al thread

che posside il semaforo Il thread che possiede il semaforo esegue la sezione critica ad una priorità pari

al massimo dei thread bloccati All’uscita della sezione critica il thread viene riportato alla priorità iniziale Ereditarietà transitiva


Esempio della soluzione della inversione delle priorità con il protocollo ‘priority enheritance’

Blocco diretto (J1) e blocco indiretto (J2)

J1

J2

J3

normale critico

P

P


Problemi del protocollo ‘priority enheritance’ : stallo

J1 J2

J1

J2

P(S1)

P(S2)

V(S2)

V(S1)

P(S2)

P(S1)

V(S1)

V(S2)

P(S2)

P(S1) P(S2)

P(S1) stallo

Protocolli di accesso a risorse condivise Problemi del protocollo ‘priority enheritance’ : catena di bloccaggi

Possibile blocco di un thread per una durata di n sezioni critiche

J1

J2

J3

P(S1)

P(S2)

P(S1) P(S2) V(S2) V(S1)

V(S2)

V(S1)

J1 P(S1)

P(S2)V(S2)

V(S1)

Protocolli di accesso a risorse condivise Protocollo ‘priority ceiling’ (tetto della priorità) Sha 1990

Viene assegnato a ciascun semaforo un tetto di priorità pari alla più alta priorità dei task che possono usare quel semaforo. Un processo può interrompere una sezione critica protetta da un semaforo se ha una priorità > tetto(semaforo)

Esempio:

J1

J2

J3

P(S2)

P(S2)

P(S0) V(S0)

V(S1)

J1

P(S2)

P(S1)V(S1)

V(S2)

P(S1)

P(S1)

Ceiling(S0)=ceiling(S1)=prio(J1); ceiling(S2)=prio(J2)

J3


Qualche proprietà del protocollo Il protocollo Priority Ceiling previene lo stallo Un processo può essere bloccato al massimo per la durata di una sola sezione

critica (di quelle che possono bloccare il processo) Schedulabilità

Sia Bi il tempo massimo di bloccaggio del task Ti da parte di task a priorità minore.

Bn = 0 perché n è il processo a più bassa priorità. Risultato: Condizione sufficiente per la schedulabilità di Rate Monotonic con Priority

Ceiling o Priority Inheritance è che:

Gestione dei sovraccarichi nei sistemi RT

Sovraccarico: la richiesta di calcolo eccede la disponibilità del processore

Eventi sporadici dovuti per esempio a: Variazioni ambientali Eventi asincroni Malfunzionamento Eccezioni simultanee …

Un sovraccarico transitorio può provocare un catastrofico effetto a catena superamento di tutte le deadline


Definizione di carico: frazione del tempo disponibile per elaborazione. Aperiodici hard (con EDF)

Periodici corrisponde al fattore di utilizzazione

J1

J2

J30 2 4 6 8 10 12 14

1(4)=2/4=0.5

2(4)=5/6=0.83

3(4)=7/9=0.78

(t) = max[k(t)

t


Schedulazione in sovraccarico La schedulazione non è fattibile. L’unica possibilità è

fare in modo che i task in ritardo siano quelli MENO IMPORTANTI

Distinzione dei task a seconda della loro importanza Es: un task con deadline lontana potrebbe essere

molto più importante di un task imminente Parametro aggiuntivo: importanza del task, vi


Valore di un task: importanza relativa di un task rispetto ad altri dell’insieme

Alcune metriche: vi = Vi costante

vi = Ci tempo di calcolo

vi = Vi/Ci densità

Ma: il valore di un task dipende anche dal suo tempo di completamento

f

f

f

fv(f)v(f)

v(f)

Non real time

hard real time

soft real time

critico

v(f)

Gestione dei sovraccarichi nei sistemi RT Valore cumulativo di un algoritmo di schedulazione A

V = vi(fi) Algoritmo ottimo: massimizza il valore cumulativo su un insieme di task

In generale: V < Vi

Chiaroveggenza: conoscenza anticipata delle attivazioni dei task Permette di raggiungere il massimo valore cumulativo su un dato insieme di

task in sovraccarico Non attuabile ma utile per avere benchmark Esempio:

C=10

C=8 C=8

Se non so che arriva J3, attivo J1 fatt. cum. =10

Se sapessi che arriva J3, attivo J2 in attesa si J3 fatt. cum. =16

J1

J2, J3


Esempio: ai Di Ci

J1 0 16 10

J2 8 7 5

J3 10 4 3

vi = Ci

J1

J2

J3

J1

J2

J3

0 4 6 82 10 12 14 16 18 20

EDF

chia.

v(f)

hard real time

fV1=0

V2=0

V3=3

V1=10

V2=5

V3=0

VEDF=3

Vchia=15


Fattore competitivo Un algoritmo A ha un fattore competitivo se e solo se garantisce un

valore cumulativo

VA Vdove V è il valore cumulativo ottenuto da un algortitmo ottimo chiaroveggente Il fattore competitivo è tra 0 e 1: 0 1 Dire che un algoritmo di schedulazione ha un fattore competitivo

garantisce che in tutti i casi fornisce un valore cumulativo pari ad almeno volte quello ottenibile da un algoritmo chiaroveggente

L’algoritmo EDF ha un fattore competitivo nullo È stato dimostrato che il fattore competitivo non può essere maggiore

di 0.25


Algoritmi robusti In un sistema real-time in condizioni di sovraccarico l’impiego di

un algoritmo di schedulazione con un fattore competitivo elevato garantisce una prestazione minima in tutte le condizioni possibili

Per esempio, se un task finisce prima della sua deadline, sarebbe opportuno usare il tempo avanzato per eseguire task rifiutati precedentemente

Algoritmi robusti: ammettono deadline ‘flessibili’ (tolleranza sulla deadline) e una strategia di recupero

Risorse condivise e sovraccarichi nei sistemi in tempo reale E.Mumolo [email protected].

Documents

Transcript of Risorse condivise e sovraccarichi nei sistemi in tempo reale E.Mumolo [email protected].