Lezioni Anno Accademico 2016/17

scrivete qui idee, riassunti dei concetti espressi, commenti approfondimenti sulle lezioni.

Lezione del 23 settembre 2016

YY

• Presentazione del corso.
• Strumenti del corso: web, wiki.mailing list
• Indice dei contenuti
• Prove di esame (Scritto, Prova Pratica, Progetto).

• Hardware Software
• Informatica
• Informazione/Dato
• Rivoluzione digitale (secondo rinascimento, Terza rivoluzione Industriale).
• Software Libero

Lezione del 27 settembre 2016

OS:Y

• Organizzazione (martedi' vs. venerdi')

In genere la lezione del martedì sarà più teorica mentre quella del venerdì più orientata agli aspetti pratici di laboratorio. Questa suddivisione potrebbe cambiare in quanto qualche martedì verrà saltato.

• Università

Università = studenti + docenti

• Digitale/Analogico

Digit significa cifra. Nell'informatica è fondamentale il passaggio dal continuo al discreto.

• Binario/Decimale

Nei calcolatori l'informazione è memorizzata utilizzando il sistema binario ... (in quanto in passato i relè consentivano di avere due stati: " 1 e 0 ": è impreciso, qualcuno sa dare una definizione migliore? Renzo (talk) 12:00, 29 September 2016 (CEST))
In quanto è molto semplice implementare le operazioni aritmetiche con dei circuiti elettronici utilizzando la codifica binaria. Per esempio è possibile creare un circuito che somma due bit con riporto con solo due porte logiche. FedericoB (talk) 17:05, 29 September 2016 (CEST)

• I linguaggi e i problemi dell'Informatica
  • Processing dell'informazione (Linguaggi di programmazione)
  • Comunicazione (Il problema che i dati che mi servono sono in un altro luogo) (Linguaggi dei protocolli di rete, che però sono dei linguaggi temporizzati)
  • Memorizzazione (Il problema che i dati mi serviranno in futuro) (Linguaggio del formato dei dati)
• Conoscenze a lungo, medio e breve termine nell'Informatica.
  • BREVE: tecnologia, determinati programmi di sviluppo.
  • MEDIO: singoli linguaggi, singoli OS, protocolli di comunicazione.
  • LUNGO: algoritmi, informatica teorica, fondamenti costruttivi di reti e di OS.

• Cos'è una distribuzione

E' un antologia di applicazioni e librerie in modo che siano compatibili tra loro.

• Sistema Operativo: perché

Un sistema operativo è un programma che controlla l’esecuzione di programmi applicativi e agisce come interfaccia tra le applicazioni e l’hardware del calcolatore.
E' uno strumento software complesso ed implementabile in diversi modi (monolitico, microkernel, etc.). I microcontroller non hanno OS. Permette: contabilità delle risorse (consente a sua volta attività di benchmarking); continuità dei servizi; controllo errori (programmi, dispositivi); multiuser (gli utenti hanno diversi diritti e proprietà sulle risorse); protezione delle attività dei processi; astrazione file system.

• Struttura a livelli (layer)

 ---------------
 ---------------
 ---------------
       OS
 ---------------L'
       hw
 ---------------L

Consente di: separare la complessità, di avere portabilità. Ogni livello rappresenta un cambio di linguaggio. Più aggiungiamo livelli più aumenta il livello di astrazione.

• Programma/processo

Algoritmo: sequenza finita di istruzioni non ambigue, atta a risolvere un problema.

Programma: traduzione degli algoritmi in un linguaggio di programmazione.

Processo: istanza esecutiva di un programma. Il programma è testo statico, quando viene eseguito diviene processo. Possiamo avere uno stesso programma in esecuzione su più processi (e.g apertura di più terminali che eseguono un editor di testo).

System call: richieste di processi al OS. e.g. printf (visto nel codice compilato in assembly tramite gcc -s), invoca write(). vi è una sequenza di azioni del tipo: richiesta di stampa al kernel --> attesa --> risposta.

• Storia dell'Informatica prima dei transistor

