Prof. Lorenzo Mezzalira, Fabio Salice – Sistemi Operativi Real Time Estratto dalle slide di...

Prof. Lorenzo Mezzalira, Fabio Salice – Sistemi Operativi Real Time

Estratto dalle slide diInformatica Industriale - DU - 10


Introduzione

Gli obiettivi di un sistema di elaborazione possono essere svariati e concomitanti, come ad esempio: semplicità ed economia. massimo sfruttamento di alcune risorse (video, dischi) massimo throughput. adeguatezza alle esigenze di una multiutenza. rispetto di vincoli temporali nelle interazioni con

l’esterno. massima affidabilità.


Introduzione

La personalità del sistema dipende notevolmente dal tipo di macchina virtuale che il Sistema Operativo implementa sulla macchina fisica.

Il software applicativo a sua volta si appoggia al supporto del S.O.

Si analizzano sistemi per cui è qualificante il comportamento temporale Come richiesto per una corretta interazione con una

realtà sede di fenomeni asincroni


Necessità di Parallelismo(per il Tempo Reale)

Caratteristiche di un ambiente di elaborazione in tempo reale: Carico di lavoro. Vincoli temporali.

Il carico di lavoro è scomponibile in: attività costituite da azioni periodiche azioni aperiodiche (generalmente sporadiche) attività di sottofondo


Parallelismo

Definizioni Scopo temporale di una azione:

Intervallo di tempo tra l'istante in cui si verifica l'evento che consente o richiede l'esecuzione dell'azione (triggering event) e l'istante di tempo in cui tale attività è, o deve essere (deadline), completata.

Attività concorrenti: Attività le cui azioni hanno scopi temporali che presentano

sovrapposizioni. Attività sequenziali:

Attività le cui azioni hanno scopi temporali che non presentano sovrapposizioni.


Parallelismo

Definizioni Processo Sequenziale:

attività internamente sequenziale e caratterizzata da un proprio contesto, cioè l'insieme delle risorse ad essa allocate ed i rispettivi stati.

Le risorse possono essere attive (processori di vari tipi) o passive (periferiche, memoria, dati, ecc.).

L’esecuzione di un processo richiede una risorsa attiva ed eventualmente un certo numero di risorse passive.

Nota: Una elaborazione ad attività concorrenti non è

necessariamente real-time. È real-time solo in presenza di specifiche temporali.


Parallelismo

I sistemi di elaborazione in tempo reale devono essere dotati di una capacità di parallelismo tra diverse elaborazioni capacità di iniziare una nuova azione anche se altre

sono già in corso. sovrapposizione di scopi temporali di diverse azioni

Chiamiamo, per l’azione i-esima: TDi la deadline

esprime la rapidità richiesta al sistema di elaborazione. TEi il massimo tempo di esecuzione netto

esprime la velocità offerta dal sistema di elaborazione.


Parallelismo

Condizione sufficiente perché sia richiesto un parallelismo di esecuzione (eventualmente con preemption) è che esistano almeno due eventi tra loro aperiodici, tali per cui sia

TDi < TEi + TEk

Condizione sufficiente perché si possa evitare preemption è che sia

TDi > kTEk

Con TDi la più breve deadline


Parallelismo:Fisico

Parallelismo reale (fisico): ottenibile quando sono disponibili tanti processori quante sono richieste dalle diverse attività potenzialmente concomitanti

multiprocessing. Il parallelismo fisico implica un'assegnazione

(scheduling) spaziale delle attività alle risorse. Problemi di sfruttamento delle risorse

ogni risorsa rimane inattiva (idle) per tutto il tempo in cui non è richiesto lo svolgimento di azioni dell'attività assegnatale


Parallelismo:Fisico

Un'applicazione non è fisicamente realizzabile, neppure con un sistema a parallelismo fisico, se per almeno un'azione si ha:

TDi < TEi

La relazione indica: potenza di calcolo insufficiente per l’algoritmo adottato,

rispetto alle prestazioni temporali richieste.


Parallelismo:Virtuale

Parallelismo virtuale (o logico): ottenibile con l'assegnazione nel tempo delle (scarse) risorse alle azioni in corso durante intervalli di tempo interni ai rispettivi scopi temporali

multitasking. Il parallelismo logico richiede uno scheduling

temporale. Buon sfruttamento delle risorse

consente un migliore sfruttamento delle risorse rispetto ad un parallelismo puramente fisico.



Coefficiente di utilizzo del processore:

