Elementi di architettura e sistemi operativi (2012/2013)

Codice insegnamento
4S02717
Crediti
12
Coordinatore
Tiziano Villa
Settore disciplinare
ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Lingua di erogazione
Italiano
L'insegnamento è organizzato come segue:
Attività Crediti Periodo Docenti Orario
Teoria 9 I semestre Tiziano Villa
Laboratorio 3 II semestre Davide Bresolin

Orario lezioni

I semestre
Attività Giorno Ora Tipo Luogo Note
Teoria mercoledì 14.30 - 16.30 lezione Aula D  
Teoria giovedì 14.30 - 16.30 lezione Aula D  
Teoria venerdì 11.30 - 13.30 lezione Aula D  
II semestre
Attività Giorno Ora Tipo Luogo Note
Laboratorio martedì 9.30 - 11.30 lezione Laboratorio didattico Gamma  
Laboratorio mercoledì 10.30 - 13.30 laboratorio Laboratorio didattico Alfa  

Obiettivi formativi

Modulo:
-------

Architettura dei calcolatori.
Il corso si propone di dare allo studente la conoscenza necessaria alla realizzazione in forma digitale di un algoritmo presentando le possibili alternative comprese tra l'utilizzo di un processore universale e la costruzione di un dispositivo digitale dedicato.
Queste conoscenze costituiscono i prerequisiti necessari alla comprensione dei meccanismi di funzionamento di un sistema informativo e del processo di traduzione di un programma da una sua descrizione ad alto livello sino a una realizzazione cablata o a codice macchina che esegue su un processore.

Sistemi operativi.
Lo scopo del corso e' di presentare l'organizzazione di un sistema operativo e le problematiche connesse di correttezza ed efficienza. Saranno trattati i seguenti argomenti:
definizione e storia dei sistemi operativi e di programmazione;
programmi di utilita', sottosistemi, sistemi a multiprogrammazione;
processi, comunicazione tra processi e sincronizzazione;
allocazione della memoria, segmentazione e impaginazione;
caricamento e collegamento, librerie;
allocazione delle risorse, schedulazione, valutazione delle prestazioni;
sistemi d'ingresso e uscita, dispositivi di memorizzazione, organizzazione degli archivi.

Programma

Modulo:
-------

Introduzione all'architettura degli elaboratori.
Realizzazione di funzioni logiche elementari con circuiti a interruttore e porte logiche CMOS.
Tipologie di circuiti: digitali e analogici; combinatori e sequenziali; sequenziali sincroni e asincroni.

Introduzione alla logica combinatoria.
Assiomi e teoremi dell'algebra di Boole.
Riscrittura di espressioni con le regole dell'algebra di Boole.

Forme normali congiuntive e disgiuntive.
Funzioni incompletamente specificate.
Ipercubi Booleani e mappe di Karnaugh.

Minimizzazione logica usando le mappe di Karnaugh.
Implicanti, primi ed essenziali.
Calcolo degl'implicanti primi di funzioni a una o piu' uscite.
Minimizzazione esatta con il metodo di Quine-McCluskey.

Ritardi nei circuiti combinatori e circuiti oscillatori.
Logica regolare e programmabile per circuiti combinatori.
Matrici logiche programmabili con piani AND e/o OR flessibili (PLA, PAL, ROM).
Selettori e deselettori.

Progettazione di circuiti combinatori dalla specifica in linguaggio naturale alla realizzazione in una tecnologia data.
Linguaggi di descrizione dei sistemi elettronici.

Aritmetica binaria con numeri negativi.
Condizioni di trabocco in complemento a due.

Addizionatori a propagazione di riporto, ad anticipo di riporto, a selezione di riporto.
Addizionatore binario modulo e segno e addizionatore di numeri in codifica BCD.
Sottrattore binario.
Unita' aritmetico-logica.

Introduzione alla logica a piu' livelli.
Conversione tra AND/OR, OR/AND e NAND, NOR.

Introduzione ai circuiti sequenziali.
Lucchetto ("latch").
Cella di memoria statica con coppia ad anello d'invertitori.
Cella di memoria SR con coppia di porte NOR (o NAND) incrociate.
Cella di memoria SR con segnale d'abilitazione.