La storia dei calcolatori non ha un inizio preciso. Nel 1900 venne trovato sul relitto di una nave greca risalente al II secolo a.C un meccanismo in grado di calcolare i movimenti degli astri, si ipotizza con una sorprendente meccanica. Oggi questo sistema viene conosciuto come Macchina di Anticitera. Negli ultimi anni di ricerche archeologiche e storiche è venuta sempre più in superficie una vena pionieristica nel mondo classico per quanto riguarda lo studio sul calcolo automatizzato e addirittura di automi (si veda Erone di Alessandria). Ma facciamo un salto in avanti di qualche secolo...
Già nel XVII secolo Pascal teorizza e mette in pratica uno strumento in grado di addizionare e sottrarre, e nel 1672 G.W. von Leibniz lo perfeziona con l'aggiunta della moltiplicazione e della divisione. Ma è solamente nei primi anni del 1800 che entra in scena la macchina analitica di Babbage. Estremamente complessa, la macchina era dotata di un sistema di input e di elaborazione dati e di un sistema di output. Ed è con Babbage che nascono le schede perforate. La macchina analitica venne presentata per la prima volta in Italia, durante un convegno torinese del 1840. Tra i vari collaboratori scientifici alla macchina è da annotare la presenza di Luigi Federico Menabrea, che tra le altre cose fu Ministro della Marina Militare, ingegnere e Presidente del Consiglio dei Ministri del Regno d'Italia (1867-1869). Il primo vero programmatore della storia, collaboratrice di Babbage, è Ada Lovelace (figlia del poeta Lord Byron!): progettò un algoritmo in grado di elaborare i numeri di Bernulli.
Nel 1896 viene fondata la Tabulating Machine Company (futura IBM) e agli albori del '900, vari scienziati (trai quali Thomas Edison e Guglielmo Marconi) portarono avanti gli studi sulla valvola termoionica, elemento indispensabile dei primi calcolatori elettronici. La valvola incrementò vertiginosamente i tempi di calcolo ma l'estrema fragilità della stessa causò una serie di problematiche che si risolsero solamente con l'entrata in gioco del transistor.

Lezione del 30 settembre 2016

YC

(Storia dopo l'avvento del transistor)

Tre innovazioni indipendenti:

• Multitasking: Inizialmente ideato per mantenere la CPU occupata con altri processi mentre si faceva Input/Output. Permette di dare l'idea al utente di poter eseguire più processi contemporaneamente anche se questi in realtà sono eseguiti dalla cpu in modo intervallato. Ci sono certi computer che hanno più esecutori e quindi possono realmente eseguire multipli processi contemporaneamente.
• Supporto Multiuser
• Interattività:l'interazione con l'utente cambia il flusso del programma.

Queste tre proprietà sono ortogonali quindi possono esistere nei sistemi varie combinazioni di queste.

Iniziano anche a separarsi i ruoli tra programmatori e utenti.Prima i computer venivano utilizzati solo da chi creava programmi ora anche da chi li utilizza senza avere le conoscenze per crearli.

Il Time Sharing.

Sistemi Paralleli (SIMD/MIMD) Sistemi Real Time

Dal 1969: UNIX.

Il linguaggio C e la portabilità dei sistemi operativi. Caratteristiche del linguaggio C:

• grande controllo sul codice generato
• costrutti per l'elaborazione a basso livello
• supporto per la programmazione strutturata
• linguaggio "leggero": poche parole chiave, I/O gestito tramite librerie
• Il compilatore C è scritto in C.

Portabilità di un compilatore. I cross-compiler.

Il comando UNIX cc (o gcc): un comando unico per attivare l'intera toolchain per generare un eseguibile.

Il punto e virgola trasforma espressioni in istruzioni (terminatore).

1975? l'avvento dei personal computer. (in realtà il primo PC forse e' la Perrottina Olivetti del 1964).

Compiti a casa: Portare esperimenti in C ritenuti "difficili".

Renzo (talk) 10:41, 1 October 2016 (CEST)

Lezione del 7 ottobre 2016

• Esempi di programmi in linguaggio C