U = i=1..n(TEi/TAi) n: numero di azioni potenzialmente richieste al

processore TEi: tempo di esecuzione netto dell'azione i-esima TAi: intervallo tra le attivazioni dell'azione i-esima.

La realizzabilità fisica con un solo processore impone che sia U < 1; questa è condizione necessaria, ma non sufficiente, perché possano essere rispettati tutti i vincoli temporali.



Eventi periodici: i valori TAi corrispondono ai periodi dei rispettivi eventi.

Eventi sporadici: i valori TAi sono quelli medi o minimi di ripetizione a seconda che si considerino gli utilizzi in media o di picco

Un parallelismo misto (logico/fisico) si realizza con un sistema dotato di più processori (N), ognuno dei quali esegue più attività in parallelismo virtuale:

U = i=1..n(TEi/TAi)< N (realizzabilità fisica )



Nel caso di un sistema mono processore: Se il coefficiente di utilizzo della CPU è U < 1, Se scheduling (temporale) è tale che ogni azione

rispetta il proprio vincolo temporale, Allora, l'effetto complessivo osservabile è

equivalente a quello ottenibile da diversi processori in parallelo

le specifiche temporali richieste riguardano solo certe azioni ed in particolare quasi sempre riguardano solo l'azione conclusiva di emissione del risultato finale. Questo rende possibile l’equivalenza



Esempio di funzioni utilità temporale della risposta e bontà del risultato

Nota: se A2 fosse stata rimandata dopo A1 (quindi senza preemption) non avrebbe rispettato la scadenza.

A2

A1

V2

V1

B2

B1

Funzioni di validità temporale

della risposta

Funzioni di bontà del risultato

Evento E1 Trigger azione A1

Evento E2 Trigger azione A2

Deadline A2

Deadline A1


Parallelismo: Virtuale

Ossevazione: la virtualizzazione del parallelismo è consentita dalla granularità (ampia) della scala dei tempi. Livello di scopo temporale e non di singola istruzione.

Se il carico di lavoro supera complessivamente il valore unitario è inevitabile dover ricorrere ad un sistema più veloce o con più processori Con più processori si aggiunge al parallelismo logico

del parallelismo fisico.


Modelli di Parallelismo Virtuale

Time-Driven Approccio ciclico: una attività è scomposta in azioni,

tutte dello stesso tipo, ripetute ciclicamente. I tempo ha un ruolo attivo mentre gli eventi (interni ed

esterni) hanno un ruolo passivo. Approccio a stato sugli eventi sia interni sia esterni.

Execution-Driven Le attività si invocano vicendevolmente e in relazione ad

eventi interni. Gli eventi esterni hanno un ruolo passivo.

Approccio a stato sugli eventi esterni. Event-Driven

Le azioni sono attivate da eventi. Approccio ad eventi


Modelli di Parallelismo Virtuale: Kernel Time-Driven

Time-driven: tutte le azioni sono eseguite sulla base di eventi temporali indipendentemente dal verificarsi di eventi interni od esterni.

Definizione: Stato Interno Insieme di variabili interne che rappresentano la storia

di una elaborazione. Consente di realizzare funzioni sequenziali (o con una

dinamica) e non puramente combinatorie. Esempio: algoritmo che realizza un PID

stato interno: la variabile che mantiene il valore precedente della misura, per il calcolo della derivata, e la variabile che mantiene il valore corrente, da aggiornare ad ogni ciclo, dell’integrale.



Ogni attività può essere realizzata come una successione di azioni.

Ogni azione consiste nella valutazione di una stessa funzione. La valutazione viene ripetuta ad ogni campionamento.

Valori di ingresso (Ii) e di stato interno (Si) producono una uscita (Oi) ed uno stato futuro (Si+1). Stato interno presente e futuro sono opzionali.



Quindi, ogni attività A consiste Nell'esecuzione ciclica ad intervalli regolari T0,T1,..,Ti.

Delle azioni a0, a1,..,ai,..

Dove ak valuta la stessa espressione Ea in cui le variabili assumono i valori campionati in Tk.

Condizione sufficiente perché si possa adottare un approccio time-driven con un singolo ciclo è che sia TEi< TDj

dove TDj è la più breve deadline.



Esempio: esecuzione delle attività concorrenti A, B e C con lo stesso periodo di campionamento.

Organizzazione dell'esecuzione delle azioni: Istante T0

si utilizzano i valori I0 e S0,

per eseguire le azioni a0, b0, c0

