Blunì - Appunti SRT PDF

Preview

Summary

appunti del cors real time systems, appunti del cors real time systems...

Description

Universit`a degli Studi di Bergamo

A PPUNTI

DI

SRT

LPs & Kyra Production

Anno Accademico 2017/2018

Contents 1

Caratteristiche di un RTOS 1.1 Caratteristiche di un Real Time System . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Caratteristiche di un Real Time Operating System . . . . . . . . . . . . . . . . . . 1.3 Caratteristiche di un Real-Time Kernel . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 1 1

2

POSIX Concurrency: mutual exclusion and synchronisation 2.1 Shared memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2

3

Inter-task communication mechanisms 3.1 Shared memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Message passing paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Send messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Receive messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Periodic Task Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Caso T1 < T2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Caso T1 > T2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Stick ports . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Cyclic Asynchronous Buffer (CAB) . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 4 5 5 5 5 5 5 6

4

Real Time Communication Protocols 4.1 Field bus in the ISO-OSI model . . . . . . . . . . 4.2 TDMA . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Control Area network: CAN bus . . . . . . . . . 4.3.1 Livello 1 - Physical layer . . . . . . . . . . 4.3.2 Livello 2 - Data Layer . . . . . . . . . . . 4.3.3 Bit-wise arbitration . . . . . . . . . . . . . 4.3.4 Tipi di messaggio . . . . . . . . . . . . . . 4.3.5 Rilevamento degli errori . . . . . . . . . . 4.3.6 Time Triggered Protocol CAN - TTP CAN

5

Data Distribution Service - DDS

6

Modello di Sistema Real Time 6.1 Modalit`a di attivazione dei job 6.2 Preemption . . . . . . . . . . . . 6.3 Real Time Task . . . . . . . . . . 6.4 Criteri di ottimalit`a . . . . . . . 6.5 Deadline hard e soft . . . . . . .

7

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

7 . . . . . . . . 7 . . . . . . . . 7 . . . . . . . . 7 . . . . . . . . 8 . . . . . . . . 8 . . . . . . . . 9 . . . . . . . . 9 . . . . . . . . 9 . . . . . . . . 10 11

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

12 . . . . 12 . . . . 12 . . . . 13 . . . . 14 . . . . 15

Schedule 7.1 Valid schedule . . . . . . . . . . . . 7.2 Feasible schedule . . . . . . . . . . 7.3 Vincoli di schedulazione . . . . . . 7.3.1 Vincoli temporali di un Job 7.3.2 Vincoli su risorse . . . . . . 7.3.3 Vincoli temporali effettivi . 7.3.4 Teorema schedulabilit`a . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . .

I

. . . . . . .

. . . . . . .

16 . 16 . 16 . 17 . 17 . 17 . 17 . 17

CONTENTS

8

Algoritmi di schedulazione 8.1 Problema della schedulazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Classificazione degli algoritmi di schedulazione . . . . . . . . . . . . . . . . . . . 8.3 Tipologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Approcci allo scheduling RT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.5 Approccio Clock Driven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.6 Approccio Priority Driven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 18 18 19 19 19

9

Algoritmi Clock-Driven 9.1 Dimensione dei frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 Mescolare Job Periodici e Aperiodici . . . . . . . . . . . . . . . . . . . . . . . . . .

20 20 21

10 Algoritmi Priority-Driven non-RT 22 10.1 Classificazione algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.2 Scheduling prioritario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.3 Anomalie di scheduling - Teorema di Graham . . . . . . . . . . . . . . . . . . . . 24 11 Algoritmi priority-driven RT 11.1 Algoritmo EDD (Earliest Due Date) . . . 11.2 Algortimo EDF (Earliest Deadline First) 11.3 Algortimo LRT (Latest Release Time) . . 11.4 Algoritmo RM (Rate Monotonic) . . . . 11.5 Algoritmo DM (Deadline Monotonic) . 11.6 Confronto RM - DM . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

25 . 25 . 25 . 26 . 26 . 26 . 26

12 Scheduling servers 12.1 Background Scheduling . . . . 12.2 Simple Periodic Server . . . . . 12.3 Bandwidth-preserving Servers 12.4 Deferrable Servers . . . . . . . . 12.5 Sporadic Servers . . . . . . . . . 12.6 Total Bandwidth Servers . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

27 . 27 . 27 . 27 . 28 . 28 . 28

13 Gestione del sovraccarico 13.1 Tipi di sovraccarico . . . . . . . . . 13.2 Cause dei sovraccarichi . . . . . . . 13.3 Gestione . . . . . . . . . . . . . . . 13.4 Value-based Scheduling . . . . . . 13.4.1 Best effort scheduling . . . 13.4.2 Admission Control . . . . . 13.4.3 Robust Scheduling . . . . . 13.4.4 Robust EDF . . . . . . . . . 13.5 Performance degradation . . . . . 13.5.1 Riduzione della precisione 13.5.2 Imprecise Computation . . 13.5.3 Job skipping . . . . . . . . . 13.5.4 Relaxing timing constrains 13.5.5 Elastic task model . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . .

