Programma preliminare (A.A. 2016-2017)

Primo modulo (SC1)

Il primo modulo del corso raffina le capacità di programmazione acquisite nei corsi di programmazione precedenti studiando la relazione tra i programmi e il loro ambiente di esecuzione, in particolare:

1. come programmare sfruttando i servizi offerti dai sistemi operativi?
2. come avviene la traduzione di un programma C in assembly?
3. come avviene l'esecuzione di un programma?
4. come viene gestita la memoria?
5. come la conoscenza dell'architettura di calcolo, del sistema operativo e del compilatore utilizzato permette di scrivere programmi più robusti ed efficienti?

I concetti sono esemplificati utilizzando come caso di studio Linux su architetture x86. Le funzionalità dei sistemi operativi e delle architetture di calcolo sono presentate dal punto di vista del programmatore, lasciando ulteriori approfondimenti sui loro meccanismi interni ai corsi del terzo anno di sistemi operativi e architetture del calcolatori.

Parte I: come programmare in un sistema operativo moderno?

• Nozioni di base sui sistemi di calcolo e la loro programmazione:
  • sistema operativo come ambiente per l'esecuzione dei programmi e per consentire l'utilizzo del calcolatore da parte degli utenti
  • hardware (architettura di Von Neumann): CPU (controllo, ALU, registri), bus, I/O (I/O bridge, controller, adattatori), memoria
• Panoramica sui servizi principali forniti da un sistema operativo:
  • gestione dei processi (creazione, esecuzione, comunicazione, sincronizzazione, controllo, eliminazione)
  • gestione della memoria (allocazione della memoria ai processi)
  • gestione dei file
  • gestione dei dispositivi di I/O
  • sicurezza e protezione
  • controllo delle prestazioni, accounting, gestione degli errori
• Interfaccia del sistema operativo verso l'utente:
  • struttura di base del filesystem: file, directory, struttura ad albero, root, home, path assoluti e relativi, file "." e "..", "~", case-sensitivity, file nascosti, link simbolici
  • utenti e gruppi, permessi rwx
  • shell bash, comandi interni (built-in), comandi esterni
  • interfaccia dei comandi (es. coreutil), desktop environment e server grafico (es. X, gnome, kde)
  • comandi principali:
    • navigazione e manipolazione file system: cd, ls, ln, pwd, mkdir, rmdir, rm, cp, mv, touch
    • ispezione file: cat, less, head, tail, grep, whereis, which, type,
    • documentazione: man, opzione --help
    • permessi: chmod
    • processi: jobs e ps, background (&, CTRL+z) e foreground (fg), terminazione processo (kill, CTRL+c), overview processi attivi (top)
  • canali stdin, stdout, stderr, redirezione > e <, shell pipe | (es: ps | less)
  • variabili di ambiente: variabile PATH, comando env, file .bashrc
• Interfaccia del sistema operativo verso i programmi:
  • passaggio dei parametri a un programma C: argc/argv
  • valore di ritorno di un processo: exit(), return della funzione main
  • accesso alle variabili di ambiente: getenv, setenv
  • programmazione di sistema: system call e standard POSIX
  • differenza tra librerie utente (es. libc, fopen, fwrite) e system call (es. open, write)
• Tool per lo sviluppo:
  • compilazione di programmi C con gcc:
    • pipeline di compilazione: preprocessore (cpp), compilatore (cc0), assemblatore (as), linker (ld)
    • file sorgente (.c), assembly (.s), oggetto (.o), eseguibile
  • disassemblamento: objdump -d
  • debugging in ambiente Linux: gdb e valgrind; errori tipici: puntatore non inizializzato, offset by 1, memory leak, accesso a memoria deallocata (stack o heap), double free, conditional jump depends on uninitialised value, ecc.

Parte II: come viene compilato un programma C in assembly?

• ISA e ABI come astrazioni per il programmatore, ISA IA32 (architetture x86), ABI System V (calling conventions)
• Metodologia generale: riformulare programma C in modo da essere direttamente traducibile in IA32 (es. x=y+1 -> x=y; x=x+1)
• Traduzione programmi C -> assembly IA32 (sintassi AT&T)
  • tipi primitivi (char, short, int, long, float, double, long double) e tipi puntatore -> tipi IA32 (Byte, Word, Double Word, Single Precision, Double Precision, Extended Precision), suffissi delle istruzioni IA32 (b, w, l)
  • variabili locali (parte I) -> registri general-purpose A, B, C, D, SI, DI e loro accesso a 8, 16, 32 bit (es. %al, %ax, %eax)
  • assegnamento -> istruzione MOV
  • letterali interi -> operandi numerici immediati decimali (es. $100) ed esadecimali (es. $0xCAFE)
  • operatori aritmetici ed espressioni intere -> istruzioni aritmetiche NEG, ADD, SUB, IMUL, INC, DEC, LEA
  • array e aritmetica dei puntatori -> indirizzamento a memoria indiretto a registro e con base, indice e scala (es. (%eax, %ecx, 4))
  • conversioni di tipo intero (type cast) -> istruzioni MOVZ e MOVS
  • selezione (if ... else) e iterazione (while, for) -> registro EFLAGS, condition code (e, ne, g, ge, l, le, a, ae, b, be) e, istruzioni di confronto CMP e TEST, istruzioni di salto JMP, Jcc, assegnamento condizionale CMOVcc
  • chiamata e ritorno da funzione -> istruzioni CALL e RET, creazione e distruzione di stack frame, calling convention System V (registri callee-save e caller save, valore di ritorno intero di una funzione), PUSH, POP
  • variabili locali (parte II), passaggio dei parametri, parametri formali -> layout dello stack frame, indirizzamento a memoria indiretto a registro con base (SP) e spiazzamento (es. 4(%esp))
  • operatori relazionali ed espressioni booleane -> istruzioni logiche bitwise AND, OR, NOT, XOR e istruzione SETcc
  • chiamate al sistema operativo -> INT e passaggio dei parametri alle system call

