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

Audio Lezione: 7\10\16

• 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

Le istruzioni atomiche vengono compiute in modo indivisibile, garantendo che l'azione non interferisca con altri processi durante la sua esecuzione. Vengono rappresentate nel seguente modo:

<istruzione atomica>

Anche gli statement sono istruzioni atomiche(escluso il caso long long).

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

Problema: posso creare sezioni critiche, tramite la programmazione, senza aiuti hardware?

ESEMPIO

 process p
   /*enter_cs*/
   A = A + 1
   /*exit_cs*/

 process q
   /*enter_cs*/
   A = A - 1
   /*exit_cs*/

Le 4 proprietà della critical section(CS)

SAFETY(1): una operazione all'interno della CS

ESEMPIO

 process p
 while 1:
   /*enter_cs*/
   A = A + 1
   /*exit_cs*/
   ...  <--- process q deve poter "entrare" qui

LIVENESS(1): no deadlock

LIVENESS(2): no starvation

LIVENESS(3): no useless wait

Dekker(1st attempt) //KEY: turno

 turn = p //var globale condivisa

 process p{
   while (turn != p)
     ;
   /*A = A + 1*/
   turn = q
   ...
 }

 process q{
   while(turn != q)
     ;
   /*A = A - 1*/
   turn = p
   ...
 }

Non rispetta la proprietà di liveness(3), infatti uno dei due processi può dover attendere a lungo il suo turno eseguendo ciclicamente l'empty statement all'interno del corpo del while. Questa situazione può verificarsi se l'altro processo fallisce dentro o fuori la sua CS (in questo caso l'attesa è infinita). Inoltre visto che i processi si alternano strettamente nell'utilizzo della loro critical section, il ritmo di esecuzione è dettato dal processo più lento dei due.

Dekker(2nd attempt) //KEY: flag, ma senza turno

 inp = false

 inq = false

 process p{
   while 1:
     while(inq)
        ;
     inp = true
     /*A = A + 1*/
     inp = false
     ...
 }

 process q{
   while 1:
     while(inp)
        ;
     inq = true
     /*A = A - 1*/
     inq = false
     ...
 }

In questo caso se uno dei processi fallisce fuori dalla CS (dopo aver settato il flag a false) l'altro processo non viene bloccato. Se invece un processo fallisce nella sua CS oppure dopo aver settato il flag a true allora l'altro processo resta bloccato indefinitamente. Non è garantita inoltre la mutua esclusione in quanto entrambi potrebbero essere al contempo nelle loro rispettive CS, ad esempio:

p valuta la condizione del while e trova inq a false

q valuta la condizione del while e trova inp a false

p assegna true a inp ed entra nella sua CS

q assegna true a inq ed entra nella sua CS

....entrambi sono nella rispettiva CS --> no liveness(1)

Dekker(3nd attempt) //KEY: come 2nd ma con due istruzioni scambiate di ordine

 process p{
   while 1:
     inp = true
     while(inq)
        ;    
     /*A = A + 1*/
     inp = false
     ...
 }

 process q{
   while 1:
     inq = true
     while(inp)
        ;
     /*A = A - 1*/
     inq = false
     ...
 }

Scambiando l'ordine di due istruzioni vi è la mutua esclusione, tuttavia se entrambi i processi assegnano true al loro rispettivo flag, prima di valutare la condizione del while, entrambi resteranno all'interno del while in attesa che l'altro processo "esca dalla CS" (non vi è mai entrato) --> deadlock

Dekker(4nd attempt) //KEY: flag + delay

 process p{
   while 1:
     inp = true
     while(inq){
       inp = false; < delay >; inp = true;
     }          
     /*A = A + 1*/
     inp = false
     ...
 }

 process q{
   while 1:
     inq = true
     while(inp){
       inq = false; < delay >; inq = true;
     }
     /*A = A - 1*/
     inq = false
     ...
 }

In questo caso il settare il proprio flag a true è indice del desiderio di entrare nella propria CS. Vi è ancora mutua esclusione. Se però dovesse verificarsi una sequenza del tipo:

