Diario delle lezioni A.A. 2017-18 - Primo modulo (SC1) - Canale 2

Giovedì 28 settembre 2017 (Lezione 1 - 150 min) - Coppa

• 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: preprocessore -> compilatore -> assemblatore -> linker, opzioni corrispondenti in gcc ed estensioni dei file intermedi (.c, .i,.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: comandi shell relativi alla pipeline di compilazione C (Camil Demetrescu, Canale 1)
• Approfondimento: storia della famiglia CPU x86

Giovedì 5 ottobre 2017 (Lezione 2 - 150 min) - Coppa

• 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))
• 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 (Bit Twiddling Hacks): esempio verifica che un numero sia pari usando operatore &
  • Esadecimale come rappresentazione compatta alternativa a quella binaria
• Materiale aggiuntivo per la lezione
• Esercizi del giorno: 1-4

Giovedì 12 ottobre 2017 (Lezione 3 - 150 min) - Coppa

• 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 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

Martedì 17 ottobre 2017 (Lezioni 4 - 90 min) - Demetrescu

• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • promozione intera nel passaggio dei parametri in C -> accesso a 32 bit ai parametri formali di tipo char e short in IA32
  • 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, modifica dell'i-esimo elemento di un array di int, short e char, con i costante e variabile, swap di due oggetti in memoria, somma degli elementi di un array di int
• Materiale aggiuntivo per la lezione
• Esercizi del giorno: 6-15

Giovedì 19 ottobre 2017 (Lezione 5 - 150 min) - Coppa

• 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

Martedì 24 ottobre 2017 (Lezione 6 - 90 min) - 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

Giovedì 26 ottobre 2017 (Lezione 7 - 150 min) - Coppa

• 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
  • Comandi GDB: go, step (s), next (n), finish (f), continue (c)
• Ordine dei byte in memoria (endianness): esempi di accesso a singoli byte/word in un dato memorizzato
• Materiale aggiuntivo per la lezione

Venerdì 3 novembre 2017 (Lezione 8 - 150 min) - Coppa

• 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

Martedì 7 novembre 2017 (Lezione 9 - 100 min) - Coppa/Demetrescu

• Esercizi ottimizzazione
• Materiale aggiuntivo per la lezione

Giovedì 9 novembre 2017 (Lezione 10 - 150 min) - Coppa

• 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

Giovedì 16 novembre 2017 (Lezione 11 - 150 min) - Coppa

• 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, touch
    • 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 write
    • 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)
• Materiale aggiuntivo per la lezione

Martedì 21 novembre 2017 (Lezione 12 - 100 min) - Coppa

• 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
• esecuzione in modalità utente (user) e in modalità supervisore (kernel)
• Materiale aggiuntivo per la lezione

Giovedì 23 novembre 2017 (Lezione 13 - 150 min) - Coppa

• Esecuzione dei processi:
  • 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: comando pstree
  • 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

Martedì 28 novembre 2017 (Lezione 14 - 100 min) - Coppa

• 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
    • ignorare segnale con sigaction: SIG_IGN, esempio
    • gestione del segnale SIGCHLD ed effetto arrivo segnale su esecuzione system call: esempio con sleep e fork
• Materiale aggiuntivo per la lezione

Giovedì 30 novembre 2017 (Lezione 15 - 150 min) - Coppa

• Segnali:
  • gestione del segnale SIGCHLD ed effetto arrivo segnale su esecuzione system call: esempio con sleep e fork
  • 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

Martedì 4 dicembre 2017 (Lezione 16 - 100 min) - Coppa

• 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
  • cenni ad esecuzione parallela: CPU multicore e instruction-level parallelism (es. AVX, pipelining)
  • cenni ad architetture CISC e RISC

Giovedì 7 dicembre 2017 (Lezione 17 - 150 min)

• Esecuzione programmi sulla CPU:
  • evoluzione negli ultimi decenni: legge di Moore, crescita esponenziale numero transistor, avvento delle architetture multicore [Moore's Law]
• 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
  • caching come strategia di duplicazione della memoria oppure per memorizzare risultati di computazioni ricorrenti
  • 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

Martedì 12 dicembre 2017 (Complementi C - 100 min) - Coppa

• 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): run, start, quit, break, step, cont, next, finish, print, delete, info break, backtrace, frame, where
  • Esempi (codice: somma.c, nullptr.c, overflow.c

Giovedì 14 dicembre 2017 (Lezione 18 - 150 min) - Coppa

• 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

Martedì 19 dicembre 2017 (Lezione 19 - 100 min) - Coppa

• 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 estenra
  • paginazione
  • frammentazione interna nelle pagine
  • come avviene il mapping degli indirizzi logici su quelli fisici?
  • paginazione con bit di validità
  • condivisione di pagine,: es.comuncazione tra processi, librerie dinamiche
  • page fault memoria virtuale e loro gestione, protection fault (SIGSEGV)
  • Paginazione con bit di validità e swapping su disco: gestione page fault
  • Working set e thrashing

Giovedì 21 dicembre 2017 (Lezione 20 - 150 min) - Coppa

• Riepielogo meccanimsmo memoria virtuale, paginazione, swap, traduzione indirizzi logici in fisici
• Esercizi sulle gerarchie di memoria e pattern di allocazione

Venerdì 22 dicembre 2017 (Lezione 21 - 150 min) - Coppa

• Esercizi sulle system call POSIX
• Esercizio per casa "unrolled linked list": testo (vedere esercizio 2) | soluzione
• coppa@SC1:~$ echo Buon Natale! In bocca al lupo per l'esame