Parte III: come viene eseguito un programma?

• 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
• Esecuzione di un processo:
  • ciclo fetch-decode-execute
  • pipelining e stalli (panoramica non dettagliata)
  • esecuzione in modalità utente (programmi utente) e in modalità supervisore (kernel)
  • flusso del controllo eccezionale
    • trap e interrupt
    • esecuzione di system call mediante trap
  • stati di un processo: running user, running kernel, waiting
• Esecuzione simultanea di più processi:
  • scheduling dei processi:
    • context switch
    • altri stati di un processo: started, ready, zombie
    • esempio del time sharing round-robin mediante timer e interrupt
  • albero dei processi
  • system call per il controllo dei processi: creazione (exec), terminazione (exit), attesa terminazione (wait), segnali e distruzione di processi (kill)

Parte IV: come vengono organizzati i dati in memoria?

• Come è strutturata la memoria?
  • accesso a memoria: transazioni in lettura e scrittura
  • cache istruzioni e dati, principio di località (spaziale, temporale)
  • gerarchie di memoria
  • allineamento
• Come viene gestita la memoria?
  • 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
    • allocazione in cascata della memoria
  • allocazione nella memoria fisica: memoria virtuale
    • mapping tra indirizzi virtuali e indirizzi fisici: MMU
    • paginazione
    • come avviene il mapping degli indirizzi logici su quelli fisici?
    • quanto spazio occupa una tabella delle pagine?
    • paginazione con bit di validità
    • paginazione con bit di validità e swapping su disco
    • thrashing
  • allocazione nella memoria logica: malloc e free, system call sbrk

Parte V: come viene ottimizzato un programma?

• Efficienza prestazionale come moneta per pagare altre qualità del software (affidabilità, usabilità, manutenibilità, portabilità, modularità, ecc.)
• Metriche prestazionali classiche:
  • tempo di esecuzione: cicli macchina (assoluti e aggregati, CPI, IPC), secondi (user/system/real)
  • spazio di memoria richiesto: byte allocati, memory footprint
  • cenni ad altre metriche: energia
• Misurazione del tempo speso da un programma: hardware counter, risoluzione del timer e precisione della misura, comando time, funzioni clock (cross-platform) e clock_gettime (POSIX)
• Metodologie sperimentali:
  • effetti imprevedibili che possono influenzare misurazioni: scheduling dei processi, swapping su disco
  • trial, aggregazione (media, varianza), intervallo di confidenza
  • pericoli nel trarre conclusioni dagli esperimenti
• Ottimizzazioni del programmatore (algoritmo e codice) e del compilatore (codice)
• Livelli di ottimizzazione in gcc
• Quali parti di un programma ottimizzare?
  • speedup e legge di Amdahl
  • profilazione delle prestazioni: gprof, valgrind massif
• Ridurre il numero di istruzioni eseguite
  • espressioni: constant folding, constant propagation, common subexpression elimination
  • cicli: loop-invariant code motion (hoisting), loop reverse
  • funzioni: inlining, tail recursion
• Ridurre il costo delle istruzioni eseguite sfruttando l'hardware
  • tempi di latenza tipici in un sistema di calcolo (da accesso a registro a round-trip time pacchetto Internet)
  • sfruttare i registri: allocazione dei registri
  • sfruttare la pipeline: istruzioni branchless
  • sfruttare istruzioni equivalenti meno costose: operator strength reduction
  • sfruttare la cache: migliorare la località degli accessi a memoria
  • sfruttare la memoria: accesso allineato
  • sfruttare unità di calcolo parallele: cenni a multicore e instruction-level parallelism (es. AVX)
• Ridurre lo spazio di memoria
  • ottimizzare lo spazio richiesto dalle strutture C
  • ridurre la dimensione del codice: dead code elimination, rimpiazzo di istruzioni con altre che richiedono meno byte (es. movl $1, D -> incl D)
• Le ottimizzazioni dei compilatori sono le migliori possibili?

Secondo modulo (SC2)

Vedere gli argomenti trattati nel diario delle lezioni A.A. 2016-2017.