p imposta flag inp a true

q imposta falg inq a true

p valuta la condizione del while

q valuta la condizione del while

p imposta flag inp a false

q imposta flag inq a false

p imposta flag inp a true

q imposta flag inq a true

allora c'è la possibilità che si ripeta all'infinito (entrambi i processi potrebbero rimanere nel while). Essendo però una condizione che dipende dalla velocità relativa dei due processi, esiseranno delle situazioni nelle quali uno dei due processi potrà entrare, così come vi saranno delle situazioni nelle quali nessun processo avrà accesso alla propria CS --> livelock

Dekker...finally //KEY: flag + turni ("cambio delay con turno)

 needp = false 

 needq = false

 turn = p

 process p{
   while 1:
     needp = true
     while (needq) { 
       needp = false 
       while(turn == q)
        ; 
       needp = true
     }
    /*A = A + 1*/
    needp = false
    turn = q
    ...
  }

 process q{
  while 1:
    needq = true
    while(needp) {
      needq = false; 
      while(turn == p)
       ; 
      needq = true
   }
   /*A = A - 1*/
   needq = false
   turn = p
   ...
 }

In questo caso il processo che vuole entrare nella sua CS ne manifesta il bisogno settando need a true. Se entrambi i processi entrano nel corpo del while il tie-break è espletato dal while la cui condizione è un turn che sarà uguale soltanto ad uno dei due processi (in questo caso turn è inizializzata a p), e dunque non si verificherànno situazioni di deadlock o livelock.

• Proprietà della sezione critica

Mutua esclusione
Assenza di deadlock
Assenza di starvation
Assenza di delay non necessari

• La test&set

E' un istruzione atomica per impostare il valore di una variabile a 1 (lock) ma ritornare il vecchio valore. Questa istruzione può essere utilizzata per gestire sezioni critiche.
Il valore ritornato dalla test and set viene comparato a 1, se è uguale si aspetta altrimenti si procede.
In questo modo il primo processo che cercherà di entrare nella sezione critica ci riuscirà e imposterà il lock a 1, gli altri processi si troveranno il lock a 1 e dovranno aspettare. Quando il primo processo avrà finito ripristinerà il vecchio valore di lock e permetterà a uno degli altri processi di eseguire la test and set e di entrare nella sezione critica.

---

Altri argomenti trattati che non sono stati qui riportati in forma di appunti: Gestione algoritmica della critical section. Algoritmo di Dekker. Gestione architetturale della critical section.

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

Lezione del 14 ottobre 2016

Audio Lezione: 14\10\16

• 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

Lezione del 18 ottobre 2016

Audio Lezione: 18/10/16

Argomenti trattati:

• Implementazione in C della Test&Set, degli Algoritmi di Dekker e Peterson.

Codice sorgente disponibile qui.

• Definizione di Semaforo.

Un semaforo è una variabile intera che può essere modificata solo da 2 operazioni atomiche: P(Proberen) e V(Verhogen).
P aspetta che il valore sia minore o uguale a zero. Quando lo diventa decrementa il valore.
S incrementa il valore.

• Invariante del Semaforo.

Il numero di Proberen deve essere minore o uguale al numero di Verhogen più il valore d'inizializzazione del semaforo.
In questo modo si può gestire per esempio l'allocazione di risorse. Il semaforo viene inizializzato al numero di risorse e ogni volta che un processo ha bisogno della risorsa esegue un proberen, quindi decrementa il valore se la risorsa è disponibile. Quando un processo rilascia la risorsa esegue un verhogen.

• Esempio: implementazione di sezione critica e di semplice sincronizzazione con semafori.

Lezione del 21 ottobre 2016

• Make

Make è un sistema per la compilazione intelligente dei programmi.
Permette invece di compilare tutto il programma tutte le volte di compilarne solo una parte, solo quella che è stata modificata. Per capirne il funzionamento è utile un parallelismo con le ricette di cucina. Si specificano dei target che sono gli obbiettivi della ricetta.Per fare una ricetta servono degli ingredienti e magari quegli ingredienti hanno a loro volta delle ricette. Make allo stesso modo definisce dei target che possono avere come dipendenze altri target.
Nel installazione del programma il programma ./configure cerca nel sistema se le librerie da cui è dipendente il programma sono presenti.