che producono i valori O0 e S1

Istante T1

si utilizzano i valori I1 e S1,

per eseguire le azioni a1, b1, c1

che producono i valori O1 e S2

…



Dal punto di vista realizzativo, il verificarsi dell'evento temporale scadenza dell'istante Ti attiva l'esecuzione della sequenza di azioni:

1. leggi i valori Ii con campionamento in ingresso

2. esegui le azioni ai, bi, ci

3. emetti i valori Oi appena calcolati e aggiorna lo stato Si.



Caratteristiche dell’approccio time-driven Gli eventi esterni giocano un ruolo passivo.

Non provocano direttamente nessuna azione. Gli eventi esterni possono essere dedotti

Rilevati come differenze di valori degli stati campionati in ingresso.

È dominante il concetto di stato. La sincronizzazione con l’I/O è effettuata mediante

controllo di programma. Lo scheduling delle azioni è statico (off-line)

Il programmatore, con la stesura del programma, decide la sequenza di esecuzione delle azioni nell’ambito del ciclo e non viene effettuata nessuna preemption.



I pregi: Semplicità: il supporto "run-time" è costituito da un

sistema operativo molto ridotto che si limita alle funzioni di lettura degli ingressi, scrittura delle uscite e alla gestione di un temporizzatore di attivazione ciclica.

Predicibilità: i tempi di esecuzione molto regolari rendono facile verificare se il fattore di utilizzazione del processore è < 1.


Modelli di Parallelismo Virtuale: Kernel Time-Driven (tempi di risposta)

Con l’ipotesi di predicibilità, detto Tp il periodo di ripetizione ciclica, il tempo di risposta Tr del sistema di elaborazione soddisfa la relazione:

Tp < Tr < 2Tp

Il caso peggiore (2Tp) si ha quando un ingresso cambia subito dopo essere stato “campionato” all’inizio del ciclo i-esimo. Le uscite ottenute alla fine del ciclo i-esimo (cioè dopo il

tempo Tp) corrisponderanno ancora al vecchio valore di quell’ingresso, mentre solo alla fine del ciclo i+1 (quindi dopo un tempo 2*Tp) le uscite terranno conto del nuovo valore.



La validità della relazione Tp<Tr<2Tp è condizionata al verificarsi di almeno una delle seguenti ipotesi più restrittive.

1. Le azioni ai, bi,... sono tra loro indipendenti In questo caso nessuna delle azioni utilizza dati prodotti da altre

azioni e il tempo di risposta non dipende dall’ordine con cui le azioni sono eseguite all’interno del ciclo.

2. Le azioni ai, bi,... presentano relazioni di precedenza rappresentabili con un grafo non ciclico e siano eseguite all’interno del ciclo di ripetizione in una sequenza che non viola alcuna precedenza.

La validità della relazione Tp<Tr<2Tp non è detto si verifichi nel caso di ciclicità.



Le relazioni di precedenza tra azioni possono essere rappresentate con un data-flow-graph.

L’aciclicità rende possibile individuare almeno una sequenza tale che all’interno del ciclo ogni azione sia eseguita dopo tutte quelle che producono i dati che essa utilizza.

Compito del progettista.

A

B

C

D

D A B C

Sequenze ammissibili D – A – B – C A – D – B – C A – B – D – C



Nota: azioni che presentano un grafo di dipendenze ciclico non costituiscono un errore di progetto. Sono la situazione tipica delle reti sequenziali con retroazione

Memoria interna (stati interni). In questi casi, i valori degli ingressi non influenzano

solo l’uscita entro il tempo 2Tp, ma anche in tempi successivi.

A

B

C

D

Ciclicità: rappresenta la variabile di stato interna



Il difetto principale dell’approccio ciclico è la notevole rigidità.

Rigidità dovuta a due aspetti: Tutte le informazioni di ingresso godono dello stesso

trattamento temporale, indipendentemente dalla loro urgenza e criticità, obbligando il progettista ad adottare la cadenza imposta dalle attività più critiche anche per tutte le altre, con uno sfruttamento non ottimale della CPU.

Tutte le attività devono essere ricondotte alla forma di ripetizione ciclica degli stessi calcoli. Questo rende piuttosto macchinoso realizzare costrutti di controllo come quelli dei linguaggi di alto livello orientati al software.


Modelli di Parallelismo Virtuale: Execution-Driven Multitasking

L’assegnamento della CPU alle attività concorrenti viene attuato:

