000-COMPLETO.pdf

obsidian-notes-AESO- MICRO_ARCHITETTURE_book MICRO_ARCHITETTURE 📂 AAA Check List 📂 Capitolo-1 📂 Capitolo-2 📂 Capitolo-3 📂 Capitolo-4 📂 Capitolo-5 📂 Capitolo-6 📂 Capitolo-7 📂 Capitolo-8 Capitolo-1 📄 1.2-L'arte di Gestire le complessità 📄 1.4-Sistemi Numerici 📄 1.5-Porte Logiche 1.2-L'arte di Gestire le complessità 1.2-L'arte di Gestire le complessità L'Astrazione L'Astrazione è la tecnica fondamentale per imparare a controllare la complessità e consiste nel nascondere dettagli quando questi non sono importanti La Disciplina è l'atto di restringere intenzionalmente le scelte di progetto in modo da poter lavorare in maniera più produttiva a un livello di astrazione più alto Le 3 Y Gerarchia: implica dividere un sistema in moduli e successivamente suddividere ulteriormente ognuno di questi moduli finchè i pezzi che li compongono non sono facili da comprendere Modularità: implica che i moduli abbiano funzioni e interfacce ben definite così da connettersi tra di loro in maniera semplice Regolarità: cerca l'uniformità tra i moduli. I moduli più comuni vengono riutilizzati più volte riducendo il numeri di moduli da progettare 1.4-Sistemi Numerici 1.4-Sistemi Numerici Numeri Decimali È il sistema numerico che si impara fin dalle elementari e che usiamo nella matematica classica. I numeri vanno da 0,..,9 e la concatenazione dei simboli porta alla creazione di numeri più grandi secondo questa regola: 3 2 1 0 974210 = 9 ∗ 10 + 7 ∗ 10 + 4 ∗ 10 + 2 ∗ 10 Numeri Binari È il sistema dei numeri in base 2. I valori che possono assumere sono quelli dei bit ovvero (0,1). Se 0 -> False Se 1 -> True Sono rappresentati sotto questa forma: 4 3 2 1 0 101102 = 1 ∗ 2 + 0 ∗ 2 + 1 ∗ 2 + 1 ∗ 2 + 0 ∗ 2 = 2210 Per convertire un numero da decimale a binario basta cercare la potenza di 2 più vicina che non superi il mio numero e mettere 1 in quella posizione, poi guardare se il resto della sottrazione è >= alla potenza di 2 successivamente minore. Se non lo è la posizione verrà occupata da uno 0, altrimenti 1. Si procede così fino ad aver convertito totalmente il numero. Numeri Esadecimali Numeri in base 16 che vanno dallo 0,..9,A,B,C,D,E,F comprendendo le prime 6 lettere dell'alfabeto. Si scrivono in questa forma: 2 1 0 2ED16 = 2 ∗ 16 + E ∗ 16 + D ∗ 16 = 74910 Per convertire in binario bisogna ricordarsi che ogni cifra esadecimale corrisponde a 4 bit binari, quindi: 2ED16 = 2− > 0010 + E− > 1110 + D− > 1101 = 0010111011012 Byte, Nibble e Word Un insieme di 8 bit è chiamato byte e rappresenta una di 2 = 256 8 possibilità. è la grandezza di misura utilizzata per misurare la grandezza degli oggetti immagazzinati nelle memorie dei calcolatori. Un gruppo di 4 bit è invece chiamato nibble e rappresenta una di 2 = 16 possibilità. Una cifra esadecimale rappresenta un 4 nibble mentra 2 un byte. I microprocessori gestiscono dat in gruppi di bit chiamati word la cui grandezza dipende dall'architettura del processore. Ad oggi operano su word di 64 bit. All'interno di un gruppo di bit, il bit che si trova nella colonna di peso 1 è chiamato bit meno significativo (lsb, less significant bit) e il bit che si trova dalla parte opposta viene chiamato bit più significativo (msb, most significant b). Allo stesso modo in una parola esiste il byte più significativo e il byte meno significativo composti da 8 bit. Somma binaria Per sommare 2 numeri binari basta metterli in colonna e sommare le cifre nella stessa colonna. 1+1=0 con riporto di 1, 1+0=1, 0+1=1, 0+0=0. ex. 10011+ 00111= ====== 11010 Numeri Binari Relativi Esistono due modi per rappresentare i numeri binari relativi (ovvero con il segno) e sono: modulo e segno complemento a 2 Numeri in modulo e segno Un numero espresso in modulo e segno a N bit utilizza il bit più significativo per esprimere il segno e i restanti N-1 bit per esprimere il modulo del numero. Il bit più significativo ha valore: 1 -> negativo 0 -> positivo Ha un intervallo di variabilità pari a N −1 [−2 N −1 + 1, 2 , però − 1] per lo 0 esistono 2 rappresentazioni e diventa complicato. Inoltre non è possibile svolgere la somma con il classico metodo. Numeri in complemento a 2 Qua lo 0 ha una sola rappresentazione ed è possibile effettuare la somma con il classico metodo. Lo 0 èscritto come una sequenza di tutti 0 -> 00..000 , il massimo numero positivo ha il 2 bit più significativo a 0 e il resto tutto a 1 -> 011..111 = 22 N −1 mentre il numero più negativo è composto da un 1 seguito da tutti 0 -> 100..000 = −2 2 e il numero -1 è scritto come una N −1 sequenza di tutti 1 -> 11..111. 2 Il bit più significativo è sempre il bit di segno e può essere invertito con l'operazione del complemneto a due. Consiste nell'invertire tutti i bit del numero e poi aggiungere 1 al bit meno significativo. La sottrazione è un operazione che avviene facendo il complemento a 2 del secondo numero e poi facendo la somma classica fra 2 numeri binari. La somma tra due numeri in complemento a 2 potrebbe risultare in un traboccamento se supera l'intervallo [−2 N −1 ,2 ] mentre una N −1 sottrazione non genererà mai questo problema. 1.5-Porte Logiche 1.5-Porte Logiche Cosa sono le porte logiche? Le Porte logiche (logic gates) sono semplici circuiti digitali che utilizzano uno o più ingressi binari per produrre un'uscita binaria. Solitamente gli ingressi vengono disegnati a sinistra o in alto mentre l'uscita a destra o in basso. Per gli ingressi solitamente vengono utilizzate le prima lettere dell'alfabeto mentre per l'uscita la lettera Y. Le relazioni tra ingressi e uscita possono essere descritti attraverso una tabella di verità o con un espressione booleana. Ci sono diversi tipi di porte logiche: La porta NOT Una porta NOT ha un ingresso A, e un'uscita Y. L'uscita è esattamente il contrario rispoetto all'ingresso, quindi se entra TRUE -> FALSE mentre se entra FALSE -> TRUE. A Y 0 1 1 0 La porta AND La porta AND genera TRUE all'uscita Y solo se entrambi A e B sono TRUE, altrimenti genera FALSE. A B Y 0 0 0 0 1 0 1 0 0 1 1 1 La porta OR La porta OR produce all'uscita Y TRUE se A, oppure B, oppure entrambi hanno valore TRUE, altrimenti FALSE. A B Y 0 0 0 0 1 1 1 0 1 1 1 1 Buffer Riproduce semplicemente il valore di ingresso. A Y 0 0 1 1 Altre porte logiche a 2 ingressi XOR Restituisce TRUE se A oppure B, ma non entrambi hanno valore TRUE. Una porta XOR a N ingressi restituisce TRUE se si ha un numero dispari di ingressi TRUE A B Y 0 0 0 0 1 1 1 0 1 1 1 0 XNOR Restituisce TRUE solo se si ha un numero pari (compreso 0) di ingressi TRUE A B Y 0 0 1 0 1 0 1 0 0 1 1 1 NAND Esegue AND e NOT. Restituisce sempre TRUE ad eccezione di quando A e B sono TRUE. A B Y 0 0 1 0 1 1 A B Y 1 0 1 1 1 0 NOR Esegue OR e NOT. Restituisce TRUE se né A né B sono TRUE. A B Y 0 0 1 0 1 0 1 0 0 1 1 0 Porte a ingressi multipli Ne esistono molte ma le più comuni sono: AND OR XOR NAND NOR XNOR AND produce TRUE solo se tutti i suoi ingressi hanno valore TRUE, OR invece se almeno uno dei suoi ingressi ha valore TRUE. Capitolo-2 📄 2.10-Riassunto 📄 2.2-Espressioni Booleane 📄 2.3-Algebra Booleana 📄 2.7-Mappe di Karnaugh 📄 2.8-Blocchi costitutivi combinatori 📄 2.9-Temporizzazioni 2.10-Riassunto 2.10-Riassunto Una rete digitale è un modulo con ingressi e uscite a valori discreti e una specifica che descrive la funzione e la temporizzazione del modulo. La funzione di una rete combinatoria può essere data da una tabella delle verità o da un’espressione booleana. L’espressione booleana relativa a una qualsiasi tabella delle verità può essere ottenuta in maniera sistematica utiliz- zando la forma somma di prodotti o la forma prodotto di somme. Nella sua forma somma di prodotti, l’espressione è scritta come la somma (OR) di uno o più implicanti, cioè prodotti (AND) dei letterali. I letterali, a loro volta, sono la forma diritta o negata delle variabili d’ingresso della funzione. Le espressioni booleane possono essere semplificate utilizzando le regole dell’algebra booleana. In particolare, esse possono essere semplificate nella loro forma minima somma di prodotti combinando tra loro gli implicanti che differiscono solo di un letterale nella forma diritta e negata: PA + PA = P. Le mappe di Karnaugh sono strumenti grafici utilizzati per minimizzare espressioni che hanno fino a quattro variabili. Le porte logiche sono connesse tra loro per creare reti combinatorie che eseguono la funzione richiesta. Una qualsiasi funzione in forma somma di prodotti può essere costruita utilizzando la logica a due livelli: in particolare, le porte NOT formano i complementi degli ingressi, le porte AND i prodotti e le porte OR formano la somma. Le porte logiche vengono inoltre combinate per creare reti più grandi, come i multiplexer, i decoder e le reti a priorità. Un multiplexer ha la capacità di scegliere un ingresso di dato basandosi su un ingresso di selezione, un decoder attiva una delle uscite a 1 in base alla configurazione presente agli ingressi, mentre una rete a priorità produce un’uscita che indica l’ingresso a priorità più alta. Queste reti rappresentano esempi di blocchi costitutivi combinatori. La specifica di temporizzazione di una rete combinatoria consiste nei ritardi di propagazione e di contaminazione attraverso la rete, che indicano rispettivamente il tempo più lungo e quello più corto tra un cambiamento di un ingresso della rete e il cambiamento dell’uscita che ne consegue. Calcolare il ritardo di propagazione di una rete implica l’individuazione del percorso critico attraverso il circuito, e successivamente la somma dei vari ritardi di propagazione di ogni elemento lungo il percorso. Ci sono diversi modi per realizzare complesse reti combinatorie che offrono buoni compromessi tra la velocità della rete e il suo costo. 2.2-Espressioni Booleane 2.2-Espressioni Booleane Cosa sono le espressioni booleane? Le espressioni booleane si basano su variabili che possono assumere solo i valori TRUE e FALSE. Terminologia Il complemento di una variabile A è il suo negato A¯. L'AND è definito come prodotto logico o implicante. Un minitermine è il prodotto di tutti gli ingressi di una funzione, quindi AB̄C̄ è un minitermine della funzione che prende come input le 3 variabili A,B,C; ¯ AB non lo è perchè non considera C. L'OR invece è definito come somma logica o implicato. Un maxitermine è la somma di tutti gli ingressi della funzione, quindi ¯ A + B + C è un maxitermine. L'ordine delle operazioni è importante: NOT ha la massima precedenza AND segue NOT OR segure AND Forma somma di prodotti Una tabella della verità con N ingressi contiene 2 N righe e ognuna di esse è associata ad un minitermine che è TRUE per quella riga. A B Y minitermine nome del minitermine 0 0 0 ĀB̄ m0 0 1 1 ¯ AB m1 1 0 0 AB̄ m2 1 1 0 AB m3 è possibile scrivere un'espressione booleana tramite la somma di tutti i minitermini in corrispondenza dei quale Y -> TRUE. ex. A B Y minitermine nome del minitermine 0 0 0 ¯ AB̄ m0 0 1 1 ¯ AB m1 1 0 0 AB̄ m2 1 1 1 AB m3 ¯ Y = AB + AB -> questa espressione è chiamata forma canonica somma di prodotti e può essere scritta così: F (A, B) = ∑(m1, m2) oppure: F (A, B) = ∑(1, 3) (1,3) perchè nella riga 1 e nella riga 3 della tebella di verità abbiamo come risultato TRUE (partono da 0). Forma prodotto di somme Un modo alternativo per scrivere le funzioni booleane è la forma canonica prodotto di somme. Ad ogni riga della tabella corrisponde un maxitermine che è FALSE per quella riga. La forma canonica prodotto di somme può essere scritta con la notazione pi greco utilizzando il simbolo di produttoria, ∏. A B Y maxitermine nome del maxitermine 0 0 0 A + B M0 0 1 1 A + B̄ M1 1 0 0 ¯ A + B M2 1 1 1 ¯ A + B̄ M3 Y = (A + B) + (Ā + B) Può essere scritta con la produttoria così: Y = ∏(M0, M2) oppure: Y = ∏(0, 2) nb La somma di prodotti produce un'espressione più corta quando poche uscite hanno TRUE, analogamente il prodotto di somme quando ci sono poche uscite FALSE. 2.3-Algebra Booleana 2.3-Algebra Booleana Cos'è l'algebra booleana? L'algebra booleana è utilizzata per semplificare le espressioni booleane e le regole sono simili a quelle dell'algebra ordinaria. Si basa su un'insieme di postulati che per definizione sono considerati corretti e obbediscono al principio di dualità: Se i simboli 0 e 1 e gli operatori ⋅ (AND) e + (OR) sono scambiati fra di loro, l'affermazione rimane corretta. Postulati Postulato Forma Duale Nome A1 B=0 se B!=1 A1' B=1 se B!=0 Alegebra binaria A2 =1 0̄ A2' =0 1̄ NOT A3 0 ⋅ 0 = 0 A3' 1 + 1 = 1 AND/OR A4 1 ⋅ 1 = 1 A4' 0 + 0 = 0 AND/OR A5 0 ⋅ 1 = 1 ⋅ 0 = A5' 1 + 0 = 0 + 1 = AND/OR 0 1 Teoremi a una variabile Postulato Forma duale Nome T1 B ⋅ 1 = B T1' B + 0 = B Identità T2 B ⋅ 0 = 0 T2' B + 1 = 1 Nullo T3 B ⋅ B = B T3' B + B = B Idempotenza T4 ¯ B̄ = B Involuzione T5 B ⋅ B̄ = 0 T5' B + B̄ = 1 Complementi Teoremi a più variabili Postulato Forma duale Nome T6 B ⋅ C = C ⋅ B T6' B + C = C + B Commutatività T7 (B ⋅ C) ⋅ D = B Postulato ⋅ T7' (B + C) Forma duale + D = Nome Associatività (C ⋅ D) B + (C + D) T8 (B ⋅ C) + (B ⋅ T8' (B + C) ⋅ (B + Distributività D) = B + (C ⋅ D) D) = B + (C ⋅ D) T9 B ⋅ (B + C) = B T9' B + (B ⋅ C) = B Assorbimento T10 (B ⋅ C) + (B ⋅ ¯ C T10' (B + C) ⋅ (B + Combinazione ) = B C) = B ¯ T11 (B ⋅ C) + (B̄ ⋅ T11' (B + C) ⋅ (B̄ + Consenso D) + (C ⋅ D) = D) ⋅ (C + D) = (B ⋅ C) + (B̄ ⋅ D) (B + C) ⋅ (B̄ + D) T12 T12' Teorema di De – – B0 ⋅ B1 ⋅ B2⋅... B0 + B1 + B2+... = (B̄0 + B̄1 + B̄2+... ) = (B̄0 ⋅ B̄1 ⋅ B̄2⋅... ) Morgan Bolla Il circoletto di negazione viene chiamato bolla. Le regole alla base dello spostamento della bolla sono: Spingere una bolla all'indietro (dall'uscita all'ingresso) o in avanti (viceversa) trasforma una porta AND in una porta OR e viceversa; se si spinge una bolla dall'uscita verso gli ingressi, questa viene trasferita a ognuno di essi; se si spingono tutte le bolle degli ingressi di una porta verso la sua uscita, quest'ultima avrà una bolla sola. Semplificare le espressioni I teoremi dell'algebra booleana sono utili per semplificare le espressioni booleane. ex. Y = ĀB + AB per il T 10 --> Y = B Un'espressione è definita minima se utilizza il minor numero possibile di implicanti. Un implicante è detto implicante primo se non può essere combinato con nessun altro elemento all'interno dell'espressione per formare un nuovo implicante con un minor numero di letterali. In un'espressione minima, gli implicanti devono essere tutti implicanti primi. 2.7-Mappe di Karnaugh 2.7-Mappe di Karnaugh Cosa sono le Mappe di Karnaugh? Le mappe di Karnaugh (K-map) sono un modello grafico di semplificazione delle espressioni booleane. Sono uno strumento molto efficace per risolvere problemi con al massimo 4 variabili. La riga in alto mostra le possibili 4 combinazioni di valori di ingresso A e B, mentre i 2 possibili valori di C sono riportati della colonna di sinistra. Ogni quadrato corrisponde a una riga della tabella di verità e contiene il valore dell'uscita Y corrispondente a quella riga. nb L'ordine 00,01,11,10 è chiamato codice Gray ed è utilizzato nelle mappe perchè preserva la proprietà la quale gli elementi adiacenti differiscono solo per una variabile. Pensare in cerchi C\AB 00 01 11 10 0 (1) 0 0 0 1 (1) 0 0 0 C\AB 00 01 11 10 0 – ABC ĀBC̄ ABC̄ AB̄C̄ C\AB 00 01 11 10 1 ¯¯ ABC ¯ ABC ABC AB̄C è sempre possibile utilizzare l'algebra booleana per semplificare le e spressioni: ¯ ¯ ¯ ¯ Y = AB̄C̄ + AB̄C = AB̄(C̄ + C) = AB̄ Ma usando la mappa di Karnaugh semplifichiamo graficamente cerchiando tutti gli 1 nei riquadri adiacenti e bisogna scrivere gli implicanti corrispondenti al quadrato dove è presente 1. Il risultato è analogo ma è più veloce vederlo. Minimizzazione logica con le mappe di Karnaugh Le regole per torvare l'espressione minima a partire da una mappa di Karnaugh sono: Utilizzare il minor numero possibile di cerchi per includere tutti gli 1; Tutti i riquadri racchiusi in un cerchio devono contenere solamente 1; Ogni cerchio deve includere un numero di riquadri che sia una potenza di 2 (1,2,4,8...) in qualsiasi direzione; Ogni cerchio deve essere il più largo possibile; è possibile disegnare un cerchio che avvolga le estremità della mappa di Karnaugh; Un 1 in una mappa di Karnaugh può essere cerchiato più di una volta, se questa operazione permette di utilizzare un minor numero di cerchi. Indifferenze Vengono indicate con il simbolo X, che significa che il valore che può assumere è sia 0, sia 1. In una mappa di Karnaugh, una X permette di aumentare ulteriormente la minimizzazione logica: infatti, queste possono essere incluse nei cerchi se l'operazione può essere utile a coprire più 1 con un numero minore di cerchi, mentre da ignorare se non sono d'aiuto. 2.8-Blocchi costitutivi combinatori 2.8-Blocchi costitutivi combinatori Multiplexer I multiplexer (MUX) sono fra le reti più comunemente usate. Sono in grado di scegliere un'uscita a partire da un certo numero di ingressi basandosi sul valore del segnale di selezione. Multiplexer 2:1 Un mux 2:1 ha 2 ingressi dati D0, D1 , un ingresso di selezione S e un'uscita Y. Il multiplexer sceglie tra i 2 ingressi di dato a seconda del valore S : Se S = 0, Y = D0 Se S = 1, Y = D1 S viene chiamato anche segnale di controllo proprio perchè controlla l'uscita del multiplexer Multiplexer più grandi Un 4:1 possiede 4 entrate e un'uscita sola e di conseguenza tutti quelli più grande come i 8:1,16:1... sono composizioni di multiplexer più piccoli che si rifanno al 2:1. nb Un mux N:1 necessita di log2N ingressi di selezione S Logica a multiplexer I multiplexer possono essere utilizzati come tabelle di ricerca (lookup table) per eseguire funzioni logiche. Con un po' di astuzia è possibile dimezzare la taglia del multiplexer utilizzando solo un multiplexer a 2 N −1 ingressi per eseguire una qualsiasi funzione logica a N ingressi. La strategia di base è fornire uno dei letterali di ingresso della funzione, insieme agli 1 e 0, agli ingressi di dato del multiplexer come mostrato qua sotto: Decoder Un decoder ha N ingressi e N 2 uscite e attiva una delle sue uscite a seconda della combinazione dei valori di ingresso. Le uscite sono dette one hot perchè solo un'uscita è "calda" (ALTA) in ogni momento Logica a decoder Ogni uscita di un decoder rappresenta un minitermine. Una funzione a N ingressi con un numero M di 1 in un'unica tabella della verità può essere costruita con un decoder N : 2 N e una porta OR a M ingressi connessa a tutti i minitermini associati ad un 1 in uscita nella tabella. Qua sotto viene riportata la funzione XNOR a 2 ingressi: 2.9-Temporizzazioni 2.9-Temporizzazioni Cosa sono le Temporizzazioni? Uno dei problemi più importanti legato alle reti è la temporizazione (timing), in altre parole fare in modo che la rete funzioni velocemente. Il Ritardo (delay) è il tempo tra un cambiamento in un ingresso e il conseguente adattamento dell'uscita di un buffer. sussy bakaa you're gay bro >:) Ritardi di propagazione e di contaminazione La logica combinatoria è caratterizzata da: Ritardo di propagazione: (t ) è il tempo massimo dal pd cambiamento in ingresso al momento in cui l'uscita raggiunge il suo valore finale Ritardo di contaminazione: (t ) è il tempo minimo in cui cd cambia un ingresso al momento in cui una qualsiasi uscita inizia in suo processo di adattamento del suo valore Percorso critico: è il percorso seguito dal segnale tra l'ingresso A o B fino all'uscita Y. Limita la velocità alla quale la rete opera Percorso minimo: è il percorso seguito dal segnale tra l'ingresso D è l'uscita Y. è il percorso più breve (e quindi anche il più veloce) perchè attraversa solo una porta dall'ingresso fino all'uscita. Alee Le Alee sono molteplici cambiamenti in uscita causati da un singolo cambiamento in ingresso. Si presenta un'Alea quando una singola variazione in una singola variabile di ingresso attraversa i confini di due implicanti primi in una mappa di Karnaugh. Capitolo-3 📄 3.2-Latch e flip-flop 📄 3.3-Progetto di reti logiche sincrone 📄 3.4-Macchine a stati finiti 📄 3.5-Temporizzazione della logica sequenziale 📄 3.6-Parallelismo 📄 3.7-Riassunto 3.2-Latch e flip-flop 3.2-Latch e flip-flop Introduzione agli elementi bistabili Il blocco costitutivo della memoria è un elemento bistabile, cioè un elemento con 2 stati stabili. La figura mostra un elemento bistabile composto da una coppia di negatori (inverter) connessi ad anello. La rete non ha ingressi, ma possiede 2 uscite, Q e ¯ Q che dipendono una dall'altra: 1. Q = 0: l1 riceve un ingresso FALSE su Q e produce un'uscita TRUE su Q̄. l2 riceve TRUE su Q e produce un'uscita FALSE su Q̄. 2. Q = 1: l1 riceve un ingresso TRUE su Q e produce un'uscita FALSE su Q̄. l2 riceve FALSE su Q e produce un'uscita TRUE su Q̄. Un elemento con un numero N di stati stabili è caratterizzato da log N bit di informazione, quindi un elemento bistabile 2 immagazzina un bit di infomazione. L'utente non ha a disposizione un ingresso che gli permetta di controllare lo stato, ma con i latch e i flip-flop l'ingresso è controllato dall'utente con delle variabili di stato. Latch Latch SR Il Latch SR è composto da 2 porte NOR collegate a croce. Il Latch ha 2 ingressi, S e R, e 2 uscite, Q e Q¯. Può essere controllato mediante S e R che attivano (settano) o disattivano (resettano) l'uscita Q. Qua sotto è mostrata la tabella di verità per comprendere il funzionamento nei vari casi: ¯ S R Q Q 0 0 Qprec Q̄prec 0 1 0 1 1 0 1 0 1 1 0 0 nb Qprec e Q̄prec sono i valori precedenti di Q e Q̄ salvati nella memoria della rete Settare un bit significa fargli assumere il valore TRUE, resettarlo fargli assumere il valore FALSE. Quando viene attivato R, Q viene resettato a 0 e Q̄ in modo opposto, quando viene attivato S , Q viene settato a 1 e ¯ Q in modo opposto. Latch D Questo Latch ha 2 ingressi: un ingresso dati, D, che controlla il prossimo stato, e un ingresso clock, CLK , che controlla invece il momento del cambio di stato. Qua sotto la tabella di verità che descrive il comportamento: CLK D D̄ S R Q Q̄ 0 X X̄ 0 0 Qprec ¯ Qprec 1 0 1 0 1 0 1 1 1 0 1 0 1 0 Quando CLK = 0, sia S sia R sono FALSI, indipendentemente dal valore assunto da D. Se invece CLK = 1, allora una porta AND produce un valore VERO e l’altra un valore FALSO, a seconda del valore di D. La Tabella di prima mostra come, dati i valori di S e di R, sia possibile determinare Q e Q ¯. Si osservi che, quando CLK = 0, Q ricorda il suo valore precedente, Q , prec mentre quando CLK = 1, Q = D. In ogni caso, resta, come ¯ Q logico, il complemento di Q. Il latch D è in grado di evitare il caso anomalo in cui gli ingressi S e R vengano attivati simultaneamente. Quando CLK = 1, il Latch è detto trasparente, cioè i dati scorrono da D a Q come se fosse un Buffer; Quando , il Latch è detto opaco, quindi viene CLK = 0 bloccato il passaggio di dati verso Q che mantiene il valore precedente Flip-Flop Flip-flop D Un Flip-flop D può essere costruito a partire da 2 Latch D in cascata controllati da 2 segnali di clock complementari come in figura: L1 viene detto master L2 viene detto slave Quando CLK = 0 , il master è trasparente e lo slave opaco. Di conseguenza il valore D viene portato a N 1. Quando CLK = 1, il master è opaco e lo slave trasparente. In questo caso N1 viene trasmesso a Q ma N1 resta isolato da. D Quindi, qualunque sia il valore di D subito prima del fronte di salita (passaggio da 0 a 1) del CLK , quello di N 1 è il valore che viene trasferito a Q al momento di tale fronte. In tutti gli altri casi, Q mantiene il suo valore precedente, dal momento che c’è sempre un latch opaco che blocca il passaggio di dati tra D e Q. Viene anche chiamato flip-flop master-slave o flip-flop attivato sui fronti Registro Un registro a N bit è un banco di N flip-flop che condividono un ingresso CLK comune in modo che tutti i bit vengano aggiornati nello stesso tempo. Flip-flop con abilitazione Un flip-flop con abilitazione aggiunge un altro ingresso, chiamato EN o EN ABLE, per determinare se memorizzare o no il dato sul fronte del CLK. Quando EN è TRUE, il flip-flop con abilitazione reagisce come un normale flip-flop D; quando invece EN è FALSE, il flip-flop con abilitazione ignora il CLK e mantiene il proprio stato. I flip-flop con abilitazione sono utili quando si desidera inserire un nuovo valore in un flip-flop esclusivamente in alcuni precisi momenti, piuttosto che a ogni cambio del clock. Flip-flop resettabile Un flip-flop resettabile aggiunge un altro ingresso, chiamato RESET. Quando l’ingresso RESET è FALSE, il flip-flop resettabile si comporta come un flip-flop D. Quando invece RESET è TRUE, il flip-flop resettabile ignora D e resetta l’uscita a 0. Questa tipologia di flip-flop è utile nel caso in cui si desideri forzare uno stato noto (cioè 0) in tutti i flip-flop della rete quando viene accesa. Questi flip-flop possono essere resettabili in modo sincrono o asincrono: Sincrono: si resettano solo al fronte di salita di CLK ; Asincrono: si resettano nel momento in cui RESET diventa TRUE, indipendentemente dal valore da CLK. 3.3-Progetto di reti logiche sincrone 3.3-Progetto di reti logiche sincrone Reti sequenziali sincrone Se si applicano valori di ingresso alla logica combinatoria, le uscite si portano sempre al valore corretto dopo un tempo pari al ritardo di propagazione. Al contrario, le reti sequenziali con percorsi ciclici possono avere condizioni di corsa o comportamenti instabili. Per evitare questi problemi, i progettisti preferiscono interrompere i percorsi ciclici inserendo in alcuni punti dei registri. Questa operazione trasforma la rete in un insieme di logica combinatoria e registri. I registri contengono lo stato del sistema, che cambia solo in corrispondenza dei fronti di clock, motivo per cui lo stato viene detto sincronizzato con il clock. Una rete sequenziale ha una serie finita di stati discreti {S0, S1,..., Sk1}. Una rete sequenziale sincrona ha un ingresso di clock i cui fronti di salita indicano una sequenza di istanti di tempo nei quali hanno luogo le transizioni di stato. Vengono spesso utilizzati i termini stato presente e stato prossimo per distinguere lo stato in cui il sistema si trova al momento attuale dallo stato in cui si porterà al prossimo fronte di clock. La specifica temporale consiste in un limite superiore (tpcq) e in un limite inferiore (tccq) del tempo dal fronte di salita del clock fino ai cambiamenti delle uscite, oltre che dei tempi di setup (attivazione) e di hold (mantenimento), tsetup e thold, che indicano invece quando gli ingressi devono essere stabili rispetto al fronte di salita del clock. Un flip-flop rappresenta l’esempio più semplice di rete sequenziale sincrona: possiede un ingresso D, un clock, CLK , un’uscita, Q, e due stati, {0, 1}. La specifica funzionale di un flip-flop consiste nell’affermazione che lo stato prossimo è D e che l’uscita, , è lo stato presente. Q 3.4-Macchine a stati finiti 3.4-Macchine a stati finiti Cosa sono le macchine a stati finiti? Sono reti sequenziali sincrone che sono in questa forma: Il loro nome deriva dal fatto che una rete con k registri può trovarsi in 2 stati diversi. Una FSM ha M ingressi, N uscite, k k bit di stato, riceve un segnale clock (CLK ) e a volte un segnale di reset. è composta da 2 blocchi di logica combinatoria, la logica di stato prossimo e la logica di uscita, e da un registro che immagazzina lo stato. Esempio di progettazione di una FSM Vogliamo far fare al nostro ingegnere Ben un semaforo per controllare il traffico a un incrocio universitario. Ben decide di risolvere il problema utilizzando una macchina a stati finiti, e installa due sensori per il traffico, T e T , a b rispettivamente in via Accademia e in viale Ateneo. Ognuno di questi sensori indica TRUE se sono presenti degli studenti sulla strada, e FALSE se non sta passando nessuno. Installa anche due semafori stradali, L e L , per controllare il a b traffico. Ogni semaforo riceve ingressi digitali che specificano se la luce accesa deve essere verde, gialla o rossa. Quindi la macchina a stati finiti ha due ingressi, Ta e , e due uscite, L e L (ciascuna da due bit). Inserisce un Tb a b clock con un periodo di 5 secondi: a ogni periodo del clock (fronte di salita) i semafori possono cambiare a seconda di quello che indicano i sensori del traffico. Decide di inserire anche un bottone di reset per far sì che si possa portare il controllore a uno stato iniziale noto al momento dell’accensione. Il diagramma degli stati indica tutti i possibili stati del sistema e le transizioni tra di essi. I cerchi rappresentano gli stati e gli archi rappresentano le transizioni tra di essi. Le transizioni avvengono al fronte di salita del clock. Se il sistema si trova nello stato S , rimane in quello stato se 0 Ta è TRUE e passa invece allo stato S se T è FALSE. 1 a Se da uno stato parte un solo arco, ciò significa che quella particolare transizione ha luogo indipendentemente dai valori degli ingressi. Per esempio, una volta arrivato allo stato S , 1 il sistema passa in ogni caso allo stato S. Il valore assunto 2 dalle uscite in ogni stato è indicato nello stato stesso. Per esempio, quando il sistema si trova in stato , S2 La è rosso e Lb è verde. La tabella degli stati (3.1, 3.2, 3.3) indica, per ogni stato presente e valori di ingresso, lo stato prossimo S del sistema. ′ Per costruire una rete reale però bisogna codificare gli stati e le uscite per scrivere la tabella delle transizioni (3.4) ed utilizzare questi codici binari. La Tabella delle uscite indica per ogni stato quale deve essere il valore assunto dall'uscita. LA = S1 1 LA = S̄1S0 0 LB = S̄1 1 LB = S1S0 0 Schema macchina alla Moore Codifica degli stati Un problema comune è quello di determinare quale codifica produce la rete desiderata col minor numero di porte logiche o col minor ritardo di propagazione. Non c'è un modo semplice per individuare la codifica migliore. Spesso è possibile scegliere una buona codifica tramite ispezione, facendo in modo che gli stati o le uscite con- nesse condividano dei bit. La scelta ricade tra una codifica binaria o codifica a singolo 1: Codifica Binaria: ogni stato viene rappresentato da un numero binario e dal momento che K numeri binari possono essere rappresentati con log2K bit, un sistema con K stati avrà Codifica a singolo 1: viene utilizzato un bit di stato per ognuno degli stati Una FSM con tre stati con codifica a singolo 1 avrà come codifiche di stato 001, 010 e 100. Ogni bit di stato viene immagazzinato in un flip-flop, quindi una codifica a singolo 1 necessita di più flip-flop rispetto a una codifica binaria. Ciononostante, con la codifica a singolo 1, le logiche di stato prossimo e di uscita risultano spesso più semplici. Macchine alla Moore e macchine alla Mealy Macchine alla Moore: le uscite dipendono solo dallo stato presenta della macchina. Nel diagramma degli stati i valori delle uscite vengono indicati nei cerchi. Macchine alla Mealy: le uscite dipendono sia dallo stato presente della macchina sia dagli ingressi attuali. Nel diagramma degli stati le uscite sono indicate sugli archi. Derivare un FSM da uno schema circuitale Serve: Esaminare la rete, gli ingressi e le uscite, i bit di stato. Scrivere le espressioni di stato prossimo e di uscita. Creare le tabelle delle transizioni e delle uscite. Ridurre le tabelle eliminando gli stati che non possono essere raggiunti. Assegnare un nome simbolico a ogni valida combinazione di bit di stato. Riscrivere le tabelle delle transizioni e delle uscite con i nuovi nomi. Disegnare il diagramma degli stati. Esprimere a parole il funzionamento della FSM. Riassunto Per progettare una FSM si utilizza la procedura seguente: Identificare gli ingressi e le uscite. Disegnare un diagramma degli stati. Per una macchina alla Moore: Scrivere la tabella degli stati. Scrivere la tabella delle uscite. Per una macchina alla Mealy: Scrivere una tabella unica di stati e uscite. Decidere la codifica degli stati, tenendo presente che la scelta influenza il progetto hardware. Scrivere le espressioni booleane per la logica di stato prossimo e la logica di uscita. Disegnare lo schema della rete. 3.5-Temporizzazione della logica sequenziale 3.5-Temporizzazione della logica sequenziale Cicli di clock Un flip-flop copia D sull'uscita Q a ogni fronte di salita del clock. Questo processo viene detto campionamento di D al fronte di salita del clock. Se D è stabile a 0 o 1 quando il clock ha fronte di salita, il comportamento del flip-flop è definito in modo chiaro. Il tempo di apertura di un elemento sequenziale viene definito da un tempo di setup e da un tempo di hold. è possibile interpretare il tempo con i cicli di clock Il periodo del clock deve essere abbastanza lungo da permettere a tutti i segnali di stabilizzarsi, il che costituisce un limite per la velocità del sistema. Nei sistemi reali, il clock solitamente non raggiunge tutti i flip-flop allo stesso tempo e questa differenza di tempo, detta sfasamento del clock, aumenta ulteriormente il periodo di clock necessario. Temporizzazione del sistema Il periodo di clock o tempo di ciclo, Tc , è il tempo fra i fronti di salita periodici del clock. fc = 1/T c è la frequenza di clock; aumentare la frequenza aumenta la quantità di lavoro. Vincolo sul tempo di setup Tc ≥ tpcq + tpd + tsetup Dove: Tc : periodo di clock tpcq : ritardi di propagazione da clock a Q tsetup : tempo di setup tpd : tempo di propagazione del segnale Quindi: tpd ≤ Tc − (tpcq + tsetup) Il termine racchiuso tra parentesi si chiama sovraccarico di sequenziamento Vincolo sul tempo di hold tccq + tcd ≥ thold Dove: : tempo di commutazione del segnale (il tempo che impiega tccq un segnale a cambiare di stato da un valore logico all’altro) : tempo in cui il dato D non deve cambiare dopo il thold fronte di salita del clock Quindi: tcd ≥ thold − tccq L'espressione viene chiamata vincolo sul tempo di hold o vincolo di ritardo minimo nb Le reti sequenziali hanno vincoli sul tempo di setup e sul tempo di hold che impongono i ritardi massimi e minimi della logica combinatoria tra i diversi flip-flop Sincronizzatori Per garantire dei livelli logici corretti, tutti gli ingressi asincroni dovrebbero essere fatti passare attraverso dei sincronizzatori. Il sincronizzatore, mostrato nella Figura, è un dispositivo che riceve un ingresso asincrono D e un clock CLK , per produrre un’uscita Q entro un certo periodo di tempo; la probabilità che l’uscita abbia un livello logico valido è estremamente alta. Se D è stabile durante il tempo di apertura, Q assume lo stesso valore di D. Se invece D cambia durante il tempo di apertura, Q può assumere un valore TRUE o FALSE, ma non può assumere un valore metastabile. Nb Un valore metastabile è un valore intermedio e instabile che può essere assunto da un circuito digitale quando si verifica una transizione di stato. In questo stato, il valore di uscita del circuito oscilla tra due valori logici possibili, senza stabilizzarsi su nessuno dei due. Img La Figura mostra un modo semplice di costruire un sincronizzatore a partire da due flip-flop. F 1 campiona D al fronte di salita di CLK : se D cambia in quel momento, l’uscita D2 potrebbe momentaneamente assumere un valore metastabile. Se il periodo del clock è abbastanza lungo, D2 con elevata probabilità si stabilizza su un livello logico valido prima della fine del periodo. Successivamente F 2 campiona D2, che a questo punto è stabile, producendo un’uscita accettabile Q. 3.6-Parallelismo 3.6-Parallelismo Cos'è il parallelismo? token: un gruppo di ingressi che vengono elaborati per produrre un gruppo di uscite latenza: tempo richiesto a un token per attraversare il sistema dall'inizio alla fine capacità produttiva: numero di token che possono essere elaborati per unità di tempo La capacità produttiva può essere aumentata se si elaborano più token allo stesso tempo. Questo modo di lavorare viene chiamato parallelismo e ne esistono di 2 tipi: parallelismo spaziale: vengono usate piuù copie dell'hardware in modo che più lavori possano essere svolti conteporaneamente parallelismo temporale: ogni compito viene diviso in fasi come una catena di montaggio (pipelining) nb Il problema principale del parallelismo è dato dalle dipendenze. Se un’azione presente dipende da un’azione precedente, invece di dipendere solo dai passi precedenti compiuti sulla stessa azione, tale azione non può iniziare finché quella prima non si è conclusa. 3.7-Riassunto 3.7-Riassunto In questo capitolo sono stati descritti l’analisi e il progetto della logica sequenziale. Al contrario della logica combinatoria, le cui uscite dipendono solo dagli ingressi presenti in quel momento, le uscite della logica sequenziale dipendono sia dagli ingressi presenti in quel momento sia dagli ingressi precedenti. Nelle reti sequenziali ci si limita ad utilizzare un numero ridotto di blocchi costitutivi progettati opportunamente. Per gli obiettivi di questo libro, l’elemento più importante è il flip-flop, che riceve un clock e un ingresso D e produce un’uscita Q. Il flip-flop copia D su Q al fronte di salita del clock e in tutte le altre situazioni ricorda lo stato precedente di Q. Un gruppo di flip-flop che condividono lo stesso clock viene detto registro. I flip-flop possono anche avere ingressi di reset e abilitazione. Nonostante esistano molte forme di logica sequenziale, si è scelto di utilizzare le reti sequenziali sincrone perché più semplici da progettare. Le reti sequenziali sincrone consistono di blocchi di logica combinatoria divisi da registri con clock. Lo stato della rete viene immagazzinato nei registri e aggiornato solo ai fronti del clock. Le macchine a stati finiti (FSM) costituiscono una tecnica molto efficace per progettare le reti sequenziali. Per progettare una FSM si seguono i passi descritti nel riassunto. Le reti sequenziali sincrone hanno una specifica temporale che include i ritardi di propagazione e di contaminazione da clock a Q, rispettivamente t e t , e i tempi di setup e hold, t pcq ccq e setup. Perché la rete operi correttamente, gli ingressi devono thold essere stabili per un tempo di apertura che inizia un tempo di setup prima del fronte di salita del clock e finisce un tempo di hold dopo il fronte di salita del clock. Il tempo di ciclo minimo T del sistema è uguale al ritardo di propagazione t c pd attraverso la logica combinatoria più t pcq+ t del registro. setup Inoltre, il ritardo di contaminazione attraverso il registro e la logica combinatoria deve essere maggiore di t. Nonostante hold l’errata convinzione comune, il tempo di hold non ha effetti sul tempo di ciclo. Le prestazioni globali del sistema vengono misurate in termini di latenza e di capacità produttiva. La latenza è il tempo necessario a un token per attraversare la rete dall’inizio alla fine. La capacità produttiva è il numero di token che il sistema può elaborare per unità di tempo. Il parallelismo migliora la capacità produttiva del sistema. Capitolo-4 📄 4.1-Introduzione 📄 4.2-Logica Combinatoria 📄 4.3-Modellazione strutturale 4.1-Introduzione 4.1-Introduzione Linguaggi di descrizione dell'hardware I progettisti si sono resi conto che è molto più produttivo fornire le specifiche delle funzioni logiche lasciando a una strumento di CAD (Computer Aided Design) il compito di produrre una rete di porte logiche ottimizzata. Tali specifiche sono fornite in genere tramite linguaggi di descrizione dell'hardware (HDL, Hardware Description Language) come System Verilog e VHDL. Origini dei linguaggi L'industria sembra indirizzarsi verso SystemV erilog ma molte aziende usano ancora V H DL nonostante sia più pesante e verboso di System Verilog. SystemV erilog V H DL Verilog è stato VHDL è stato sviluppato nel 1981 dal sviluppato nel 1984 Dipartimento della Difesa per SystemV erilog V H DL dalla ditta Gateway descrivere struttura e funzionamento Design Automation dell’hardware. Le sue radici derivano come linguaggio dal linguaggio di programmazione Ada. proprietario per la Inizialmente pensato come linguaggio simulazione logica. di documentazione, è divenuto presto uno strumento di simulazione e sintesi circuitale. Simulazione e sintesi I due obbiettivi principali degli HDL sono la simulazione e la sintesi. Nella simulazione si forniscono valori di ingresso al modulo e si controlla alle uscite se il modulo funziona correttamente. Nella sintesi la descrizione testuale del modulo viene tradotta in rete di porte logiche. Simulazione La simulazione è fondamentale per consentire di collaudare un sistema prima di costruirlo fisicamente visto che correggere un errore quando il sistema digitale è già stato prodotto può essere enormemente costoso. L'operazione di correggere un errore (bug) viene detta "debuggare": Sintesi La sintesi logica trasforma il codice H DL in uno schema di porte logiche e fili (netlist) che descrivono la realizzazione circuitale del modulo. Il sintetizzatore logico può fare ottimizzazioni per ridurre la quantità di hardware necessaria. Il codice H DL viene diviso tra moduli sintetizzabili e "banco di prova" (testbench), dove i moduli sono la parte circuitale e il banco contiene le istruzioni per applicare valori agli ingressi, verificare la correttezza dei valori in uscita ed evidenziare la discrepanze tra valori attesi e valori effettivi. I vari H DL hanno modi specifici di descrivere le classi di componenti logiche, definiti idiomi. 4.2-Logica Combinatoria 4.2-Logica Combinatoria Operatori a singolo bit Gli operatori a singolo bit (bitwise) agiscono su segnali costituiti da bit singoli o su bus multibit. ex. l'operatore neg descrive 4 negatori collegati a bus a 4 bit module neg (input logic [3:0] a, language-sv output logic [3:0] y); assign y = ~a; endmodule nb l'ordinamento dei bit di un bus è arbitrario e può essere: little-endian: a[N − 1 :0] big-endian: a[0:N ] − 1 Commenti a spazio vuoto I commenti in SystemVerilog sono simili a quelli in C: iniziano con la coppia di caratteri. Commenti che iniziano con la coppia di caratteri // terminano invece alla fine della riga. Operatori di riduzione Gli operatori di riduzione sono costituiti da porte logiche a tanti ingressi che producono una sola uscita module and8(input logic [7:0] a, output logic y); language-sv assign y = &a; // assign y = &a è molto più facile da scrivere di // assign y = a & a & a & a & // a & a & a & a; endmodule Assegnamento condizionale Un assegnamento condizionale seleziona l'uscita da generare fra varie alternative sulla base di un ingresso chiamato condizione (preticamente un if) module mux2(input logic [3:0] d0, d1, input logic s, output language-sv logic [3:0] y); assign y = s ? d1 : d0; endmodule Nb L’operatore condizionale ?: seleziona, sulla base della pri- ma espressione, la seconda o la terza espressione. La prima espressione è denominata condizione: se la condizione vale 1 l’operatore sceglie la seconda espressione, se vale 0 la terza Variabili interne p e g sono variabili interne perchè non sono nè ingressi nè uscite ma sono utilizzate solo all'interno del modulo. Sono simili alle variabili locali nei linguaggi di programmazione. language-sv module sommatore (input logic a, b, rin, output logic s, rout); logic p, g; //qua avviene la dichiarazione delle variabili interne assign p =a ^ b; assign g =a & b; assign s = p ^ rin; assign rout = g | (p & rin); endmodule Precedenze Numeri I numeri possono essere rappresentati in binario, ottale, decimale o esadecimale. La dimensione, ovvero il numero di bit, può essere specificata, e nelle posizioni più significative vengono inseriti 0 fino a riempire tale dimensione. Concatenazione di bit Spesso è necessario operare su un sottoinsieme dei segnali di un bus, o concatenare segnali provenienti da sorgenti diverse in un bus. Queste operazioni sono denominate in inglese bit swizzling (cocktail di bit). assign y = {c[2:1], {3{d}}, c, 3'b101}; language-sv // L’operatore {} è usato per concatenare bus. {3{d}} indica tre copie di d. Ritardi Le istruzioni H DL possono essere associate a ritardi, specificati in unità arbitrarie. I ritardi sono molto utili durante la simulazione per predire quanto velocemente funzionerà un circuito (se vengono specificati ritardi significativi) e anche in fase di debugging per comprendere cause ed effetti dei vari comportamenti (capire quale sia la causa di un’uscita sbagliata è molto difficile se tutti i segnali cambiano simultaneamente durante la simulazione). I ritardi vengono ignorati durante la sintesi: il ritardo di una porta logica prodotta dallo strumento di sintesi dipende dalle specifiche in termini di tpd e tcd e non da valori numerici messi nel codice H DL. 'timescale 1ns/1ps //è scritta qua!!! language-sv module esempio(input logic a, b, c, output logic y); logic ab, bb, cb, n1, n2, n3; assign #1 {ab, bb, cb} = ~{a, b, c}; assign #2 n1 = ab & bb & cb; assign #2 n2 = a & bb & cb; assign #2 n3 = a & bb & c; assign #4 y = n1 | n2 | n3; endmodule Nb I file SystemVerilog possono includere una direttiva di scala temporale che indica il valore di ogni unità di tempo. La direttiva è nella forma 'timescale unit/precision'. In questo esempio ogni unità è 1 ns, e la simulazione ha 1 ps di precisione. Se non si specifica la scala temporale, viene adottato, in genere, il valore di 1 ns sia per l’unità sia per la precisione. In SystemVerilog il simbolo # è usato per indicare il numero di unità di ritardo. 4.3-Modellazione strutturale 4.3-Modellazione strutturale L’Esempio 1 mostra come costruire un multiplexer 4:1 con tre multiplexer 2:1. Ogni copia del multiplexer 2:1 è chiamata istanza. Più istanze di uno stesso modulo si distinguono grazie a nomi diversi, in questo caso muxbasso , muxalto e muxuscita. language-sv module mux4(input logic [3:0] d0, d1, d2, d3, input logic [1:0] s, output logic [3:0] y); logic [3:0] basso, alto; mux2 muxbasso(d0, d1, s, basso); mux2 muxalto(d2, d3, s, alto); mux2 muxuscita(basso, alto, s, y); endmodule Le tre istanze di mux2 sono denominate muxbasso, muxalto e muxuscita. Il modulo mux2 deve essere definito da qualche altra parte nel codice SystemVerilog ___ L’Esempio 2 usa la modellazione strutturale per costruire un multiplexer 2:1 partendo da una coppia di buffer tristate. Tuttavia non è consigliabile costruire circuiti logici facendo uso di buffer tristate. module mux2(input logic [3:0] d0, d1, input logic s, output language-sv tri [3:0] y); tristate t0(d0, ~s, y); tristate t1(d1, s, y); endmodule In SystemVerilog, espressioni come ~s sono permesse nell’elenco di ingressi e uscite di un’istanza. Espressioni arbitrariamente complesse sono comunque sconsigliate perché rendono il codice poco leggibile. ___ L’Esempio HDL 3 mostra come i moduli possano accedere a parti di un bus. Un multiplexer 2:1 a 8 bit è realizzato con due dei multiplexer 2:1 a 4 bit già definiti, che lavorano rispettivamente sul nibble alto e su quello basso degli 8 bit. language-sv module mux2_8(input logic [7:0] d0, d1, input logic s, output logic [7:0] y); mux2 muxlsb(d0[3:0], d1[3:0], s, y[3:0]); mux2 muxmsb(d0[7:4], d1[7:4], s, y[7:4]); endmodule nb In generale, i sistemi complessi vengono realizzati in modo gerarchico. Il sistema completo viene descritto strutturalmente istanziando le sue componenti principali, quindi ogni componente viene descritta strutturalmente in termini di blocchi che la costituiscono, e il processo viene ripetuto ricorsivamente finché i blocchi sono abbastanza semplici da poter essere descritti in modo comportamentale. È buona norma evitare (o comunque contenere al massimo) di mischiare descrizioni strutturali e comportamentali all’interno di un singolo modulo. Capitolo-5 📄 5.2-Circuiti aritmetici 📄 5.3-Sistemi di numerazione 📄 5.5-Componenti di memoria 📄 5.6-Matrici logiche 📄 5.7-Riassunto 5.2-Circuiti aritmetici 5.2-Circuiti aritmetici Cosa fanno? I circuiti aritmetici sono i blocchi costruttivi centrali dei calcolatori. I calcolatori e la logica digitale eseguono molte funzioni aritmetiche: addizioni, sottrazioni, confronti, traslazioni, moltiplicazioni e divisioni. Addizione Si inizia esaminando come sia possibile sommare due numeri binari a 1 bit. Dopodiché, l’operazione viene estesa ai numeri binari a N bit. Semisommatore Il semisommatore ha due ingressi, A e B, e due uscite, S e R. out S rappresenta la somma di A e B. Se sia A sia B hanno valore 1, S è uguale a 2, un valore che non può essere rappresentato con una sola cifra binaria. Di conseguenza, il valore 2 viene rappresentato con un riporto (carry) Rout nella colonna successiva. Il semisommatore può essere costruito con una porta XOR e una AN D. Routviene sommato al bit più significativo successivo, però al semisommatore manca un ingresso R per accettare R in della out colonna precedente. Sommatore completo Un sommatore completo acceta l'ingresso Rin Sommatore a propagazione di riporto Un sommatore a N bit somma due ingressi a N bit, A e B, e aggiunge R per produrre un risultato a N bit S e un riporto in. Viene comunemente chiamato sommatore a propagazione di Rout riporto (o CPA, Carry Propagate Adder) perché il riporto di un bit si propaga nel bit successivo. Sommatore a propagazione di riporto a onda Il metodo per costruire un sommatore a propagazione di riporto a onda a N bit è collegare in cascata N full adder completi. In questo modo Rout di uno stadio costituisce Rin per lo stadio successivo. Il ritardo di un full adder è: tpropag = N tF A Sommatore ad anticipazione di riporto Un sommatore ad anticipazione di riporto (CLA, Carry-Lookahead Adder) è un altro tipo di sommatore a propagazione di riporto che risolve il problema della velocità dividendo il sommatore stesso in blocchi e aggiungendo un circuito per determinare velocemente il riporto di uscita da ciascun blocco appena è noto il riporto di ingresso. I sommatori ad anticipazione di riporto utilizzano segnali di generazione (G) e di propagazione (P ) che descrivono come una colonna o un blocco determinano il proprio riporto. La colonna i di un sommatore genera sicuramente se A e B sono entrambi Ri i i uguali a 1. Di conseguenza G , cioè il riporto generato dalla i colonna i , viene calcolato come G = A B.i i i Tutti i blocchi del CLA calcolano i segnali di generazione e di propagazione sia di colonna sia di blocco simultaneamente. Il percorso critico della rete inizia con il calcolo di G e G 0 3:0 nel primo blocco del sommatore ad anticipa- zione di riporto. Dopodiché, R avanza direttamente fino a R in attraverso la out porta AND/OR in ogni blocco fino all’ultimo Sommatore a prefissi Questi sommatori calcolano G e P per coppie di colonne, poi per gruppi di 4 colonne, poi di 8, 16 ecc., fino a che il segnale di generazione di ogni colonna non è noto. Le somme sono calcolate a partire da questi segnali di generazione. La strategia di un sommatore a prefissi è di calcolare il più rapidamente possibile il segnale di ingresso R per ogni i1 colonna i per poi eseguire la somma, utilizzando l’espressione: Si = (Ai ⊕ Bi) ⊕ Ri−1 Sottrazione I sommatori sono in grado di sommare numeri sia positivi sia negativi utilizzando la rappresentazione dei numeri in complemento a 2. La sottrazione è facile quanto l'addizione: si inverte il segno del secondo numero e poi si esegue la somma. Comparatori Un comparatore determina se due numeri binari sono uguali o se uno dei due è maggiore o minore dell’altro. Un comparatore riceve due numeri binari a N bit, A e B. Esistono due tipi comuni di comparatori: Comparatore di uguaglianza: produce una singola uscita che indica se A == B oppure no. Comparatore di valore: produce invece una o più uscite che indicano i valori relativi di A e di B. Il comparatore determina se i bit corrispondenti a ogni colonna A e B sono uguali utilizzando delle porte XNOR. La comparazione avviene effettuata calcolando A − B e guardando il segno (bit più significativo). Se 1 -> A < B Se 0 -> A ≥ B ALU Un’unità logica/aritmetica (ALU, Arithmetic/Logical Unit) unisce all’interno di una singola unità una serie di operazioni logiche e matematiche. La Figura mostra il simbolo di una ALU a N bit con ingressi e uscite di N bit. La ALU riceve un segnale di controllo a 2 bit, chiamato ControlloALU , che specifica quale funzione debba eseguire. Alcune ALU producono uscite ulteriori, chiamate flag, che danno informazioni aggiuntive sul risultato dell'ALU. L’uscita F lagALU è composta dalle flag N , Z , C e V che indicano, rispettivamente, che il risultato dell’ALU è negativo (Negative) o uguale a zero (Zero) o che il sommatore ha generato un riporto (Carry) o un traboccamento (oVerflow). Traslatori e rotatori I traslatori (shifter) e i rotatori (rotator) traslano i bit ed eseguono la moltiplicazione o la divisione per potenze di 2. Come suggerisce il nome, i traslatori traslano un numero binario a destra o a sinistra di uno specifico numero di posizioni. Esistono diversi tipi di traslatori: Traslatore logico: trasla un numero verso sinistra (LSL, Logical Shift Left) o verso destra (LSR, Logical Shift Right) e riempie gli spazi lasciati vuoti con 0. Ex. 11001 LSR 2 = 00110; 11001 LSL 2 = 00100 Traslatore aritmetico: stessa funzione di un traslatore logico ma quando trasla un numero verso destra (ARS , Arithmetic Shift Right), riempie i bit più significativi con una copia del precedente bit più significativo (msb, most significant bit). La traslazione aritmetica verso sinistra ( ASL, Arithmetic Shift Left) si comporta come la traslazione logica verso sinistra. Ex. 11001 ASR 2 = 11110; 11001 ASL 2 = 00100 Rotatore: trasla un numero verso sinistra (ROL, Rotate Left) o verso destra (ROR, Rotate Right) circolarmente, in modo che gli spazi lasciati vuoti vengano riempiti dai bit all’estremità opposta del numero. Ex. 11001 ROR 2 = 01110; 11001 ROL 2 = 00111 Un traslatore a N bit può essere costruito con un numero N di Multiplexer N:1. Moltiplicazione La moltiplicazione tra numeri binari senza segno è simile alla moltiplicazione decimale ma con solo uni e zeri. La Figura confronta la moltiplicazione di numeri decimali e binari. In entrambi i casi vengono formati dei prodotti parziali moltiplicando una singola cifra del moltiplicatore per tutte le cifre del moltiplicando. I prodotti parziali traslati vengono poi sommati per ottenere il risultato finale. In generale un moltiplicatore N × N moltiplica due numeri a N bit e produce un risultato a 2N bit. I prodotti parziali nella moltiplicazione binaria corrispondono o al moltiplicando o a tutti 0. La moltiplicazione tra numeri binari a 1 bit è equivalente a un’operazione AND, quindi vengono utilizzate porte AND per formare i prodotti parziali. Divisione La divisione binaria può essere effettuata utilizzando l’algoritmo seguente per i numeri senza segno a N bit nell’intervallo N −1 [0, 2 ] : R' = 0 language-sv for i=N-1 to 0 R = {R' =B R = R' 5.3-Sistemi di numerazione 5.3-Sistemi di numerazione I calcolatori operano sia con numeri interi sia con numeri frazionari. Esistono i numeri in virgola fissa e i numeri in virgola mobile (guarderemo solo qeusti ultimi). Numeri in virgola mobile Come la notazione scientifica, anche i numeri in virgola mobile hanno un segno, una mantissa (M ), una base (B) e un esponente (E). Il punto decimale è mobile perchè viene posizionato immediatamente a destra della cifra più significativa. I numeri in virgola mobile sono in base 2 con una mantissa binaria: vengono usati 32 bit per rappresenatare 1 bit di segno, 8 bit di esponente e 23 di mantissa. Il primo bit della mantissa è sempre uguale a 1 e quindi non ha bisogno di essere rappresentato (uno più significativo implicito), infatti solo i bit frazionari vengono riportati così da liberare un bit di dato utile. L'esponente deve essere in grado di rappresentare sia numeri positivi, sia numeri negativi. Per fare ciò si utilizza un esponente con codifica ad eccesso, costituito da l'esponente sommato ad un eccesso costante. La virgola mobile utlizza l'eccesso 127: E = 7 -> 7 + 127 = 134 = 100001102 E = −4 -> −4 + 127 = 123 = 011110112 Casi speciali 0, ±∞ e NaN Formati a precisione singola e doppia singola precisione: a 32 bit, float doppia precisione: a 64 bit, double Arrotondamento I metodi di arrotondamento sono: arrotondamento per difetto arrotondamento per eccesso arrotondamento verso lo zero arrotondamento al numero più vicino Si genera un traboccamento per eccesso (overflow) quando un numero è troppo grande per essere rappresentato. Si genera un traboccamento per difetto (underflow) quando un numero è troppo piccolo per essere rappresentato. Addizione in virgola mobile I passaggi per sommare due numeri in virgola mobile con lo stesso segno sono: 1. Estrarre i bit dell’esponente e quelli della mantissa. 2. Aggiungere l’1 più significativo per ottenere la mantissa effettiva. 3. Confrontare gli esponenti. 4. Traslare se necessario la mantissa con esponente minore. 5. Sommare le due mantisse. 6. Normalizzare la mantissa risultante sistemando, se necessario, l’esponente. 7. Arrotondare il risultato. 8. Assemblare l’esponente e la mantissa nella notazione in virgola mobile. 5.5-Componenti di memoria 5.5-Componenti di memoria Tipi di memorie I sistemi digitali hanno bisogno delle memorie per immagazzinare i dati utilizzati e generati da questi tipi di circuiti. Ci sono 3 tipi di memorie: Memoria ad accesso casuale dinamica: (DRAM) Memoria ad accesso casuale statica: (SRAM) Memoria a sola lettura: (ROM) Panoramica La memoria è organizzata come una matrice bidimensionale di celle di memoria. A ogni accesso la memoria può leggere o scrivere il contenuto di una riga della matrice. Questa riga viene specificata da un indirizzo (address). Il valore letto o scritto nella memoria viene chiamato dato (data). Un componente con un numero N di bit di indirizzo e un numero M di bit di dato possiede 2N righe e M colonne. Ogni riga di dati viene chiamata parola. componente di 4 parole x 3 bit Celle di bit I componenti di memoria vengono realizzati come matrici di celle di bit e ogni cella di dato è connessa a una linea di parola e una linea di bit. Per ogni configurazione dei bit di indirizzo, la memoria attiva una sola linea di parola che, a sua volta, attiva le celle di bit presenti nella riga corrispondente. Porte di memoria Tutte le memorie possiedono una o più porte. Ognuna di queste fornisce un accesso in lettura e/o scrittura a un indirizzo di memoria. Le memorie multi-porta possono accedere a più indirizzi nello stesso momento. Tipi di memorie Le memorie sono classificate in base a come immagazzinano i bit nella cella di bit. Memorie ad accesso casuale (RAM) Memorie a solo lettura (ROM) La RAM è una memoria volatile, ovvero perde traccia dei suoi dati una volta spenta. La ROM è una memoria non volatile, cioè trattiene i suoi dati per un tempo indefinito. Memoria ad accesso casuale dinamica La RAM dinamica (DRAM) memorizza un bit come presenza o assenza di carica in un condensatore. In caso di lettura, il valore dato viene traferito dal condensatore alla linea di bit. In caso di scrittura, il valore del dato viene trasferito dalla linea di bit al condensatore. La lettura distrugge il valore del bit, quindi la parola deve essere refreshata dopo ogni lettura. Memoria ad accesso casuale statica In una RAM statica (SRAM) i bit immagazzinati in memoria non hanno bisogno di essere ricaricati. A differenza della DRAM, se il rumore deteriora il valore del bit immagazzinato, i negatori collegati a croce lo riportano al valore di partenza. Banchi di registri I sistemi digitali utilizzano un certo numero di registri per immagazzinare variabili temporanee. Questo gruppo, chiamato banco di registri, viene solitamente costruito come una piccola componente SRAM multi-porta. Memoria a sola lettura Una memoria a sola lettura (ROM, Read Only Memory) memorizza un bit come presenza o assenza di un transistore. La Figura mostra una semplice cella di bit di una ROM. Per leggere la cella, la linea di bit viene portata debolmente TRUE. Dopodiché, viene accesa la linea di parola. Se il transistore è presente, questo spinge la linea di bit a un valore FALSE; se invece è assente, la linea di bit resta TRUE. Il contenuto di una ROM può essere indicato con la notazione a punti. La figura mostra una ROM da 4 parole x 3 bit: Un punto posto all’intersezione tra una riga (linea di parola) e una colonna (linea di bit) indica che il bit di dato è uguale a 1. Per esempio: A B Dato0 Dato1 Dato2 Y 0 0 1 1 0 011 0 1 0 1 1 110 1 0 0 0 1 100 1 1 0 1 0 010 Le ROM possono essere costruite utilizzando la logica a due livelli, con una serie di porte AND seguite da una serie di porte OR. Le porte AND producono tutti i mintermini possibili, quindi vanno a formare un decoder. Esistono diversi tipi di ROM: ROM programmabile ROM programmabile a fusibili ROM cancellabile ROM cancellabili elettricamente Reti logiche realizzate con componenti di memoria Componenti di memoria utilizzati per svolgere funzioni logiche vengono chiamati lookup table. Utilizzando una memoria per eseguire funzioni logiche, l’utente può consultare il valore di uscita corrispondente a una data combinazione di ingressi (indirizzo). Ogni indirizzo corrisponde a una riga nella tabella delle verità e ogni bit di dato corrisponde a un valore di uscita. Descrizione HDL delle memorie Nelle RAM, le scritture avvengono sul fronte di salita del clock se l'abilitazione in scrittura è attivata (we, write enable). Le letture avvengono immediatamente invece. Nelle ROM i contenuti vengono specificati nell'istruzione. H DLcase module memoria_ram #(parameter N = 6, M = 32) language-sv (input logic clk, input logic we, input logic [N-1:0] ind, input logic [M-1:0] ding, input logic [M-1:0] dusc); logic [M-1:0] mem [2**N-1:0]; always_ff @(posedge clk) if (we) mem [ind] dispositivi a bassa larghezza di banda. Dalla prospettiva della CPU: Emette comandi I /O (inviare istruzioni ai dispositivi di input/output per eseguire operazioni specifiche). Continua altre attività. Controlla l'interrupt alla fine del ciclo fetch-execute. Se riceve un interrupt: Salva e passa al livello privilegiato. Esegue il gestore dell'interrupt. Ripristina il contesto per l'istruzione successiva. Queste sono considerate operazioni atomiche dal punto di vista del sistema operativo. Data Transfers (DMA) Come eseguono i dispositivi I /O i trasferimenti dati? L'I /O basato su interrupt risolve i problemi del polling, ma: Il sistema operativo deve ancora trasferire i dati uno per uno. Il costo della gestione degli interrupt è maggiore rispetto al polling. Accesso diretto alla memoria (DM A): Un meccanismo che consente ai controller di I/O di trasferire dati direttamente alla e dalla memoria principale senza coinvolgere la CPU. Gli interrupt vengono utilizzati solo al completamento del trasferimento I/O o in caso di errore. Controller DMA La DM A è implementata con un controller specializzato Un dispositivo I/O è collegato a un controller DMA per eseguire l'operazione DM A. Più dispositivi possono essere collegati allo stesso controller. Il controller è visto come un memory-mapped I/O. Si occupa dell'arbitrato del bus e dei trasferimenti dati. Diventa il master del bus. Condivide il bus di memoria con la CPU. Trasferimento DMA: 1. La CPU configura il DMA fornendo identità, operazione, indirizzo di memoria e numero di byte da trasferire. 2. Il DMA avvia l'operazione sul dispositivo e arbitra la connessione. Trasferisce i dati dal dispositivo o dalla memoria. 3. Una volta completato il trasferimento DMA, il controller invia un'interruzione alla CPU. DMA e Gerarchia della Memoria: Senza DMA: il processore gestisce tutti i trasferimenti dati. Attraversa la traduzione degli indirizzi (M M U ). I trasferimenti possono superare i limiti delle pagine virtuali. Nessun impatto sulla gerarchia della cache. Con DMA: il controller DMA gestisce i trasferimenti dati. Aggiunge un altro percorso verso la memoria. Possibili problemi: 1. Utilizzo di indirizzi virtuali o fisici? 2. Scrittura di dati in posizioni cache? Virtual DMA: il controller DM A esegue la traduzione degli indirizzi internamente utilizzando una cache (TLB) piccola. Complesso ma flessibile. La cache riduce la latenza di accesso della CPU e libera più banda per i trasferimenti DMA, ma introduce problemi di coerenza. Soluzione: invalidare selettivamente le linee cache coinvolte nei trasferimenti DMA. Fisico DMA: il controller lavora con indirizzi fisici, DM A trasferendo dati a livello di pagina. Più semplice ma meno flessibile. Driver dei dispositivi Il file system definisce lo spazio dei nomi e le politiche di caching, è indipendente dall'hardware. Il driver del dispositivo lavora nello spazio del kernel, gestisce l'interfaccia con il controller del dispositivo, la sincronizzazione e i trasferimenti di dati. Operating Systems: Principles and Practice Topics Definizione di sistema operativo Software per gestire le risorse di un computer per gli utenti e le applicazioni Sfide dei sistemi operativi Affidabilità, sicurezza, reattività, portabilità, … Cosa è un Sistema Operativo Funzionalità Principali: Pianificazione delle risorse Memoria Virtuale Comunicazione e sincronizzazione tra processi (I P C ) Ruoli del SO Arbitro: Gestisce l'allocazione delle risorse e garantisce l'isolamento tra utenti e applicazioni. Illusionista: Creare l'illusione di risorse illimitate per ogni singola applicazione. Collante: Fornisce servizi comuni e standard per semplificare lo sviluppo delle applicazioni. Sfide dei SO Affidabilità: Il sistema fa ciò per cui è stato progettato? Disponibilità Sicurezza: Il sistema può essere compromesso da un attaccante? Privacy Portabilità: Per i programmi: Interfaccia di programmazione delle applicazioni (API) e Interfaccia astratta della macchina Per il sistema operativo: - Livello di astrazione dell'hardware Prestazioni: Latenza Quanto tempo impiega un'operazione per completarsi? Throughput Quante operazioni possono essere eseguite per unità di tempo? Overhead Quanto lavoro aggiuntivo viene svolto dal sistema operativo? Equità Quanto è equa la performance ricevuta da utenti diversi? Prevedibilità Quanto è consistente la performance nel tempo? Struttura del SO: Trade-off nella progettazione del SO: Kernel monolitico: La maggior parte delle funzionalità del SO viene eseguita all'interno del kernel. Microkernel: Nel kernel vi sono solo meccanismi centrali, la maggior parte delle funzionalità del SO viene eseguita come server a livello utente. Più affidabile grazie all'isolamento maggiore; più facile da debuggare, mantenere ed estendere. Modello ibrido: Combina le migliori pratiche dei due approcci precedenti. The Kernel Abstraction Topics Concetto di processo: Un processo è un'astrazione del SO per l'esecuzione di un programma con privilegi limitati Operazione in dual-mode: user mode vs kernel mode Kernel mode: eseguire con privilegi completi Utente mode: eseguire con meno privilegi Safe control transfer: Come passiamo da una modalità all'altra? Concetto di processo Processo: una sequenza di attività avviata da un programma, eseguita con privilegi limitati. Il Process Control Block (P CB) tiene traccia delle informazioni del processo. La tabella dei processi contiene tutti i P CB. Include thread (esecutori di istruzioni) e spazio degli indirizzi (memoria accessibile). Programma: sequenza statica di istruzioni. Processo: una sequenza di attività descritta da un programma. Più processi possono essere attivati sullo stesso programma. Il P CB è una struttura dati che contiene informazioni su un processo, come lo stato corrente, i registri della CPU, i puntatori ai thread e le risorse assegnate come memoria e file aperti. Dual-Mode Operation Nel dual-mode operation, il sistema può operare in due modalità: kernel mode: accesso completo alle risorse hardware e ai privilegi. user mode: privilegi limitati solo a quelli concessi dal kernel del sistema operativo. Protezione della memoria con indirizzi fisici basata su Base-Bound Il metodo base-bound viene utilizzato per fornire protezione alla memoria, limitando l'accesso alla memoria utilizzata da un processo Utilizza due registri, base e bound, per definire l'intervallo di memoria accessibile da un processo. Problemi con base-bound? Nessuna o limitata possibilità di espansione di heap e stack Assenza di condivisione della memoria Necessità di lavorare con indirizzi fisici -> difficile spostare la memoria Frammentazione della memoria Indirizzi Virtuali Traduzione eseguita dall'hardware, utilizzando una tabella impostata dal kernel Di solito, l'M M U si occupa della traduzione degli indirizzi Mode Switch Da user-mode a kernel-mode: Interruzioni: Scatenate da timer e dispositivi di I/O Eccezioni: Scatenate da comportamenti imprevisti del programma o comportamenti maligni Chiamate di sistema: Richiesta del programma al kernel di eseguire un'operazione per suo conto Solo un numero limitato di punti di ingresso molto attentamente codificati Chiamate anche Interruzioni Software (SW I ) Da kernel-mode a user-mode: Ritorno da interruzioni, eccezioni, chiamate di sistema Riprende l'esecuzione sospesa Avvio di un nuovo processo/nuovo thread Salto alla prima istruzione nel programma/thread Cambio di contesto del processo/thread Ripresa di un altro processo User-level upcall Notifica asincrona al programma utente Come gestire le interruzioni in modo sicuro? Vettore e stack delle interruzioni: Situato nella memoria del kernel ed è specifico per ogni processore. Mascheramento delle interruzioni: L'handler delle interruzioni viene eseguito con le interruzioni disabilitate e vengono riattivate quando l'handler completa l'operazione. Trasferimento atomico del controllo: Salva il puntatore dello stack corrente Salva il contatore del programma corrente Salva la parola di stato del processore corrente (condizioni) Passa allo stack del kernel; mette SP, PC, PSW sullo stack Passa alla modalità kernel Indirizza attraverso la tabella delle interruzioni Passa all'handler, PC e PSW del kernel L'handler dell'interruzione salva i registri che potrebbero essere sovrascritti Gestione delle interruzioni... Esecuzione trasparente e riavviabile Processi Topic Creazione e Gestione dei processi fork(), exec(), wait(), exit(),... Shell Una shell è un sistema di controllo dei processi che consente agli utenti di creare e gestire un insieme di programmi per eseguire determinati compiti. Creazione La chiamata di sistema per creare un nuovo processo coinvolge diverse fasi: Creare e inizializzare il P CB nel kernel. Creare e inizializzare un nuovo spazio degli indirizzi. Caricare il programma nello spazio degli indirizzi. Copiare gli argomenti nella memoria dello spazio degli indirizzi. Inizializzare il contesto hardware per avviare l'esecuzione dal punto di inizio specificato. Informare lo scheduler che il nuovo processo è pronto per essere eseguito. Gestione UNIX La gestione dei processi in UNIX comprende diverse chiamate di sistema: fork : crea una copia del processo corrente e lo avvia in esecuzione, senza argomenti. exec : cambia il programma in esecuzione nel processo corrente. wait : attende il completamento di un processo. signal : invia notifiche tra processi. Terminazione La terminazione di un processo in UNIX può avvenire per diverse ragioni: A causa di un'eccezione. Invocando exit. Quando un processo termina, restituisce un valore di uscita al suo processo padre: Se il padre non ha già chiamato wait , il processo terminato passa allo stato zombie. Se il processo padre è già terminato, il processo init (primo processo avviato dal kernel durante l'avvio del SO -> PID = 1) si occupa dell'attesa della terminazione dei figli. Concurrency Thread Un thread è una singola sequenza di esecuzione separata e schedulabile, utilizzata per strutturare programmi, garantire responsività, sfruttare i multi-core e interagire con dispositivi di I/O lenti. Un processo può avere uno o più thread: Programma utente single-threaded Programma utente multi-threaded Kernel multi-threaded: più thread che condividono le strutture dati del kernel, in grado di utilizzare istruzioni privilegiate. Il concetto di astrazione dei thread prevede un numero illimitato di processori, con un processore dedicato a ciascun thread. Questa disposizione consente ai thread di eseguire con velocità variabile, il che richiede che i programmi siano progettati in modo da funzionare con qualsiasi programma. L'implementazione dei thread richiede diversi elementi, tra cui il Thread Control Block (T CB), una struttura dati che memorizza informazioni sul thread. È inoltre necessario definire un insieme di operazioni sui thread e un scheduler, una funzione del sistema operativo che assegna i processori ai thread. P CB (Process Control Block): Struttura dati associata ad ogni processo. Tabella dei processi: Contiene tutti i PCB, uno per l'intero sistema nel kernel. T CB (Thread Control Block): Una per ogni thread. Tabella dei thread: Una per ogni processo (thread di livello utente), una per l'intero sistema nel kernel (thread di livello kernel). Funzioni per thread thread_create(thread, func, args) thread_yield() thread_join(thread) thread_exit(exit_status) User-level threads Gli User-level thread sono implementati attraverso una libreria a livello utente, senza coinvolgere il sistema operativo. Ogni processo contiene una tabella dei thread nello spazio utente, e lo scheduling dei thread è gestito dal RunTime Support (RT S ) del processo. I thread possono utilizzare la funzione thread_yield() per rilasciare il processore, e un'attivazione dello scheduler consente lo scheduling preemptive (Scheduler interrompe thread quando vuole). Vantaggi: Creazione, terminazione e cambio di contesto molto efficienti: non richiedono chiamate di sistema, solo chiamate alla libreria dei thread. Possono essere implementati su qualsiasi SO che non supporti il multi-threading. Limitazioni: Le sys-call bloccanti bloccano tutti i thread di livello utente di un processo. Non sfruttano le architetture multiprocessore: tutti i thread di un processo vengono pianificati sullo stesso processore. Kernel-level threads Sono gestiti direttamente dal kernel, consentendo loro di sfruttare appieno le architetture multiprocessore. Operazioni sui thread e interazioni tra i thread tramite sys- call Maggiore overhead rispetto ai thread di livello utente. Lo scheduling dei thread è implementato dal sistema operativo. I thread possono invocare chiamate di sistema bloccanti, ma solo l'invocatore viene bloccato. Thread Switch Due cause: Volontaria Dovuta a un'interruzione/eccezione. Modo volontario sia per i thread user-level sia kernel-level: Si salvano i registri Si passa al nuovo thread Si ripristinano i registri dal TCB del nuovo thread. Per interruzione: L'handler dell'interruzione salva i registri nello stack del kernel e chiama una funzione per lo switch dei thread. Altra versione: l'handler salva direttamente i registri nel T CB e riprende lo stato salvato dal TCB. Sicronizzazione Modello Globale vs Locale Nel modello globale, i processi/thread possono condividere dati attraverso variabili di memoria condivisa. Nel modello locale, invece, non vi è condivisione di dati e la cooperazione avviene attraverso lo scambio esplicito di messaggi. Global Local Sincronizzazione thread Quando più thread operano sulla stessa memoria condivisa, possono sorgere problemi di inconsistenza e concorrenza. Questa incertezza può causare comportamenti imprevisti nel programma. Definizioni Race condition: il risultato dipende dall'ordine delle operazioni tra i thread Mutua esclusione: solo un thread può eseguire una particolare operazione alla volta Sezione critica: blocco di codice eseguito da un singolo thread alla volta Lock: variabile di sincronizzazione che garantisce la mutua esclusione Acquisizione del lock prima dell'accesso alla sezione critica e rilascio dopo aver completato l'accesso ai dati condivisi Attesa dei thread se il lock è già acquisito Too much milk problem Il problema del "too much milk" è un esempio classico di race condition. Immagina due coinquilini che condividono un frigorifero e decidono di fare la spesa separatamente per comprare il latte. Entrambi i coinquilini controllano il frigorifero per vedere se c'è abbastanza latte prima di andare a comprarlo. Il problema sorge quando entrambi vedono che il latte sta finendo, quindi entrambi decidono di comprarne di più. Alla fine, quando entrambi tornano con il latte, scoprono che ora hanno troppo latte perché non si sono coordinati. Questo è il risultato di una mancanza di sincronizzazione tra i due coinquilini, che porta a una situazione indesiderata. La soluzione a questo problema sarebbe l'utilizzo di un meccanismo di mutua esclusione, come ad esempio una lock sul frigorifero. In questo modo, un coinquilino acquisirebbe il blocco prima di controllare il latte nel frigorifero e rilascerebbe il blocco solo dopo aver completato l'operazione di spesa. In questo modo, l'altro coinquilino sarebbe bloccato dall'accedere al frigorifero fino a quando il primo non avesse finito, evitando così il problema del "too much milk". Regole per Lock La lock deve essere libera inizialmente. Acquisire sempre la lock prima di accedere a dati condivisi. Rilasciare sempre la lock dopo aver finito con i dati condivisi. Mai far rilasciare la lock da qualcun altro. Mai accedere ai dati condivisi senza aver prima acquisito la lock. Semantica Mesa VS Hoare Semantica Mesa: Signal mette il thread in attesa nella lista dei pronti. Chi emette il segnale mantiene il lock e il processore. Semantica Hoare: Signal assegna il processore e il lock al thread in attesa. Quando il thread in attesa termina, il processore/lock viene restituito a chi ha emesso il segnale. Possibilità di segnali nidificati! Condition Variables Le Condition Variables consentono di sincronizzare l'accesso a dati condivisi senza dover rimanere in attesa attiva. Le operazioni principali sono: wait : rilascia atomicamente la lock e mette in attesa il thread fino a quando non viene segnalato. signal : sveglia uno dei thread in attesa, se presente. broadcast : sveglia tutti i thread in attesa, se presenti. Altre regole: Si deve SEMPRE mantenere il lock quando si chiama wait , signal , broadcast. Le condition variables non mantengono memoria: se si invia un segnale quando nessuno sta aspettando, non accade nulla. La funzione wait rilascia atomicamente il lock. Se si chiama prima wait e poi si rilascia il lock, e viceversa, il comportamento è diverso. Quando un thread viene svegliato da wait , potrebbe non essere eseguito immediatamente. Signal / broadcast mettono il thread nella lista dei pronti. Quando il lock viene rilasciato, chiunque potrebbe acquisirlo. La funzione wait DEVE essere inclusa in un ciclo while. Ciò semplifica l'implementazione sia delle variabili di condizione che dei lock. Semplifica il codice che utilizza variabili di condizione e lock. Spinlock Una Spinlock è un tipo di Lock in cui il processore aspetta in un loop che il lock diventi libero (attesa attiva!). Si presume che il lock venga tenuto per un breve periodo. Viene utilizzato per proteggere l'elenco dei processi pronti e per implementare i lock. Semafori Un semaforo ha un valore intero non negativo. P() attende in modo atomico che il valore diventi > 0, quindi lo decrementa. (Prende) V() incrementa in modo atomico il valore. (Lascia) Le strutture dati di un semaforo sono un intero e una coda. Le uniche operazioni sono P e V , e sono atomiche. Riassunto Utilizza una struttura coerente per la sincronizzazione. Utilizza sempre blocchi e variabili di condizione. Acquisisci sempre il blocco all'inizio della procedura e rilascialo alla fine. Tieni sempre il blocco quando utilizzi una variabile di condizione. Utilizza sempre un ciclo while durante l'attesa. Evita sempre l'attesa attiva nella funzione sleep(). Multi-Object Synchronization Topics Definizione di Deadlock. Condizioni per la sua comparsa. Evitare e risolvere il Deadlock (Algoritmo del Banchiere) Deadlock Risorsa: qualsiasi elemento necessario a un thread per svolgere il proprio lavoro (CPU, spazio disco, memoria, blocco). Preemptable: può essere tolto dall'OS (e successivamente restituito). Non-preemptable: deve essere rilasciato dal thread. Starvation: il thread attende indefinitamente. Deadlock: attesa circolare delle risorse. Deadlock => starvation, ma non viceversa. Condizioni per Deadlock Accesso limitato alle risorse: Un numero limitato di thread può utilizzare contemporaneamente una risorsa. Nessuna preemption Attesa con risorse in mano: Un thread detiene le risorse assegnate mentre attende un'altra. Catena circolare di richieste. Algoritmo del banchiere Stabilisce in anticipo i bisogni massimi di risorse. Assegna dinamicamente le risorse quando sono necessarie Attende se il soddisfacimento della richiesta porterebbe al deadlock. La richiesta può essere concessa se esiste un ordinamento sequenziale dei thread privo di deadlock. Definizioni Stato sicuro: Per qualsiasi sequenza possibile di future richieste di risorse, è possibile alla fine concedere tutte le richieste e quindi far terminare correttamente tutti i processi Potrebbe richiedere attesa anche quando le risorse sono disponibili! Stato non sicuro: Alcune sequenze di richieste di risorse possono risultare in un deadlock Stato condannato: Tutti i possibili calcoli portano al deadlock Esempio Concedi la richiesta solo se il risultato è uno stato sicuro La somma delle massime necessità di risorse dei thread correnti può essere maggiore delle risorse totali A condizione che ci sia un modo per far terminare tutti i thread senza finire in un deadlock Esempio: procedi solo se numero di risorse libere >= massimo rimanente che potrebbe essere necessario a questo thread per terminare Garantisce che questo thread possa terminare Ogni processo dichiara il numero di risorse di cui ha bisogno. Alla richiesta di un processo P , il banchiere verifica se l'assegnazione delle risorse mantiene uno stato sicuro. A questo scopo: Considera lo stato S raggiunto se la richiesta viene concessa. Per ogni processo calcola il requisito residuo R (il numero di risorse di cui ha ancora bisogno). Ordina i processi in base al valore crescente di R. Esegue l'algoritmo. Se alla fine tutti i processi sono contrassegnati, lo stato è sicuro. Se S è sicuro, la richiesta può essere concessa. Altrimenti, il processo P attende fino a quando non ci sono abbastanza risorse per consentirgli di procedere. Scheduling Topics Politica di pianificazione: cosa fare dopo, quando ci sono più thread pronti a essere eseguiti Politiche per un singolo processore Politiche per multiprocessori Definizioni Task/Job Richiesta dell'utente: es. clic del mouse, richiesta web, comando shell, … Latenza/tempo di risposta Quanto tempo impiega un compito per essere completato? Throughput Quanti compiti possono essere eseguiti per unità di tempo? Overhead Quanto lavoro extra viene svolto dallo scheduler? Fairness Quanto è uguale la performance ricevuta da diversi utenti? Predictability Quanto è consistente la performance nel tempo? Workload Insieme di compiti da eseguire per il sistema Scheduler preemptive Se possiamo togliere risorse da un compito in esecuzione Work-conserving La risorsa è utilizzata ogni volta che c'è un compito da eseguire Algoritmo di scheduling Prende un carico di lavoro in input e decide quali compiti fare prima Metrica di performance (throughput, latenza) in output Considerare solo gli scheduler work-conserving Politiche per un singolo processore FIFO Programma i compiti nell'ordine in cui arrivano Li continua ad eseguire finché non sono completati o rilasciano il processore Shortest Job First SJF (Shortest Job First) è un'algoritmo di scheduling che può essere non pre-emptive o pre-emptive. Non pre-emptive: viene eseguito il compito con il minor lavoro rimanente fino al termine o al rilascio del processore. Pre-emptive: viene eseguito il compito con il minor lavoro rimanente e, se si presenta un compito più breve, viene effettuato uno switch di contesto. SJF è considerato ottimale per il tempo medio di risposta, ma può causare problemi come la Starvation e la varianza nel tempo di risposta. Round Robin Round Robin è un algoritmo di scheduling in cui ogni compito ottiene una risorsa per un periodo di tempo fisso, chiamato "time quantum". Se il compito non s

Document Details

Tags

Related

Full Transcript

Upgrade to continue