• Git

Git è un sistema di versioning, serve a tener traccia delle modifiche apportante a un progetto nel tempo. E' utile per collaborare a un progetto condiviso.
Possibilità per ogni membro del repository di lavorare in maniera indipendente e poi aggiornare il progetto comune.
Ce ne sono stati tanti di sistemi di versioning tipo SVN, Mercurial ma attualmente Git è il più utilizzato.
Git non serve solo per scrivere programmi ma per esempio anche libri, in modo collaborativo.
Git è completamente distribuito, non esiste in un repository una copia principale e delle copie secondarie ma ogni copia può essere principale.
Per iniziare un repository git si utilizza il comando git init.
Per aggiungere un file al repository si utilizza il comando git add.
Ma ad ogni singola modifica git non aggiorna automaticamente il repository ma è l'utente che tramite il comando git commit indica che una certa versione del progetto deve essere salvata.
Il comando git log serve a visualizzare la storia del repository.
Il comando git diff serve a vedere la differenza tra ciò che è nel repository e le modifiche di cui non si è ancora fatto il commit.
Dopo aver dato il comando add si dice che i file sono 'on stage' prima del commit.
Il comando git checkout serve a spostarsi nella storia del repository.
Il comando git clone serve a copiare un repository remoto.
Il comando git push serve a inviare le modifiche al repository remoto mentre il comando git pull serve a ricevere le modifiche più aggiornate dal repository remoto.
Il merge è il processo in cui uno degli utenti che crea un conflitto deve "a mano" scegliere quali parti dei due commit in conflitto vuole tenere.
Git è utile per trovare i bug che non erano presenti in versioni precedenti del progetto. Si può tornare alla versione precedente stabile e avanzare nella storia fino a trovare una versione instabile. A questo punto è probabile che l'origine del bug sia nelle modifiche che hanno creato questa versione instabile.
Github è una piattaforma di repository dove possono essere mantenuti dei progetti gratuitamente se sono con licenza libera.
In una directory in cui è presente un repository git e sempre la presente la cartella .git dove il sistema di versioning mantiene il database della storia.

Lezione del 25 ottobre 2016

Audio Lezione: 25/10/16

Argomenti trattati:

• Semafori fair

Un semaforo è "fair" quando tende a non sbloccare dallo stato di attesa sempre lo stesso processo ma cerca di distribuire la possibilità di esecuzione a più processi.

• Problemi classici della concorrenza risolti con semafori
  • Produttore/consumatore

Due processi: produttore e consumatore. Il produttore genera continuamente dei valori e il consumatore continuamente li legge. Il consumatore deve leggere i valori nello stesso ordine in cui il produttore li genera.

Un meccanismo di sincronizzazione e richiesto perchè sorgono immediatamente due problemi:

• Produttore troppo veloce: il consumatore non fa in tempo a consumare il valore e c'è la possibilità che i valori non ancora letti vengano sovrascritti.
• Consumatore troppo veloce: possibilità che il consumatore legga un valore che ha già letto perchè il produttore non ha fatto in tempo a produrne uno nuovo.

Per risolvere il problema utilizziamo due semafori: empty e full.

Il produttore aspetta che il segnale del semaforo empty (Proberen), scrive il valore e dà segnale sul semaforo full (Verhogen).

Il consumatore aspetta il segnale del semaforo full (Proberen), legge il valore e dà segnale sul semaforo empty (Verhogen).

• Buffer-limitato

Simile al problema produttore/consumatore ma qui lo scambio avviene tramite un buffer limitato.

In questo modo nel caso di rallentamento temporaneo del consumer il producer non deve aspettare ma può produrre più unità e viceversa nel caso di rallentamento del producer, se il buffer ha più di un elemento, il consumer può utilizzare il tempo in attesa del producer per consumare più dati.

