Please enable JavaScript.

Coggle requires JavaScript to display documents.

SERT, Algoritmi non ottimali, 1- Intro Embedded, 2 - Intro Real Time, 3 -…

- - - - Cosa fa un sistema embedded?
        
        elabora i segnali esterni
        
        comunica tra mondo esterno ed interno
        
        memorizza l'informazione
        
        NB: a seconda del contesto, si possono fare delle ottimizzazioni, ad esempio un sensore fotografico viene usato sia su una reflex che su una webcam!
        
        Quali sono le sue caratteristiche?
        In ambito commerciale ci interessiamo a:
        
        costo finale, molto incisivo sulle scelte
        
        time to market, non posso venderlo troppo tardi
        time to live, quanto dura il prodotto?
        volume, fortemente dipendente dallo scopo (chip sottocutaneo vs chip nell'aereo)
        
        In ambito hardware ci interessiamo a:
        
        interfacce di comunicazione: incidono molto sul prezzo finale
        
        interfacce utente: pulsanti, led, ...
        
        consumo energetico: quanto dura il prodotto?
        dimensioni/peso, come per il volume.
        
        In ambito software guardiamo a:
        
        capacità di calcolo, comunicazione e memorizzazione
        
        LOC, quante ne può memorizzare il prodotto?
        
        QoS, molti sistemi embedded sono impegnati in campi come la sicurezza (es airbag)
        
        Aggiornamenti, per i bugfix.
        
        Dependable
        Un concetto forte espresso finora riguarda il fatto che un sistema embedded svolge un ruolo chiave, e per questo altri componenti dipendono da lui.
        Il sistema dependable deve garantire nel miglior modo aspetti come:
        
        affidabilità, probabilità di guasto?
        
        manutenibilità, tempo per ripararlo?
        
        disponibilità, probabilità che funzioni? (influenzato dai primi due fattori)
        
        safety, guasto non deve recare danno a persone (es: tolgo sensore laser dal pc, non devono poterlo usare)
        
        sicurezza, resistenza a usi non autorizzati (es: non devo poter togliere il laser dal pc in maniera semplice).
- - - - Ridefinisco il sistema RT
        Un sistema è un mapping tra input e output.
        Un sistema real time è un sistema basato sulla correttezza logica del dato + tempistiche per avere tale dato.
        
        "Veloce", "Immediato", etc NON SONO tempistiche, una tempistica è un delta di tempo preciso.
        
        Con quale tasso opera un sistema rt?
        
        Puramente ciclico, periodico.
        
        Perlopiù ciclico, alcune operazioni eseguite più di rado (es. atterraggio rispetto al volo stesso).
        
        asincroni e perlopiù predicibili, non periodici, come i segnali radar, predicibili (se oggetto fermo posso prevedere non si muoverà per un pò).
        
        asincroni e impredicibili, non so dove/quando/, ma quando accadrà, dovrò operare in un certo modo (es: airbag).
        
        Job, Task, Processore, Risorsa
        
        Un job è un'unita di lavoro schedulabile ed eseguibile dal sistema rt. Può essere processo, invio msg, lettura file etc, quindi il concetto di "Unità" dipende dal contesto.
        
        Un task è un insieme di job correlati, con scopo in comune.
        esempio: il task è 'fare una multa', composto dai job 'prendi velocità', prendi 'targa', 'check velocità', assegna multa.
        
        Un processore è un componente attivo del sistema rt che esegue il job. Componente attivo può essere una cpu, un canale radio, un disco etc..
        
        Una risorsa è una componente passiva la cui disponibilità è necessaria per eseguire un job.
        
        La differenza tra processore e risorsa?
        Il processore ha una velocità, incide sulle tempistiche, la risorsa no, di lei ci interessa solo presenza/assenza.
        Una risorsa può diventare processore?
        
        Dipende dal contesto, esempio:
        una cpu è processore, la ram incide sui tempi di risposta? se nel contesto preso in caso si allora è un processore, altrimenti è una risorsa.
        
        Vincoli temporali nei job
        Definiamo:
        
        istante di rilascio, il job diventa disponibile per l'esecuzione. Non è detto venga ri-eseguito subito.
        
        scadenza/deadline, tempo entro il quale il job deve aver completato l'esecuzione.
        
        tempo di risposta del job, se job viene rilasciato dopo 5s, e ha completato l'operazione in 3s, ci ha messo 2s per rispondere.
        
        scadenza relativa è massimo tempo di risposta ammesso.
        
        scadenza assoluta è istante rilascio + scadenza relativa.
- - - - Ho finito? Co-Design
        Stampare il circuito non è l'ultima fase, devo effettuare un partizionamento hardware/software.
        esempio: vorrei che la luce del proiettore si spegnesse se raggiunta una certa temperatura, come realizzo ciò?
        
        hardware: il sensore, rilevata la temperatura eccessiva, stacca la luce, il software non sa cosa sia successo. Non è modificabile, ma è più sicuro (non c'è comunicazione e quindi ritardi).
        
        software: il sensore, rilevata la temperatura eccessiva, comunica l'evento al microcontrollore, che quindi è a conoscenza della situazione, il quale stacca la luce. E' flessibile (alzo/abbasso la soglia) ma è un carico di lavoro in più da gestire!
        
        Mediante Co-Design gestisco l'interfacciamento hardware/software e di realizzare queste componenti in maniera separata e contemporanea.
        
        Sistemi basati su piattaforme
        
        Si basa sull'uso di una piattaforma di riferimento, come i Systems-On-Chips, che sono dei miniPC.
        Essi sono modificabili ed adattabili per nuove funzioni.
        Quindi si definisce la piattaforma più idonea al nostro scopo, e la si usa per progettare lo scopo nello specifico.
        Perchè nascono?
        Corsa alla miniaturizzazione, quindi meno ritardi nella propagazione del segnale. Adesso l'attuale limite fisico è dato dal calore, non dalla distanza dei componenti!
        Attualmente, un progettista può scegliere tra:
        
        circuito integrato apposito, se deve progettare una sola funzione non riprogrammabile, può usare:
        -componente COTS, circuito integrato già prodotto.
        -componente ASIC, specializzato per quella funzione. Più costoso, ma permette di rispondere a particolari esigenze di dimensioni, prestazioni, inadeguatezza dei COTS, e può diventare un nuovo standard per un tipo di piattaforma, favorendo il progresso.
        
        Logiche programmabili
        
        microprocessori, inclusi microcontrollori etc...
        
        Progettazione ASIC
        
        Si usano le standard cell, circuiti digitali riutilizzabili (come dei Lego).
        
        Si parla di cella, circuito digitale completo già progettato ed ottimizzato, da riusare a piacimento, a differenza dei transistor.
        
        Le definizioni delle celle sono raccolte in librerie commerciali, includenti migliaia di celle per realizzare determinate funzioni (logiche base, flip flop etc..).
        
        Le celle hanno stessa altezza, bisogna preoccuparsi solo del distanziamento ottimale per le interconnessioni.
        
        Evoluzione con Gate Array
        Semplifica gli ASIC, ma nei gate array il chip è parzialmente fabbricato, cioè silicio organizzato gruppi di transistor organizzati in righe regolari separati da canali per le interconnessioni.
        Oggi, essendoci meno progetti, e quindi meno necessità di ASIC, si parla di logiche programmabili, che sono più diffuse.
        
        Logiche programmabili PLD
        
        Sono chip che integrano:
        
        risorse logiche (che possono essere configurate per specifici compiti)
        
        linee di interconnessione (collegabile o meno a risorse logiche)
        
        La programmabilità può essere:
        
        one-time-programmable OTP, cioè irriversibile.
        
        riprogrammabile, cioè configurabile più volte
        
        riconfigurabile, cioè configurabile più volte in modo selettivo mentre il circuito è in funzione
        
        Complessità dei PLD
        Definita in base alla complessità delle celle (aka risorse logiche elementari)
        
        una cella semplice sfrutta maggiormente il silicio (due porte logiche o un multiplexer o un flip flop)
        
        una cella complessa facilita le interconnessioni, e può ridurre il numero di celle usate.
        (due/quattro porte logiche e un multiplexer e un flip flop)
        
        Tipologie di PLD
        Si parte dalle PLA, formate da AND e OR e interconnessioni OTP, passando poi per le CPLD e le FPGA, celle complesse distribuite nel chip.
        
        Utilizzo di microprocessori
        Si usano perchè sono flessibili, aumentando quindi mantenibilità, sono programmabili, semplici ed economici.
        L'unico svantaggio è che le prestazioni (energia, dissipazione, potenza etc) sono peggiori rispetto all'implementazione hardware della stessa funzionalità.
        
        Tipologie
        Esistono microprocessori general purpose ma anche dedicati, come ASP.
        Importante è anche la forma:
        
        COTS : chips indipendenti
        
        Intellectual Property IP, sono descrizioni, cioè compro come sono fatti, poi li modifico io!
        
        Digital Signal Processor
        Sono processori dedicati, ottimali per elaborazione numerica (spesso ricorsiva, es : x = x +1)
        Architetture per DSP:
        
        realizzano MAC (unità di Multiply and Accumulate al secondo) con una singola istruzione
        
        ottimizzano piccoli cicli, ed operano in //
        
        hanno insiemi di istruzioni 'grandi'
        
        hanno gerarchie di memoria per distinguere tra codice e dati.
        
        Network Processor
        
        Usati nelle reti per buffer pacchetti, ritrasmissioni etc.
        
        Sono multiprocessori, uno per ogni canale ( processore singolo detto Channel Processor CP)
        
        CP in assembler
        
        Microcontrollori MCU
        Hanno molte periferiche e interfacce nel singolo chip, non per general purpose, ottime per alta integrazione con hardware ma poca potenza di calcolo (pochi registri, un timer, memorie piccoli, etc...).
        Essendo piccoli, hanno pochi piedini, e quindi non hanno interfacce sofisticate verso l'esterno!
        (ad esempio non ci collego la Ram direttamente!)
- - - - Modello del carico (caratterizzazione)
        
        Un task include un insieme di entità schedulabili dette job, i quali hanno scadenze, proprietà intrinseche, usano risorse e dipendono da altri job (es ordinamento con cui vengono eseguiti)
        
        Vincoli temporali
        
        Istante di rilascio/Release time: istante di tempo r(i) in cui job J(i) è disponibile per l'esecuzione.
        
        Scadenza/Deadline: tempo d(i) in cui J(i) deve aver completato l'esecuzione.
        
        Scadenza relativa: massimo intervallo di tempo D(i) che intercorre da r(i) e d(i), D(i) = d(i) - r(i)
        Sostanzialmente mi dice "quanto tempo ho per completare il job" (infatti è la differenza tra la scadenza e quando il job è pronto per essere eseguito)
        
        Intervallo di fattibilità : ( r(i), d(i) ]
        
        I vincoli temporali spesso sono forniti, poichè è da loro che inizio a modellare.
        Spesso si parla di *jitter quando il tempo di rilascio non è preciso ma presenta un delta di rilascio, r(i) in [ r(i-), r(i+) ]
        
        Task aperiodici e sporadici
        Esistono due task particolari:
        
        task aperiodico : release time casuale non predefinito, non posso dire nulla.
        
        task sporadico, è un task aperiodico ma esiste un intervallo minimo tra il rilascio di due job.
        
        Tempo di esecuzione e(i)
        Relativo a un job J(i), è il tempo per completare il job J(i) se fosse l'unico job e avesse tutte le risorse necessarie.
        
        Non dipende dallo scheduling (c'è solo il job), ma solo da quello che fa e dal processore.
        
        Problema di e(i) : oggi è difficile stabilire questo tempo, l'hardware è complesso e non deterministico, spesso ho un intervallo di esecuzione.
        Come ci lavoro?
        
        WCET: Worst Case Execution Time
        
        Mi baso sul limite superiore dell'intervallo di esecuzione, se un job ci mette dai 3 ai 5 secondi, assumo ce ne metta 5 e lavoro su questo dato!
        
        NB: La stima dell'intervallo è importante!, nel caso precedente non posso dire "allora lavoro con 20s cosi sono sicuro!"
        
        Cosa voglio nell'HRT?
        
        Va bene parlare di WCET, ma rimane il problema della stima!
        
        Voglio predicibilità a scapito delle prestazioni, come?
        
        Uso processori meno sofisticati, no strutture dati dinamiche, no interazioni complesse tra job (2 job che interagiscono sono più facili da osservare rispetto 100), poche primitive di sincronizzazione.
        
        Queste modifiche rendono il sistema
        quasi deterministico
        Come caratterizzo il modello del carico/applicazione?
        
        Modello a task periodici
        
        Introdotto nel 1973, rappresenta bene le applicazioni real-time, gli algoritmi basati su tale modello sono facili, ed esistono metodi e strumenti per l'analisi.
        Meno buono con jitter elevati.
        
        Principio base: ogni computazione è modellata con un task periodico T(i), che è una sequenza di job.
        
        T(i) ha un periodo p(i), cioè intervallo di tempo tra gli istanti di rilascio dei job di T(i)
        (e.g: ogni 2s viene rilasciato un job del task T(1) )
        
        Il tempo di esecuzione e(i) di T(i) è il massimo dei tempi di esecuzione dei job di T(i)
        (e.g : T(1) ha j(1) = 2s e j(2) = 3s --> T(1) ha tempo di esecuzione 3s (di j(2) )
        
        Normalmente p(i) >= e(i), il contrario vorrebbe dire che qualche job viene rilasciato prima di essere totalmente eseguito.
        
        1 more item...
- - - - Ambiente esecuzione SERT
        
        E' un ambiente di esecuzione già funzionante, è bare-metal (si interfaccia direttamente con hw), compatto, real time (prestazioni predicibili, verificabili e validabili), e sopratutto semplice (scritto in basso livello, cioè C e Assembly, poichè si interfaccia con hw).
        
        Sviluppo codice sistemi embedded
        
        Tale operazione viene svolta su un calcolatore general purpose (detto host).
        E' necessario installare un ambiente di sviluppo cross compiler in grado di generare codice macchina per sistemi embedded.
        
        Il programmatore si interfaccia inizialmente con i led luminosi della scheda, e dopo con porta seriale per ottenere messaggi del sistema.
        (Non ho schermi o tastiere).
- - - - Schedulazione ciclica strutturata
        
        Avere uno scheduler che si attiva ad intervalli regolari, con intervalli Idle regolari, porta alla possibilità di usare un dispositivo hardware per le interruzioni periodiche, oltre alla possibilità di monitorare al meglio i vincoli.
        
        Una procedure con tali caratteristiche è detta cyclic executive.
        
        Gli istanti in cui lo scheduler ciclico strutturato prende decisioni, porta al partizionamento del tempo in frame prefissati con un blocco di schedulazione associato.
        
        Nel frame i job non si interrompono, se iniziano in un frame, finiscono in quel frame.
        
        La fase di ogni task periodico è un multiplo intero positivo del frame.
        
        In altre parole, non posso tagliare un frame, ma devo averli interi. La fase è definita dall'istante del rilascio del primo job.
        
        regola : Se job arriva dopo l'inizio del frame
        i (ma che non è ancora concluso), il job andrà messo nel frame i+1. Solo se arriva esattamente all'inizio del frame i allora vi rimane.
        
        Se job finisce esattamente all'inizio del frame i Il job non viene visto dallo scheduler, perchè lo scheduler si sveglia solo all'inizio del frame (magari 1infinitesimo di secondo dopo) e quindi vede solo quando le cose cadono nel mezzo del frame.
        
        Vincoli sui frame
        
        Poichè job non interrompibili nel frame, il frame deve essere maggiore di tutti i tempi di esecuzione dei job.
        
        (frame / iperperiodo) è un intero.
        H/f - [H/f] == 0
        Senza taglierei un frame.
        
        Il frame deve essere piccolo tale che tra l'istante di rilascio e scadenza job ci sia sempre almeno un frame
        2f - mcd( p(i),f ) <= D(i) per ogni task.
        
        Vedi esempio pagina 3
        
        Osservazione: grazie ai frame, so esattamente gli istanti in cui deve essere schedulato un job.
        Poi è sempre compito mio sapere chi mettere, ma grazie a questo so almeno i punti in cui far iniziare un job.
        
        Casi particolari
        
        Cosa succede se c'è un singolo Task che non mi fa rispettare le condizioni sul frame?
        
        Posso spezzare uno o più job, in modo da dividere i tempi di esecuzione. Tuttavia introduco vincoli di precedenza, quindi devo rispettare un ordine per i pezzi del job spezzato.
        L'insieme di job frammentati non equivale all'insieme iniziale!
        
        Come gestire job non armonici?
        Può capitare che l'iperperiodo sia elevato, e cosi anche il numero di frame interni.
        
        Posso abbassare i periodi di alcuni task nei requisiti.(Se Tx ha periodo 25, abbasso a 24)
        NB: aumenta l'utilizzo, quindi deve essere ponderato.
        
        Se ho tempi non interi?
        
        Poichè il tempo è virtuale posso moltiplicare tutti i periodi per una costante in modo da averli interi, però aumenta il frame.
        
        Gestione job aperiodici
        
        Vengono eseguiti quando il processore è idle
        
        Attivazione può essere ritardata, e si cerca di ridurne i tempi di risposta (perchè rubano tempo a job periodici)
        
        Slack Stealing
        
        Per ogni frame può esserci un margine di tempo ancora disponibile (quindi non nullo).
        
        Lo scheduler può eseguirvi job aperiodici prima di quelli periodici (basta che i RT finiscano prima del frame).
        
        Bisogna mantenere, per ogni frame, dati sullo slack disponibile e slack usato dai job aperiodici (un job aperiodico può essere eseguito in più slack di diversi frame, devono essere interrompibili)
        
        Esempio pagina 4
        
        Aperiodici Hard real time
        
        Nel momento in cui il job aperiodico sia Hard Real Time?
        
        Poichè non posso mancare la loro scadenza, introduco un test di accettazione, in cui si deve dimostrare che il job può essere schedulato ed espletato secondo le sue scadenze, e permettendo le scadenze degli altri job.
        
        Si usa in particolare l'algoritmo EDF: ha la precedenza il job con scadenza più vicina.
        
        Algoritmo EDF nel cyclic executive
        
        Si introducono due code:
        
        coda EDF per job accettati
        
        coda EDF per job non ancora accettati (quindi devono ancora fare il test).
        
        In pratica introduco solo quelli nella prima coda, accettazione e schedulazione sempre a inizio frame.
        (NB: non vuol dire che gli aperiodici vanno per forza ad inizio frame, solo le scelte su come gestirli)
        
        va bene solo nei casi in cui la schedulazione non richiede di schedulare job aperiodici in mezzo ad un frame.
        
        1 more item...
- - - - 4) Esecuzione
        
        Da terminale uBoot (cioè quello della scheda):
        go 0x80000000
        
        Non operando con i led (la funzione creata è un ciclo e basta), non so se funziona tutto.
        
        Sui sistemi BareMetal esiste un controllo di sicurezza WatchDog che comporta il reset della scheda se non si eseguono operazioni in un delta temporale.
        
        5) Aggiunta dei led: salti ed indirizzi
        
        Per evitare di riscrivere tutti i flag, creo un makefile.
        
        Eseguendolo, ritorna un errore: manca sert.lds. Perchè?
        
        Ho usato indirizzi relativi, che vanno bene finchè i salti sono del tipo salta x istruzioni dopo ma non vanno bene per salti del tipo salta ad indirizzo x. Devo usare path assoluti, che vanno specificati nel file.lds
        
        vi sert.lds
        dove scrivo:
        
        ENTRY (_reset)
        mem_start = 0x80000000;
        mem_lenght= 512*1024*1024; #512Mib
        mem_end = mem_start + mem_lenght
        MEMORY
        {
        ram(rwx): ORIGIN = mem_start, LENGHT = mem_lenght
        }
        SECTIONS
        {
        .text : { *(.text)
        .=ALIGN(4);
        } > ram
        .rodata: { *(.rodata)
        .= ALIGN(4);
        } > ram
        .data: { *(.data)
        .= ALIGN(4);
        } > ram
        .bss: { -bss_start=. ;
        *(.bss)
        *(COMMON);
        -bss_end=. ;
        .= ALIGN(4); } > ram
        }
        
        Con questa scrittura il makefile funziona correttamente, posso vedere le estensioni prodotte con:
        make clean
        nb: in sert.sym ho le variabili dichiarate ed usate
        
        Legenda
        
        *.(text) : qualsiasi sia il nome del file con estensione .text
        
        .=ALIGN(4) : dove sono arrivato, vai a capo per mantenere l'allineamento
        
        >ram : metti tutto quello di prima in ram
        
        bss (dove ho le variabili inizializzate a 0) ha un trattamento leggermente diverso:
        
        *(COMMON): è un flag per le variabili weak.
        
        bss_start=. e bss_end=. mantengono in queste variabili la posizione in cui sei arrivato.
        
        6) Implementazione effettiva dei led.
        
        Per poter effettuare questa operazione occorre leggera la documentazione.
        
        Da essa, scopriamo che ci interessa il componente GPIO General Purpose Input Output, che però non è di BeagleBone, quindi dobbiamo andare sulla documentazione del produttore.
        
        Ciò che dobbiamo fare è settare SetDataOut(offset = 1944), mettendola ad 1 nel registro.
        
        L'offset fornito è però relativo, devo vedere la sezione MemoryMap della documentazione, che mi porta ad usare l'indirizzo di gpoi1.
        
        Abilito i led nel codice
        void _reset()
        
        {
        int *gpoi1 = (int *) 0x4804c000;
        gpoi1[0x134/4] &= ~ (1<<21) | (1<<22) | (1<<23) | (1<<24)
        for(;;)
        ;
        }
        
        Legenda
        
        tilde è per avere una maschera completa.
        
        & è AND per forzare i bit a 0.
        
        0x134/4 perchè raggruppo in 4 byte alla volta.
- - - - EDF
        
        Priorità job direttamente proporzionale alla vicinanza della scadenza.
        
        Servono tempi di rilascio r(i) e scadenze assolute d(i), non richiede di sapere in anticipo il tempo di esecuzione. (perchè gli switch sono basati sulle scadenza sopratutto).
        
        Il context switch si ha quando, dato un job i in esecuzione, ne arriva un altro con scadenza assoluta più vicina rispetto al job i (lo lascio passare avanti perchè ha dei tempi più ristretti!)
        
        E' un algoritmo a priorità dinamica a livello di task (perchè nel task posso avere job con priorità diverse, a livello statico di job ( se ho scadenza fissata non cambia).
      - LRT
        
        E' l'inverso di EDF, schedulando i job iniziando dall'ultima scadenza fino al presente. Più avanti è l'istante di rilascio, maggiore è la priorità.
        
        Rispetto a EDF, è meno aggressivo e più predicibile, poichè si interessa solo alla scadenza.
        
        Non è priority driven, poichè per la caratteristica sopra citata non è work conserving. (es: job pronto ma ha priorità bassa, potrebbe non usare subito il processore, infatti qui si parte dall'ultima scadenza dell'ultimo job, non dal primo job che posso eseguire subito!). Infatti si produce lo schedule di EDF traslato verso destra.
        
        A differenza di EDF, è necessario conoscere in anticipo i tempi di esecuzione, perchè mi serve sapere cosa avverrà in futuro (visto che parto dal futuro verso il "passato"). Non è quindi un algoritmo online, e un job a runtime romperebbe tutto.
      - LST
        
        Basato sullo slack:
        (l'istante di scadenza) - (tempo attuale di esecuzione + tempo che serve per completare l'esecuzione).
        Mi dice quanto tempo posso "sprecare" essendo sicuro di non perdere la scadenza. Più è basso o tendente allo 0, più ho urgenza di completarlo, più ha priorità.
        
        Se job i è in esecuzione, non perde tempo, quindi lo slack non varia. Decresce lo slack dei job non in esecuzione.
        
        Un job non ancora reso disponibile, avente scadenza d(i) vede comunque il suo slack diminuire! ( perde comunque tempo, anche se non è "colpa sua").
        
        :red_cross: rispetto EDF ed LRT, richiede di conoscere i tempi di esecuzione massimi di tutti i job, ed è abbastanza difficile.
        
        Esistono due varianti:
        
        nonstrict LST: scheduler chiamato e cambiamento della priorità job sono in casi di
        rilascio/conclusione di un job/temporizzate/tick periodico.
        Non ottimale.
        
        strict LST: modifiche continue, ottimale ma complesso e con alto overhead. Ad esempio j1 e j2 potrebbero avere slack infinitesimali e quindi su superano a vicenda ogni ms.
        
        E' di tipo priorità dinamica a livello di job (perchè mentre esegue lo slack cambia, e questo può portare a cambi della priorità!)
- - - - Fattore di utilizzazione di EDF (IMPORTANTE)
        
        Teorema (Liu Layland, 1973): un sistema T di task indipendenti, interrompibili, con scadenze relative uguale ai periodi (aka scadenze implicite) e fattore di utilizzazione U(T) ha schedulazione fattibile su un singolo processore se e solo se U(T) ≤1.
        
        Corollario: l’algoritmo EDF ha un fattore di utilizzazione U(EDF)=1 per sistemi di task indipendenti, interrompibili, con scadenze relative uguali o maggiori dei rispettivi periodi.
        
        Dimostrazione del teorema
        
        "se e solo se" Se U(T) > 1, allora il processore è più che pieno, e qualcuno mancherà le scadenze perchè non eseguito.
        
        "se U(T)≤1 allora esiste schedulazione che rispetta le scadenze" (cioè il viceversa):
        trovo algoritmo che produce schedulazione fattibile di ogni sistema T con U(T)≤1, cioè EDF.
        Invece di dimostrare "per ogni", mi metto in un caso in cui EDF non la trova, e quindi deve essere U(T)>1.
        Definisco t il tempo in cui il primo job J(i,c) manca la scadenza. Prima di t processore lavora.
        
        caso 1: i periodi che includono t iniziano sempre dopo r(i,c).
        Stiamo dicendo che il job J(i,c) andrebbe eseguito tra r(i,c) rilascio e r(i,c) + p(i) (scadenza), ma non riesce.
        Poichè deve essere eseguito J(i,c), gli altri periodi di altri task partono dopo r(i,c), quindi hanno scadenze dopo J(i,c) e quindi sono meno prioritari. Cioè mancare la scadenza implicita vuol dire che il processore non riesce ad eseguire tutto il carico richiesto.
        IN PRATICA t < tempo esecuzione di J(i,c) + tempo altri job non eseguiti fino a t perchè dopo non si continua.
        
        caso 2: esistono task aventi periodo che include t (nelle slide è T(L))
        Questo task T(L), che ha periodo che inizia prima del rilascio di J(i,c), verrà eseguito fino ad un certo istante t' prima del rilascio r(i,c) di J(i,c) ( t' può essere prima di r(i,c) se la durata di T(L) è inferiore, altrimenti verrebbe switchato con J(i,c).
        Adesso opero in [t',t] (nel caso 1 partivo da t' = 0) facendo lo stesso ragionamento del caso 1.
        In entrambi i casi vediamo che U(T) > 1.
        
        Quindi abbiamo visto che, per U(T) ≤1, non fallisce.
        
        Recap
        Presi task indipendenti, interrompibili, schedulati su singolo processore, allora:
        
        Se un sistema di task ammette una schedulazione fattibile, l’algoritmo EDF ottiene una schedulazione fattibile per quel sistema di task.
        
        Un sistema di task ammette una schedulazione fattibile se e solo se U(T) ≤1 (appena visto)
        
        EDF ha U(edf) = 1 per scadenze implicite, dobbiamo dimostrarlo per scadenze > dei periodi.
        
        Densità di un sistema di task
        Il teorema di prima non vale se la scadenza relativa è inferiore al periodo.
        
        Si introduce il concetto di densità di un task, ovvero ∆T = e/(min(D,p)) =
        con D scadenza relativa, p periodo.
        
        Teorema: Un sistema T di task indipendenti ed interrompibili e densità ∆T ha una schedulazione fattibile su un singolo processore se ∆T ≤ 1
        E' una condizione sufficiente, ma non necessaria.
        
        Utilizzazione e densità
        
        In un sistema di Task interrompibili con
        
        Teorema 1 : se, per ogni task, Di = pi (scadenza implicita), allora esiste schedulazione fattibile se e solo se U(T)≤1.
        
        Corollario 1: se, per ogni task, Di ≥ pi allora esiste schedulazione fattibile se e solo se U(T)≤1. (per forza ≤ sennò manco scadenze per forza)
        
        dimostrazione:
        
        passo base per l'induzione, per un task: , ,
        
        Ora, se fisso k ≥ 1, ho che (k+1)/k è > 1, allora:
        , se adesso prendo la disequazione in verde, e divido a destra e sinistra per kp, trovo: , in pratica ho creato un collegamento tra e/p ed equazione in verde.
        Poichè k va ad infinito, otteniamo che e/p ≤ 1
        
        per gli n-1 task in fase (il processore non è tutto per me), il ragionamento è lo stesso, solo che ho sommatorie:
        ≤ da cui:
        < da cui U(t) ≤ 1
        
        l’idea intuitiva è che nei periodi successivi inizierò ad eseguire i job un po’ oltre quel periodo, perchè ho mangiato del tempo per via dell’utilizzazione precedente.Quindi prima o poi arriverà ad un task che mancherà la scadenza, perch è mi mangio ogni volta un pezzo del ”vantaggio”.
        Se i task non sono in fase si può complicare un po’ la dimostrazione
        
        Corollario 2: Il fattore di utilizzazione di EDF per task con Di ≥ pi è U(EDF) = 1 (ossia EDF determina una schedulazione fattibile se U(T) ≤ 1)
        
        Teorema 2: Se per qualche task Ti , Di < pi , allora esiste una schedulazione fattibile se ≤ 1
        
        Osservazione: U(T) MAI > ∆T, perchè?
        
        Prendo come è definito U(T) e ∆T, se in ∆T ho Di ≥ p(i) allora prendo p(i), ma è come è definito U(T).
        
        se Di < p(i) allora ∆T > U(T), basta confrontare i denominatori.
        
        Tutte queste cose servono per definire il Test di schedulabilità per EDF
        
        Test di schedulabilità per EDF
        
        Dato un sistema T completamente definito di task interrompibili, come stabilire se è schedulabile con EDF?
        
        ∆T ≤ 1 ? se sì, allora è schedulabile per T2 (quindi stavo in condizione Di < p(i) ) Se le scadenze sono implicite posso anche vedere l'utilizzazione.
        
        altrimenti ∆T >1 , sto in Di ≥ pi per ogni i, ma allora ∆T coincide con U(T) (perchè prendo p(i) al denominatore), ma allora sto dicendo che U(T) > 1, allora il sistema non è schedulabile.
        
        altrimenti, se ci sono alcuni Di< p(i), posso allora simulare EDF su una lunghezza = 2H+max(pi) +max(Di).
        Però devo sapere tutto!
        
        Se le fasi sono sconosciute, posso avere un risultato analitico? Analisi di schedulabilità
        sappiamo che la schedulabilità basata su ∆T è sufficiente ma non necessaria.
        Il teorema di Baruah ci dà una condizione sufficiente e necessaria:
        
        Un sistema T con task periodici indipendenti, interrompibili, con U(T) < 1, è schedulabile con EDF se e solo se, per ogni L >0 ho:
        (parte intera inferiore, infatti non controllo tutti gli L, ma solo gli L multipli dei periodi dei task entro l'iperperiodo, con L minore del massimo tra le scadenze relative dei vari task e )
        
        Algoritmi a priorità fissa
        
        In generale sono peggiori rispetto a quelli dinamici.
        
        I sistemi di task semplicemente periodici
        [detti anche armonici, ovvero presi T(i) e T(k) con p(i) < p(k), p(k) è multiplo intero di p(i) ]
        sono classi in cui è ammesso un algoritmo a priorità fissa ottimale.
        
        Ottimalità RM
        
        Un sistema T di task semplicemente periodici (armonici), interrompibili ed indipendenti le cui scadenze relative sono non inferiori (allora sono ≥ ) ai rispettivi periodi ha una schedulazione RM fattibile su un singolo processore se e solo se U(T) ≤ 1
        (va bene come andrebbe bene EDF).
        
        dimostrazione:
        mi metto in task in fase, scadenze = periodi, processore mai idle. Dico che T(i) manca scadenza t.
        I task T(k) più prioritari di T(i) hanno periodo più piccolo (e frequenza maggiore) di p(i).
        Quindi, se scadenze = periodo -> t coincide con periodo, e inoltre t deve essere un multiplo di tutti i periodi precedenti! (perchè sistema di task armonici!). Se T(i) manca la scadenza, allora il tempo t non basta per completare le esecuzioni di tutti i task precedenti a T(i) cioè più importanti di T(i).
        Formalmente:
        t < cioè U(T) > 1
        
        Ottimalità DM (better than RM)
        
        Se per un sistema di task periodici, indipendenti ed interrompibili che sono in fase ed hanno scadenze relative minori o uguali ( ≤) ai rispettivi periodi esiste un algoritmo a priorità fissa che produce una schedulazione fattibile, allora anche l’algoritmo DM produrrà una schedulazione fattibile. (se ci riesce algoritmo a priorità fissa, ci riesce anche DM)
        
        L’algoritmo DM coincide con RM se tutte le scadenze relative sono proporzionali ai rispettivi periodi allora:
        
        corollario:
        " L’algoritmo RM è ottimale tra tutti gli algoritmi a priorità fissa qualora le scadenze relative dei task siano non superiori (≤) e proporzionali ai rispettivi periodi (perchè coincide con DM in caso di proporzionalità)".
        
        Nel corollario non parlo di fase, perchè è il caso peggiore!
- - - - Test di schedulabilità (Lehoczky, Sha, Ding 1989)
        
        Dati job T1......Ti, in fase a t0 con priorità decrescenti con T1......Ti−1 effettivamente schedulabili (rispettano scadenze).
        Il task Ti può essere schedulato nell’intervallo di tempo [t0, t0+D] se ∃ t ≤ Di (scadenza relativa) tale che wi(t) ≤ t.
        
        Banalmente sto dicendo: T(i) schedulabile in un certo intervallo lungo "D" se in questo lasso di tempo riesco ad eseguire tutti i job più importanti di me + me stesso senza violare la scadenza relativa di T(i).
        
        Come lo applico
        
        Ordino i task con priorità decrescente. Parto dal task più importante. Calcolo wi(t) per tutti t ≤ Di tali che t è multiplo intero dei periodi dei task precedenti al Task in esame. Se almeno uno di questi ritorna wi(t) ≤ t allora T(i) è schedulabile, altrimenti potrebbe mancare la scadenza, non è detto che la manchi per forza.
        
        Vedere esempio pagina 6
        
        Massimo tempo di risposta Wi
        
        Il massimo tempo di risposta Wi di un task Ti in un sistema a priorità fissa con tempi di risposta piccoli è:
        Wi = min{t ≤ Di : t =wi(t)}
        
        Non potrei simulare e basta?
        
        Non sempre è meglio, perchè non sempre posso determinare il caso peggiore o introdurre concetti come job parzialmente non interrompibili. Inoltre la simulazione ha complessità pseudo-polinomiale quindi è meno veloce di quel che si crede.
        
        Task periodici con tempi di risposta arbitrari
        
        Fino ad ora abbiamo operato in condizioni piuttosto semplici. Passiamo a task con tempi di risposta arbitrari, cioè:
        
        Un job non deve per forza completare prima che il job successivo dello stesso task sia eseguito.
        
        e' possibile che Di ≥ pi (deriva dal primo punto)
        
        Posso averer nello stesso istante più job di uno stesso task in attesa di essere eseguiti.
        
        Un job rilasciato contemporaneamente a tutti i job dei task con priorità maggiore non ha necessariamente il massimo tempo di risposta possibile. Cioè il teorema visto nel caso di prima non è più valido, e quindi non mi può più dire il caso peggiore.
        
        Assumo sempre che i job di uno stesso task hanno vincoli di precedenza impliciti fra di loro, ovvero sempre eseguiti FIFO.
        
        Intervalli totalmente occupati
        
        Ho insieme task τi=T1....Ti con priorità decrescente.
        Definisco un intervallo totalmente occupato di un livello π(i) un intervallo (t0, t1] tale che:
        
        all’istante t0 tutti i job di τi rilasciatiti prima di t0 sono stati completati, non ho lavoro arretrato.
        
        all’istante t0 un job di Ti è rilasciato.
        
        l’istante t1 è il primo istante in cui tutti i job di Ti rilasciati a partire da t0 sono stati completati.
        
        In un intervallo totalmente occupato ci sono solo task dell'insieme τi, non ne ho altri! L'intervallo si conclude quando l'ultimo job di τi viene completato, quindi non ho momenti idle.
        
        Vedi esempi pagina 7.
        
        Test di schedulabilità generale di Lehoczky 1990
        
        Nell'esempio calcolo questi tempi a mano. Questo test è basato sempre su task in fase.
        
        La differenza rispetto ai tempi di risposta piccoli è che un job rilasciato insieme ad altri non è detto abbia il massimo tempo di risposta.
        
        Per determinare l'intervallo totalmente occupato, cioè la sua lunghezze massima, devo procedere iterativamente:
        
        L'inizio è determinato dai rilasci dei primi job in base, appartenenti ai task in τ(i).
        Il primo t (alla sinistra dell'equazione di sopra) si può trovare con: . Determinato questo t lo metto dentro la sommatoria di prima e vedo se l'uguaglianza è vera.
        Simile alla formula delle risposte piccole, l'obiettivo è trovare t che rende vera questa uguaglianza.
        
        Sostanzialmente ho due macrocasi:
        
        Se il primo job di tutti i task in τ(i) termina entro il primo periodo del task: allora w i,1(t) := w i(t) cioè sto semplicemente riproponendo il test per i tempi di risposta in cui Di < pi.
        
        altrimenti almeno un primo job di τ(i) termina dopo il periodo del task -> uso algoritmo iterativo.
        Devo calcolare tutti i tempi di risposta massimi di tutti i job di Ti dentro l'intervallo totalmete occupato, se tutti rispettano la scandenza allora Ti è schedulabile.U
        
        Lemma per calcolare i tempi di risposta
        
        Come calcolare i tempi di risposta di tutti i job di Ti nell’intervallo totalmente occupato di livello πi ?
        
        Il tempo di risposta massimo Wi,j del j-esimo job di Ti in un intervallo totalmente occupato di livello πi in fase è uguale al minimo valore di t che soddisfa l’equazione:
        == job eseguibile da rilascio a sua scadenza?
        con
        
        Notiamo che in w c'è j * e(i) perchè il j-esimo job del task aspetta i precedenti job del task associato.
        
        Il j-esimo job rispetta scadenza relativa se soddisfatta per t ∈ [ (j−1)pi , (j−1)pi + Di ]
        
        Vedi esempio pagina 8
        
        NB: quando calcolo w del 1° job del task 2, t posso farlo variare tra i multipli dei task a lui precedenti.
        Il task 1 ha periodo 2, quindi posso verificare per t = 2, t = 4 etc... t = 3 non c'è bisogno.
        Il secondo job del secondo task parte da t = periodo = 3, ma anche qui posso assumere i multipli t = 2, t = 4, t = 6 come prima.
        
        Per il task 3:
        
        job 1: t parte dai multipli dei periodi dei task precedenti a 3, e quindi parte da 2 (periodo di T1), poi t = 3 (periodo di T2), poi 4 (periodo di T1 *2) etc... Quando w<=t verifico anche che w<= scadenza relativa = 7
        
        job 2: parte da t = 5 perchè è periodo di T3, ma seguendo la logica dei multipli posso partire da t = 6.
        Quando soddisfo w<=t verifico anche che w<= scadenza assoluta data da periodo + scadenza relativa = 5+7 = 12.
        (perchè non parte da 0 bensi dal periodo, e quindi la scadenza ne dipende).
        
        Questo test ha limiti?
        
        Si, perchè dipende da periodi, scadenze e tempi di esecuzioni (no fasi).
        
        Questi elementi sono invarianti nel procedimento.
        
        Non adatto a scheduling online (esoso).
        
        cerco qualcosa di meno "pesante"...
        Condizione di schedulabilità
        
        Condizione sufficiente per la schedulabilità di un sistema di task calcolabile velocemente ed applicabile anche quando alcuni parametri temporali dei task non sono noti.
        
        Ad esempio, EDF fornisce condizione schedulabilità: Basta che U(insieme di Task) ≤ U(EDF) = 1
        
        Condizione di Schedulabilità di Liu-Layland
        
        Un sistema τ di n task indipendenti ed interrompibili con scadenze relative uguali ai rispettivi periodi può essere effettivamente schedulato su un processore in accordo con RM se il suo fattore di utilizzazione Uτ e' ≤ a URM(n) = dove n + il numero di task. Nelle condizioni del teorema, RM == DM.
        
        Nel caso di n che va verso infinito, riesco a rispettare scadenza se carico inferiore al 69,3%
        
        Questa condizione, nel caso non venisse rispettata, non ci dice "non è schedulabile", ma solo che "forse** non è schedulabile"
        
        Si può fare di meglio?
        
        Test iperbolico (Bini, Buttazzo,2001) : Un sistema T di n task indipendenti ed interrompibili con scadenze relative uguali ai rispettivi periodi (Di = pi ) può essere effettivamente schedulato su un processore con RM se
        è meglio perchè considera le singole utilizzazioni, mentre l'atro "mette tutto insieme.
        
        Se per ogni task allora coincide con Liu-Layland. Generalmente il test iperbolico è migliore o uguale (mai peggiore) di Liu-Layland.
        
        1 more item...
- - - - Tempo massimo di blocco per auto-sospensione
        
        Dato un task Tk , sia x(k) il tempo massimo di auto-sospensione di ogni job di Tk.
        
        Prendo ora un Task Ti di priorità inferiore rispetto Tk, Tk ritarda Ti di:
        + dove:
        
        x(i): tempo che Ti si autosospende.
        
        sommatoria per tutti i tast più importanti di Ti (da 0 a i-1) considerando il minimo tra tempo esecuzione del job e autosospensione. (come abbiamo visto nell'esempio!)
        
        Questa formula definisce completamente il rallentamento del task? NO, poichè non include rallentamenti del cambio contesto, quante volte T(i) si autosospende o un blocco di un processo non interrompibile. Esaminiamo quest'ultimo.
        
        Non interrompibilità dei job
        
        Fino ad ora, un job di priorità massima non era interrompibile (a patto che fosse il più importante).
        Ciò non è vero, un job inferiore potrebbe essere tranquillamente non interrompibile, basta che interagisca con quale device esterno o operi su risorsa critica.
        
        Un job Ji è bloccato per non interrompibilità quando è pronto all’esecuzione ma non può essere eseguito a causa di un job di priorità minore che non può interrompere l’esecuzione. Quindi questo interessa solamente i job di priorità superiore!
        
        Nell'intervallo di tempo, in cui eseguo un job meno prioritario al posto di uno più importante per questo motivo, si verifica una inversione di priorità.
        
        Ricordiamo che le schedulabilità tramite EDF ed RM non valgono in caso di job non interrompibili.
        
        Blocco dovuto a non interrompibilità
        
        Definisco θ(k) il tempo d’esecuzione massimo della più lunga sezione non interrompibile dei job di Tk.
        Ovviamente più è grande, peggio è. E' comunque minore del tempo di esecuzione.
        
        Sia bi(np) il tempo massimo di blocco per non interrompibilità che un job di Ti può subire nel momento del suo rilascio, : per ogni Tk di priorità inferiore rispetto Ti}.
        Cioè per ogni k, se esso ha un intervallo di tempo in cui non è interrompibile, questo tempo è teta di k. Poi tra tutti quelli ottenuti prendo il massimo.
        Ovviamente vengo rallentato dai task meno importanti, quelli più importanti prenderebbero comunque le risorse.
        
        Il tempo massimo di blocco bi dipende sia da bi(np) (non interrompibilità) che da bi (ss) (autosospensione).
        
        In pratica un Task i subisce ritardi sia se Task più importanti vanno in autosospensione sia se Task meno importanti diventano non bloccanti.
        
        Il tempo massimo di blocco bi, per il task i, in RM/DM è :
        +
        
        La prima parte dipende da x(i) cioè autosospensione, la seconda dal tempo massimo di blocco per non interrompibilità per (Ki + 1) volte. K(i) è quante volte viene sospeso il Task i, + 1 perchè devo considerare anche il primo rilascio.
        
        Cambi di contesto
        
        Definisco CS il costo di un cambio di contesto tra due job, incluso il tempo necessario all’esecuzione dello scheduler. Metto questi rallentamenti nel tempo di esecuzione!
        
        C'è un fattore 2 perchè considero quando viene messo in esecuzione e quando viene tolto dall’esecuzione. Questo vale solo localmente, globalmente non ci va questo fattore 2.
        
        Se CS grande, la schedulazione LST basata su Slack, che richiede molti cambi di contesto, si dimostra inefficiente.
        
        Test di schedulabilità per job bloccanti
        
        Ho calcolato prima b(i), come lo uso nei test di schedulabilità?
        
        Idea: al tempo che ha un job per terminare devo togliere il tempo massimo di blocco (alla fine in questo blocco perde tempo utile).
        
        Ne consegue che, per essere schedulabile, devo riuscire ad eseguirlo considerando questi tempi di blocco! Allora:
        
        per (tempi di risposta piccoli)
        
        per (caso generale)
        
        ATTENZIONE: nella seconda formula, perchè b(i) e non j * b(i) ?
        Per il discorso di prima: Il blocco è qualcosa che considero soltanto quando devo studiare la schedualbilità del singolo job ed è relativa solo al singolo job. Non ha senso considerarla per tutti i task insieme, si fa sempre studio task per task.
        
        Esempio: sto al 3° job di Ti, quindi sicuramente devo includere 3*e(i) (perchè eseguo per forza i primi due job + lui).
        Poichè sto facendo una analisi sul 3° job devo vedere solo quando lui viene bloccato, cioè per un tempo massimo b(i). Lui ha solo un tempo di blocco.
        
        Condizioni di schedulabilità per task bloccanti a priorità fissa
        
        Senza task bloccanti, vedevamo la schedulabilità grazie al fattore di utilizzazione. Ma ora? Devo farlo un task alla volta!
        
        La sommatoria guarda ai task di priorità superiore, e poichè ogni job di Ti potrebbe impiegare un tempo e(i) + b(i), ho che Ti è schedulabile se:
        
        Perchè bi/pi? Perchè come abbiamo detto, b(i) è un valore che vale singolarmente, non globalmente. Inoltre, per come è definita l'utilizzazione (e/p) mi riconduco a questa scrittura. NB: bi è già il tempo massimo di blocco per il task i , già include i ritardi dovuti a task più importanti e meno importanti!
        
        1 more item...