Abbiamo commentato i programmi dal 1.1 al 1.7 che si possono trovare in questa pagina.

• Economia Push/Economia Pull

Nell'economia push si basa la produzione sulla previsione di domanda e la si cerca di aumentare tramite la pubblicità. Questa è stata la principale metodologia utilizzata nei secoli scorsi. Al giorno d'oggi si sta facendo avanti un differente approccio chiamato "economia pull" dove la produzione è basata sulla domanda effettiva. Per esempio per richiedere un finanziamento per l'economia push l'approccio comune è tramite una banca a cui si chiede un prestito in base alle previsioni di ricavo. Invece nell'economia pull è esemplare il fenomeno del crowdfounding dove si riceve un finanziamento dalla "folla" cioè da un gruppo di persone che dona una piccola parte di denaro ciascuna in base al reale interesse per il prodotto/servizio.

• Sistemi Operativi e parallelismo

Più processi si dicono in esecuzione concorrente quando accedono a risorse condivise. Un programma è multithread quando tutti i thread condividono la stessa memoria. Ogni thread deve avere un suo stack. La concorrenza si studia in particolare in sistemi operativi in quanto un sistema operativo multitasking è un sistema concorrente. Concorrenza di processi in architetture SMP (Symmetric multiprocessor system) e non. (RD: non mi pare di aver spiegato cosa sia l'SMP)
Simulazione del fenomeno della race condition. Si ha race condition quando un programma concorrente può puo' produrre diversi risultati se eseguito piu' volte per colpa della diversa evoluzione temporale delle elaborazioni.
Per risolvere questo dovremmo raggruppare le istruzioni in sezioni critiche (sequenze inscindibili di istruzioni che devono essere eseguite come se fossero atomiche, tutta la sequenza o niente).

• Architettura a livelli e virtualizzazione

Dato un A e un A’ e riusciamo a usare A’ come A, allora A’ lo possiamo chiamare A virtuale. L'idea che alla base delle macchine virtuali è di creare un interprete di un ISA differente o uguale a quello del sistema in modo da virtualizzare una reale macchina hardware e quindi poterla usare per gli stessi scopi di una macchina reale. E' quindi possibile, per esempio, installare sistemi operativi su hardware virtuale.
L'insieme dei componenti hardware virtuali e il software installato su di questi prende il nome di macchina virtuale. Uno dei principali vantaggi, oggi molto utilizzato in ambito cloud, è quello di poter suddividere facilmente risorse hardware fisiche, per esempio spazio su disco e potenza di elaborazione, tra macchine virtuali differenti.

• Laboratorio di cross-compiling

Nel ultima parte della lezione abbiamo fatto un esperimento sulla portabilità dei compilatori.
Abbiamo a disposizione un linguaggio ad alto livello che chiameremo L, due interpreti hw0 e hw1 per linguaggi a basso livello che chiameremo lhw0 e lhw1 e infine due compilatori L->lhw0 uno scritto in python e l'altro in L.
Se compiliamo con il compilatore scritto in python (abbiamo un interprete python installato sulla macchina che stiamo utilizzando) il compilatore scritto in L otteniamo un compilatore scritto in lhw0 L->lhw0.
Se ora modifichiamo il compilatore scritto in L L->lhw0 in modo che crei codice per hw1 (basta modificare gli indici numerici delle istruzioni) otteniamo un compilatore in L L->lhw1. Se lo compiliamo con il compilatore L->lhw0 otteniamo un cross-compiler scritto in lhw0 L->lhw1, cioè un compilatore che crea codice eseguibile su una macchina diversa da quella attuale.
Se ora utilizziamo il cross compiler L->lhw1 per compilare il compilatore scritto in L L->hw1 otteniamo invece un compilatore che può essere eseguito su hw1.
A questo punto su hw1 potremmo utilizzare l'ultimo compilatore creato per compilare sempre il compilatore scritto in L L->hw1 ma vedremo che otterremo sempre lo stesso file perché avremo raggiunto il limite.
Il materiale per poter replicare l'esperimento sulla portabilità dei compilatori è qui. Renzo (talk) 13:42, 8 October 2016 (CEST)

Lezione del 11 ottobre 2016

• C

  #include <stdio.h>

  void dump (void* f, size_t len){ //size_t is the sizeof() return type
        unsigned char *s = f;
        size_t i;
        for (i = 0; i < len; i++)
                printf("%02x",s[i]); //%02x means print at least 2 digits and add 0's if there are less
        printf("\n");
  }

  int main(){

  int v[] = {1, 2, 3, 4}; //v is (int*) 0x32ef...
  v[2] = 42; //*((int*) 0x32ef) + 2 = 42, moves the address by 2 "positions", aka 4+4 bytes
  v = 0x33;//(int*) 0x32ef.. = 0x33 (i.e.) 4 = 42

  char s[] = "ciao";
  int t[] = {0x63, 0x69, 0x61, 0x6f, 0x00}; //ciao in ASCII hex. if int OUT:'c'. if char OUT:"ciao"
  char u[] = {99, 105,97, 111, 0 }; //ciao in ASCII dec. OUT:"ciao"

  char *q = "ciao"; 
  char *w = "mare";

  printf("%s", s);
  printf("%s", t);
  printf("%s", u);

  dump(s, sizeof(s));
  dump(t, sizeof(t));
  dump(q, sizeof(*q)); //*q size is 1B (it points to 1 char). OUT: 63('c')
  dump(q, sizeof(q)); //q size is 8B. OUT: 5B of "ciao" + 3B of contiguous string "mare"
  }

OUTPUT:

  ciao
  c  
  ciao
  63 69 61 6f 00
  63 00 00 00  69 00 00 00  61 00 00  00 6f 00 00  00 00 00 00 00 //int are 4B, char 1B, so we have empty bytes. 
  Little endian pattern is evident. %s allow to print untill the first null, so printf prints just 'c' with int declaration of t[]
  63 
  63 69 61 6f  00 6d 61 72 // 6d = m, 61 = a, 72 = r.

• Assioma di finite progress.

"Tutto è vero purchè ogni statement abbia durata sconosciuta, ma finita"

• Modalità di concorrenza.

1- Inconsapevolmente concorrenti: ogni processo elabora ciò per cui è stato creato. Il kernel si occupa di coordinazione e comunicazione.

2- Indirettamente concorrenti: processi che accedono a file condivisi.

3- Consapevolmente concorrenti: il programma ha diversi processi in esecuzione.

• Convenzioni usate nel corso (e negli esami) relative alle istruzioni atomiche
• Proprieta' di Safety e Liveness

-Safety: se il programma evolve, evolve bene(S)

"Something good happens"

-Liveness: il programma va avanti(L)

"Something eventually happens"

• Problema del consenso.

Il problema è così definito: ci sono n processi, ognuno propone un valore. Al termine tutti i processi devono accordarsi su di 1 dei valori proposti.Il suddetto problema è risolvibile se e solo se vengono rispettate le seguenti proprietà (2 di Safety + 1 di Liveness)

Proprietà:

S(1)- Tutti i processi devono ritornare lo stesso valore

S(2)- Ogni processo corretto decide uno tra i valori proposti

L(1)- Ogni processo corretto deve dare una risposta

w/o S(1): f(x) = x

w/o S(2): f(x) = 42

w/o L(1): f(x) = while(1)

• w/o = without

• Problemi delle elaborazioni concorrenti. Prima definizione (non formale) di Deadlock e Starvation

Introduzione alla notazione per la rappresentazione dei processi concorrenti

ESEMPIO 1.0

 process p {
   ...
   ...
 }

 process q {
   ...
   ...
 }

Due processi eseguiti in concorrenza.

 ...
 cobegin
 ...
 //
 ...
 //
 ...
 coend

cobegin e coend indicano la sezione di codice con le istruzioni (rappresentate da "..." e separate da "//")che verranno eseguite in concorrenza.

ESEMPIO 1.1 - Merge sort

 cobegin 
   sort(v[1 : N])
 //
   sort(v[N : N])
 //
   merge(v[1 : N]), v[N : M])
 coend