Nel caso il buffer sia completamente pieno/vuoto rimangono comunque i problemi di sincronizzazione tipici del problema: il producer non deve sovrascrivere dei valori che il consumer non ha ancora letto e il consumer non deve leggere più volte lo stesso valore se il producer non è stato abbastanza veloce da cambiarlo.

Come soluzione al problema si può utilizzare un coda circolare. Il produttore esegue una enqueue e il consumatore una dequeue.

Il problema può essere generalizzato facilmente a produttori/consumatori multipli ma in questo caso dobbiamo creare un semaforo per rendere atomiche la enqueue e la dequeue altrimenti incorriamo in una race condition nel accesso alla coda.

Lezione del 28 ottobre 2016

Implementazione dei semafori
Un processo che esegue una Proberen in teoria dovrebbe aspettare continuando a controllare se può entrare nella sezione critica. Questo meccanismo si chiama "busy waiting" e consuma molte istruzioni della CPU.
Il busy waiting è diverso dal polling in quando il polling prevede di eseguire altre azioni mentre si aspetta tra un tentativo e l'altro.
Di solito si utilizza il busy waiting solo quando il tempo di lock di un processo è molto breve. Questo perchè anche se esoso di risorse del processore il busy waiting non comporta un context switch, cioè salvare tutto lo stato del processo in memoria, e quindi permette di risparmiare memoria. Se invece il tempo di lock è più lungo allora è preferibile utilizzare un context-switch dove il processo si blocca da solo e chiama un processo di blocking che lo mette in una coda di attesa associata al semaforo che sta aspettando. Il controllo passa poi allo scheduler della CPU che seleziona un altro processo da eseguire. Le primitive suspend and wakeup indicano rispettivamente lo spostamento di un processo nella/dalla coda dei processi ready.

• nei kernel monoprocessore

Implementazione dei semafori tramite mutex che possono essere a loro volta implementate con un sistema di mascheramento degli interrupt.

• nei kernel multiprocessore

Utilizzo di soluzioni hardware come test and set. Sono soluzioni che utilizzano il busy waiting ma in questo caso solo per rendere atomico le operazioni del semaforo, che sono poche istruzioni.

Certe implementazioni dei semafori potrebbero permettere di far andare il valore in negativo. Questo serve per misurare il numero dei processi in attesa di quel semaforo.
Il problema della cena dei filosofi:
5 filosofi passano la loro vita pensando e mangiando. Condividono un tavolo circolare con 5 sedie e ogni sedia appartiene a un solo filosofo. Alla sinistra e alla destra di ogni piatto c'è una bacchetta per un totale di 5 bacchette. La bacchetta destra che un filosofo usa per mangiare viene quindi utilizzata come bacchetta sinistra dal filosofo alla sua destra e simmetricamente è uguale per il filosofo che siede a sinistra.
Ogni tanto un filosofo smette di pensare e cerca di prendere le rispettive bacchette, se ci riesce può mangiare e poi rilasciare le bacchette.
Questo problema è un modello di problema ad accesso a insiemi di risorse. Mentre nel produttore/consumatore e buffer limitato gli attori in gioco avevano la necessità di avere l'accesso esclusivo a una sola risorsa in questo problema è richiesto l'accesso a insiemi di risorse (le bacchette) le cui parti possono essere desiderate da altri richiedenti.

• soluzione con contesa sulle posate e casi di deadlock

Poniamo un semaforo per ogni bacchetta. Può succedere però, se nel implementazione i filosofi "prendono in mano" prima la bacchetta destra e poi quella sinistra, che tutti prendono in mano contemporaneamente la bacchetta destra e rimangono in un'attesa infinita della bacchetta sinistra che non gli verrà mai rilasciata perché anche il rispettivo filosofo alla propria sinistra è in attesa.
Questo è un caso di deadlock.

Una soluzione può essere quella di imporre che un filosofo sia "mancino" cioè prenda prima la bacchetta a sinistra e poi la destra.

• soluzione con acquisizione atomica di entrambe le posate, casi di starvation