II

29 29 29 29 30 30 30 31 31 31 31 32 32 32 32

CONTENTS

14 Accesso alle risorse condivise 33 14.1 Protocolli di accesso alle risorse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 14.1.1 PIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 14.1.2 PCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

III

1

Caratteristiche di un RTOS 1.1 Caratteristiche di un Real Time System 





La concorrenza: serve per eseguire processi che nel mondo reale sono paralleli. Elevata sicurezza e affidabilit`a: molti sistemi sviluppati con RTOS tengono sotto controllo dei processi per cui una failure potrebbe compromettere la sicurezza di un ambiete o di persone. Garanzia del tempo di risposta: Sistemi che utilizzano RTOS devono garantire che le azioni vengano eseguite entro dei limiti temporali ben precisi. Quindi la predicibilit `a dell’esecuzione di questi sistemi `e elevata.

1.2 Caratteristiche di un Real Time Operating System 

Timeliness: deve provvedere dei meccanismi per: – gestione del tempo (timer, delays) – gestione dei tasks con specifici vincoli di tempo







Predicibilit`a: deve garantire in anticipo che la deadline verr `a rispettata e notificarne il mancato rispetto. Fault tolerant: deve garantire di non incorrere in crach nel caso di guasti SW/HW Peak load: deve essere progettato affinch `e il suo funzionamento sia garantito anche in momenti di carico di lavoro elevato.

1.3 Caratteristiche di un Real-Time Kernel In general, real-time operating systems must provide: 

Preemptive, priority-based scheduling



Preemptive kernels



Latency must be minimized

1

2

POSIX Concurrency: mutual exclusion and synchronisation Due metodi fondamentali per l’interazione fra attivit`a: 

Shared memory



Message Passing:

2.1 Shared memory La memoria condivisa `e stata la prima tecnica supportata dai vecchi sistemi operativi in quanto semplice in quanto a livello HW ogni thread pu`o accedere alla stessa memoria. E’ necessario per o` che a tale memoria sia permesso l’accesso dalle attivit `a concorrenti una per volta per evitare di leggere o scrivere dati mentre altri processi li stanno modificando. Esiste quindi il concetto di mutua esclusione 











Due o pi u ` thread possono fare accesso ad una risorsa condivisa (es: una variabile globale) solo in modo mutuamente esclusivo. Per garantire che, in ogni istante, solo un thread possa accedere alla risorsa occorre definire delle sezioni critiche. La libreria pthread gestisce l’accesso alle sezioni critiche attraverso degli oggetti detti mutex(mutualexclusive). Ogni thread puo` acquisire e rilasciare il controllo di un mutex attraverso due funzioni definite dalla libreria stessa. Fino a quando un thread mantiene il controllo su un certo mutex, nessun altro thread pu o` acquisirne il controllo. Quando un thread rilascia il controllo di un mutex, un altro puo` prenderne possesso.

2

2.1 Shared memory

In POSIX la libreria pthread consente di notificare il verificarsi di particolari eventi: Un thread resta in attesa del verificarsi di un particolare evento 





Un altro thread esegue una notifica ≪sbloccando≫ il thread in attesa.

Il meccanismo richiede l’uso dei mutex e di un’altra particolare variabile detta dizione≫.

con-

≪

La libreria mette a disposizione funzioni per l’attesa, la notifica e la notifica broadcast di ≪condizioni≫

Al momento della chiamata a pthread cond signal, il thread chiamante rilascia il mutex e l’esecuzione passa al thread in attesa. In caso non ci siano thread in attesa il chiamante riacquisisce il mutex e riprende l’esecuzione La funzione pthread cond signal pu`o notificare soltanto un singolo thread in attesa. Nel caso si vogliano notificare pi u ` thread `e possibile usare pthread cond broadcast: 

Il chiamante rilascia il locks il mutex.



Tutti thread in attesa vengono notificati e concorrono per l’acquisizione del mutex.



Solo uno lo acquisisce entrando nella sezione critica.

3

3

Inter-task communication mechanisms 3.1 Shared memory VANTAGGI 

Meccanismo veloce



basso run-time overhead



e` disponibile la schedulability analysis

SVANTAGGI 

L’accesso ai dati deve avvenire in mutua esclusione



Esistono regioni che non sono preemptive.



semaphores, priority inheritance, priority ceiling.



Non sono ottime in caso di approcci modulari



Informazioni locali dei task sono esposte a tutti i task



un cambiamento in un task pu o` comportare l’aggiornamento anche degli altri

3.2 Message passing paradigm Un altro metodo per lo scambio di informazioni fra task e il message passing: 