Se isoliamo le istruzioni senza considerare cobegin e coend, lo pseudocodice è corretto. Se consideriamo anche cobegin e coend il programma esegue la funzione di merge() in concorrenza con le due chiamate a sort(), utilizzando risorse in comune e pertanto cercando di ordinare elementi non ancora ordinati nelle due metà dell'array. Se spostiamo l'invocazione di merge al di fuori della sezione cobegin ... coend, lo pseudocodice (vedi in basso) è corretto.

 cobegin 
   sort(v[1 : N])
 //
   sort(v[N : N])
 coend
   merge(v[1 : N]), v[N : M])

In particolare nella programmazione concorrente si devono affrontare due problemi che riguardano la liveness, parliamo di deadlock e starvation.

DEADLOCK: uno o più processi non possono continuare l'esecuzione perchè ognuno di essi è in attesa che gli altri facciano qualcosa

ESEMPIO 1.2

 process p {
 while 1:
   prendi a
   prendi b
   calcola f(a,b)
   lascia a
   lascia b
 }
 
 process q {
 while 1:
   prendi a
   prendi b
   calcola f(a,b)
   lascia a
   lascia b
 }

Supponiamo di invertire l'ordine di prendi a e prendi b nel processo p. Dopo che entrambi i processi eseguono la prima istruzione lo scenario che si sviluppa è il seguente: al processo p serve la risorsa a, presa dal processo q, al quale servirebbe la risorsa b, presa dal processo p. I processi aspettano a vicenda che uno rilasci la risorsa che possiede l'altro. Risorsa necessaria ad entrambi i processi per eseguire l'istruzione (f(a,b)) che le richiederebbe entrambe. I processi sono deadlocked.

