Domande Teoria PDF

Gestione del sovraccarico Illustrare la differenza tra overrun e overload. Overload è causato da vari o lunghi overrun. Esistono due tipi di overrun: overrun di attivazione (avviene solo in clock-driven) che avviene quando vengono attivati troppi processi aperiodici e overrun di esecuzione (sia cloc...

Gestione del sovraccarico Illustrare la differenza tra overrun e overload. Overload è causato da vari o lunghi overrun. Esistono due tipi di overrun: overrun di attivazione (avviene solo in clock-driven) che avviene quando vengono attivati troppi processi aperiodici e overrun di esecuzione (sia clock-driven che event-driven) che avviene quando un processo viene eseguito per un tempo più lungo del previsto. Illustrare i tipi di overload e le loro cause. Esistono tre tipi di overload: overload temporaneo causato da overrun di attivazione, overload temporaneo causato da overrun di esecuzione e overload permanente, che avviene quando l'utilizzazione della CPU è maggiore di 1. Illustrare i tipi di gestione del sovraccarico transitorio. Per gestire il sovraccarico transitorio si possono usare: a. Best-effort scheduling: accetta tutti i job e li schedula in base alla loro importanza. Il problema è che questo metodo può portare alla starvation di alcuni job. b. Admission control: effettua un controllo prima di schedulare un job. Se può garantire che il carico del sistema rimanga minore di uno lo schedula. Il problema è che non da priorità ai task importanti ed è lento perche' garantisce gli Worst Case Execution Times (WCETs). c. Robust scheduling: ha tre politiche; una per l'accettazione, una per il rifiuto e una per il recupero. Per l'accettazione usa un algoritmo qualsiasi di schedulazione (EDF, RM, etc.), per il rifiuto usa una politica value-based che rifiuta i job meno importanti in modo da mantenere il carico minore di uno, caso succeda che l'esecuzione di un job finisca prima vengono recuperati i job rifiutati in precedenza in base alla loro importanza (value-based). Illustrare il funzionamento del best-effort scheduling. Vedere 3. A. Illustrare il funzionamento dell’admission control. Vedere 3. B. Illustrare il funzionamento del robust scheduling. Vedere 3. C. Illustrare il funzionamento del robust EDF. Il robust EDF è un tipo di robust scheduling che usa l'EDF come algoritmo di accettazione per i job. Il rifiuto e il recupero, invece, avvengono tramite la priorità dei task: se uno dei job accettati dall' EDF può portare il carico ad un valore minore di uno, esso viene rifiutato. In caso di un’esecuzione finita in anticipo, il job con più importanza (value-based) tra quelli rifiutati viene recuperato. Illustrare i tipi di gestione del sovraccarico permanente. Per gestire il sovraccarico permanente si deve cercare di ridurre l'utilizzo totale della CPU. Si può farlo tramite: a. La riduzione della precisione b. Il job skipping c. Load adaption d. L'elastic Task Model Illustrare il funzionamento della riduzione di precisione. Un job è costituito da due parti per quanto riguarda la precisione di calcolo: una parte obbligatoria e una parte opzionale, che contiene i bit meno significativi della computazione. Evitando di eseguire la parte opzionale dei job si riduce il tempo di calcolo e quindi il carico dello schedule. Illustrare il funzionamento del job skipping. Il job skipping consiste nel saltare un job su S, in modo da ridurre il carico e rendere lo schedule fattibile. Il job skipping può essere implementato in due modi: attraverso il ROT (Red Only Tasks) e BWP (Blue When Possible). Il ROT prevede che si si saltino sempre 1 su S jobs il che non è ottimale poiché si saltano job che non porterebbero l'utilizzo della CPU a più di 100%, ovvero U > 1. Il BWP prevede alcune regole: a. I primi S - 1 jobs devono essere rossi (non skippadbili) b. Se un job blu (skippadbile) finisce l'esecuzione entro la sua deadline, il prossimo job è blu c. Tra due skip devono esserci S - 1 job rossi Illustrare il firm task model. Guardare BWP nell'esercizio 10 Illustrare il load adaption. Il load adaption consiste nel diminuire o aumentare il periodo di un task in modo da mantenere il carico minore di 1. NB: I periodi per i task devono essere tra i range ammissibili per ogni task Illustrare l’elastic task model. L'elastic task model è una forma di Load Adaption che fa uso di un’analogia alla molle in Fisica. Viene applicata una forza per la compressione dei task come se fossero una molla, la compressione dipende sia dalla forza che dalle costanti delle molle e quanto più si comprime, più aumenta lo sforzo per comprimerle ulteriormente. Dare la definizione di carico e carico istantaneo. Il carico e la quantità di calcolo richiesto dalla CPU nell'unità di tempo. GUARDARE LE FORMULE DI CARICO SUGLI APPUNTI. Analisi di schedulabilità Illustrare i tipi di analisi di schedulabilità per l’algoritmo rate monotonic (RM). Per l'algoritmo RM esistono tre verifiche possibili, di cui solo una sufficiente e necessaria: a. Analisi dell'utilizzo (solo necessaria) b. Hyperbolic Bound Test (solo necessaria c. C. Analisi dei tempi di risposta (necessaria e sufficiente) d. Illustrare le analisi di schedulabilità possibili per l’algoritmo deadline monotonic (DM). Per l'algoritmo DM esistono tre verifiche possibili: a. Analisi dell'utilizzo b. Analisi dell'interferenza c. Analisi dei tempi di risposta Illustrare quando uno schedule EDF e’ fattibile. Uno schedule EDF è fattibile quando l'utilizzo della CPU e minore di 1 (si analizza l'utilizzo totale nell'iperperiodo) Scheduling servers Illustrare il funzionamento del background scheduling. Il background scheduling consiste nello schedulare dei job aperiodici quando non c'è nessun altro job in esecuzione. Illustrare il funzionamento di un server periodico semplice. Un server periodico semplice riempie il suo budget all'attivazione del server (all'inizio di ogni periodo), se ha almeno un job aperiodico in coda e consuma il suo budget in forma lineare (un’unità di tempo alla volta) finche' non lo finisce o finchè non finisce di eseguire i job aperiodici. Illustrare il funzionamento di un defferable server (DS). Un DS funziona in modo similare al server periodico semplice, con l'unica differenza che riempie il budget all'inizio di ogni periodo indipendentemente se ci sono o meno job in coda. Illustrare il funzionamento di uno Sporadic Server (SS). Lo sporadic server ha due regole ben distinte per il riempimento e la consumazione del budget. Lo SS consuma in modo uguale agli altri server visti finora. Regole per il riempimento: a. Il budget parte pieno b. Lo SS è attivo quando un job a priorità Pi ha Pi > Pss o quando SS sta eseguendo c. RT (Replenish Time) è il tempo di riempimento, che viene calcolato come la somma di Tss (periodo dello SS) con Ta (il tempo "assoluto" dove è stato attivato SS) d. RA (Replenish Amount) è la quantità di budget che viene riempito, che viene calcolato come il budget consumato da Ta fino a Td (quando SS si è disattivato) Illustrare il funzionamento di un Total Bandwidth Server (TBS). Nel TBS la dimensione del server Us (utilizzo del server) viene allocata in precedenza, e siccome non si sanno i tempi d'arrivo ma solo gli WCETs viene assegnata una deadline al job aperiodico in modo che l'utilizzo Us non venga mai superato. Illustrare per quali problematiche e’ stato introdotto lo Sporadic Server (SS) al posto del Defferable Server (DS). Il DS ha il problema che se un job arriva poco prima del riempimento del budget, questo viene eseguito per più tempo che il budget preveda. Poiché viene consumato e subito riempito senza considerare la consumazione. Invece con lo SS, questo riempimento viene "posticipato" con il replenish time (RT) e il replenish amount (RA), in modo da evitare che il budget reale (tempo dedicato all'esecuzione di job aperiodici) superi il budget del server. Schedulazione priority driven RT Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Earliest Due Date (EDD). Nell'EDD I job vengono attivati tutti a inizio schedule e vengono schedati in base alla deadline più imminente, siccome i job vengono attivati tutti a inizio schedule non c'e' preemption e lo schedule è sempre uguale. Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Earliest Deadline First (EDF). Nell' EDF la priorità più alta è data ai job con la deadline assoluta più vicina. Questo algoritmo di schedulazione permette preemption. Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Latest Release Time (LRT). Per la schedulazione LRT si schedulano i job a partire dall' ultima deadline e continua a schedulare i job con istante di rilascio maggiore. All'inizio dello schedule dovrebbe esserci un "buco". Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Least Slack Time First (LST). L'algoritmo Least Slack Time First (LST) assegna priorità ai task in base al loro slack time, ovvero il tempo residuo che può essere "perso" senza violare la deadline. Lo slack time è calcolato come: Slack Time=(Deadline−Tempo Attuale)−Tempo Rimanente Il task con lo slack time minimo (quindi più urgente) viene eseguito per primo. Questo approccio è utile nei sistemi real-time per rispettare le scadenze, ma può essere sensibile alle variazioni temporali, causando frequenti cambi di contesto. Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Deadline Monotonic (DM). DM assegna la priorità ai task in base alla loro deadline relativa. Più piccola è la deadline relativa, più grande sarà la priorità del task. La priorità della schedulazione con DM e fissa e l'algoritmo ammette preemption Illustrare i meccanismi di funzionamento dell’algoritmo di schedulazione Rate Monotonic (RM). RM assegna la priorità ai task in base al loro periodo. Più piccolo il periodo più alta e la priorità. La priorità nel RM è fissa e l'algoritmo ammette preemption. Schedulazione priority driven non RT Illustrare il funzionamento della schedulazione priority driven. La schedulazione priority driven prevede la schedulazione dei job in base a qualche parametro di priorità. All'istante t lo schedule deve eseguire il job con priorità più alta in t. Illustrare le anomalie di Richard. Le anomalie di Richard avvengono quando, con l'aumentare del numero dei processori e la riduzione delle dimensioni dei job, lo schedule aumenta. Illustrare l’algoritmo di schedulazione FCFS e perché e’ imprevedibile in un sistema RT. L'algoritmo di schedulazione FCFS schedula i job in base al loro arrivo, quindi il job che arriva per primo viene schedulato per primo e cosi via. Il problema è che dipendendo dall'ordine di arrivo (tempo di attivazione) e dalle dimensioni dei job il tempo di risposta può essere molto grande o molto piccolo, rendendo il sistema imprevedibile. Illustrare l’algoritmo di schedulazione SJF (Shortest Job First) e spiegare perché non e’ adatto ad un sistema RT. L'algoritmo di schedulazione SJF prevede la schedulazione dei job più piccoli nella coda di job pronti (attivati). Il problema è che causa starvation, ovvero se arrivano sempre job piccoli e ce n'è uno più lungo in coda il job più lungo non verrà mai eseguito, perdendo quindi la sua deadline, ovvero non è adatto a un sistema RT. Illustrare l’algoritmo di schedulazione Longest Execution Time First. L'algoritmo LETF prevede la schedulazione dei job con i tempi d'esecuzione più lunghi prima, il che è il contrario dell'algoritmo di schedulazione SJF, ma porta le stesse problematiche di starvation, rendendolo inutile in un sistema RT. Illustrare l’algoritmo di schedulazione Round Robin. L'algoritmo di schedulazione RR è una variante dell'algoritmo FCFS, ma prevede l'introduzione della preemptipon, ovvero ad ogni job che viene eseguito dalla CPU viene assegnato un tempo massimo d'esecuzione in modo da eseguire tutti i job in una maniera condivisa. Quando un job finisce il suo tempo d'esecuzione viene rimesso nella coda dei processi pronti. Anche questore algoritmo non è adatto a un sistema RT poiché non prevede nessun compromesso per rispettare la deadline. Illustrare il funzionamento del multi-level scheduling. Il multi level scheduling prevede l'utilizzazione di diversi algoritmi di schedulazione per job con diverse priorità, ad esempio usare RR per job con alta priorità e FCFS per job a bassa priorità. Schedulazione clock driven Illustrare il funzionamento della schedulazione clock driven. Nella schedulazione clock driven le decisioni di schedulazione avvengono in determinati istanti di tempo. Illustrare come e perché lo schedule in un sistema clock driven può essere memorizzato in una tabella (specificare il formato della tabella e il significato dei suoi parametri). La schedulazione clock driven è offline e lo schedule si ripete and ogni iperperiodo H. Quindi lo schedule dell'iperperiodo può essere memorizzato in una tabella. La tabella è costituita da vari elementi con la forma (t, T(t)), con t l'istante di tempo in cui viene eseguito il task T. Illustrare l’utilità di un frame nella schedulazione clock driven. Il frame è la divisione dello schedule in varie parti uguali. Questa divisione permette di effettuare la schedulazione di job aperiodici, gestire il temporizzatore (istante di decisione a inizio frame), la verifica del rispetto della deadline e la gestione di errori ed eccezioni. Illustrare come viene calcolata la dimensione di un frame dati i parametri di un set di task. Il dimensionamento del frame avviene attraverso tre verifiche: a. Le lunghezze di frame possibili sono divisori interi di H b. La lunghezza del frame deve essere maggiore o uguale del maggior tempo di esecuzione c. La lunghezza del frame f deve rispettare la seguente regola (per ogni job i da schedulare): 2f - MCD(f, pi) < Di Illustrare perché i task vengono frazionati nella schedulazione clock driven. Caso l'ultima condizione di dimensionamento del frame non venga soddisfatta per nessuna dimensione di frame possibile i task con dimensione più grande vengono suddivisi in sotto-task in modo da soddisfare la condizione. Per il frazionamento si mantengono gli stessi periodi e le stesse deadline del task iniziale, solo il tempo d'esecuzione che viene divisa tra i sotto-task. Illustrare un esempio di frazionamento di un task nella schedulazione clock driven. Suppongo di avere un task T1 (10, 8, 9) con Ti (pi, ei, Di), e che le condizioni di dimensionamento di un frame non vengano soddisfatte. Suddivido quindi il task T1 in tre task: T1,1 (10, 4, 9) ---- T1,2 (10, 2, 9) ---- T1,3 (10, 2, 9). E verifico ancora che le condizioni di dimensionamento del frame vengono soddisfatte. Come diminuire l’overhead nella schedulazione clock driven. Per diminuire l'overhead nella schedulazione clock driven si deve cercare di utilizzare il frame con la dimensione più grande in modo da diminuire gli istanti di decisone di schedulazione che sono la causa dell' overhead. Dare la definizione e il problema dell’overhead. L'overhead è il tempo di CPU che viene ceduto all'algoritmo di schedulazione perché possa completare lo schedule. Illustrare la differenza tra job sporadico e job aperiodico. Un job sporadico ha la deadline di tipo hard, ovvero la perdita della sua deadline (deadline miss) comporterebbe gravi conseguenze all'ambiente in cui viene utilizzato. Invece un job aperiodico è di tipo deadline soft, ovvero non comporta conseguenze disastrose in caso della perdita della sua deadline (deadline miss) dove viene utilizzato. Illustrare la schedulazione di job aperiodici mediante lo slack stealing. Lo Slack stealing consiste nell'utilizzare lo spazio libero (slack time) di un frame per l'esecuzione del job aperiodico, ma l'esecuzione del job aperiodico avviene prima dell'esecuzione dei job periodici dentro frame. Poiché l'importante dei job periodici non è tanto il tempo di risposta (al contrario dei job aperiodici) ma si che rispetti la sua deadline. Modello sistema RT Definire le condizioni perché uno schedule sia valido (valid schedule). Uno schedule è valido quando: a. Tutti i job partono dopo la propria attivazione b. Il job in esecuzione all'istante t è quello con la priorità più alta in t c. Il tempo di CPU assegnato ad un job deve essere uguale al suo tempo d'esecuzione d. Ogni job è assegnato a un processore alla volta e. Ad ogni processore è assegnato un job alla volta Definire le condizioni perché uno schedule sia fattibile (feasible schedule). Uno schedule è fattibile quando è valido e tutti i job nello schedule rispettano la propria deadline. Definire quando un insieme di job è schedulabile. Un insieme di job è schedulabile se il suo schedule è fattibile con almeno un algoritmo di schedulazione. Definire quando un algoritmo di scheduling è ottimo. Un algoritmo è ottimo se un insieme qualsiasi di job è schedulabile e l'algoritmo riesce a schedularlo. Illustrare i vincoli di consistenza temporale e delle risorse di un job. Vincolo di consistenza temporale: in un job un operazione può iniziare quando la precedente è finita. Vincolo delle risorse di un job: solo un job alla volta può accedere alla sezione critica di una risorsa condivisa. Accesso a risorse condivise Illustrare il problema di inversione della priorità. Il problema della inversione della priorità avviene quando un job blocca un altro per un tempo indeterminato. Per blocco si intende l'attesa di un job a priorità più alta causato da un job con priorità più bassa (avviene solamente con job che cercano di accedere a risorse condivise). Illustrare il funzionamento del Non-preemptive Protocol. Il non-preemptive protocol elimina la preemption quando un job esegue la sua sezione critica, quindi finche il job non ha finito di eseguire la sua sezione critica nessun job potrà eseguire. Il problema di questo protocollo è che causa blocchi non necessari. Illustrare il funzionamento del Priority Inheritance Protocol (PIP). Nel PIP, un job che sta eseguendo la sua sezione critica assume la priorità più alta tra i job che ha bloccato. Nel PIP però un job con priorità più alta può fare preemption sul job che sta eseguendo la sezione critica. Quando il job finisce di eseguire la sua sezione critica, la priorità ritorna a quella nominale. I problemi del PIP è che non evita i blocchi a catena e la starvation. Illustrare il funzionamento del Priority Ceiling Protocol (PCP). Il PCP assegna la priorità ai semafori delle risorse, dove la priorità e la più alta tra le risorse che usano quel semaforo. Il job assume la priorità di ceiling quando (e per tutto il tempo) un job cerca di accedere a qualsiasi risorsa condivisa. Quando il job finisce di accedere alla sua sezione critica (rilascia il semaforo) ritorna alla sua priorità nominale. Sistemi operativi real time Illustrare l’utilità della concorrenza in un sistema operativo RT. Un sistema RT deve essere in grado di controllare o di rispondere a eventi in un ambiente. L'ambiente è una situazione nel mondo reale, e nel mondo reale gli eventi avvengono simultaneamente e non in sequenza come la tipica programmazione. Dunque un SO RT deve essere in grado di gestire gli eventi esterni e deve essere in grado di rispondere in tempo reale (entro un certo tempo - concetto di deadline), per farlo fa uso della concorrenza tra processi, in modo da creare un'"illusione" di esecuzione in parallelo. Illustrare i possibili stati (e le transizioni tra gli stati) che un processo può assumere in un sistema RT. Un processo può essere: avviato, pronto, in esecuzione, in attesa e finito. Il processo passa da avviato a pronto, da pronto all'esecuzione, dall'esecuzione a fine o a attesa e da attesa a pronto. Illustrare il funzionamento del Direct Memory Access (DMA), le problematiche associate a un comune DMA in un sistema RT e le possibili soluzioni per queste problematiche. Alcuni dispositivi di I/O accedono la memoria mediante DMA. Il che vuol dire che i dati dalla memoria non passano prima per la CPU e dopo per il dispositivo di I/O, ma direttamente dalla memoria al dispositivo. Il problema è che la CPU e il dispositivo con DMA usano lo stesso BUS di memoria e questo deve essere gestito. Esistono due soluzioni: a. Cycle stlealing: Ogni volta che il dispositivo di I/O deve accedere alla memoria ruba un ciclo di memoria alla CPU in modo da poter usare esclusivamente il BUS. Il problema è che questo genera imprevedibilità nel sistema RT poiché non si sa mai quando la CPU dovrà cedere e per quanto dovrà cedere il BUS al dispositivo. b. Time Slice: Fa sempre un ciclo di memoria dedicato al dispositivo e un ciclo di memoria dedicato alla CPU, in modo da dividere il BUS per un tempo equo tra il dispositivo I/O e la CPU. Il problema di questa soluzione è che si diminuisce la portata di dati dalla memoria alla CPU, ma almeno è prevedibile. Illustrare i problemi associati all’uso di una Cache in un sistema RT. La cache non è portata per sistemi RT poiché è fonte di imprevedibilità, poiché la CPU andrebbe prima a cercare in cache e dopo, se il dato non si trova in cache (cache miss), vai cercarlo in memoria. Il cache miss e il cache hit causano inprevedibilita poiché non si sa mai quando ci sarà un cache hit o viceversa, il che non è ammissibile in un sistema RT. Illustrare i problemi associati alle interruzioni in un sistema operativo RT. Le interruzioni generate dai dispositivi di I/O possono creare ritardi indeterminati sui normali processi del sistema. Illustrare come vengono gestite le interruzioni in un sistema operativo RT. Le interruzioni possono essere gestite in tre modi in un OS RT: a. Disabilito tutte le interruzioni a parte il timer (clock, penso). Assegna dispositivi di I/O a dei task. Grande prevedibilità ma grosso impatto sulle performance del processore. b. Disabilito tutte le interruzioni a parte quelle del timer e gestisco i dispositivi di I/O mediante delle kernel routine attivate con il timer. Alta prevedibilità grazie alle routine periodiche ma grosso impatto sulla CPU, inoltre il kernel inoltre va modificato quando si aggiungono dispositivi c. Abilita tutte le interruzioni ma limita i driver alle minime dimensioni possibili. Non ci sono più attese ma la prevedibilità diminuisce in quanto i processi potrebbero avere più importanza delle operazioni di I/O Illustrare come vengono gestite le chiamate di sistema (Syscall) in un sistema operativo RT. Affinchè non ci siano ritardi indeterminati nell'esecuzione dei processi alle chiamate di sistema viene assegnato un tempo massimo d'esecuzione in modo da non generare imprevedibilità. Illustrare perché un comune meccanismo di semafori non è adatto a un sistema RT e quali soluzioni si possono intraprendere. Un comune semaforo non è adatto a un sistema real time perché può causare il problema dell'inversione della priorità. In modo da evitare questo problema, nei sistemi real time sono stati introdotti diversi protocolli: a. Non-preemptive protocol b. Priority inheritance protocol c. Priority ceiling protocol Illustrare il funzionamento di un sistema RTLinux rispetto al Linux normale. Il sistema RTLinux è un path applicabile al comune kernel di Linux. RTLinux fa andare il kernel di Linux normale come se fosse un processo (a bassa priorità) del kernel real time. Illustrare la differenza tra RTLinux e RTAI (Real Time Application Interface). RTLinux fa andare il kernel normale di Linux come se fosse un processo a bassa priorità del kernel real time, invece l'RTI fornisce servizi per la gestione RT, Linux diventa un task in background che funziona quando non ci sono attività RT. POSIX threads Illustrare la differenza tra concorrenza competitiva e concorrenza cooperativa e quali tipi di comunicazione vengono usati in questi tipi di concorrenza. La concorrenza cooperativa tra due processi consiste nell'utilizzo della stessa risorsa per un fine comune, invece la concorrenza competitiva sono due processi che cercano di avere l'esclusività della risorsa per raggiungere il singolo obiettivo. La comunicazione competitiva fa uso dello scambio di messaggi tra i processi, mentre la concorrenza cooperativa prevede che i processi usino la stessa porzione di memoria (memoria condivisa). Illustrare come viene creato un Thread in POSIX, i parametri per la creazione e la loro utilità. Un thread in posse viene creato mediante la funzione pthread_create( ) che ha come parametri: a. Un puntatore al thread b. Un puntatore alla funzione che è l'attività del thread c. Un puntatore ai parametri della funzione d. Un puntatore agli attributi di configurazione del thread Illustrare cos’è un thread joinable e un thread detached, e la differenza tra di loro. Un thread invocante fa join del thread joinable invocato (attende la sua terminazione), mentre un thread detached non presenta questo vincolo e ha l'esecuzione autonoma rispetto al thread invocante. Illustrare la struttura di una funzione (task/attività) assegnata ad un p_thread e l’uscita del thread a fine programma. La funzione che esegue l'attività del thread è di tipo void e deve terminare con la segnalazione dell'uscita dal thread con p_thread_exit, dove il parametro di p_thread_exit rappresenta il dato ritornato al thread chiamante. Illustrare il join di un thread joinable. p_thread_join Illustrare come la libreria pthread gestisce l’accesso alle sezioni critiche attraverso dei mutex. Per accedere alla sezione critica: pthread_mutex_lock ( &nomeMutex ), per rilasciare la sezione critica: pthread_mutex_unlock ( &nomeMutex ), per segnalare l'uscita dalla sezione critica: pthread_cond_signal ( &nomeCondizione ), per aspettare che la risorsa si liberi (aspetta la notifica) pthread_cond_wait ( &nomeCondizione ). Inter task communication Illustrare i modi possibili di comunicazione tra task. I modi possibili di comunicazione tra task sono: a. Variabili globali condivise b. Scambio di messaggi c. Porte d. Porte stick e. CAB Illustrare il funzionamento della comunicazione tra task mediante l’uso di variabili globali Condivise. Nella comunicazione mediante variabili globali condivise i task possono sia leggere che scrivere la variabile condivisa ma lo fanno in modo esclusivo mediante un semaforo. Illustrare il funzionamento della comunicazione tra task mediante lo scambio di messaggi. Nello scambio di messaggi ogni task ha la sua propria memoria che viene usata come "casella postale" per i messaggi inviati. Lo scambio di messaggi avviene tramite un canale. Illustrare il funzionamento della comunicazione tra task mediante l’uso di porte di Comunicazione. Ogni volta che due task devono comunicare creano una porta e usano i primitivi send e receive. I messaggi inviati alla porta vengono memorizzati in un buffer, la lettura dei messaggi avviene in FIFO ed ogni volta che un messaggio viene letto esso viene eliminato. Illustrare il funzionamento della comunicazione tra task mediante l’uso di porte stick. Le porte stick sono porte che mantengono sempre l'ultimo valore scritto e ogni volta che un task deve inviare un messaggio, questo viene riscritto. Le porte stick funzionano in modo similare alle variabili globali. Illustrare perché sono state introdotte le porte stick al posto delle porte comuni. Le porte stick sono state introdotte per risolvere il problema di riempimento e svuotamento (che causano eccezioni) del buffer della porta. Una porta stick non resta mai vuota e non si riempie mai con più di un valore. Illustrare i problemi di comunicazione ritrovati nelle porte quando i periodi tra due task che comunicano sono diversi. Come questi problemi differiscono da quelli riscontrati nella comunicazione mediante una porta stick? Quando due task con periodi diversi comunicano mediante una porta possono occorrere dei problemi, se il task di lettura ha il periodo più piccolo del task di scrittura, svuoterà il buffer, generando un’eccezione. Se invece il task di scrittura ha il periodo più piccolo il buffer viene riempito più della sua capacita massima e genera un’eccezione. La porta stick invece ha problemi di consistenza, ovvero quando i task hanno periodi diversi può darsi che il task che legge possa leggere due volte lo stesso valore (periodo lettura più piccolo) o non leggere neanche il valore (periodo lettura più grande). Illustrare il funzionamento della comunicazione tra task mediante l’uso di un Cyclic Asynchronous Buffer (CAB). Il CAB è una serie di buffer che vengono allocati dinamicamente. L'ultimo valore sul CAB è sempre presente (come con la porta stick) e quando un task deve scrivere, la scrittura viene messa in un altro buffer. Quindi se il CAB viene usato da N task la dimensione del CAB deve essere di N + 1 buffer. Illustrare come deve essere dimensionato un Cyclic Asynchronous Buffer (CAB) in modo da evitare che il CAB si blocchi. Numero di buffer = N task + 1. Poiché può succedere che gli N task stiano scrivendo, dunque deve essere creato un altro buffer in modo da salvare l'ultimo valore scritto. Illustrare il protocollo di lettura di un Cyclic Asynchronous Buffer (CAB). Lettura di un CAB: a. Richiesta di lettura b. Assegnazione del puntatore del buffer al task c. Lettura del buffer d. Libera il puntatore Illustrare il protocollo di scrittura di un Cyclic Asynchronous Buffer (CAB). Scrittura di un CAB: a. Richiesta di scrittura b. Assegnazione al puntatore a un buffer che non sia l'ultimo scritto c. Scrittura del buffer d. Libera puntatore RT communication protocols Illustrare i livelli di comunicazione di un CAN secondo lo standard ISO/OSI e come questo differisce in termini di livelli di comunicazione dal vecchio CAN. Il CAN con specifica a parte A ha tre livelli di comunicazione: il Physical Layer, il Transfer Layer e l'Object Layer. Il CAN con specifica a parte B invece ha i livelli conforme lo standard ISO/OSI: Application, Data Link Layer, Physical Layer. Illustrare il funzionamento del Data Link Layer in un sistema RT. Il Data Link Layer è diviso in due parti: A. LLC (Logical Link Control): a. Gestisce quali messaggi leggere b. le notifiche di Overload c. la gestione del recupero. B. MAC (Medium Access Control): a. Codifica del frame b. Detezione degli errori c. Segnalazione degli errori d. Acknowledgement e. Serializzazione/ Deserializzazione Illustrare cos'è un CAN (Controller Area Network). Un CAN è un protocollo di comunicazione, sicuro, veloce e prevedibile idealizzato da Bosch. Il CAN connette vari nodi in modo che possano comunicare tutti in un unica rete senza che ci sia bisogno di una connessione Point-to-point come avveniva prima del CAN o di altri protocolli di comunicazione mediante un BUS. I nodi sono sempre in ascolto sulla rete e identificano il messaggio attraverso un ID che esiste in ognuno dei messaggi, l'ID serve anche a dare precedenza ai messaggi mediante la bit-wise arbitration. Illustrare la differenza tra un CAN 2.0 con specifica a parte A e un CAN 2.0 con specifica a parte B e come può avvenire la comunicazione tra nodi con le diverse specifiche. Il CAN con specifica a parte A differisce dal CAN con specifica a parte B per il loro ID, il CAN con specifica a parte A ha un ID di 11-bit mentre quello a parte B ha un ID a 29-bit. Cambia anche la descrizione dei livelli di comunicazione, che nel CAN a parte B viene descritta dal modello ISO/OSI. Ci sono anche altre differenze riportate nello standard (vedere file Sistemi real time/CAN bus/Standard CAN 2.0) Illustrare il CRC (Cyclic Redundancy Check). Il CRC consiste in alcuni calcoli realizzati con i valori degli altri Field e viene salvato nel CRC Field. Mentre il destinatario riceve il messaggio anche lui calcola il CRC e lo confronta con quello del CRC Field, se è uguale procede sennò invia l'errore CRC ERROR. Illustrare il Frame Check. Il frame check consiste nel verificare le dimensioni dei frame e assicurarsi che non vengano eccedute altrimenti genera un FORM ERROR. Illustrare l’acknowledgement check. L'acknowledgement check avviene durante la trasmissione del messaggio, se il ricevente riceve il messaggio, riscrive l'ACK SLOT con un bit dominante per informare il mittente che il messaggio è stato ricevuto. Se il mittente (che resta sempre in ascolto) non legge un bit dominante nell'ACK SLOT allora genera un AKCLOWLEDGEMENT ERROR. Illustrare il funzionamento del monitoring nella trasmissione tra nodi. Mentre un nodo invia il messaggio allo stesso tempo legge i valori del BUS, se i valori non corrispondono a quelli inviati, genera un BIT ERROR. Illustrare il funzionamento del bit stuffing. Il bit stuffing consiste nel inserire un bit di polarità diversa ad ogni 5 bit di polarità uguale. Sia il mittente che il ricevente hanno il meccanismo di bit stuffing, quindi i dati non vengono fraintesi. Se il ricevente identifica che dopo 5 bit di polarità uguale non è stato mandato un bit di polarità inversa genera lo STUFF ERROR. Illustrare l’utilità di un error flag e come procede la trasmissione dei messaggi dopo che Avviene. Quando un nodo rileva un errore invia un ERROR FLAG, che consiste nell'invio di 6 bit di uguale polarità nel BUS. Gli altri nodi rilevano l'ERROR FLAG perché viola le regole di bit stuffing e quindi a sua volta generano anche loro un ERROR FLAG, la lunghezza totale della sequenza di bit di stessa polarità dopo l'error flag può arrivare a 12-bit. Illustrare il Time Triggered Protocol (TTP) CAN. Nel TTP CAN la comunicazione dipende da una temporizzazione e deriva dal TDMA. Il TTP can prevede un ciclo base composto da (tutti sono intervalli di tempo): A. Reference message: Indica l'inizio del ciclo base B. Exclusive Window: invio di messaggi periodici che con competono per il BUS C. Arbitration Window: invio di messaggi "event-triggered" che competono per il BUS D. Free Window: non utilizzata Data Distribution Service (DDS) Illustrare le entità del DDS e le loro funzionalità/usi. Il DDS ha le seguenti entità: A. DataDomainFactory: è il Global Data Space, dove stanno tutti i Data Space B. DomainParticipand: è il dominio, che viene identificato con un nome (String) e dove stanno i suoi Topic C. Publisher: è l'entità che scrive i dati, ogni Publisher può avere vari DataWriter D. Subscriber: è l'entità che legge i dati, ogni Subscriber può avere vari DataReader E. DataReader: è l'entita responsabile per la lettura dei dati nel suo Topic F. DataWriter: è l'entità responsabile per la scrittura dei dati nel suo Topic G. Topic: è l'argomento, ovvero il tipo di dato Illustrare l’utilità del DDS. Il DDS è un API che serve come interfaccia tra la comunicazione e l'applicativo. Il DDS "nasconde" quello che avviene dentro i meccanismi di comunicazione, in modo che il programma si preoccupi solamente dei dati che vengono ricevuti/inviati. “Efficient and Robust Delivery of the Right Information to the Right Place at the Right Time.” Illustrare la necessita’ dei QoS tra entità. I parametri di QoS servono a legare le entità in base a delle qualità. Per alcuni QoS è necessario che coesistano tra le entità che vogliono comunicare, altrimenti non può avvenire comunicazione. Illustrare il QoS: Durability. La QoS DURABILITY indica se i dati scritti andranno a vivere più a lungo dei tempi in cui sono stati scritti. Ovvero se i dati scritti verranno salvati per DataReader che arriveranno in futuro o meno, o anche se verranno salvati in una memoria permanente (quindi per sempre). Illustrare il QoS: Reliability. La QoS RELIABILITY indica il livello di affidabilità che devono avere le entità che lo implementano. Ovvero, se garantisce che tutta la cronologia del DataWriter sarà inviata al DataReader o meno. Illustrare il QoS: History. La QoS HISTORY indica come si deve comportare il servizio in caso un dato cambi più volte prima che possa essere comunicato a uno o più Subscriber. Il servizio indica se devono essere inviati tutti i valori intermedi, solo alcuni o tutti. (NON NECESSARIO PER LA COMUNICAZIONE) Illustrare il QoS: Deadline. La QoS DEADLINE indica ogni quanto un DataReader deve aggiornare il valore di ogni istanza e quanto un DataWriter deve scrivere un nuovo valore. Il valore default è infinito, ovvero non aggiorna ne riscrive mai. Illustrare il QoS: Liveliness. La QoS LIVELINESS indica ogni quanto un’entità deve indicare se è ancora attiva e se questo valore viene inserito manualmente o automaticamente. La LIVELINESS serve per sapere se un’entità continua ad avere l'OWNERSHIP o meno. Illustrare il QoS: Time_Based_Filter. La QoS Time_Based_Filter specifica se un DataReader è interessato in alcuni "sottovalori" dei dati (subset of the values of the data) Illustrare il QoS: Ownership. La QoS OWNERSHIP indica se è permesso a vari DataWriter di scrivere la stessa istanza di dati e, se si, come devono essere gestite le modifiche (OWNERSHIP_STRENGTH). Illustrare il QoS: Ownership_Strength. La QoS OWNERSHIP_STRENGTH indica l'importanza data a un DataWriter per decidere quale dei DataWriter permessi di scrivere la stessa istanza andrà a scriverla davvero. (QoS solo per il DataWriter). Illustrare il QoS: Destination_order. La QoS DESTINATION_ORDER indica l'ordine dei dati modificati da un Publisher. Illustrare il QoS: Latency_Budget. La Qos Latency_Budget indica il massimo Delay accettabile da quando il dato viene scritto a quando il ricevitore viene notificato dell'arrivo. Illustrare il QoS: Resource_Limits. La QoS RESOURCE_LIMITS indica il numero massimo di risorse che possono essere consumate dalle entità. Illustrare il QoS: User_Data. Nella QoS USER_DATA vengono passati valori come parametri del QoS che rappresentano dati utente. Illustrare il QoS: Partition. La QoS PARTITION dichiara una partizione in comune per il Publisher e il Subscriber. Un DataWriter di un Publisher può comunicare con un DataReader di un Subscriber solamente se il Pulisher e il Subscriber hanno una partizione in comune.