Diario delle lezioni A.A. 2017-18 - Primo modulo (SC1) - Canale 1
Lunedì 25 settembre 2017 (Lezione 1 - 150 min) - Demetrescu
- Informazioni preliminari sul corso
- Astrazioni nei sistemi di calcolo e Instruction Set Architecture (ISA)
- Differenza tra linguaggio macchina e linguaggio assembly
- Pipeline di compilazione C: compilatore -> assemblatore -> linker, opzioni corrispondenti in gcc ed estensioni dei file intermedi (.c, .s, .o)
- Comando file per ispezionare il tipo di file
- Disassembler: objdump e opzione -d
- Introduzione all'ISA IA32 (x86 a 32 bit)
- Registri IA32 come contenitori per variabili: registri dati A, B, C, D, DI, SI
- Sintassi Assembly AT&T: operandi immediati ($10, $0x0F, ecc.), nomi dei registri (%eax, %ax, %al, ecc.), suffissi delle istruzioni (b, w, l, ecc.)
- Traduzione C -> Assembly IA32
- Corrispondenza tra tipi di dato C (char, short, int, ecc.) e tipi di dato macchina (Byte, Word, Long Word, ecc.)
- Istruzione di assegnamento: istruzione movimento dati MOV (=)
- Materiale aggiuntivo per la lezione
- Approfondimento: storia della famiglia CPU x86
Lunedì 2 ottobre 2017 (Lezione 2 - 150 min) - Demetrescu
- Tipologia operandi di una istruzione: immediato (solo per operando sorgente), registro, memoria
- Scrittura di file .s, direttiva .globl, etichette, commenti #
- Linking di moduli .s e moduli .c mediante gcc
- Traduzione C -> Assembly IA32
- funzioni senza parametri e valore di ritorno (per funzioni non void) nel registro A
- operatori aritmetico-logici: istruzioni INC (++), DEC (--), ADD (+), SUB (-), IMUL (*), NEG (-), AND (&), OR (|), XOR (^), NOT (~)
- esempi di traduzione di assegnamenti e calcolo di espressioni aritmetiche
- lettura dei parametri dallo stack frame del chiamante:
- stack frame: indirizzo di ritorno, System V ABI calling convention del C per passaggio parametri in stack e valore di ritorno
- convenzione su stack crescente verso il basso e indirizzi crescenti verso l'altro
- indirizzamento indiretto con registro (base) e spiazzamento: imm(reg) (es. 4(%esp))
- promozione intera nel passaggio dei parametri in C -> accesso a 32 bit ai parametri formali di tipo char e short in IA32
- Vincolo IA32: al più uno degli operandi di una istruzione può essere di tipo memoria
- Approfondimenti su rappresentazione dei numeri e operatori bit a bit:
- Operatori bit a bit e uso di maschere per operazioni su interi: esempio verifica che un numero sia pari usando operatore &
- Ottale ed esadecimale come rappresentazione compatta alternativa a quella binaria
- Materiale aggiuntivo per la lezione
- Esercizi del giorno: 1-4
Venerdì 6 ottobre 2017 (Complementi C - 90 min) - Demetrescu/Coppa
- manuali comandi: man, categorie manpages, riferimento opengroup
- Valgrind (codice esempi):
- uninitialized data: unitialized-var.c, unitialized-conditional-jump-and-ptr.c
- invalid access: invalid-heap-memory.c (use-after-free), invalid-stack-memory.c, offset-by-one-heap.c, offset-by-one-stack.c
- double free / invalid free: double-free.c, invalid-free.c
- memory leak: memory-leak.c
- Gnu Debugger (gdb)
- Concetto di debugger
- Comandi di base (sintesi, documentazione): file, run, quit, break, step, cont, next, finish, print, x, delete, info break, backtrace, frame
- Esempi (codice: somma.c, nullptr.c, sum.c
Lunedì 9 ottobre 2017 (Lezione 3 - 150 min) - Demetrescu
- Traduzione C -> Assembly IA32
- costrutti if e if ... else: trasformazione basata su goto e traduzione IA32 mediante CMP, Jcc, JMP, condition code (e, ne, l, le, g, ge, b, be, a, ae)
- esercizi svolti: calcolo del valore assoluto di un intero e calcolo del minimo di due numeri
- registro EFLAGS, cenni ai flag ZF, SF, OF, CF, cenni alla relazione con i condition code, nozione di side-effect sui flag delle operazioni aritmetico logiche, CMP S, D come calcolo della differenza D-S
- iterazione: costrutti while e for
- esercizi svolti: calcolo della somma dei primi n numeri, calcolo del fattoriale
- uso del debugger gdb per l'analisi di programmi misti C/assembly IA32 (compilazione con gcc -m32 -g e uso del comando gdb go)
- Materiale aggiuntivo per la lezione
- Esercizi del giorno: 5
Venerdì 13 ottobre 2017 (Lezione 4 - 90 min) - Demetrescu/Coppa
- Traduzione programmi C -> assembly IA32 (sintassi AT&T)
- indirizzi di memoria: modello a 32 e 64 bit, word size
- tipi puntatore -> IA32 Double Word
- array e aritmetica dei puntatori -> indirizzamento a memoria con base, indice e scala (es. (%eax, %ecx, 4))
- esempi: modifica di un intero passato per indirizzo (valore assoluto), modifica dell'i-esimo elemento di un array di int, short e char, con i costante e variabile, swap di due oggetti in memoria
- Materiale aggiuntivo per la lezione
- Esercizi del giorno: 6-15
Lunedì 16 ottobre 2017 (Lezione 5 - 150 min) - Demetrescu
- Traduzione programmi C -> assembly IA32 (sintassi AT&T)
- esercizi svolti: funzione che verifica l'uguaglianza di due stringhe C
- conversioni di tipo intero (type cast) -> istruzioni MOVZ e MOVS
- calling convention System V: registri callee-save e caller save, istruzioni PUSH, POP (semantica e uso)
- chiamata e ritorno da funzione -> istruzioni CALL e RET (semantica e uso)
- passaggio dei parametri -> allocazione della memoria nello stack frame
- Materiale aggiuntivo per la lezione
Venerdì 20 ottobre 2017 (Lezione 6 - 90 min) - Demetrescu/Coppa
- Traduzione programmi C -> assembly IA32 (sintassi AT&T)
- variabili locali -> allocazione della memoria nello stack frame
- istruzione LEA per il calcolo di indirizzi ed espressioni: esempio del calcolo di indirizzi di variabili locali in stack e calcolo di espressioni aritmetiche
- espressioni booleane -> istruzione SETcc
- Consultazione del manuale Intel (ISA, Volume 2: Instruction Set Reference)
- Materiale aggiuntivo per la lezione
- Esercizi del giorno: 16-17
Lunedì 23 ottobre 2017 (Lezione 7 - 150 min) - Demetrescu
- Complementi sull'istruction set IA32:
- Vincoli istruzioni IA32
- assegnamento condizionato con istruzione CMOV: esempio del calcolo del massimo tra due numeri
- istruzione XOR per azzerare un registro
- istruzione TEST per confrontare un registro con zero
- shift logico SHL/SHR ed aritmetico SAL/SAR: applicazione su rappresentazioni con e senza segno, moltiplicazione e divisione intera per 2^S
- esercizi svolti
- Ordine dei byte in memoria (endianness): esempi di accesso a singoli byte/word in un dato memorizzato
- Materiale aggiuntivo per la lezione
Lunedì 30 ottobre 2017 (Lezione 8 - 150 min) - Demetrescu
- Introduzione all'ottimizzazione dei programmi
- metriche prestazionali classiche: tempo di esecuzione (tempo reale, cicli di clock) e spazio di memoria richiesto (byte allocati)
- efficienza prestazionale come moneta per pagare altre qualità del software (affidabilità, usabilità, manutenibilità, portabilità, modularità, ecc.)
- ottimizzazioni del programmatore (algoritmo e codice) e del compilatore (codice)
- Profilazione delle prestazioni: uso di time e gprof
- Esempi di misurazione dei tempi con time ed impatto delle ottimizzazioni dei compilatori: -O0 (o nulla), -O1, -O2
- Tipologia di ottimizzazione: riduzione del work (numero di istruzioni eseguite) di un programma
- ottimizzazioni di espressioni e logica del programma
- constant folding (CF), constant propagation (CP), common subexpression elimination (CSE), dead code elimination (DCE)
- principio della cortocircuitazione: operatori || e && in C, esempio della ricerca sequenziale
- identità algebriche per semplificare espressioni logiche complesse: verifica modulo vettore minore di soglia senza fare ricorso a sqrt
- ottimizzazioni dei loop
- loop-invariant code motion (loop hoisting)
- uso delle sentinelle: ricerca di un elemento in un array
- ottimizzazioni delle funzioni
- inlining: tecnica base e trade-off sul numero di istruzioni nel chiamato, inlining come enabler di altre ottimizzazioni
- modifiche alle strutture dati per ottimizzare operazioni frequenti costose:
- principio dell'augmentation: esempio dell'inserimento in coda in una lista collegata, calcolo della lunghezza di una lista collegata
- precomputation: esempio di lookup su tabella per verificare se un carattere è una consonante
- Materiale aggiuntivo per la lezione
Venerdì 03 novembre 2017 (Lezione 9 - 100 min) - Demetrescu
Lunedì 06 novembre 2017 (Lezione 10 - 150 min) - Demetrescu
- Legge di Amdahl
- Esercizio sull'uso della precomputation: calcolo dell'i-esimo numero primo
- Sistema operativo come:
- ambiente per consentire l'utilizzo del calcolatore da parte degli utenti
- ambiente di esecuzione per i programmi, fornendo risorse e servizi
- Panoramica sui servizi principali forniti da un sistema operativo (discussione di alto livello):
- gestione della CPU
- gestione della memoria
- gestione dei dispositivi di I/O
- sicurezza e protezione
- controllo delle prestazioni, gestione utenti, gestione degli errori
- Interfaccia del sistema operativo:
- verso l'utente:
- interfaccia dei comandi
- per esplorare/manipolare il file system (es. ls, cp, mv, ecc.)
- per esplorare/manipolare programmi (es. shell bash, ps)
- per impostare permessi, ecc.
- desktop environment e server grafico (es. X, gnome, KDE), cenni
- verso i programmi:
- passaggio dei parametri a un programma C: argc/argv
- stato di terminazione di un processo: exit(), return della funzione main, accesso allo stato di terminazione nella shell con $?
- variabili di ambiente:
- accesso da shell: comando env, assegnamento VAR=VALUE, stampa con echo $VAR
- accesso da programma: getenv, setenv, variabile environ
- variabile PATH: concatenazione della directory locale . al PATH
- altri esempi di variabili: PWD, USER, PS1
- variabili di ambiente come strumento di comunicazione monodirezionale tra processo genitore e processo figlio
- Materiale aggiuntivo per la lezione
Lunedì 13 novembre 2017 (Lezione 11 - 150 min) - Demetrescu
- POSIX come standard per:
- API (libc, system call)
- file system (nomi speciali file, alcuni aspetti della struttura delle directory ref)
- tool di sistema (coreutils)
- shell e shell scripting
- espressioni regolari
- variabili di ambiente
- Nozione di file system: struttura ad albero, root, home, path assoluti e relativi, file "." e "..", "~", case-sensitivity, file nascosti, cenni a struttura standard per il file system FHS [ref], man hier, comando tree
- Complementi sulla shell:
- definizioni export di variabili di ambiente
- file configurazione bash: .bashrc
- comandi built-in vs. esterni:
- comando built-in type
- comando esterno which (cerca eseguibile in PATH)
- Gestione dei file e degli canali di I/O:
- visione utente:
- comandi built-in nella shell: cd, pwd,
- comandi esterni (coreutils): ls, cp, rm, mv, mkdir
- redirezione su file canali standard >
- pipe (esempio: cat file | grep parola)
- visione programmatore:
- libc: FILE*, stdin, stdout, stderr, printf, fprintf
- system call: file descriptor (canali 0, 1, 2), esempio write
- uso comando man (man man per uso documentazione) e sezioni (1, 2, 3, ecc.), esempio man open, man 2 open
- gestione degli errori:
- errno, perror
- esempio: read su canale non valido
- Librerie utente vs. system call
- comando strace su hello world
- system call wrapper e invocazione diretta di una system call: istruzione IA32 INT, invocazione di system call (INT 0x80, passaggio dei parametri) [ref], man syscall (Architecture calling conventions)
- compilazione programma senza libc: gcc -m32 -nostdlib
Venerdì 17 novembre 2017 (Lezione 12 - 100 min) - Demetrescu
- Dall'eseguibile al processo:
- process control block e risorse associate ai processi: PID, registri, PID processo genitore, puntatori alla memoria, privilegi del processo, accounting (tempo speso dal processo, limiti, ecc.), priorità dello scheduling, risorse I/O (file aperti ecc.)
- loader e anatomia dello spazio logico di un processo:
- code, data, heap, librerie dinamiche, stack
- caso di studio Linux/x86: ispezione immagine di un processo mediante /proc/pid/maps [man proc]
- Flusso del controllo normale ed eccezionale: [ref1, ref2]
- eccezioni recuperabili e non recuperabili
- eccezioni sincrone (interne):
- trap: istruzione IA32 INT
- fault: es. divisione per zero
- abort: es. parity error
- eccezioni asincrone (esterne):
- interrupt: dispositivi I/O, timer, ecc.
- tabella delle eccezioni (interrupt vector)
- cenni alla tabella delle eccezioni IA32
Lunedì 20 novembre 2017 (Lezione 13 - 150 min) - Demetrescu
- Esecuzione dei processi:
- esecuzione in modalità utente (user) e in modalità supervisore (kernel)
- stati di un processo: ready, running user, running kernel, waiting (diagramma degli stati in Linux)
- multiprogrammazione e scheduling dei processi: [ref]
- context switch: salvataggio dello stato della CPU nel PCB
- esempio del time sharing round-robin mediante timer e interrupt
- cenni allo scheduling con priorità
- albero dei processi
- terminazione dei processi con kill -9
- system call per il controllo dei processi:
- getpid(), getppid()
- creazione (fork, exec)
- terminazione (exit)
- attesa terminazione (wait)
- processi zombie
- Materiale aggiuntivo per la lezione
Venerdì 24 novembre 2017 (Lezione 14 - 100 min) - Demetrescu
- Esempi uso system call:
- fork: effetto clonazione memoria tra padre e figlio
- exit: differenza tra exit e _exit
- fork+exec: implementazione di una rudimentale shell (versione 1, versione 2)
- Meccanismo dei segnali:
- principi, segnali POSIX più comuni: man 7 signal [rif1, rif2]
- invio di un segnale con il comando kill: man 1 kill, kill -l
- invio di un segnale con la funzione POSIX kill: man 2 kill, esempio programma kamikaze
- gestore di un segnale:
- installazione gestore con signal: man signal, esempio gestore SIGINT
- installazione gestore con sigaction: man sigaction, esempio gestore SIGINT
- Materiale aggiuntivo per la lezione
Lunedì 27 novembre 2017 (Lezione 15 - 150 min)
- Creazione di processi:
- Effetto arrivo segnale su esecuzione system call: esempio con pause e installazione gestore SIGINT
- Gestione dei permessi:
- permessi sulle risorse (rwx)
- visione utente: chmod (ottale)
- Gestione dei file:
- system call open, read, write e close
- esempio: realizzazione comando cat
- operazioni di I/O interrotte da segnali, gestione errore EINTR su read interrotta prima di leggere almeno un byte
- Esercizi: implementazione di una semplice shell con uno o più comandi e supporto di comandi interni
- Materiale aggiuntivo per la lezione
Venerdì 1 dicembre 2017 (Lezione 16 - 100 min) - Demetrescu
- Complementi sui segnali:
- processo kamikaze (esempio)
- ignorare segnale con sigaction: SIG_IGN, ripristino default con SIG_DFL
- segnale SIGCHLD
- Esecuzione programmi sulla CPU:
- ciclo fetch-decode-execute
- architetture superscalari, pipelining, hazard e stalli, branch prediction
- aspetti prestazionali: clock e frequenza del processore, IPC e CPI
- ottimizzazioni del codice sfruttando la pipeline: istruzioni branchless, instruction scheduling
Lunedì 4 dicembre 2017 (Lezione 17 - 90 min)
- Esecuzione programmi sulla CPU:
- evoluzione negli ultimi decenni: legge di Moore, crescita esponenziale numero transistor, avvento delle architetture multicore
- cenni ad esecuzione parallela: CPU multicore e instruction-level parallelism (es. AVX, pipelining)
- cenni ad architetture CISC e RISC
- Come è strutturata la memoria? (parte I) [ref1, ref2]
- astrazione con modello lineare
- transazioni di lettura e scrittura: configurazione del bus, trasferimenti da CPU a memoria e viceversa
- divario tra velocità CPU (cycle time) e velocità accesso a memoria, evoluzione del trend
- principio di località, località spaziale e temporale
- cache come buffer per compensare divario tra velocità di processamento e velocità di accesso ai dati sfruttando il principio di località
- partizionamento in blocchi, dimensione blocco (linea di cache), cache hit e cache miss, cenni a strategia di replacement
- esempi di analisi: somma degli elementi di un array, prodotto di matrice, scansione lineare di un array vs. lista collegata
Lunedì 11 dicembre 2017 (Lezione 18 - 150 min)
- Come è strutturata la memoria? (parte II) [ref1, ref2]
- gerarchie di memoria:
- registri, cache L1 (D+I), L2, L3, memoria, disco
- trasferimento dati a blocchi tra livelli successivi di una memoria gerarchica
- analisi di costo/dimensione/velocità dei livelli di una memoria gerarchica
- caso di studio: Intel Core i7, gerarchia di memoria (L1i, L1d, L2, L3, DDR3) [ref1][ref2]
- ottimizzazioni del codice nell'uso della memoria:
- allineamento e padding:
- stack frame a 16 byte prima di una call
- allineamento dei campi delle struct: riordinare le struct per ridurre il padding [rif]
- Come viene gestita la memoria? [ref1, ref2]
- memoria fisica (gestita dal sistema operativo) e memoria virtuale (visibile ai processi)
- allocazione dinamica della memoria
- frammentazione interna ed esterna
- qualità di un allocatore: tempo e spazio
- cenni ad implementazione di un allocatore: malloc/free, sbrk(2)
- allocazione nella memoria fisica: memoria virtuale
- mapping tra indirizzi virtuali e indirizzi fisici: MMU
Venerdì 1 dicembre 2017 (Lezione 19 - 100 min) - Demetrescu
- Panoramica sui vari allocatori presenti in un sistema di calcolo:
- allocazione dello spazio ai vari processi da parte del kernel
- allocazione dello spazio a un singolo processo da parte dell'allocatore libc
- Allocazione nella memoria fisica: memoria virtuale
- limiti dei sistemi con accesso diretto alla memoria fisica: frammentazione esterna
- paginazione
- frammentazione interna nelle pagine
- come avviene il mapping degli indirizzi logici su quelli fisici?
- paginazione con bit di validità
- condivisione di pagine, es. librerie dinamiche
- page fault memoria virtuale e loro gestione, protection fault (SIGSEGV)
Lunedì 18 dicembre 2017 (Lezione 20 - 150 min)
Venerdì 22 dicembre 2017 (Lezione 21 - 100 min) - Demetrescu
Page was generated in 0.0742 seconds