Un'altra soluzione è quella di rendere atomico l'acquisizione di entrambe le posate.

Può succede che 4 filosofi compiano una "congiura", cioè siano d'accordo a non lasciar risorse a un quinto filosofo. Questo è un caso di starvation e non è irreale in quando i 4 filosofi potrebbero essere processi malevoli che siano stati programmati di proposito per questo.

System Call:

• POSIX.

Il POSIX è uno standard (IEEE 1003) che definisce le signature delle system call. Un sistema operativo deve rispettare il POSIX per essere definito "Unix-like".

Di solito i parametri delle system call sono pensati per essere contenuti in un registro. Quasi sempre le system call ritornano un intero: 0 se la procedura è stata eseguita correttamente, -1 se c'è un errore. Quando una system call ritorna -1 la variabile "globale" errno (error number) contiene il codice di errore. La variabile errno non è realmente globale perché ne esiste una per ogni processo.

Unix è un sistema operativo file-system centrico quindi quando facciamo input/output anche da periferiche come stampanti e lettori CD usiamo le system call per la scrittura/lettura dei file.

Un catalogo delle system call principali può essere trovato qui.

• fork/exec

fork e exec sono system call importanti e servono per creare un nuovo processo:

fork: genera un processo clone di quello che ha chiamato fork.

exec: "cambia" il codice eseguito dal processo corrente.

Quindi per "aprire un nuovo programma" si utilizza una fork seguita da un exec.

Lezione del 4 novembre 2016

• Problema della Cena dei filosofi. Soluzione con acquisizione atomica delle bacchette (con starvation)
• Tecnica del passaggio del testimone (Passing the Baton).

Non uscire dalla mutua esclusione se c'è qualcun altro che vuole entrarci e semplicemente fare in modo che lui l'acquisisca. La mutua esclusione termina solo se non c'è nessuno che più la richiede.

ESEMPIO IMPLEMENAZIONE BATON

  void baton(int i) {
    int j;
    for (j=1; j<5; j++) {
       if(philo_status[(i+j)%5] == 'W' && philo_status[(i+j+1)%5] != 'E' && philo_status[(i+j+4)%5] != 'E') {
          semaphore_V(philowait[(i+j)%5]);
          return;
       }
    }
    semaphore_V(mutex);
  }

• Cena dei filosofi, acquisizione atomica delle bacchette con passaggio del testimone.
• Implementazione della congiura dei filosofi

• Le system call di gestione file (open, read, write, close, lseek)

Quando lavoriamo con dei file dobbiamo sempre specificare se vogliamo solo leggerli oppure anche scrivere, magari in append mode. Ci sono quindi varie modalità con cui possiamo interagire con i file.
Un utente potrebbe essere autorizzato a gestire il file in certe modalità oppure no.
Il descrittore di un file è un intero.
Le system call, a differenza delle chiamate di funzioni di libreria, non sono bufferizzate.

ESEMPIO

Se si decommenta printf stampa 2 volte hello world perchè la stringa resta nel buffer.

Se si decommenta write stampa 1 volta hello world.

Per vedere le chiamate di sistema effettuate in fase di esecuzione, compilare il codice sorgente e poi utilizzare strace -f "eseguibile".

   #include<stdio.h>
   #include<unistd.h>

  int main(int argc, char* argv[]){
    //printf("hello world"); //if you ends the strings with \n is like to "fflushing" the buffer 
    //write(1, "hello world", 11); // 1 and 11 are file descriptors
    switch(fork()) {
      case 0: //child
         break;
      default: //parent
         wait(NULL);
         break;
      case -1: //error
         break;
    }
    printf("\n");
    return 0;
  }

Copia il file passato come primo argomento (argv[1]) nel file passato come secondo argomento (argv[2]), se quest'ultimo non esiste, allora lo crea.

  #include<stdio.h>
  #define BUFSIZE 2048
  char buffer[BUFSIZE];
  int main(int argc, char *argv[]){
     int fdin = open(argv[1], O_RDONLY);
     int fdout = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, 0666); //0666 is the umask used to modify the permissions of new files

     int n;
     while((n = read(fdin, buffer, BUFSIZE)) > 0)
        write(fdout, buffer, n);
    
     close(fdin);
     close(fdout);
     return 0;
   }