Attraverso un supporto di esecuzione in grado di commutare, su richiesta, da una attività all’altra.

Lasciando al programmatore la responsabilità di invocare le commutazioni. Le commutazioni avvengono nei punti strategici delle varie

attività.

Le attività assumono la forma di Coroutine: Le coroutine sono processi che si attivano l'un l'altro.



I tempi di attivazione delle coroutine derivano da eventi interni.

La generazione di eventi interni dipende dai tempi di esecuzione delle singole azioni.

Gli eventi esterni sono passivi (come per il caso Time-Driven)

Rilevati da analisi delle variazioni degli stati esterni acquisiti in ingresso.



Il comportamento temporale è responsabilità del programmatore.

Non c’è garanzia sul rispetto di eventuali requisiti temporali

Tecnica utilizzata solo in applicazioni semplici e con requisiti di tempo reale lasco.

Raramente utilizzata.


Modelli di Parallelismo Virtuale: Event-Driven Multitasking

Eventi esterni o temporali assumono un ruolo attivo: attivano i processi (che eseguono azioni)

Denominato anche data-driven poiché agli eventi sono associati dati.

Le sincronizzazioni con gli eventi sono basate, tipicamente, sul meccanismo dell’interrupt.

Per il rispetto di vincoli temporali occorre una politica di scheduling.

Politica di scheduling sia per i servizi alle interruzioni sia per i processi.

Questo approccio è più complesso ma anche più generale

Adatto anche per i casi visti precedentemente.


Modelli di Parallelismo Virtuale: Considerazioni sulle tecniche

L'approccio Event-Driven costituisce il caso più generale.

Considerando eventi esterni, interni e temporali. Può supportare anche sottoinsiemi di attività

impostate secondo gli schemi precedenti. Time-Driven o Execution-Driven.

Fornisce la massima flessibilità di progetto anche se a costo di una problematica molto più articolata e complessa.


Modelli di Parallelismo Virtuale: Considerazioni sulle tecniche

In particolare, un'applicazione complessa potrà comprendere:

Un sotto insieme di attività cicliche di controllo e supervisione (trasformazionali), i cui vincoli temporali consistono in una attivazione ciclica regolare, adatte ad una gestione di tipo Time-Driven;

Alcune attività di tipo reattivo a eventi sporadici e con vincoli temporali sui tempi di risposta, adatte ad una gestione Event-Driven;

Attività di sottofondo senza particolari vincoli temporali che utilizzano in modo Execution-Driven i tempi lasciati liberi dalle attività precedenti.


Scheduling Temporale

Lo scheduling è una funzione del Sistema Operativo che sceglie a quale processo assegnare il controllo della CPU:1. In seguito ad invocazione di primitive dal processo in

esecuzione2. In occasione di risposte ad interrupt (tipicamente da RTC)

Non-Preemptive (solo nel primo caso): Al termine del servizio di ogni interruzione il controllo viene

nuovamente ceduto al processo interrotto. Riduce overhead (il cambio di contesto viene effettuato solo

in relazione alle chiamate del S.O.) e riduce i problemi di rientranza.

Adatto per real-time lasco poiché le prestazioni di tempo reale sono lasciate al programmatore.


Scheduling Temporale

Preemptive (in entrambi i casi): Al termine del servizio di ogni interruzione il controllo non

viene ceduto processo interrotto. Passaggio al S.O. che individua in processo da attivare in

relazione ad analisi sulle scadenze temporali o priorità. Adatto per sistemi in tempo reale. Richiede una analisi accurata da parte del programmatore:

Protezione delle regioni critiche. Esplicita atomicità (non interruzione).

Tutte le funzioni eseguibili da processi differenti devono essere realizzate in modo rientrante.

Soprattutto le funzioni di libreria La gestione di interruzione con annidamento devono essere

gestite dal S.O. I vettori di interrupt devono passare per il S.O. e non

possono essere direttamente collegati alle routine di servizio


Scheduling TemporaleAlgoritmi di Scheduling

Round-Robin e FIFO Vantaggi:

Semplicità e basso overhead. Evita la Starvation dei Processi.

Svantaggi Nessuna garanzia di Tempo Reale. Non si privilegiano azioni urgenti.

Fixed Priority - Processi con Priorità Statica Vantaggi

Semplicità. Tiene conto di urgenza e importanza.

Svantaggi Occorre una attenta attribuzione delle priorità Le azioni di un processo sono indifferenziate come urgenza Presenta il problema dell'inversione di priorità con l'uso di