ogni task lavora con la sua propria memoria privata.



I dati sono scambiati fra i task utilizzando dei messaggi attraverso un canale.

Molti sistemi operativi permettono di astrarre i canali di comunicazione attraverso la definizione delle porte. Ogni porta pu`o: 

differire dalle altre per il numero dei task che sono abilitati a spedire messaggi



differire dalle altre per il numero dei task che sono abilitati a ricevere messaggi



politiche di utilizzo



gestione delle eccezioni

Ogni porta, prima di essere utilizzata deve essere creata e inizializzata. Le due primitive fondamentali sono: Send e Receive

4

3.3 Periodic Task Communication

3.2.1 Send messages Un messaggio spedito su una specifica porta viene inserito in un buffer creato alla creazione della posrta setta. Ogni porta deve definire come viene gestita la situazione in cui viene spedito un messaggio su una porta che ha il proprio buffer pieno: 

il mittente resta bloccato finch e` non si libera spazion nel buffer, ovvero un destinatario estrae/legge un messaggio del buffer



il messaggio che si `e tentato di spedire viene perso



un codice di errore e` tornato dalla funzione di send

3.2.2 Receive messages Alla ricezione viene estratto il messaggio che sta ”in testa” al buffer della specifica porta che si sta ”ascoltando”. Nel caso si cerchi di leggere da una porta con buffer vuoto: 

il ricevente resta bloccato fino a che un nuovo messaggio `e disponibile



un errore e` tornato dalla funzione di lettura della porta

3.3 Periodic Task Communication

3.3.1 Caso T1 < T2 T1 spedisce pi u` messaggi di quanti T2 pu`o riceverne e quindi, nel caso in cui si riempia il buffer della porta, il task T1 proceder`a alla velocit`a del task T2

3.3.2 Caso T1 > T2 T2 legge pi u ` messaggi di quanti T1 pu`o spedire e quindi, nel caso in cui si il buffer della porta sia vuoto, il task T2 proceder`a alla velocit`a del task T1

3.4 Stick ports Le stick port funzionano come segue: 

il messaggio piu` recente `e sempre disponibile



un nuovo messaggio sovrascrive sempre quello precedente



la lettura di un messaggio non ”consuma”, ovvero non elimina il messaggio dal buffer della porta

5

3.5 Cyclic Asynchronous Buffer (CAB)

Quindi con questo tipo di porte non esistono code piene o vuote e non esiste il concetto di messaggi precedenti a livello di porta.

Anche se in questo tipo di porte un task non pu o` bloccarsi per casi di buffer pieno (sender) o vuoto (receiver) `e necessario l’accesso al buffer in mutua esclusione. Tale tipo di accesso pu`o causare, per esempio in caso di messaggi lunghi, che i task restino a lungo in attesa che un mutex/semaforo venga rilasciato. A tale fine si possono utilizzare meccanismi di buffe replication

3.5 Cyclic Asynchronous Buffer (CAB) I CAB sono: 

e` un meccanismo per lo scambio di messaggi fra task con diverse velocit`a



conflitti di memoria non sono possibili in quanto i buffer interni sono replicati



per il resto funzionano come le stick ports

Un CAB in pratica generalizza il concetto di Dual Buffering per N ricevitori: 







l’accesso ai dati viene eseguito tramite puntatori in memoria accedendo ai dati un task non e` forzato ad effettuare la copia degli stessi nel proprio spazio di memoria molti tasks posso accedere simultaneamente allo stesso messaggio in ogni istante, il puntatore (mbr) punta al pi u ` recente buffer utilizzato da chi ha scritto l’ultimo messaggio.

Un CAB utilizzato per N tasks deve avere N+1 buffers. Il buffer in pi`u `e necessario per mantenere il messaggio pi u ` recente nel caso in cui tutti gli altri buffer siano occupati.

6

4

Real Time Communication Protocols 4.1 Field bus in the ISO-OSI model

4.2 TDMA 

assicura che l’accesso al canale si a libero da collisioni



la banda per ogni singolo nodo `e rispettata e garantita



assume che tutti i nodi siano sincronizzati fra loro



pu`o succedere chela rete sia sottoutilizzata





la trasmissione regolare di pacchetti pu o` essre vista come ”heartbeats” e quindi `e semplificata la gestione del fault dei nodi jitter molto limitato

4.3 Control Area network: CAN bus CAN `e basato sul meccanismo di comunicazione broadcast. I pacchetti trasmessi da un nodo CAN non contengono indirizzi di alcun genere, dato che non sono associati indirizzi alle singole stazioni. Il contenuto del messaggio (giri al minuto, temperatura motore,temperatura abitacolo. . . ) e` identificato univocamente tramite un identificatore, che definisce anche la priorit `a del messaggio. La specifica CAN e` cos...