STARVATION: quando un processo attende una risorsa indefinitamente, e questa non gli viene mai allocata

ESEMPIO 1.3

 process p {
 while 1:
   prendi a
   calcola f(a)
   lascia a
 }

 process q {
 while 1:
   prendi a
   calcola f(a)
   lascia a
 }

Supponiamo che i processi per realizzare "prendi a" verifichino la disponibilità di a tramite polling (provando ripetutamente se a è libero). Il processo q può essere sfortunato e non riuscire mai ad avere accesso ad a (tutte le volte che cerca di "prenderlo" lo troverà impegnato da p). Il processo q è in starvation.

ESEMPIO 1.4 "Supponiamo di avere tre processi (P1, P2, P3) i quali richiedono periodicamente accesso alla risorsa R. Consideriamo la situazione nella quale P1 è in possesso della risorsa, e sia P2 che P3 attendono per quella risorsa. Quando P1 esce dalla sua sezione critica, a P2 o P3 dovrebbe essere permesso l'accesso a R. Assumiamo che il SO garantisca l'accesso a P3 e che P1 richieda nuovamente la risorsa prima che P3 termini la sua sezione critica. Se il SO dovesse garantire l'accesso a P1 dopo che P3 abbia finito, e successivamente dovesse garantire alternativamente a P1 e P3 l'accesso alla risorsa, allora P2 potrebbe vedersi indefinitamente negato l'accesso alla risorsa, sebbene non vi sia una situazione di deadlock" (Stallings W.(2015). Operating System: internals and design principles. (8th ed). Pearson)

---

Altri argomenti trattati che non sono stati qui riportati in forma di appunti: Proprieta' della sezione critica. Gestione algoritmica della critical section. Algoritmo di Dekker. Gestione architetturale della critical section. La test&set.

Renzo (talk) 10:35, 17 October 2016 (CEST)

Lezione del 14 ottobre 2016

• Sistemi Operativi per elaboratori multiprocessore SMP/non SMP
• Macchine di von Neumann (e di Harvard).
• Il bus.
• Interrupt e Trap
• Gestione degli interrupt
• Mascheramento degli interrupt
• Interrupt Nidificati
• DMA
• Device a carattere e device a blocchi
• System call come trap.
• La gerarchia delle memorie
• cache