Cella di memoria SR campionata in discesa mastro-servo ("master-slave").
Problema della memorizzazione degli uni spuri.
Bistabili ("flip-flop").
Bistabile D campionato in discesa mastro-servo.
Bistabile JK campionato in discesa mastro-servo.
Bistabile D campionato in discesa o salita.
Metodologie di temporarizzazione sincrona.
Metastabilita' e ingressi asincroni.

Registri di base. Registri a scorrimento. Contatori.
Analisi di registri a scorrimento e contatori dallo schema logico al grafo degli stati.
Sintesi di registri a scorrimento e contatori dal grafo degli stati allo schema logico.

Analisi e sintesi di macchine a stati finiti.
Macchine di Moore, Mealy, Mealy sincronizzate.
Trasformazione da macchine di Moore a macchine di Moore temporizzate.
Confronto tra macchine di Moore temporizzate e macchine di Mealy sincronizzate.

Minimizzazione degli stati di macchine a stati finiti.
Impatto della minimizzazione degli stati sulla minimizzazione logica.

Codifica degli stati di macchine a stati finiti.
Codifica degli stati basata sulle uscite.

Progettazione di circuiti sequenziali dalla specifica,
alla macchina a stati finiti, alla rappresentazione logica minimizzata.
Relazioni tra i percorsi critici e la frequenza/periodo di un circuito sequenziale.

Architettura di un processore.
Unita' di controllo e unita' esecutiva.
Ciclo di prelievo-decodifica-esecuzione di un'istruzione.
Tipi d'istruzioni. Registri fondamentali.

Protocollo a 4 fasi d'interazione con la memoria.
Interazione con le unita' d'ingresso-uscita.
Schemi d'interconnessione dell'unita' esecutiva.
Schematico di un'unita' esecutiva MIPS elementare che realizza un sottoinsieme minimale d'istruzioni macchina.

Cicli di esecuzione delle operazioni di somma tra registri,
lettura/scrittura da/a memoria, salto (macchina di Mealy sincrona).
Micro-operazioni per eseguire le istruzioni RTL e dipendenza dallo schema d'interconnessione.
Tempistica delle transizioni di stato e delle micro-operazioni (operazioni immediate e operazioni ritardate).

Realizzazione dell'unita' di controllo di Moore con una ROM o PLA.
Tempistica interfaccia memoria-registri.
Microprogrammazione orizzontale e verticale.

Macchine a stati finite estese.
Progettazione di processori dedicati: esempio del processore che realizza l'algoritmo di Euclide del Massimo Comun Divisore.


Introduzione ai sistemi operativi.
Cronistoria dei sistemi di calcolo e dei sistemi operativi:
- da ENIAC fino ai sistemi distribuiti fine anni 80;
- da Internet fine anni 80 fino alla nuvola e ai sistemi mobili odierni.

Funzioni del sistema operativo: l'esempio di protezione della memoria con traduzione degl'indirizzi e modalita' nucleo-utente.
Multiprogrammazione, concorrenza e spazi d'indirizzamento.

Processi e flussi esecutivi ("threads") come meccanismi di gestione della protezione della memoria e della concorrenza.
Stati di un processo, code degli stati di un processo, cambiamenti di stato.
Esempio di gestione con la pila ("stack") delle chiamate a procedura.

Chiamate principali di sistema per gestire la creazione, esecuzione, interruzione, commutazione di contesto, duplicazione ("fork") e confluenza ("join"), terminazione di flussi esecutivi ("threads").
Eventi interni ed esterni per l'interruzione volontaria o la prelazione.
Interruzioni.
Gestione dei flussi esecutivi in modalita' sistema operativo oppure utente.
Multiprogrammazione.

Introduzione alla concorrenza.
Gestione di servizi di rete con gruppi di flussi esecutivi di servizio ("threaded web server").
Programmazione di servizi di rete di tipo ATM con gestione ad eventi.
Analisi di un esempio paradigmatico di agenti concorrenti rispetto a una sezione critica.

Il problema dell'attesa attiva.
Definizione di sezioni critiche mediante la disabilitazione/riabilitazione delle interruzioni.
Disabilitazione delle interruzioni durante la sezione critica o durante l'acquisizione e rilascio dei lucchetti.
Istruzioni macchina atomiche per lettura-modifica-scrittura e loro uso per definire sezioni critiche.

I semafori. Il problema produttori-consumatori con i semafori.