umask
Con la open possiamo usare dei permessi al massimo per quelli garantiti dal umask.
Un numero composto da quattro cifre ottali. Controlla la maschera di creazione dei file. I bit di permesso contenuti nella maschera NON vengono settati nel nuovo file creato. Corrisponde all'opereazione:

 R:(D &(~M)) 

Può essere vista come una sottrazione, i bit accesi nella umask vengono spenti nel file creato.

e.g. se i permessi di default corrispondono a 0666(D) e la maschera corrisponde a 0022(M), R è uguale a 0666-0022 = 0644. Infatti

  0022 =        |000|000|010|010|
 ~0022 =        |111|111|101|101|(7755)
  0666 =        |000|110|110|110|
 ~0022 & 0666 = |000|110|100|100|(0644)

Tabella significato cifre umask

 OTTALE  BINARIO  SIGNIFICATO
  0       000      Nessun permesso
  1       001      Solo esecuzione
  2       010      Solo scrittura
  3       011      Scrittura ed esecuzione
  4       100      Solo lettura
  5       101      Lettura ed esecuzione
  6       110      Lettura e scrittura
  7       111      Lettura, scrittura ed esecuzione

I permessi sono rappresentati in simboli come segue:

 r: read
 w: write
 x: execute

umask - S da shell per visualizzare la umask attuale con rappresentazione simbolica

ls -l "nomefile" da shell per visualizzare i permessi del file in notazione simbolica: '-' seguito da 3 triple che indicano i permessi di accesso per ugo, ovvero, rispettivamente, per user, per group, per other.

ESEMPIO

 -rw-r--r--

• File aperti durante fork/exechttps://www.kernel.org/

I file aperti vengono ereditati dai processi figli. Processo padre e processo figlio condividono lo stesso offset nei file comuni. In questo modo si evita di sovrascriversi a vicenda. Ogni volta che il padre o il figlio scrivono sul file aggiornano l'offset comune.In questo modo se l'altro processo vuole anche lui scrivere in quel file partirà dal offset aggiornato e non sovrascriverà i dati scritti dal altro processo.

• La system call dup e la ridirezione

E' possibile fare in modo che più file descriptor siano associati a un unico file (per la precisione a un unica file table, che serve per gestire un file).
La system call dup permette di fare ciò. Ritorna un nuovo file descriptor che punta a una file table già esistente.
Possiamo quindi "ridirezionare" l'output o l'input di un processo figlio modificando i file descriptor prima di creare il processo figlio. Per esempio possiamo modificare un file descriptor che puntava a un normale file in modo che punti a un file di standard output e quindi anche se al processo figlio sembrerà di scrivere in un normale file starà scrivendo nel terminale.

ESEMPIO

  #include<sys/types.h>
  #include<sys/stat.h>
  #include<fcntl.h>
  #include<stdio.h>
  #include<unistd.h>

  int main(int argc, char * argv[]){
    int fdout;
    if(argc > 1);
    fdout = open (argv[1], O_WRONLY | O_CREAT | O_TRUNC, 0666);
    switch(fork()) {
        case 0: //child
          dup2(fdout, 1); // duplica descrittore file, posso ridirezionare l'output. E' come fare '>' dalla shell 
          execlp(”ls”, “-l”, 0); 
          close(fdout);
          break;
        default: // parent
          wait(NULL);
          break;
        case -1: // error
          break;
    }
    printf(“\n”);
    return 0;
   }

Lezione del 8 novembre 2016

Codice per la congiura dei filosofi

#include <stdio.h>
#include <stdint.h>
#include <pthread.h>
#include "semaphore.h"

semaphore philowait[5];
semaphore mutex;
semaphore cospsem;
char philo_status[]="TTTTT";