risorse condivise tra processi a diversa priorità



Definizione: Si dice OTTIMO un Algoritmo di Scheduling che Rispetta Tutte

le Scadenze se ciò è Possibile. Rate Monotonic - Priorità Statiche (algoritmo ottimo)

Processi caratterizzati da: Esecuzione Periodica con Periodo Ti

Scadenza (Deadline) al termine del Periodo Ti

Tempo di Esecuzione Netto Ci Eguale per ogni ciclo

Teorema: Se le priorità sono assegnate in ordine inverso alle durate Ti e con n processi il coefficiente di utilizzazione della

CPU è U = i=1..n(Ci/Ti) < n(21/n-1) 0,7

allora viene garantito il rispetto di tutte le scadenze



Earliest Deadline First - Priorità Dinamica (ottimo) Dà la precedenza al processo con scadenza più vicina. Il S.O. deve conoscere le scadenze delle azioni.

Shortest Slack - Priorità Dinamica (ottimo) Dà la precedenza al processo meno dilazionabile. La possibilità di dilazione (laxity) è la differenza tra scadenza

e tempo di esecuzione netto ancora mancante. il S.O. deve conoscere le scadenze e i tempi di esecuzione

netti.


Cooperazione:Primitive di S.O. Real-Time

Primitive Servizi che il sistema operativo mette a disposizione

dei processi. Procedure considerate elementari a livello della

macchina astratta vista dai processi. Costituiscono un'occasione perché il S.O. svolga le

sue funzioni Possono essere eseguite parte in contesto processo, parte in

contesto S.O. L'altra Occasione è costituita dalle risposte ad

interruzioni (RTC o hardware)


Primitive di S.O. Real-Time

Primitive per servizi generali CREATE

Porta un processo dallo stato dormiente a pronto, allocandogli un contesto con descrittore dinamico, con i parametri: priorità, entry point, ampiezza di stack

SUSPEND porta un processo nello stato sospeso

ENINT Abilita un livello di interruzione e gli associa una specifica

routine di servizio applicativo, con visibilità sul contesto del processo invocante che ne diventa proprietario

DISINT Disabilita un livello di interruzione di cui il processo invocante

e' proprietario



Primitive di Temporizzazione ABS_WAIT (abs_time)

Risveglia il Processo Invocante quando t = abs_time REL_WAIT (rel_time)

Risveglia il processo invocante dopo un intervallo pari a rel_time

CYC_WAIT (period) Riattivazione Periodica dopo ogni intervallo pari a period

.....T_OUT (...., tout_time) Associa ad altre attese una scadenza di time out



Primitive di Sincronizzazione WAIT (Semaphore [, t_out])

Attesa su un semaforo con eventuale t_out Si possono adottare diverse semantiche per gli eventi sul

semaforo: Eventi Volatili Eventi Persistenti Binari Eventi Persistenti a Conteggio (= Risorse)

SIGNAL (Semaphore) Produce un evento sul semaforo

RENDEZ-VOUS Primitiva di livello superiore, tipica del linguaggio ADA, che

produce la sincronizzazione stretta tra i due processi Invocanti



Primitive di Comunicazione Costituiscono una estensione delle primitive di

sincronizzazione, a cui è associato un trasferimento (con eventuale trasporto) di informazioni.

Per realizzare il rapporto Produttore-Consumatore Senza deposito

Sincronizzazione stretta basata su primitive tipo Rendez-vous Con accodamento di messaggi

SEND_MESS (message, queue) Accoda il messaggio message nella coda queue, senza

attendere il consumatore



RECEIVE_MESS (queue, message [,tout]) Il processo riceve il primo messaggio nella coda queue,

eventualmente attendendo che ne arrivi uno. Spesso è precisato un Time-Out.

Con deposito di singoli caratteri su buffer circolare. PUT_CHAR (char, buffer [,tout])

Inserisce il carattere char nel buffer (circolare) se c'e' posto, altrimenti attende che si liberi un posto, eventualmente con il tempo limite tout.

GET_CHAR (buffer, char [,tout])

Attende, eventualmente con time-out, che ci sia un carattere nel buffer (circolare).

Prof. Lorenzo Mezzalira, Fabio Salice – Sistemi Operativi Real Time Estratto dalle slide di...

Documents

Transcript of Prof. Lorenzo Mezzalira, Fabio Salice – Sistemi Operativi Real Time Estratto dalle slide di...