I monitor.
Gestione di una coda infinita con i monitor.
Il problema dei lettori-scrittori con i monitor.
Confronto tra monitor e semafori.
Gestione di una lista con l'istruzione atomica compare-and-swap.

Contesa sulle risorse e stallo.
Algoritmo per rilevare lo stallo.
Algoritmo del banchiere per evitare uno stallo.

Schedulazione di processi.
Algoritmi FIFO, RR, minimo tempo di completamento senza e con prelazione, lotteria.
Schedulazione con piu' code di priorita'.
Valutazione degli algoritmi di schedulazione.

Gestione della memoria principale.
Schemi di traduzione degl'indirizzi da virtuali a fisici:
rilocazione, segmentazione semplice, multi-segmentazione, impaginazione, multi-livello: segmentazione + impaginazione, impaginazione a due livelli, tavola inversa.
Ruolo del sistema operativo nella traduzione degl'indirizzi.
Formato di un elemento nella tavola delle pagine.

Introduzione al concetto di cache e gerarchia della memoria come gerarchia di cache a piu' livelli.
Cache a indirizzamento diretto, associativo a piu' vie, completamento associativo.

TLB come cache delle traduzioni degl'indirizzi da virtuali a fisici.
Gestione dell'insuccesso nell'accesso a una TLB.
Organizzazione della TLB, e accesso in parallelo alla TLB e cache dei dati.
Memoria virtuale e impaginazione su richiesta.
Meccanismo dell'impaginazione su richiesta e gestione di una mancanza di pagina. Eccezioni trasparenti e precise.

Politiche di rimpiazzo della pagine: FIFO, MIN, LRU, casuale.
Anomalia di Belady.
Algoritmo dell'orologio e della seconda scelta.
Saturazione del sistema per il sovraccarico di accessi in memoria
("thrashing"). Insieme di lavoro.

Cenni ai dispositivi d'ingresso-uscita.
Il disco rigido: caratteristiche e prestazioni. Schedulazione delle richieste del disco.

Organizzazione degli archivi di documenti ("file systems"); nomi e strutture dati di memorizzazione e ricerca.

Modalità d'esame

Modulo:
-------

Le competenze sono verificate con una prova scritta di teoria e una prova scritta e/o pratica di laboratorio; il voto della prima contribuisce per i 3/4 del voto finale e quello della seconda per 1/4.
L'esame deve essere completato (teoria+laboratorio) entro l'inizio dell'anno accademico successivo a quello in cui e' stato erogato il corso ed e' stata sostenuta con successo la prova di teoria o la prova di laboratorio (a seconda di quale delle due e' stata superata per prima).