void baton(int i){
    int j = 0;
    //iterate through remaining philosophers
    for(j = 1; j < 5;j++){
        //if there's any waiting philosopher, and no other philosophers(on his left and right side) are eating
        if(philo_status[(i+j)%5]=='W' && philo_status[(i+j+1)%5]!= 'E' && philo_status[(i+j+4)%5]!='E'){
            semaphore_V(philowait[(i+j)%5]);
            return;
        }
    }
    semaphore_V(mutex);
}

void ok2eat(int i){
    semaphore_P(mutex);
    philo_status[i]='W';
    if(philo_status[(i+1)%5] == 'E' || philo_status[(i+4)%5] == 'E'){
        semaphore_V(mutex);
        semaphore_P(philowait[i]); //wait for baton
    }
    philo_status[i] = 'E';
    printf("philo eating:   %d |%s|\n",i,philo_status);
    baton(i);
}

void ok2think(int i){
    semaphore_P(mutex);
    philo_status[i] = 'T';
    printf("philo thinking: %d |%s|\n",i,philo_status);
    baton(i);
}

void conspiracy_in(){
    static int first_time = 1; //this variable's value is preserved between calls to this function
    semaphore_P(mutex);
    if(first_time){
        //first conspirator entering here will act like nothing happened
        first_time = 0;
    }
    else{
        //conspire
        semaphore_V(cospsem);
    }
    semaphore_V(mutex);
}

void conspiracy_out(){
    semaphore_P(cospsem);
}

void *philo(void *arg) {
    int i = (uintptr_t)arg;
    while (1) {
        //thinking/still thinking
        usleep(random() % 200000);
        ok2eat(i);
        //eating

        //conspirators need to be synchronized to conspire
        if(i==1 || i==3) conspiracy_in();
        usleep(random() % 200000);
        if(i==1 || i==3) conspiracy_out();
        ok2think(i);
        //thinking again
    }
}

int main(int argc, char *argv[]) {
    int i;
    pthread_t philo_t[5];
    srandom(time(NULL));
    mutex = semaphore_create(1);
    cospsem = semaphore_create(0);
    for (i=0; i<5; i++)
        philowait[i]=semaphore_create(0);
    for (i=0; i<5; i++)
        pthread_create(&philo_t[i], NULL, philo, (void *)(uintptr_t) i);
    for (i=0; i<5; i++)
        pthread_join(philo_t[i], NULL);
}

• Problema dei lettori e scrittori

Spesso quando gestiamo la concorrenza all’accesso a strutture dati separiamo i ruoli di solo lettori con anche quello di scrittori (che per fare ciò possono dover anche leggere).

Mentre che per i lettori non c’è un limite a quanti contemporaneamente possono avere accesso alle informazioni, gli scrittori devono avere accesso esclusivo alla struttura dati.

Questo perché incorriamo in una race-condition solo quando modifichiamo la struttura dati.

Dare precedenza di accesso a una categoria o all’altra porta starvation nella categoria con meno priorità.

Una soluzione che abbiamo dato è quella di dare esclusività ai ruoli a turno:

dopo che uno scrittore ha finito di scrivere garantisce l’accesso prima a tutti i lettori in attesa e se non sono presenti agli scrittori in attesa. Per i lettori è il contrario: dopo che l’ultimo lettore ha finito di leggere garantisce l’accesso a uno dei possibili scrittori in attesa e se non ce ne sono ai lettori.

La soluzione in C al problema lettori e scrittori può essere trovata qui.

• Semafori Binari(Introduzione)

Un semaforo binario è un semaforo ordinario che rispetta la seguente invariante: nP<=nV+Init<=nP+1, ovvero è un semaforo che può assumere solo valori 0 o 1.

Si può dimostrare che i semafori ordinari sono espressivi tanto quanto quelli binari(e viceversa) fornendo una implementazione di semafori binari tramite i semafori ordinari e viceversa una implementazione di semafori ordinari tramite semafori binari. (l'invariante dei semafori binari si può anche scrivere 0 <= nV + Init - nP <= 1 dove nV + Init - nP rappresenta proprio il valore del semaforo).