Testi di riferimento
Attività Autore Titolo Casa editrice Anno ISBN Note
Teoria R.Katz, G.Borriello Contemporary logic design (Edizione 2) Pearson Education International 2005 0-13-127830-4 Consigliato
Teoria Y.N. Patt, S.J. Patel Introduction to Computing Systems (Edizione 2) McGrawHill 2004 978-0-07-246750-5 Laboratorio
Teoria Franco Fummi, Mariagiovanna Sami, Cristina Silvano Progettazione Digitale (Edizione 2) McGraw-Hill 2007 8838663521 Ufficiale
Teoria A. Silberschatz - P.B. Galvin - G. Gagne Sistemi Operativi. Concetti ed esempi. (Edizione 8) Pearson Paravia Bruno Mondadori 2009 978-88-7192-569-1 Ufficiale
Materiale didattico
Titolo Formato (Lingua, Dimensione, Data pubblicazione)
Architettura - Cap. 1-10 Borriello-Katz  x-gzipx-gzip (en, 745 KB, 18/11/12)
Architettura - Cap. 11 CLD Katz  zipzip (en, 110 KB, 18/11/12)
Architettura - Cap. 12 CLD Katz  zipzip (en, 174 KB, 18/11/12)
Architettura - Lezioni Katz  x-gzipx-gzip (it, 1061 KB, 05/12/12)
Architettura - Lezioni Vahid  x-gzipx-gzip (en, 291 KB, 18/11/12)
Lezioni UCB Sistemi Operativi  pdfpdf (en, 9620 KB, 12/12/12)
XX-TV Temi d'esame  x-gzipx-gzip (it, 1030 KB, 07/10/12)
Introduzione al Laboratorio  pdfpdf (it, 65 KB, 04/03/13)
Lab 01 - Esercizi  pdfpdf (it, 35 KB, 12/03/13)
Lab 01 - Introduzione alla Shell  pdfpdf (it, 222 KB, 04/03/13)
Lab 02 - Comandi avanzati della Shell  pdfpdf (it, 85 KB, 05/03/13)
Lab 02 - Esercizi  pdfpdf (it, 53 KB, 12/03/13)
Lab 03 - Esercizi  pdfpdf (it, 45 KB, 12/03/13)
Lab 03 - Redirezione dell'I/O  pdfpdf (it, 66 KB, 12/03/13)
Lab 04 - Esercizi  pdfpdf (it, 52 KB, 13/03/13)
Lab 04 - Programmazione della Shell  pdfpdf (it, 88 KB, 13/03/13)
Lab 05 - Compitino  pdfpdf (it, 54 KB, 22/03/13)
Lab 05 - Controllo del flusso  pdfpdf (it, 95 KB, 20/03/13)
Lab 06 - Esercizi  pdfpdf (it, 46 KB, 27/03/13)
Lab 06 - Introduzione al C  pdfpdf (it, 180 KB, 26/03/13)
Lab 07 - Compitino del 27/03  pdfpdf (it, 53 KB, 27/03/13)
Lab 07 - I/O Avanzato in C  pdfpdf (it, 109 KB, 27/03/13)
Lab 08 - Compitino del 3 Aprile  pdfpdf (it, 53 KB, 05/04/13)
Lab 08 - Le funzioni in C  pdfpdf (it, 442 KB, 03/04/13)
Lab 09 - I File  pdfpdf (it, 59 KB, 09/04/13)
Lab 10 - I file parte seconda  pdfpdf (it, 56 KB, 10/04/13)
Lab 11 - Esercizi  pdfpdf (it, 46 KB, 17/04/13)
Lab 11 - I Puntatori  pdfpdf (it, 152 KB, 16/04/13)
Lab 12 - Allocazione dinamica della memoria  pdfpdf (it, 181 KB, 17/04/13)
Lab 13 - Codice per la gestione delle liste  zipzip (it, 0 KB, 07/05/13)
Lab 13 - Strutture dati dinamiche  pdfpdf (it, 129 KB, 07/05/13)
Lab 14 - Compitino dell'8 Maggio  pdfpdf (it, 53 KB, 09/05/13)
Lab 14 - Librerie e compilazione separata  pdfpdf (it, 326 KB, 08/05/13)
Lab 15 - Compitino del 14 Maggio  pdfpdf (it, 53 KB, 15/05/13)
Lab 15 - Makefile  pdfpdf (it, 87 KB, 14/05/13)
Lab 16 - Introduzione all'architettura LC-3  pdfpdf (it, 1009 KB, 15/05/13)
Lab 17 - Compitino del 22 Maggio  pdfpdf (it, 59 KB, 22/05/13)
Lab 17 - Indirizzamento della memoria nell'LC-3  pdfpdf (it, 738 KB, 22/05/13)
Laboratorio: Modalità d'Esame  pdfpdf (it, 56 KB, 28/05/13)
Riepilogo Finale Risultati Compitini  pdfpdf (it, 37 KB, 05/06/13)
Soluzioni del Compitino del 10 Aprile  pdfpdf (it, 58 KB, 07/05/13)
Soluzioni del Compitino del 13 Marzo  pdfpdf (it, 72 KB, 22/03/13)
Soluzioni del Compitino del 14 Maggio  pdfpdf (it, 72 KB, 28/05/13)
Soluzioni del Compitino del 17 Aprile  pdfpdf (it, 102 KB, 22/05/13)
Soluzioni del Compitino del 20 Marzo  pdfpdf (it, 60 KB, 28/03/13)
Soluzioni del Compitino del 22 Maggio  pdfpdf (it, 52 KB, 28/05/13)
Soluzioni del Compitino del 27 Marzo  pdfpdf (it, 39 KB, 05/04/13)
Soluzioni del Compitino del 3 Aprile  pdfpdf (it, 57 KB, 07/05/13)
Soluzioni del Compitino del 6 Marzo  pdfpdf (it, 60 KB, 13/03/13)
Soluzioni del Compitino del 8 Maggio  pdfpdf (it, 77 KB, 28/05/13)

Statistiche per i requisiti di trasparenza (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

I dati relativi all'AA 2012/2013 non sono ancora disponibili